树与二叉树分析

1、第六章第六章深圳大学计算机系一、树的定义一、树的定义( (Tree)Tree)2第一节树的概念与基本术语第一节树的概念与基本术语n树是有树是有n(n0)n(n0)个结点的有限集合。个结点的有限集合。n如果如果 n=0n=0，称为空树；称为空树；n如果如果 n0,n0,称为非空树称为非空树, ,对于非空树对于非空树, ,有且仅有一个特有且仅有一个特定的称为根定的称为根( (Root)Root)的节点的节点( (无直接前驱无直接前驱) )n如果如果 n1n1，则除根以外的其它结点划分为则除根以外的其它结点划分为 m (m0)m (m0)个个互不相交的有限集互不相交的有限集 T1, T2 ,T1,

2、T2 , Tm, Tm，其中每个集合其中每个集合本身又是一棵树，并且称为根的子树本身又是一棵树，并且称为根的子树( (SubTree)SubTree)。( (此此为递归定义为递归定义) )n每个结点都有唯一的直接前驱，但可能有多个后继每个结点都有唯一的直接前驱，但可能有多个后继第章树与二叉树第章树与二叉树一、树的定义一、树的定义( (举例举例) )3第一节树的概念与基本术语第一节树的概念与基本术语n其中：其中：A A是根；其余结点分成三个互不相交的子集，是根；其余结点分成三个互不相交的子集，nT1=B,E,F,K,LT1=B,E,F,K,L； T2=C,G T2=C,G； T3=D,H,I,J

3、,M, T3=D,H,I,J,M,nT1,T2,T3T1,T2,T3都是根都是根A A的子树，且本身也是一棵树的子树，且本身也是一棵树第章树与二叉树第章树与二叉树A只有根结点的树只有根结点的树ACGBDEFKLHMIJ有有13个结点的树个结点的树二、树的基本术语二、树的基本术语4第一节树的概念与基本术语第一节树的概念与基本术语n结点：结点：包含一个数据元素及若干指向其子树的分支包含一个数据元素及若干指向其子树的分支n结点的度：结点的度：结点拥有的子树数结点拥有的子树数n叶结点：叶结点：度为度为0 0的结点的结点 没有子树的结点没有子树的结点 n分支结点：分支结点：度不为度不为0 0的结点的结点

4、 包括根结点包括根结点 ，也称为非终端结点。也称为非终端结点。除根外称为内部结点除根外称为内部结点第章树与二叉树第章树与二叉树1层2层4层3层Height= 4ACGBDEFKLHMIJ二、树的基本术语二、树的基本术语5第一节树的概念与基本术语第一节树的概念与基本术语n孩子：孩子：结点的子树的根结点的子树的根 直接后继，可能有多个直接后继，可能有多个 n双亲：双亲：孩子的直接前驱孩子的直接前驱 最多只能有一个最多只能有一个 n兄弟：兄弟：同一双亲的孩子同一双亲的孩子n子孙：子孙：以某结点为根的以某结点为根的树中的所有结点树中的所有结点n祖先：祖先：从根到该结点从根到该结点所经分支上的所有结点所

5、经分支上的所有结点第章树与二叉树第章树与二叉树1层2层4层3层Height= 4ACGBDEFKLHMIJ二、树的基本术语二、树的基本术语6第一节树的概念与基本术语第一节树的概念与基本术语n层次：根结点为第一层，其孩子为第二层，依此类推层次：根结点为第一层，其孩子为第二层，依此类推n深度：树中结点的最大层次深度：树中结点的最大层次n有序树：子树之间存有序树：子树之间存 在确定的次序关系。在确定的次序关系。n无序树无序树: :子树之间子树之间 不存在确定的次序关系。不存在确定的次序关系。第章树与二叉树第章树与二叉树1层2层4层3层Height= 4ACGBDEFKLHMIJ二、树的基本术语二、树

6、的基本术语7第一节树的概念与基本术语第一节树的概念与基本术语n森林：互不相交的树的集合。森林：互不相交的树的集合。对树中每个结点而言，对树中每个结点而言，其子树的集合即为森林其子树的集合即为森林. .第章树与二叉树第章树与二叉树ArootBCDEFGHIJMKLF任何一棵非空树是一个二元组 Tree = （root，F）其中：root 被称为根结点 F 被称为子树森林线性结构线性结构树型结构树型结构第一个数据元素第一个数据元素 ( (无前驱无前驱) ) 根结点根结点 ( (无前驱无前驱) )最后一个数据元素最后一个数据元素 (无后继无后继)多个叶子结点多个叶子结点 ( (无后继无后继) )其它

