树结构的定义和基本操作.ppt

《树结构的定义和基本操作.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6章树6.1树结构的定义和基本操作6.2二叉树6.3遍历二叉树6.4树和森林6.5树的应用习题前面谈的基本上是线性表结构，线性表,栈、队列、串、一维数组，即使二维数组(矩阵结构、十字类别)也不过只是线性表的组合，即：除首元素和尾元素以外，每一个元素有唯一的前驱和后续元素。树形结构是一种重要的非线性结构，讨论的是层次和分支关系，即：除了有一个根元素没有前驱以外，每一个元素都有唯一的前驱元素；另外，每一个元素有零个或多个后继元素。例如，人类社会的族谱和各种社会组织机构都可以用树来形象表示。树在计算机领域中也得到广泛应用。6.1树结构的定义和基本

2、操作6.1.1树的定义递归定义：树(tree)是n(n>0)个结点的有限集。在任意一棵树中：(1)有且只有一个特定的称为根(root)的结点。(2)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1，T2，…，Tm，其中每一个集合本身又是一棵树，称为子树(subtree)。图6.1所示，在图中的树有13个结点，A是树根，其余结点构成三个互不相交的子集：T1={B，E，F，K，L}，T2={C，G}，T3={D，H，I，J，M}；T1，T2和T3都是根A的子树，且它们本身也是一棵树。如在T1中，B是该子树根，其余结点又构成两个互不相交

3、子集，T11={E，K，L}和T12={F}，T11和T12都是根B的子树，且它们本身也是一棵树。图6.1树的示例上面是树的一个递归定义，树除了该递归定义外，还有其它定义。如图6.2所示为图6.1中树的各种表示.从图6.1的示例可以看出，树有两个特点：(1)树的根结点没有前驱结点，其余结点有且只有一个前驱结点。(2)树结点可以有零个或多个后继结点。树结构描述的是层次和分支关系。图6.2树的其它三种表示方法图6.2(a)是以嵌套集合的形式表示(任何两个集合，或不相交，或一个包含另一个)；图6.2(b)是以广义表的形式表示，根作为子树森林组成的表

4、的名字写在表的左边；图6.2(c)用的是凹入表示法。6.1.2树的常用术语结点：是包含一个数据元素和若干指向其子树的分支(即关系).结点的度：结点拥有的子树数。叶子：度为0的结点。分支结点：度不为0的结点。树的度：树内各结点的度的最大值，图6.1所示树是一个3叉树.孩子结点(child)：结点的后继，结点子树的根结点。双亲结点(parent)：孩子结点的前驱。s是f的孩子,则f是s的双亲.兄弟结点(sibling)：同一个双亲的孩子之间互称为兄弟。祖先结点：从根到该结点的所经过分支上的所有结点,图6.1树中L结点的祖先结点是A，B，F。子孙结

5、点：以某结点为根的子树中任一结点都称为该结点的子孙.图6.1树中D的子孙结点为H，I，J，M.结点的层次：根是第1层，依次为第2层…。树的深度：树中结点的最大层次，图6.1所示的树深度为4.有序树：树中结点的各子树看成从左至右是有次序的,例如,人类社会的族谱就是一个有序树。无序树：树中结点的各子树没有次序的，孩子结点的顺序可以调整。森林：m(m≥0)棵互不相交的树的集合。森林和树之间的联系是：一棵树取掉根，其子树构成一个森林；同样，一个森林增加一个根结点成为树.6.1.3树的基本操作(1)initiate(T)：T树的初始化，包括建树。(2)

6、root(T)：求T树的根。(3)parent(T,x)：求T树中x结点的双亲结点。(4)child(T,x,i)：求T树中x结点的第i个孩子结点。(5)right_sibling(T,x)：求T树中x结点的右兄弟。(6)Insert_child(y,i,x)：将根为x的子树置为y结点的第i个孩子(7)del_child(x,i)：删除x结点的第i个孩子(整个子树)。(8)traverse(T)：遍历T树。按某个次序依次访问树中每一个结点，并使每个结点都被访问且只被访问一次。(9)clear(T)置空T树。以上操作的具体实现，依赖于采用的

7、存储结构。6.2二叉树6.2.1定义及其操作二叉树是另一种树形结构，它的特点是每一个结点至多只有两棵子树，并且，子树有左、右之分，其次序不能颠倒。递归定义：二叉树是n(n≥0)个结点有限集，当n>1时，有而且仅有一个结点为根结点，其余结点构成为2个互不相交的子集T1，T2，其中每一个子集又是一棵二叉树，分别称作为根结点的左子树和右子树。注意：二叉树不是度为2的树，在度为2的树中，当一个结点的度为1时，其子树是不考虑序的；而在二叉树中，当一个结点的度为1时，其子树要考虑序，即：是作为双亲的左子树还是作为双亲右子树。另外，树不允许为空树，但二叉树

8、允许为空。由二叉树的递归定义可知，二叉树有五种基本形态，如图6.3所示。(a)空树(b)仅有根(c)右子树空(c)左、右子树均在d)左子树空图6.3二叉树的五种形态