第六章 树和二叉树

《第六章 树和二叉树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六章　树和二叉树6.1树的定义和基本术语6.2二叉树6.3遍历二叉树和线索二叉树6.4树和森林6.5赫夫曼树及其应用1.树(Tree)：是n(n≥0)个结点的有限集。在任意一棵非空树中(1)有且只有一个称为根(Root)的结点。(2)其余的结点被分为m(m≥0)个互不相交的有限集，其中每个集合本身又是一棵树，称为根(Root)结点的子树(Sub_Tree)。6.1树的定义和基本术语6.1.1基本术语树的定义本身是递归的。递归定义和递归操作在树和二叉树中应用是比较广泛的，应注意领会递归的实质。2.树的表示法：有图示法、集合表示法、广义表表示法和缩进表示法，见图6.1。(A(B(

2、E,F(L),G),C(H,I(M,N)),D(J,K)))(b)广义表表示法ACEFGHJKLNMBID(a)图示法ADBCIMNHGEFLKJ(c)集合表示法ABEFLGCHIMNDKJ(d)缩进表示法图4.1树的几种表示法3.结点的分类：从计算机的角度来分，可以分为终端结点和非终端结点；以树的特征来分，可以分根结点、分支结点和叶子结点；用族谱的关系来分，可以分为双亲结点和孩子结点、祖先结点和子孙结点、兄弟结点和堂兄弟结点。4.度：分为结点的度和树的度两种。结点的度是指与该结点相连接的孩子结点的数目。树的度是指该棵树中所有结点的度中的最大值。5.深度：树是一种分层结构，根结

3、点作为第一层。结点的层次(或称深度)就是指从根结点开始的层次数。树的深度(或层数)是指该树中所有结点的层次中的最大值。用图示法表示的二叉树中，边的数目(或称分支数，用e表示)恰好比结点数目(用n表示)少一个，即e=n-1。这是树状结构中最重要的一个结论。6.有序树与无序树：如果将树中结点的各棵子树看成是从左到右有次序的(即不能互换),则称该树为有序树，否则称为无序树。7．有向树与无向树：如果树的每个分支都是从一个结点到另一个结点有方向的，则称该树为有向树，否则称为无向树。8.n元树：树的度为n的有向树。9.位置树：是一棵有向树。如果树中结点的每个孩子结点位置是不能被改变的(改变

4、则不是原树)，则称该树为位置树。如某结点可能没有第一个孩子结点，但却可能会有第二个、第三个孩子结点。10.m叉树：是树的度为m的有向位置树，即m元位置树。11.森林：是m(m≥0)棵互不相交的树的集合。对于树中的每个结点而言，其子树的集合就是森林。因此，森林和树是密切相关的。森林中的树也可以有顺序关系和位置关系。树状结构也是用于存储数据的，我们也要对其中的数据进行加工处理。总体上，树的基本操作有如下几种：InitTree(T)——构造一棵空树T。ClearTree(T)——将已经存在的树T清空。TreeEmpty(T)——判断树T是否为空树。TreeDepth(T)——计算树T

5、的深度。InsertChild(T,p,i,c)——插入子树c为树T中p指向结点的第i棵子树。DeleteChild(T,p,i)——删除树T中p所指结点的第i棵子树。TraverseTree(T)——按某种次序对树T中的所有结点进行访问，每个结点仅访问一次。6.1.2树的基本操作二叉树(BinaryTree)是一种特殊的有向树，也称二元位置树。它的特点是每个结点至多有两棵子树，即二叉树中的每个结点至多有两个孩子结点，且每个孩子结点都有各自的位置关系。或者说，二叉树的子树有左右之分，其次序不能任意颠倒。给二叉树下个更加确切的定义，就是：二叉树或者为空，或者是由一个根结点加上两棵

6、分别称为左子树和右子树的、互不相交的二叉树组成。6.2二叉树6.2.1二叉树的定义可以看出，二叉树的定义是递归的，前面提到的树的定义也是递归的。这说明树状结构在处理数据时很多操作是可以通过递归来完成的。图6.2二叉树的五种基本形态(a)空二叉树(b)仅有根结点(c)右子树为空(d)左子树为空(e)左右子树均非空根据二叉树的定义，可以总结出二叉树有如图6.2所示的五种形态：【例6.1】列举出只有两个结点、三个结点的二叉树的所有形态1.只有两个结点的二叉树的形态有两种，如图6.3所示图6.3只有两个结点的二叉树的所有形态2.只有三个结点的二叉树的形态有五种，如图6.4所示图6.4只

7、有三个结点的二叉树的所有形态6.2.2二叉树的性质与结论性质1：在二叉树的第i(i≥1)层上至多有2i-1个结点。(该性质证明利用归纳法很容易实现，留给读者自己去思考)性质2：深度为k(k≥1)的二叉树上至多有2k-1个结点。(该性质证明直接利用性质1即可，留给读者自己去思考)性质3：任意一棵二叉树中，叶子结点的数目(用n0表示)总比度为2的结点的数目(用n2表示)多一个，即n0=n2+1。证明：设结点总数为n，度为1的结点数目为n1，则有n=n0+n1+n2(6-1)由于二叉树中除根之外的