7、数据元素其它数据元素( (一个前驱、一个前驱、 一个后继一个后继) )其它数据元素其它数据元素( (一个前驱、一个前驱、 多个后继多个后继) )一、二叉树一、二叉树( (Binary Tree)Binary Tree)9第二节二叉树第二节二叉树n二叉树是一种特殊的树二叉树是一种特殊的树n每个结点最多有棵子树每个结点最多有棵子树n二叉树的子树有左右之分二叉树的子树有左右之分第章树与二叉树第章树与二叉树LLRR空树只有根只有左子树 只有右子树有左右子树二、二叉树性质二、二叉树性质10第二节二叉树第二节二叉树n在二叉树的第在二叉树的第i i层上至多有层上至多有2 2i-1i-1个结点个结点n证明：证

8、明：1.1.i=1, i=1, 只有一个根节点，因此只有一个根节点，因此2 2i-1i-1=2=20 0=1=12.2.设第设第i-1i-1层上，以上性质成立，即第层上，以上性质成立，即第i-1i-1层至层至多有多有2 2(i-1)-1(i-1)-1结点。由二叉树的定义可知，任何结点。由二叉树的定义可知，任何结点的度小于结点的度小于2 2，因此，第，因此，第i i层上的结点数最多层上的结点数最多为第为第i-1i-1层上的两倍，即层上的两倍，即2 2* *2 2i-2i-2=2=2i-1i-1第章树与二叉树第章树与二叉树三、二叉树性质三、二叉树性质11第二节二叉树第二节二叉树n深度为深度为k k

9、的二叉树至多有的二叉树至多有2 2k k-1-1个结点个结点n证明：证明：1.1.由性质，已知第由性质，已知第i i层上结点数最多为层上结点数最多为2 2i-1i-1 k k2.2. 2 2i-1 i-1 = 2= 2k k-1-1 i=1i=1第章树与二叉树第章树与二叉树四、二叉树性质四、二叉树性质12第二节二叉树第二节二叉树n如果二叉树终端结点数为如果二叉树终端结点数为n n0 0，度为度为2 2的结点数为的结点数为n n2 2，则则n n0 0=n=n2 2+1+1n证明：证明：1.1.设设n n1 1为度为为度为1 1的结点，则总结点数的结点，则总结点数n= nn= n0 0+n+n1

10、 1+n+n2 22.2.设设B B为二叉树的分支数，除根结点外，每个结点有且为二叉树的分支数，除根结点外，每个结点有且只有一个分支，因此只有一个分支，因此n=B+1n=B+13.3.每个分支皆由度为每个分支皆由度为1 1或或2 2的结点发出，的结点发出，B=nB=n1 1+2n+2n2 24.n=B+1=(n4.n=B+1=(n1 1+2n+2n2 2)+1 )+1 = = n n0 0+n+n1 1+n+n2 2，因此，因此 n n0 0=n=n2 2+1+1第章树与二叉树第章树与二叉树五、满二叉树五、满二叉树13第二节二叉树第二节二叉树n一个深度为一个深度为k k且有且有2 2k k-1

11、-1个结点的二叉树个结点的二叉树n每层上的结点数都是最大数每层上的结点数都是最大数n可以自上而下、可以自上而下、自左至右连续编号自左至右连续编号第章树与二叉树第章树与二叉树621754389 10 1113 14 1512六、完全二叉树六、完全二叉树14第二节二叉树第二节二叉树n当且仅当每一个结点都与深度相同的满二叉树当且仅当每一个结点都与深度相同的满二叉树中编号从中编号从1 1到到n n的结点一一对应的二叉树的结点一一对应的二叉树n叶子结点只在最大两层上出现叶子结点只在最大两层上出现n左子树深度与右子树左子树深度与右子树深度相等或大深度相等或大第章树与二叉树第章树与二叉树621754389

12、10 11 12六、完全二叉树六、完全二叉树( (性质性质) )15第二节二叉树第二节二叉树n具有具有n n个结点的完全二叉树个结点的完全二叉树, ,其深度为其深度为loglog2 2n +1n +1n设设k k为深度，由二叉树性质，已知为深度，由二叉树性质，已知 2 2k-1k-1-1-1 n n 2 2k k-1-1即即 2 2k-1k-1 n n 2 2k k即即 k = logk = log2 2n +1n +1第章树与二叉树第章树与二叉树621754389 10 11 12六、完全二叉树六、完全二叉树( (性质性质) )16第二节二叉树第二节二叉树n在完全二叉树中，结点在完全二叉树中

