《《数据结构（C++描述）》-李根强-电子教案 第6章》由会员分享，可在线阅读，更多相关《《数据结构（C++描述）》-李根强-电子教案 第6章（100页珍藏版）》请在金锄头文库上搜索。
1、第6章 树,数据结构（C+描述）,6.6 哈夫曼树,.树和森林,6.4线索二叉树,6.3遍历二叉树,6.2 二叉树,6.1 树的基本概念,退出,目录,6.1 树的基本概念,6.1.1 树的定义,1树的定义,树是由n（n0）个结点组成的有限集合。若n=0，称为空树；若n0，则： （1）有一个特定的称为根（root）的结点。它只有直接后继，但没有直接前驱； （2）除根结点以外的其它结点可以划分为m（m0）个互不相交的有限集合T0，T1，Tm-1，每个集合Ti（i=0,1,m-1）又是一棵树，称为根的子树，每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。 由此可知，树的定义是一个递
2、归的定义，即树的定义中又用到了树的概念。 树的结构参见图6-1。,在图6-1(c)中，树的根结点为A，该树还可以分为三个互不相交子集T0，T1，T2，具体请参见图6-2，其中T0=B，E，F，J，K，L，T1=C，G，T2=D，H，I，M，其中的T0，T1，T2都是树，称为图6-1（C）中树的子树，而T0，T1，T2又可以分解成若干棵不相交子树。如T0可以分解成T00，T01两个不相交子集，T00=E，J，K，L，T01=F，而T00又可以分为三个不相交子集T000，T001，T002，其中，T000=J，T001=K，T002=L。,2树的逻辑结构描述,一棵树的逻辑结构可以用二元组描述为：
3、tree =(k,R) k=ki1in;n0,kielemtype R=r 其中，n为树中结点个数，若 n=0，则为一棵空树， n 0时称为一棵非空树，而关系 r 应满足下列条件： （1）有且仅有一个结点没有前驱,称该结点为树根; （2）除根结点以外,其余每个结点有且仅有一个直接前驱; （3）树中每个结点可以有多个直接后继(孩子结点)。,例如，对图6-1(c )的树结构,可以二元组表示为： K=A，B，C，D，E，F，G，H，I，J，K，L，M R=r r=(A,B)，(A,C)，(A,D)，(B,E)，(B,F)，(C,G)，(D,H)，(D,I)，(E,J)，(E,K)，(E,L)，(H,
4、M),3树的基本运算,树的基本运算可以定义如下几种：,(1) inittree(&T) 初始化树T。 (2) root(T) 求树T的根结点。,(3) parent(T,x) 求树T中，值为x的结点的双亲。 (4) child(T,x,i) 求树T中，值为x的结点的第i个孩子。 (5) addchild(y,i,x) 把值为x的结点作为值为y的结点的第i个孩子插入到树中。 (6) delchild(x,i) 删除值为x的结点的第i个孩子。 (7) traverse(T) 遍历或访问树T。,6.1.2 基本术语,1.结点 指树中的一个数据元素，一般用一个字母表示。,2.度 一个结点包含子树的数目
5、，称为该结点的度。,3.树叶（叶子） 度为0的结点，称为叶子结点或树叶，也叫终端结点。,4.孩子结点 若结点X有子树，则子树的根结点为X的孩子结点，也称为孩子，儿子，子女等。如图6-1（c）中A的孩子为B，C，D。,5.双亲结点 若结点X有子女Y，则X为Y的双亲结点。,6.祖先结点 从根结点到该结点所经过分枝上的所有结点为该结点的祖先，如图6-1（c）中M的祖先有A，D ，H 。,7.子孙结点 某一结点的子女及子女的子女都为该结点子孙。,8.兄弟结点 具有同一个双亲的结点，称为兄弟结点。,9.分枝结点 除叶子结点外的所有结点，为分枝结点，也叫非终端结点。,10层数 根结点的层数为1，其它结点的
6、层数为从根结点到该结点所经过的分支数目再加1。,11. 树的高度（深度） 树中结点所处的最大层数称为树的高度，如空树的高度为0，只有一个根结点的树高度为1。,12.树的度 树中结点度的最大值称为树的度。,13. 有序树 若一棵树中所有子树从左到右的排序是有顺序的，不能颠倒次序。称该树为有序树。,14. 无序树 若一棵树中所有子树的次序无关紧要，则称为无序树。,15森林（树林） 若干棵互不相交的树组成的集合为森林。一棵树可以看成是一个特殊的森林。,6.1.3 树的表示,1树形结构表示法 具体参 见图6-1 。,2. 凹入法表示法 具体参见图6-3 。,3. 嵌套集合表示法 具体参 见图6-4 。
7、,4.广义表表示法 对图6-1（c）的树结构，广义表表示法可表示为： （A（B（E（J，K，L），F），C（G），D（H（M），I）,6.1.4 树的性质,性质1 树中的结点数等于所有结点的度加1。,证明：根据树的定义，在一棵树中，除根结点以外，每个结点有且仅有一个直接前驱，也就是说，每个结点与指向它的一个分支一一对应，所以，除根结点以外的结点数等于所有结点的分支数（即度数），而根结点无直接前驱，因此，树中的结点数等于所有结点的度数加1。,性质 2 度为k的树中第i层上最多有ki-1个结点（i1）。,下面用数学归纳法证明： 对于i=1，显然成立，假设对于i-1层，上述条件成立，即第i-1层最多
8、有ki-2个结点， 对于第i层，结点数最多为第i-1层结点数的k倍（因为度为k），故第i层的结点数为ki-2*k= ki-1。,性质3 深度为h的 k叉树最多有 个结点。,证明：由性质2可知，若每一层的结点数最多，则整个k叉树结点数最多，共有 =k0+k1+kh-1= 。 当一棵K叉树上的结点数达到 时，称为满K叉树。,性质4 具有n个结点的k叉树的最小深度为logk(n(k-1)+1)。,（请注意，x 表示取不小于x的最小整数，或叫做对x上取整。） 证明：设具有n个结点的k叉树的深度为h，即在该树的前面h-1层都是满的，即每一层的结点数等于ki-1个(1ih-1)，第h层（即最后一层）的结点
9、数可能满，也可能不满，这时，该树具有最小的深度。由性质3知道，结点数n应满足下面条件： n ，通过转换为：kh-1n(k-1)+1kh，再取以k为底的对数后，可以得到： h-1logk(n(k-1)+1)h，即有：logk(n(k-1)+1)hlogk(n(k-1)+1)+1，而h只能取整数，所以，该k叉树的最小深度为h=logk(n(k-1)+1) 。,6.2 二叉树,6.2.1 二叉树的定义,1二叉树的定义,和树结构定义类似，二叉树的定义也可以递归形式给出： 二叉树是n（n0）个结点的有限集，它或者是空集（n=0），或者由一个根结点及两棵不相交的左子树和右子树组成。 二叉树的特点是每个结点
10、最多有两个孩子，或者说，在二叉树中，不存在度大于2的结点，并且二叉树是有序树（树为无序树），其子树的顺序不能颠倒，因此，二叉树有五种不同的形态，参见图6-5 。,2二叉树的基本运算,（1）inittree(&T) 二叉树的初始化。,（2）root(T) 求二叉树的根结点。,（3）parent(T,x) 求二叉树T中值为x的结点的双亲。,（4）lchild(T,x) 求二叉树T中值为x的结点的左孩子。,(5) rchild(T,x) 求二叉树T中值为x的结点的右孩子。,(6) lbrother(T,x) 求二叉树T中值为x的结点的左兄弟。,(7) rbrother(T,x) 求二叉树T中值为x的
11、结点的右兄弟。,(8) traverse(T) 遍历二叉树T。,(9) createtree(&T) 建立一棵二叉树T。,(10) addlchild(&T,x,y) 在二叉树T中，将值为y的结点作为值为x的结点的左孩子插入。,(11) addrchild(&T,x,y) 在二叉树T中，将值为y的结点作为值为x的结点的右孩子插入。,(12) dellchild(&T,x) 在二叉树T中，删除值为x 的结点的左孩子。,(13) delrchild(&t,x) 在二叉树T中，删除值为x 的结点的右孩子。,6.2.2 二叉树的性质,性质1 若二叉树的层数从1开始，则二叉树的第k层结点数，最多为2k-
12、1个（k0）。 可以用数学归纳法证明之。,性质2 深度（高度）为k的二叉树最大结点数为2k-1（k0）。,证明： 深度为k的二叉树，若要求结点数最多，则必须每一层的结点数都为最多，由性质1可知，最大结点数应为每一层最大结点数之和。既为 20+21+2k-1=2k-1。,性质3 对任意一棵二叉树，如果叶子结点个数为n0，度为2的结点个数为n2，则有n0=n2+1。,证明：设二叉树中度为1的结点个数为n1，根据二叉树的定义可知，该二叉树的结点数n=n0+n1+n2。又因为在二叉树中，度为0的结点没有孩子，度为1的结点有1 个孩子，度为2的结点有2个结孩子，故该二叉树的孩子结点数为 n0*0+n1*
13、1+n2*2 ，而一棵二叉树中，除根结点外所有都为孩子 结点，故该二叉树的结点数应为孩子结点数加1即：n=n0*0+n1*1+n2*2+1因此,有 n=n0+n1+n2=n0*0+n2*1+n2*2+1，最后得到n0=n2+1。,为继续给出二叉树的其它性质，先定义两种特殊的二叉树。,满二叉树 深度为k具有2k-1个结点的二叉树，称为满二叉树。 从上面满二叉树定义可知，必须是二叉树的每一层上的结点数都达到最大，否则就不是满二叉树。,完全二叉树 如果一棵具有n个结点的深度为k的二叉树，它的每一个结点都与深度为k的满二叉树中编号为1 n的结点一一对应，则称这棵二叉树为完全二叉树。 从完全二叉树定义可
14、知，结点的排列顺序遵循从上到下、从左到右的规律。所谓从上到下，表示本层结点数达到最大后，才能放入下一层。从左到右，表示同一层结点必须按从左到右排列，若左边空一个位置时不能将结点放入右边。,从满二叉树及完全二叉树定义还可以知道，满二叉树一定是一棵完全二叉树，反之完全二叉树不一定是一棵满二叉树。满二叉树的叶子结点全部在最底层，而完全二叉树的叶子结点可以分布在最下面两层。深度为4的满二叉树和完全二叉树如图6-6所示。,性质4 具有n个结点的完全二叉树高度为log2(n)+1 或 log2（n+1） 。 (注意x表示取不大于x的最大整数，也叫做对x下取整，x表示取不小于x的最小整数，也叫做对x上取整。
15、),证明：设该完全二叉树高度为k，则该二叉树的前面k-1层为满二叉树，共有2k-1-1个结点，而该二叉具有k层，第k层至少至少有1个结点，最多有2k-1个结点。因此有下面的不等式成立：（2k-1 1） +1 n （2k-1-1）+2k-1，即有 2k-1n2k-1。由式子后半部分可知, n2k-1 由式子前半部分可知 2k-1n 由有 n+12k ，同时取对数得： log2(n+1)k 故 klog2(n+1),即 k=log2(n+1)。即得到第二个结论。 由有2k-1n,同时取对数得：klog2n+1即 k=log2 n+1,即第一个结论成立,证毕。,性质5如果将一棵有n个结点的完全二叉树从上到下，从左到右对结点编号1，2，n，然后按此编号将该二叉树中各结点顺序地存放于一个一维数组中，并简称编号为j的结点为 j(1jn)，则有如下结论成立：,（1）若 j=1，则结点j为根结点，无双亲，否则j的双亲为 j/2； （2）若2jn，则结点j的左子女为2j ,否则无左子女。即满足2jn的结点为叶子结点； （3）若2j+1n，则结点j的右子女为2j+1，否则无右子女； （4）若结点j序号为奇数且不等于1，则它的左兄弟为j-1； （5）若结点j序号为偶数且不等于n，它的右兄弟为j+1； （6） 结点j所在层数(层次)为log2j+1；,
