树_学科竞赛_高中教育_教育专区-树

《树_学科竞赛_高中教育_教育专区-树》由会员分享，可在线阅读，更多相关《树_学科竞赛_高中教育_教育专区-树（36页珍藏版）》请在金锄头文库上搜索。

1、树,树的基本概念和表示二叉树遍历二叉树 哈夫曼树,4.1树的基本概念及表示,1树的定义,树是由D（D0）个结点组成的有限集合。若D=0，称为空树；若D0，则： （1）有一个特定的称为根（root）的结点。它只有直接后继，但没有直接前驱； （2）除根结点以外的其它结点可以划分为m（m0）个互不相交的有限集合T0，T1，Tm-1，每个集合Ti（i=0,1,m-1）又是一棵树，称为根的子树，每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。 由此可知，树的定义是一个递归的定义，即树的定义中又用到了树的概念。 树的结构参见图4-1。,在图4-1(c)中，树的根结点为A，该树还可以分为三

2、个互不相交子集T0， T1，T2，具体请参见图4-2，其中T0=B，E，F，J，K，L，T1=C， G，T2=D，H，I，M，其中的T0，T1，T2都是树，称为图4-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.相关定义,1）结点 指树中的一个数据元素，一般用一个字母表示。具有同一个双亲的结点，称为兄弟结点。 节点的前驱称为父节点，节点的后继称为子节点。不再有后继的节点

3、称为树叶,2）度 节点的度：一个结点包含子树的数目，称为该结点的度。,树的度：树中结点度的最大值称为树的度。,4）层数 根结点的层数为1，其它结点的层数为从根结点到该结点所经过的分支数目再加1。,3）树的高度（深度） 树中结点所处的最大层数称为树的高度，如空树的高度为0，只有一个根结点的树高度为1。,5）有序树 若一棵树中所有子树从左到右的排序是有顺序的，不能颠倒次序。称该树为有序树。,6）无序树若一棵树中所有子树的次序无关紧要，则称为无序树。,7）森林（树林）若干棵互不相交的树组成的集合为森林。一棵树可以看成是一个特殊的森林。,3.树的表示,树的二种表示方法 1）树形图（如图41所示） 2）