13、，结点i i的双亲为的双亲为 i/2i/2n结点结点i i的左孩子的左孩子LCHILD(i)=2iLCHILD(i)=2in结点结点i i的右孩子的右孩子RCHILD(i)=2i+1RCHILD(i)=2i+1第章树与二叉树第章树与二叉树621754389 10 11 122i+2i2i+32i+12ii+1i/2七、二叉树的顺序存储结构七、二叉树的顺序存储结构17第二节二叉树第二节二叉树n用一组连续的存储单元依次自上而下用一组连续的存储单元依次自上而下, ,自左至右自左至右存储结点存储结点第章树与二叉树第章树与二叉树完全二叉树的顺序表示一般二叉树的顺序表示完全二叉树的顺序表示一般二叉树的顺序

14、表示1 2 3 4 5 6 7 8 9101 2 3 4 0 5 6 7 8 0 0 910 12489 105673912364789 105一、一、 二叉树的顺序存储表示二叉树的顺序存储表示例例:ABCDEF A B D C E F 0 1 2 3 4 5 6 7 8 9 10 11 12 131401326二叉树的顺序存储缺点：浪费空间。二叉树的顺序存储缺点：浪费空间。七、二叉树的链式存储结构七、二叉树的链式存储结构20第二节二叉树第二节二叉树1.1.二叉链表二叉链表n采用数据域加上左、右孩子指针采用数据域加上左、右孩子指针第章树与二叉树第章树与二叉树datalChildrChildlC

15、hild data rChild七、二叉树的链式存储结构七、二叉树的链式存储结构21第二节二叉树第二节二叉树1.1.二叉链表二叉链表( (举例举例) )n二叉树（左）及其二叉链表（右）二叉树（左）及其二叉链表（右）第章树与二叉树第章树与二叉树ABCDFEroot ABCDFErootlchild data rchild结点结构结点结构:；七、二叉树的链式存储结构七、二叉树的链式存储结构23第二节二叉树第二节二叉树. .三叉链表三叉链表n采用数据域加上左、右孩子指针及双亲指针采用数据域加上左、右孩子指针及双亲指针第章树与二叉树第章树与二叉树lChild data parent rChildpar

16、entdatalChildrChild七、二叉树的链式存储结构七、二叉树的链式存储结构24第二节二叉树第二节二叉树. .三叉链表三叉链表( (举例举例) )n二叉树（左）及其三叉链表（右）二叉树（左）及其三叉链表（右）第章树与二叉树第章树与二叉树ABCDFEroot ABCDFE root一、遍历二叉树一、遍历二叉树25第三节遍历二叉树第三节遍历二叉树n树的遍历就是按某种次序访问树中的结点，要树的遍历就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次求每个结点访问一次且仅访问一次（非线性结（非线性结构线性化）构线性化）n对对“二叉树二叉树”而言，可以有三条搜索路径：而言，可以有三条

17、搜索路径：n1先上后下先上后下的按层次遍历；n2先左先左（子树）后右后右（子树）的遍历；n3先右先右（子树）后左后左（子树）的遍历。第章树与二叉树第章树与二叉树LR一、遍历二叉树一、遍历二叉树26第三节遍历二叉树第三节遍历二叉树n一个二叉树由根节点与左子树和右子树组成一个二叉树由根节点与左子树和右子树组成n设访问根结点用设访问根结点用D D表示，遍历左、右子树用表示，遍历左、右子树用L L、R R表示表示n如果规定如果规定先左子树后右子树先左子树后右子树，则共有三种组合，则共有三种组合1.1.DLR DLR 先序遍历先序遍历 2.LDR 2.LDR 中序遍历中序遍历 3.LRD 3.LRD 后

18、序遍历后序遍历 第章树与二叉树第章树与二叉树LR二、先序遍历二叉树二、先序遍历二叉树27第三节遍历二叉树第三节遍历二叉树n算法：算法：1.1.若二叉树为空，则返回；否则：若二叉树为空，则返回；否则：2.2.访问根节点访问根节点( (D)D)3.3.先序遍历左子树先序遍历左子树( (L)L)4.4.先序遍历右子树先序遍历右子树( (R)R)第章树与二叉树第章树与二叉树LR二、先序遍历二叉树二、先序遍历二叉树28第三节遍历二叉树第三节遍历二叉树n算法算法( (举例举例) )：第章树与二叉树第章树与二叉树ADBFCGE输出结果：输出结果：ABDEGCFABDEGCF二、先序遍历二叉树二、先序遍历二叉

