Algorithms and Datastrucstures:Trees 树的数学定义 有向树：有向图在不考虑边的方向时是一棵树，该有向图称为有向树。 根树：一颗有向树，如果恰有一个结点的入度为0，其余所有结点的入 度都为1，则称为根树。 R S T W X Z b ALDS
6 物料管理 ALDS 6 Algorithms and DataStrucstures:Trees 树的数学定义 有向树：有向图在不考虑边的方向时是一棵树，该有向图称为有向树。 根树：一颗有向树，如果恰有一个结点的入度为0，其余所有结点的入 度都为1，则称为根树。 R S T U V Y W X Z
Algorithms and Datastrucstures:Trees 树的ADT 数据及关系： 具有相同数据类型的数据元素或结点的有限集合。树T的二元组形式为： T=(D,R) 其中D为树T中结点的集合，R为树中结点之间关系的集合。 D={Root}UDp 其中，Root为树T的根结点，D为树T的根Root的子树集合。 R={<Root,r;>,i=1,2,...m} 其中，r是树T的根结点Root的子树T,的根结点。 7 ALDS
7 物料管理 ALDS 7 Algorithms and DataStrucstures:Trees 树的ADT 数据及关系: 具有相同数据类型的数据元素或结点的有限集合。树T的二元组形式为： T＝（D，R） 其中D为树T中结点的集合，R为树中结点之间关系的集合。 D＝{Root}∪DF 其中，Root为树T的根结点，DF为树T的根Root的子树集合。 R＝{<Root，ri>，i＝1，2，…，m} 其中，ri是树T的根结点Root的子树Ti的根结点
Algorithms and Datastrucstures:Trees 树的ADT 操作： Constructor: 前提：已知根结点的数据元素之值。 结果：创建一棵树。 Getroot: 前提：已知一棵树。， 结果：得到树的根结点。 FirstChild: 前提：已知树中的某一指定结点p。 结果：得到结点p的第一个儿子结点。 NextChild: 前提：已知树中的某一指定结点p和它的一个儿子结点u。 结果：得到结点p的儿子结点u的下一个兄弟结点V。 8 ALDS
8 物料管理 ALDS 8 Algorithms and DataStrucstures:Trees 树的ADT 操作: Constructor： 前提：已知根结点的数据元素之值。 结果：创建一棵树。 Getroot: 前提：已知一棵树。. 结果：得到树的根结点。 FirstChild： 前提：已知树中的某一指定结点 p。 结果：得到结点 p 的第一个儿子结点。 NextChild： 前提：已知树中的某一指定结点 p 和它的一个儿子结点 u。 结果：得到结点 p 的儿子结点 u 的下一个兄弟结点 v
Algorithms and Datastrucstures:Trees 树的ADT 操作： Retrieve: 前提：已知某一关键字key。 结果：检索具有关键字key的结点v。 InsertChild: 前提：已知某结点p及新结点的数据值value.。 结果：根据value值创建一个新结点q, 并将其插入作为结点p的儿子结点。 DeleteChild: 前提： 己知某结点p及它的儿子结点的序号k。 结果：删除结点p的第k个儿子结点。 IsEmpty: 结果：若树仍未创建，返回True,否则返回False。 9 ALDS
9 物料管理 ALDS 9 Algorithms and DataStrucstures:Trees 树的ADT 操作: Retrieve: 前提：已知某一关键字 key。 结果：检索具有关键字 key 的结点 v。 InsertChild: 前提：已知某结点 p 及新结点的数据值 value。 结果：根据 value 值创建一个新结点 q, 并将其插入作为结点 p 的儿子结点。 DeleteChild: 前提：已知某结点 p 及它的儿子结点的序号 k。 结果：删除结点 p 的第 k 个儿子结点。 IsEmpty: 结果：若树仍未创建，返回 True，否则返回 False
Algorithms and Datastrucstures:Trees 5.2二叉树 二叉树在树结构的应用中起着非常重要的作用，因为对二叉树的 许多操作算法简单，而任何树都可以与二叉树相互转换，这样就解决 了树的存储结构及其运算中存在的复杂性。 5.2.1二叉树的定义 定义：二叉树(Binary Tree)是结点的有限集合，它或者为空，或者 由一个根结点及两棵互不相交的左、右子树构成，而其左、右子树又都 是二叉树。 这也是一个递归定义。二叉树可以为空，根的左、右子树都可以为 空。必须注意的是，二叉树不是树的特殊情况，它们是两种不同的数据 结构。若将二叉树的左、右子树颠倒，就成为另一棵不同的二叉树。 即使二叉树中的根结点只有一棵子树，也要说明该子树是左子树，还是 右子树。这是二叉树与树的最主要的差别。 10 ALDS
10 物料管理 ALDS 10 Algorithms and DataStrucstures:Trees 5.2 二叉树 二叉树在树结构的应用中起着非常重要的作用，因为对二叉树的 许多操作算法简单，而任何树都可以与二叉树 相互转换，这样就解决 了树的存储结构及其运算中存在的复杂性。 5.2.1 二叉树的定义 定义：二叉树（Binary Tree）是结点的有限集合，它或者为空，或者 由一个根结点及两棵互不相交的左、右子树构成，而其左、右子树又都 是二叉树。 这也是一个递归定义。二叉树可以为空，根的左、右子树都可以为 空。必须注意的是，二叉树不是树的特殊情况，它们是两种不同的数据 结构。 若将二叉树的左、右子树颠倒，就成为另一棵不同的二叉树。 即使二叉树中的根结点只有一棵子树，也要说明该子树是左子树，还是 右子树。这是二叉树与树的最主要的差别