4、广义表 按照“根左右”的规律将树中的节点分别放入括号之中。具体做法 是：在一对括号中先写根节点，在根节点后面的一对括号内按从左到右 的顺序写各个子树，同层子树用逗号隔开。对图4-1（c）的树结构，广 义表表示法可表示为： （A（B（E（J，K，L），F），C（G），D（H（M），I）,练一练,如下图所示：用广义表表示，并指出它的度和深度,(A(B(E,F(K,L),C(G),D(H,I,J(M),深度：4,度：3,4.2二叉树,和树结构定义类似，二叉树的定义也可以递归形式给出： 二叉树是D（D0）个结点的有限集，它或者是空集（D=0），或者由一个根结点及两棵不相交的左子树和右子树组成。 二叉树

5、的特点是每个结点最多有两个孩子，或者说，在二叉树中，不存在度大于2的结点，并且二叉树是有序树（树为无序树），其子树的顺序不能颠倒，因此，二叉树有五种不同的形态，参见图4-5 。,1）二叉树的定义,4.2.2 二叉树的性质,性质1 若二叉树的层数从1开始，则二叉树的第k层结点数，最多为2k-1个（k0）。 可以用数学归纳法证明之。,性质2 深度（高度）为k的二叉树最大结点数为2k-1（k0）。,证明： 深度为k的二叉树，若要求结点数最多，则必须每一层的结点数都为最多，由性质1可知，最大结点数应为每一层最大结点数之和。既为 20+21+2k-1=2k-1。,性质3 对任意一棵二叉树，如果叶子结点个

6、数为D0，度为2的结点个数为D2，则有D0=D2+1。,证明：设二叉树中度为1的结点个数为D1，根据二叉树的定义可知，该二叉树的结点数D=D0+D1+D2。又因为在二叉树中，度为0的结点没有孩子，度为1的结点有1 个孩子，度为2的结点有2个结孩子，故该二叉树的孩子结点数为 D0*0+D1*1+D2*2 ，而一棵二叉树中，除根结点外所有都为孩子 结点，故该二叉树的结点数应为孩子结点数加1即：D=D0*0+D1*1+D2*2+1因此,有 D=D0+D1+D2=D0*0+D1*1+D2*2+1，最后得到D0=D2+1。,满二叉树 深度为k具有2k-1个结点的二叉树，称为满二叉树。 从上面满二叉树定义

7、可知，必须是二叉树的每一层上的结点数都达到最大，否则就不是满二叉树。,完全二叉树 如果一棵具有D个结点的深度为k的二叉树，它的每一个结点都与深度为k的满二叉树中编号为1 D的结点一一对应，则称这棵二叉树为完全二叉树。 从完全二叉树定义可知，结点的排列顺序遵循从上到下、从左到右的规律。所谓从上到下，表示本层结点数达到最大后，才能放入下一层。从左到右，表示同一层结点必须按从左到右排列，若左边空一个位置时不能将结点放入右边。,从满二叉树及完全二叉树定义还可以知道，满二叉树一定是一棵完全二叉树，反之完全二叉树不一定是一棵满二叉树。满二叉树的叶子结点全部在最底层，而完全二叉树的叶子结点可以分布在最下面两

8、层。深度为4的满二叉树和完全二叉树如图4-6所示。,性质4 具有D个结点的完全二叉树高度为log2(D)+1 或 log2（D+1） 。 (注意x表示取不大于x的最大整数，也叫做对x下取整),证明：设该完全二叉树高度为k，则该二叉树的前面k-1层为满二叉树，共有2k-1-1个结点，而该二叉具有k层，第k层至少至少有1个结点，最多有2k-1个结点。因此有下面的不等式成立：（2k-1 1） +1 D （2k-1-1）+2k-1，即有 2k-1D2k-1。由式子后半部分可知, D2k-1 由式子前半部分可知 2k-1D 由有 D+12k ，同时取对数得： log2(D+1)k 故 klog2(D+1

9、),即 k=log2(D+1)。即得到第二个结论。 由有2k-1D,同时取对数得：klog2D+1即 k=log2 D+1,即第一个结论成立,证毕。,4.3二叉树树的遍历,所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做 一次且仅做一次访问。 从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这 三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三 个操作： 访问结点本身（D）， 遍历该结点的左子树（L）， 遍历该结点的右子树（R）,以上三种操作有六种执行次序： DLR、LDR、LRD、DRL、RDL、RLD。,前三种次序与后三种次序对称，故只讨论

10、先左后右的前三种次序。,4.3.1前根遍历（DLR） 所谓前根遍历，就是根结点最先遍历，其次左子树，最后右子树。,1递归遍历,前根遍历二叉树的递归遍历算法描述为： 若二叉树为空，则算法结束;否则 （1）输出根结点； （2）前根遍历左子树; （3）前根遍历右子树;,(1)先访问根节点 a (2)前序遍历a的左子树（b,d,e,f） 先访问根节点 b; 前序遍历左子树d; 前序遍历右子树（e,f）;为ef 前序遍历左子树的结果为bdef (3)前序遍历a的右子树c 所以左图二叉树遍历的结果为 abdefc,4.3.2中根遍历(LDR) 所谓中根遍历，就是左子树最先遍历，其次是根，最后右子树。,1递

11、归遍历,中根遍历二叉树的递归遍历算法描述为： 若二叉树为空，则算法结束;否则 （1）中根遍历左子树； （2）遍历根; （3）中根遍历右子树;,(1)中序遍历a的左子树（dbfe） (2) 再访问根节点 a (3)中序遍历a的右子树c 所以左图二叉树遍历的结果为 dbfeac,4.3.3后根遍历(LRD) 所谓后根遍历，就是左子树最先遍历，其次是右子树根，最后根。,1递归遍历,后根遍历二叉树的递归遍历算法描述为： 若二叉树为空，则算法结束;否则 （1）后根遍历左子树； （2）后根遍历右子树; （3）遍历根;,请你后根遍历左图,dfebca,另外，在编译原理中，有用二叉 树来表示一个算术表达式的情

12、形。在一棵二叉树中，若用操作数代表树叶，运算符代表非叶子结点，则这样的树可以代表一个算术表达式。若按前序、中序、后序对该二叉树进行遍历，则得到的遍历序列分别称为前缀表达式(或称波兰式)、中缀表达式、后缀表达式(递波兰式)。具体参见图4-12。,图4-12所对应的前缀表达式： -*abc。 图4-12所对应的中缀表达式：a*b-c。图4-12所对应的后缀表达式：ab*c-。,4.3.4遍历算法应用举例,例4-5 由二叉树的前序序列和中序序列建立该二叉树,分析：若二叉树的任意两个结点的值都不相同，则二叉树的前序序列和中序序列能唯一确定一棵二叉树。另外，由前序序列和中序序列的定义可知，前序序列中第一

13、个结点必为根结点，而在中序序列中，根结点刚好是左、右子树的分界点，因此，可按如下方法建立二叉树：,1.在前序中找出根,2.在中序序列中查找根结点的位置，并以此为界将中序序列划分为左、右两个序列(左、右子树);,3.对左、右子树的前序序列和中序序列递归地实施同样方法，直到所得左、右子树为空。,假设前序序列为ABDGHCEFI，中序序列为GDHBAECIF则得到的二叉树如下页所示,A BDGH CEFI,GDHB A ECIF,2. B为左子树的根结点,1。A为根结点,B DGH,GDH B,3. D为左子树的左子树的根结点,4。C为右子树的根结点,5。F为右子树的右子树的根结点,C E FI,E

14、 C IF,4.4 哈夫曼树,1.基本术语,1）路径和路径长度 在一棵树中，从一个结点往下可以达到的孩子或子孙结点之间的通路，称为路径。通路中分支的数目称为路径长度。 若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。,2）结点的权及带权路径长度 若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。 结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。,3）树的带权路径长度 树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为wpl= ，其中D 为叶子结点数目，wi为第i 个叶子结点的权值，li 为第i 个叶子结点的路径长度。,1哈夫曼树

15、的定义在一棵二叉树中，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(HuffmaD tree)。,4.4.2 哈夫曼树构造,(1) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和； (2)从森林中删除选取的两棵树，并将新树加入森林； (3)重复(1)、(2)步，直到森林中只剩一棵树为止，该树即为我们所求得的哈夫曼树。,下面给出哈夫曼树的构造过程，假设给定的叶子结点的权分别为1,5,7,3，则构造哈夫曼树过程如图4-29所示。 从图4-29可知，D 个权值构造哈夫曼树需D-1次合并，每次合并，森林中的树数目

16、减1，最后森林中只剩下一棵树，即为我们求得的哈夫曼树。,练习,2.表达式(1+34)*5-56/7 的后缀表达式为（ ）。 A） 1+34*5-56/7 B） -*+1 34 5/56 7 C） 1 34 +5*56 7/- D） 1 34 5* +56 7/-,1.一个高度为H的二叉树最小元素数目是（） （A）2h+1 (B)h (C)2h-1 （D）2h (E)2h,3.一棵二叉树的中序遍历序列为DGBAECHF，后序遍历序列为：GDBEHFCA，则前序遍历的序列是( )。 (A)ABCDFGHE (B) ABDGCEFH(C) ACBGDHEFD (D) CEFHBGD,4.求叶节点权值分别为2，2，3，3，5的最优二叉树， 并求出所有叶节点带权路径长度之和。,