19、树29第三节遍历二叉树第三节遍历二叉树第章树与二叉树第章树与二叉树三、中序遍历二叉树三、中序遍历二叉树30第三节遍历二叉树第三节遍历二叉树n算法：算法：1.1.若二叉树为空，则返回；否则：若二叉树为空，则返回；否则：2.2.中序遍历左子树中序遍历左子树( (L)L)3.3.访问根节点访问根节点( (D)D)4.4.中序遍历右子树中序遍历右子树( (R)R)第章树与二叉树第章树与二叉树LR三、中序遍历二叉树三、中序遍历二叉树31第三节遍历二叉树第三节遍历二叉树n算法算法( (举例举例) )：第章树与二叉树第章树与二叉树ADBFCGE输出结果：输出结果：DBGEAFCDBGEAFC三、中序遍历二叉

20、树三、中序遍历二叉树32第三节遍历二叉树第三节遍历二叉树第章树与二叉树第章树与二叉树；四、后序遍历二叉树四、后序遍历二叉树33第三节遍历二叉树第三节遍历二叉树n算法：算法：1.1.若二叉树为空，则返回；否则：若二叉树为空，则返回；否则：2.2.后序遍历左子树后序遍历左子树( (L)L)3.3.后序遍历右子树后序遍历右子树( (R)R)4.4.访问根节点访问根节点( (D)D)第章树与二叉树第章树与二叉树LR四、后序遍历二叉树四、后序遍历二叉树34第三节遍历二叉树第三节遍历二叉树n算法算法( (举例举例) )：第章树与二叉树第章树与二叉树ADBFCGE输出结果：输出结果：DGEBFCADGEBF

21、CA四、后序遍历二叉树四、后序遍历二叉树35第三节遍历二叉树第三节遍历二叉树第章树与二叉树第章树与二叉树；遍历练习遍历练习n 用二叉树来表示表达式n 先序遍历得到前缀表达式（波兰式）-+ a b c / d en 中序遍历得到中缀表达式 (a+b)c d/en 后续遍历得到后缀表达式（逆波兰式）ab+cde/-eabcd- -+/e e e遍历的应用遍历的应用1.根据遍历顺序来确定二叉树的结构（逻辑上）2. 根据先序序列建立二叉树的二叉链表（物理上） 仅知二叉树的先序序列“abcdefg” 不能唯一确定一棵二叉树，由二叉树的先序和中序序列建树由二叉树的先序和中序序列建树 如果同时已知二叉树的中

22、序序列“cbdaegf”，则会如何？ 二叉树的先序序列二叉树的中序序列左子树左子树左子树左子树 右子树右子树右子树右子树根根根根a b c d e f gc b d a e g f例例: :aab bccddeeffggabcdefg先序序列中序序列练习练习n假设一颗二叉树的先序遍历序列为ABDEHCFGIn中序遍历序列为DBEHAFCIGn请画出这颗二叉树n思考：如果给出后序遍历序列和中序遍历序列，是否可以确定该二叉树的结构？4、建立二叉树的存储结构不同的定义方法相应有不同的存储结构的建立算法不同的定义方法相应有不同的存储结构的建立算法在此讨论利用先序序列，建立二叉链表在此讨论利用先序序列，

23、建立二叉链表 以先序序列创建一棵二叉树以先序序列创建一棵二叉树ABCD以空白字符“ ”表示A(B( ,C( , ),D( , )空树空树只含一个根结点只含一个根结点的二叉树的二叉树A以字符串“A ”表示以下列字符串表示A B C D A BCD上页算法执行过程举例如下：ATBCD一、增加新指针一、增加新指针45第四节线索二叉树第四节线索二叉树n最简单的方法是在每个结点中，增加前驱最简单的方法是在每个结点中，增加前驱( (fwd)fwd)和后继和后继( (bkwd)bkwd)指针指针n在做二叉树遍历（前、中、后序），将每个结在做二叉树遍历（前、中、后序），将每个结点的前驱和后继信息添入点的前驱和

24、后继信息添入fwdfwd和和bkwdbkwd域中域中第章树与二叉树第章树与二叉树fwdlChilddatarChildbkwd问题：遍历是将非线性结构线性化，结点的先后关系的信息（某个结点在序列中的前驱和后继等信息）在遍历的动态过程中得到，如何保存这些动态信息呢？二、利用空指针二、利用空指针46第四节线索二叉树第四节线索二叉树n在有在有n n个结点的二叉树中，必定存在个结点的二叉树中，必定存在n+1n+1个空链个空链域域n因为每个结点有两个链域（左、右孩子指针），因为每个结点有两个链域（左、右孩子指针），因此共有因此共有2 2n n个链域个链域n除根结点外，每个结点都有且仅有一个分支相除根结点

25、外，每个结点都有且仅有一个分支相连，即连，即n-1n-1个链域被使用个链域被使用第章树与二叉树第章树与二叉树二、利用空指针二、利用空指针47第四节线索二叉树第四节线索二叉树n在结点中增加两个标记位（在结点中增加两个标记位（LTag, RTag)LTag, RTag)nLTag=0, lChildLTag=0, lChild域指示结点的左孩子域指示结点的左孩子LTag=1, lChildLTag=1, lChild域指示结点的前驱结点域指示结点的前驱结点nRTag=0, lChildRTag=0, lChild域指示结点的右孩子域指示结点的右孩子RTag=1, lChildRTag=1, lCh

