资源预览内容
第1页 / 共36页
第2页 / 共36页
第3页 / 共36页
第4页 / 共36页
第5页 / 共36页
第6页 / 共36页
第7页 / 共36页
第8页 / 共36页
第9页 / 共36页
第10页 / 共36页
亲,该文档总共36页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
树,树的基本概念和表示二叉树遍历二叉树 哈夫曼树,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,该树还可以分为三个互不相交子集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)结点 指树中的一个数据元素,一般用一个字母表示。具有同一个双亲的结点,称为兄弟结点。 节点的前驱称为父节点,节点的后继称为子节点。不再有后继的节点称为树叶,2)度 节点的度:一个结点包含子树的数目,称为该结点的度。,树的度:树中结点度的最大值称为树的度。,4)层数 根结点的层数为1,其它结点的层数为从根结点到该结点所经过的分支数目再加1。,3)树的高度(深度) 树中结点所处的最大层数称为树的高度,如空树的高度为0,只有一个根结点的树高度为1。,5)有序树 若一棵树中所有子树从左到右的排序是有顺序的,不能颠倒次序。称该树为有序树。,6)无序树若一棵树中所有子树的次序无关紧要,则称为无序树。,7)森林(树林)若干棵互不相交的树组成的集合为森林。一棵树可以看成是一个特殊的森林。,3.树的表示,树的二种表示方法 1)树形图(如图41所示) 2)广义表 按照“根左右”的规律将树中的节点分别放入括号之中。具体做法 是:在一对括号中先写根节点,在根节点后面的一对括号内按从左到右 的顺序写各个子树,同层子树用逗号隔开。对图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),或者由一个根结点及两棵不相交的左子树和右子树组成。 二叉树的特点是每个结点最多有两个孩子,或者说,在二叉树中,不存在度大于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 对任意一棵二叉树,如果叶子结点个数为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个结点的二叉树,称为满二叉树。 从上面满二叉树定义可知,必须是二叉树的每一层上的结点数都达到最大,否则就不是满二叉树。,完全二叉树 如果一棵具有D个结点的深度为k的二叉树,它的每一个结点都与深度为k的满二叉树中编号为1 D的结点一一对应,则称这棵二叉树为完全二叉树。 从完全二叉树定义可知,结点的排列顺序遵循从上到下、从左到右的规律。所谓从上到下,表示本层结点数达到最大后,才能放入下一层。从左到右,表示同一层结点必须按从左到右排列,若左边空一个位置时不能将结点放入右边。,从满二叉树及完全二叉树定义还可以知道,满二叉树一定是一棵完全二叉树,反之完全二叉树不一定是一棵满二叉树。满二叉树的叶子结点全部在最底层,而完全二叉树的叶子结点可以分布在最下面两层。深度为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),即 k=log2(D+1)。即得到第二个结论。 由有2k-1D,同时取对数得:klog2D+1即 k=log2 D+1,即第一个结论成立,证毕。,4.3二叉树树的遍历,所谓遍历(Traversal)是指沿着某条搜索路线,依次对树中每个结点均做 一次且仅做一次访问。 从二叉树的递归定义可知,一棵非空的二叉树由根结点及左、右子树这 三个基本部分组成。因此,在任一给定结点上,可以按某种次序执行三 个操作: 访问结点本身(D), 遍历该结点的左子树(L), 遍历该结点的右子树(R),以上三种操作有六种执行次序: DLR、LDR、LRD、DRL、RDL、RLD。,前三种次序与后三种次序对称,故只讨论先左后右的前三种次序。,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递归遍历,中根遍历二叉树的递归遍历算法描述为: 若二叉树为空,则算法结束;否则 (1)中根遍历左子树; (2)遍历根; (3)中根遍历右子树;,(1)中序遍历a的左子树(dbfe) (2) 再访问根节点 a (3)中序遍历a的右子树c 所以左图二叉树遍历的结果为 dbfeac,4.3.3后根遍历(LRD) 所谓后根遍历,就是左子树最先遍历,其次是右子树根,最后根。,1递归遍历,后根遍历二叉树的递归遍历算法描述为: 若二叉树为空,则算法结束;否则 (1)后根遍历左子树; (2)后根遍历右子树; (3)遍历根;,请你后根遍历左图,dfebca,另外,在编译原理中,有用二叉 树来表示一个算术表达式的情形。在一棵二叉树中,若用操作数代表树叶,运算符代表非叶子结点,则这样的树可以代表一个算术表达式。若按前序、中序、后序对该二叉树进行遍历,则得到的遍历序列分别称为前缀表达式(或称波兰式)、中缀表达式、后缀表达式(递波兰式)。具体参见图4-12。,图4-12所对应的前缀表达式: -*abc。 图4-12所对应的中缀表达式:a*b-c。图4-12所对应的后缀表达式:ab*c-。,4.3.4遍历算法应用举例,例4-5 由二叉树的前序序列和中序序列建立该二叉树,分析:若二叉树的任意两个结点的值都不相同,则二叉树的前序序列和中序序列能唯一确定一棵二叉树。另外,由前序序列和中序序列的定义可知,前序序列中第一个结点必为根结点,而在中序序列中,根结点刚好是左、右子树的分界点,因此,可按如下方法建立二叉树:,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 C IF,4.4 哈夫曼树,1.基本术语,1)路径和路径长度 在一棵树中,从一个结点往下可以达到的孩子或子孙结点之间的通路,称为路径。通路中分支的数目称为路径长度。 若规定根结点的层数为1,则从根结点到第L层结点的路径长度为L-1。,2)结点的权及带权路径长度 若将树中结点赋给一个有着某种含义的数值,则这个数值称为该结点的权。 结点的带权路径长度为:从根结点到该结点之间的路径长度与该结点的权的乘积。,3)树的带权路径长度 树的带权路径长度规定为所有叶子结点的带权路径长度之和,记为wpl= ,其中D 为叶子结点数目,wi为第i 个叶子结点的权值,li 为第i 个叶子结点的路径长度。,1哈夫曼树的定义在一棵二叉树中,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(HuffmaD tree)。,4.4.2 哈夫曼树构造,(1) 在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和; (2)从森林中删除选取的两棵树,并将新树加入森林; (3)重复(1)、(2)步,直到森林中只剩一棵树为止,该树即为我们所求得的哈夫曼树。,下面给出哈夫曼树的构造过程,假设给定的叶子结点的权分别为1,5,7,3,则构造哈夫曼树过程如图4-29所示。 从图4-29可知,D 个权值构造哈夫曼树需D-1次合并,每次合并,森林中的树数目减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的最优二叉树, 并求出所有叶节点带权路径长度之和。,
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号