26、ild域指示结点的后继结点域指示结点的后继结点第章树与二叉树第章树与二叉树LTaglChilddatarChildRTag懂原理，最多会画即可，对于建立过程不需要掌握一、树的存储结构一、树的存储结构48第五节树与森林第五节树与森林1.1.双亲表示法双亲表示法n采用一组连续的存储空间采用一组连续的存储空间n由于每个结点只有一个双亲，只需要一个指针由于每个结点只有一个双亲，只需要一个指针第章树与二叉树第章树与二叉树ABCDEFG-10001130 1 2 3 4 5 6AEBGDFC一、树的存储结构一、树的存储结构49第五节树与森林第五节树与森林2.2.孩子表示法孩子表示法n可以采用多重链表，即每

27、个结点有多个指针可以采用多重链表，即每个结点有多个指针n最大缺点是空链域太多最大缺点是空链域太多(d-1)n+1d-1)n+1个个 第章树与二叉树第章树与二叉树AEBGDFC data child1child2child3childd一、树的存储结构一、树的存储结构50第五节树与森林第五节树与森林2.2.孩子表示法孩子表示法n将每个结点的孩子排列起来，用单链表表示将每个结点的孩子排列起来，用单链表表示n将每个结点排列成一个线性表将每个结点排列成一个线性表第章树与二叉树第章树与二叉树AEBGDFCABCDEFG0123456Root123 45 6 一、树的存储结构一、树的存储结构51第五节树与

28、森林第五节树与森林3.3.孩子兄弟表示法孩子兄弟表示法n采用二叉链表采用二叉链表n左边指针指向第一个孩子，右边指针指向兄弟左边指针指向第一个孩子，右边指针指向兄弟第章树与二叉树第章树与二叉树AEBGDFC datafirstChild nextSiblingBCDGFE A 二、树与二叉树的对应关系二、树与二叉树的对应关系52第五节树与森林第五节树与森林n树与二叉树都可以采用二叉链表作存储结构树与二叉树都可以采用二叉链表作存储结构n任意给定一棵树，可以找到一个唯一的二叉树任意给定一棵树，可以找到一个唯一的二叉树( (没有右子树没有右子树) )第章树与二叉树第章树与二叉树AEBGDFCBCDGF

29、E A ABGDFCE树对应的二叉树树与二叉树的转换树与二叉树的转换: :以二叉链表作为存储结构，将其解释为树或二叉树，以二叉链表作为存储结构，将其解释为树或二叉树，实现两者之间的转换。实现两者之间的转换。三、森林与二叉树的对应关系三、森林与二叉树的对应关系54第五节树与森林第五节树与森林n如果把森林中的第二棵树的根结点看作是第一如果把森林中的第二棵树的根结点看作是第一棵树的根结点的兄弟，则可找到一个唯一的二棵树的根结点的兄弟，则可找到一个唯一的二叉树与之对应叉树与之对应第章树与二叉树第章树与二叉树三棵树的森林对应的二叉树T1 T2 T3AFHB C DGIJEKABCEDHIKFGJ四、树的

30、遍历四、树的遍历55第五节树与森林第五节树与森林n对树的遍历主要有两种：对树的遍历主要有两种：1. 1. 先根（次序）遍历先根（次序）遍历2. 2. 后根（次序）遍历后根（次序）遍历第章树与二叉树第章树与二叉树AEBGDFC四、树的遍历四、树的遍历56第五节树与森林第五节树与森林1. 1. 先根（次序）遍历先根（次序）遍历 当树非空时当树非空时n 访问根结点访问根结点n 依次先根遍历根的各棵子树依次先根遍历根的各棵子树 输出结果：输出结果：ABEFCDGABEFCDG第章树与二叉树第章树与二叉树AEBGDFC四、树的遍历四、树的遍历57第五节树与森林第五节树与森林2. 2. 后根（次序）遍历后

31、根（次序）遍历 当树非空时当树非空时n依次后根遍历根的各棵子树依次后根遍历根的各棵子树n访问根结点访问根结点 输出结果：输出结果：EFBCGDAEFBCGDA第章树与二叉树第章树与二叉树AEBGDFC五、森林的遍历五、森林的遍历58第五节树与森林第五节树与森林n对森林的遍历主要有两种：对森林的遍历主要有两种：1. 1. 先序遍历先序遍历2. 2. 中序遍历中序遍历第章树与二叉树第章树与二叉树AEBGDFC五、森林的遍历五、森林的遍历59第五节树与森林第五节树与森林1. 1. 先序遍历 若森林不空，则n访问访问森林中第一棵树的根结点；n先序遍历先序遍历森林中第一棵树的子树森林；n先序遍历先序遍历

32、森林中(除第一棵树之外)其余树构成的森林。第章树与二叉树第章树与二叉树即：依次从左至右依次从左至右对森林中的每一棵树树进行先根遍历先根遍历。AFHBCDGIJEK先序遍历：ABCDEFGHIKJ五、森林的遍历五、森林的遍历第五节树与森林第五节树与森林第章树与二叉树第章树与二叉树1. 1. 先序遍历五、森林的遍历五、森林的遍历61第五节树与森林第五节树与森林2.2. 中序遍历 若森林不空，则n中序遍历中序遍历森林中第一棵树的子树森林；n访问访问森林中第一棵树的根结点；n中序遍历中序遍历森林中(除第一棵树之外)其余树构成的森林。第章树与二叉树第章树与二叉树即：依次从左至右依次从左至右对森林中的每一

33、棵树树进行后根遍历后根遍历。AFHBCDGIJEK中序遍历：BCEDAGFKIJH五、森林的遍历五、森林的遍历第五节树与森林第五节树与森林第章树与二叉树第章树与二叉树2. 2. 中序遍历思考？思考？n当树以二叉链表(孩子兄弟表示法)进行存储，则树的先根遍历和后根遍历与二叉树的遍历算法有什么关系？树的先根-二叉树的先序树的后根-二叉树的中序 遍历的对应关系遍历的对应关系先根遍历先根遍历后根遍历后根遍历树树二叉树二叉树森林森林先序遍历先序遍历先序遍历先序遍历中序遍历中序遍历中序遍历中序遍历练习练习1.1.若一个二叉树具有若一个二叉树具有8个度为个度为2的结点，的结点，7个度为个度为1的结点，则度为

34、的结点，则度为0的结点（叶子）个数是的结点（叶子）个数是_。2.2.具有具有n个结点的二叉树中，一共有个结点的二叉树中，一共有_个指针个指针域，其中域，其中_个用来指向结点的左右孩子，有个用来指向结点的左右孩子，有_个为个为NULL。练习练习3.3.假定用一维数组假定用一维数组a7顺序存储一个循环队列，顺序存储一个循环队列，队首和队尾指针分别用队首和队尾指针分别用front和和rear表示，当前表示，当前队列中已有队列中已有4个元素：个元素：12，23，78，60，其中，其中12为队首元素，为队首元素，front的值为的值为3，请画出对应的，请画出对应的存储状态。当连续做存储状态。当连续做2次

35、出队运算后，再让次出队运算后，再让15，36，40，50，60元素依次进队，分别画出队、元素依次进队，分别画出队、入队后对应的存储状态。入队后对应的存储状态。练习练习4.4.二叉树的中序和后序遍历结果分别为二叉树的中序和后序遍历结果分别为EFBCGHIDA和和FEIHGDCBA。 （1） 画出该树，求其先序遍历的结果；画出该树，求其先序遍历的结果； （2）将其转换为树，画出转换后的树）将其转换为树，画出转换后的树。 （3）求其先根、后根遍历序列。求其先根、后根遍历序列。一、最优二叉树一、最优二叉树68第六节赫夫曼树及其应用第六节赫夫曼树及其应用n路径：从树中一个结点到另一个结点之间的分路径：从

36、树中一个结点到另一个结点之间的分支构成这两个结点之间的路径支构成这两个结点之间的路径n路径长度：路径上的分支数目路径长度：路径上的分支数目n树的路径长度：从树根到树的路径长度：从树根到每个结点的路径长度之和每个结点的路径长度之和n右树路径长度为：右树路径长度为：2 2* *1 + 31 + 3* *2 + 12 + 1* *3 = 113 = 11第章树与二叉树第章树与二叉树ADBFCGE一、最优二叉树一、最优二叉树69第六节赫夫曼树及其应用第六节赫夫曼树及其应用n结点的带权路径长度：从结点到树根之间的路结点的带权路径长度：从结点到树根之间的路径长度与结点上权的乘积径长度与结点上权的乘积n树的

37、带权路径长度树的带权路径长度( (WPL)WPL)：树中所有叶子结点树中所有叶子结点的带权路径长度之和的带权路径长度之和nWPL = 2WPL = 2* *5+35+3* *3+23+2* *4=274=27第章树与二叉树第章树与二叉树ADBFCGE5一、最优二叉树一、最优二叉树70第六节赫夫曼树及其应用第六节赫夫曼树及其应用n最优二叉树：假设二叉树有最优二叉树：假设二叉树有n n个叶子，其每个个叶子，其每个叶子结点带权叶子结点带权w wi i，则带权路径长度则带权路径长度WPLWPL最小的最小的二叉树称为最优二叉树或赫夫曼二叉树称为最优二叉树或赫夫曼( (Huffman)Huffman)树。

38、树。nWPL = 1WPL = 1* *5+25+2* *3+23+2* *4=194=19第章树与二叉树第章树与二叉树ADBCE5第六节赫夫曼树及其应用第六节赫夫曼树及其应用第章树与二叉树第章树与二叉树例：例：设设5 5个叶子结点，分别带权个叶子结点，分别带权7 7、9 9、5 5、4 4、2 2， 至少画出至少画出2 2种二叉树，并计算带权路径长度。种二叉树，并计算带权路径长度。27549WPL(T)= 72+52+23+43+92 =60WPL(T)= 74+94+53+42+21 =89 7 9 254二、二、HuffmanHuffman树树( (构造构造) )73第六节赫夫曼树及其应

39、用第六节赫夫曼树及其应用n在在HuffmanHuffman树中，权值最大的结点离根最近树中，权值最大的结点离根最近n权值最小的结点离根最远权值最小的结点离根最远第章树与二叉树第章树与二叉树ADBCE5二、二、HuffmanHuffman树树( (算法算法) )74第六节赫夫曼树及其应用第六节赫夫曼树及其应用1.1.根据给定的根据给定的n n个权值个权值( (w w1 1, w, w2 2, , , w, wn n) )构成构成n n棵二叉树棵二叉树的集合的集合F=TF=T1 1, T, T2 2, , , T, Tn n ，其中每棵二叉树其中每棵二叉树T Ti i中只中只有一个带权为有一个带权

40、为w wi i的根结点，左右子树为空的根结点，左右子树为空2.2.在在F F中选取两棵根结点的权值最小的树作为左右子树中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置其根结点的权值为其左右构造一棵新的二叉树，且置其根结点的权值为其左右子树根结点的权值之和子树根结点的权值之和3.3.在在F F中删除这两棵树，同时将新得到的二叉树加入中删除这两棵树，同时将新得到的二叉树加入F F中中4.4.重复重复2, 32, 3，直到，直到F F只含一棵树为止只含一棵树为止第章树与二叉树第章树与二叉树二、二、HuffmanHuffman树树( (举例举例) )75第六节赫夫曼树及其应用第六节赫

41、夫曼树及其应用第章树与二叉树第章树与二叉树F : 7 5 2 4F : 7 5 6F : 7 11 7524初始合并2 475246F : 18 1175246合并5 65合并7 11274611189例如例如: : 已知权值已知权值 W= 5, 6, 2, 9, 7 56275276976713975267139797166713295252第六节赫夫曼树及其应用第六节赫夫曼树及其应用第章树与二叉树第章树与二叉树练习：练习：设叶子结点设叶子结点a a、b b、c c、d d、e e的权值分别的权值分别为为5 5 、4 4 、10 10 、12 12 、9 9，构造，构造HuffmanHuff

42、man树，并树，并计算带权路径长度。计算带权路径长度。三、三、HuffmanHuffman编码编码79第六节赫夫曼树及其应用第六节赫夫曼树及其应用n设给出一段报文：设给出一段报文：GOOD_GOOD_GOOD_GOOOOOOOO_OFFGOOD_GOOD_GOOD_GOOOOOOOO_OFFn字符集合是字符集合是 O, G, _, D, FO, G, _, D, F，各个字符出各个字符出现的频度现的频度( (次数次数) )是是 W W 15, 4, 4, 3, 2 15, 4, 4, 3, 2。n若给每个字符以等长编码若给每个字符以等长编码O: 000 G: 001 _: 010 D: 011

43、 F: 100O: 000 G: 001 _: 010 D: 011 F: 100n则总编码长度为则总编码长度为 (1 (15+4+4+3+2) 5+4+4+3+2) * * 3 = 84. 3 = 84.第章树与二叉树第章树与二叉树三、三、HuffmanHuffman编码编码80第六节赫夫曼树及其应用第六节赫夫曼树及其应用n若按各个字符出现的概率不同而给予不等长编若按各个字符出现的概率不同而给予不等长编码，可望减少总编码长度。码，可望减少总编码长度。n各字符各字符 O, G, _, D, F O, G, _, D, F 出现概率为出现概率为 1 15/28, 4/28, 4/28, 3/28

44、, 2/28 ,5/28, 4/28, 4/28, 3/28, 2/28 ,化整化整为为 1 15, 4, 4, 3, 2 5, 4, 4, 3, 2 第章树与二叉树第章树与二叉树三、三、HuffmanHuffman编码编码81第六节赫夫曼树及其应用第六节赫夫曼树及其应用n各字符出现概率各字符出现概率 取整数取整数 为为115, 4, 4, 3, 25, 4, 4, 3, 2n如果规定，如果规定，HuffmanHuffman树的左子树小于右子树，树的左子树小于右子树，则可构成右图所示则可构成右图所示HuffmanHuffman树树第章树与二叉树第章树与二叉树415423G_FDO三、三、Huf

45、fmanHuffman编码编码82第六节赫夫曼树及其应用第六节赫夫曼树及其应用n令左孩子分支为编码令左孩子分支为编码0 0，右，右孩子分支为编码孩子分支为编码1 1n将根结点到叶子结点路径上的将根结点到叶子结点路径上的分支编码，组合起来，作为该分支编码，组合起来，作为该字符的字符的HuffmanHuffman码，则可得到：码，则可得到：O:1 _:011 G:010 D:001 O:1 _:011 G:010 D:001 F:000 F:000第章树与二叉树第章树与二叉树41542300001111G_FDO三、三、HuffmanHuffman编码编码83第六节赫夫曼树及其应用第六节赫夫曼树及

46、其应用n则总编码长度为则总编码长度为 1 15 5* *1+(2+3+4+4)1+(2+3+4+4)* *3 = 54 3 = 54 84 84nHuffmanHuffman是一种前缀编码，解码是一种前缀编码，解码时不会混淆时不会混淆n如如GOODGOOD编码为：编码为：0101100101011001第章树与二叉树第章树与二叉树41542300001111G_FDO 若设计长短不等的编码，则必须是任一个若设计长短不等的编码，则必须是任一个字符的编码都不是另一个字符编码的前缀，称为字符的编码都不是另一个字符编码的前缀，称为前缀编码。前缀编码。前缀编码前缀编码 利用利用赫夫曼树赫夫曼树可以构造一

47、种不等长的二进制可以构造一种不等长的二进制编码，并且构造所得的赫夫曼编码是编码，并且构造所得的赫夫曼编码是一种最优一种最优前缀编码前缀编码，即使，即使所传电文的总长度最短所传电文的总长度最短。第六节赫夫曼树及其应用第六节赫夫曼树及其应用第章树与二叉树第章树与二叉树练习：练习：对电文对电文abbaccdeecabbaccdeec进行进行HuffmanHuffman编码。编码。四、四、HuffmanHuffman编码实现编码实现86第六节赫夫曼树及其应用第六节赫夫曼树及其应用第章树与二叉树第章树与二叉树HuffmanHuffman树的构造。用静态链表实现树的构造。用静态链表实现, ,结构如下。结构

48、如下。n n个叶子结点的个叶子结点的HuffmanHuffman树共树共2n-12n-1个结点。个结点。( (两两合两两合并，直至一个，共生成并，直至一个，共生成n-1n-1个结点）个结点）设静态链表为设静态链表为HTHT，计算过程如下：，计算过程如下： 初始令初始令n=n=叶子结点数，设置叶子结点数，设置0 0nn-1-1结点的结点的datadata、weightweight，并令所有单元的，并令所有单元的parent,lchild,rchildparent,lchild,rchild为为0 0 从从0n-10n-1中选取中选取parentparent为为0 0，权值最小的两个结点，权值最小的两个结点， 设为设为s1,s2,s1,s2,令令n n为此两结点的父结点，修改为此两结点的父结点，修改: : HTs1.parent = n; HTs2.parent = n; HTs1.parent = n; HTs2.parent = n; HTn.lchild = s1; HTn.rchild = s2; HTn.lchild = s1; HTn.rchild = s2; HTn.weight = HTs1.weight+HTs2.weight