第6章 树和二叉树-100-3

1、第6章 树和二叉树张成文张成文北京邮电大学计算机学院北京邮电大学计算机学院6.1 6.1 树的定义与基本术语树的定义与基本术语6.2 6.2 二叉树的类型定义二叉树的类型定义6.36.3 二叉树的存储结构二叉树的存储结构6.4 6.4 二叉树的遍历二叉树的遍历6.5 6.5 线索二叉树线索二叉树6.6 6.6 树和森林树和森林6.7 6.7 树和森林的遍历树和森林的遍历6.9 6.9 哈夫曼树与哈夫曼编码哈夫曼树与哈夫曼编码主要内容6.8 6.8 树的存储结构树的存储结构ABCDEFGHIJMKL例如例如: : 树的定义与基本术语树的定义与基本术语1.1.定义定义: : 树树是是n(n0)n(

2、n0)个结点的有限集合个结点的有限集合T T。当。当n=0n=0时时, ,称为空树称为空树; ;当当n0n0时时, ,该集合满足如下条件该集合满足如下条件: : (1) (1) 其中必有一个称为根其中必有一个称为根(root)(root)的特定结点的特定结点, ,它没它没有直接前驱有直接前驱, ,但有零个或多个直接后继。但有零个或多个直接后继。 (2) (2) 其余其余n-1n-1个结点可以划分成个结点可以划分成m(m0)m(m0)个互不相个互不相交的有限集交的有限集T T1 1,T,T2 2,T,T3 3, ,T,Tm m, ,其中其中T Ti i又是一棵树又是一棵树, ,称为称为根根roo

3、troot的子树。每棵子树的根结点有且仅有一个直的子树。每棵子树的根结点有且仅有一个直接前驱接前驱, ,但有零个或多个直接后继。但有零个或多个直接后继。 一、树一、树(tree)的基本概念的基本概念:ABCDEFGHIJMKLA( B(E, F(K, L), C(G), D(H, I, J(M) )T1T3T2树根例如例如: : (1). 树型图示树型图示 (2).嵌套集合嵌套集合 (3).凹入凹入(书目书目) (4). 广义表广义表(用根作为表的名字写在表的左边用根作为表的名字写在表的左边)ABCDEFGHIJKLMA - B - E - K - L - F - C - G - D - H

4、- M - I - J -2. 树的表示法树的表示法:线性结构线性结构树型结构树型结构第一个数据元素第一个数据元素 ( (无前驱无前驱) ) 根结点根结点 ( (无前驱无前驱) )最后最后一个一个数据元素数据元素 (无后继无后继)多个多个叶子结点叶子结点 ( (无后继无后继) )其它数据元素其它数据元素 ( (一个前驱、一个前驱、 一个一个后继后继) )其它数据元素其它数据元素 ( (一个前驱、一个前驱、 多个多个后继后继) )对比对比树型结构树型结构和和线性结构线性结构的结构特点的结构特点结点的度结点的度结点所拥有的子树的数目。叶子结点叶子结点度为零的结点。度不为零的结点。孩子结点孩子结点结

5、点的子树的根称为结点的孩子。分枝结点分枝结点3.3.树的相关术语树的相关术语DHIJM双亲双亲结点是其孩子的双亲。祖先祖先从树根到双亲的所有结点称为该结点的祖先。子孙子孙以结点为根的子树的所有结点称为该结点的子孙。兄弟兄弟同一父母的所有孩子互称兄弟。层次（层次（level） 树根为第一层，其孩子为第二层，孙子为第三层，以此类推。DHIJM有序树有序树结点各子树从左至右是有秩序的树称为有序树。无序树无序树结点各子树没有秩序的树称为无序树。深度深度树中结点的最大层次称为树的深度。DHIJM树的结点数树的结点数n和分支数和分支数b的关系是的关系是:abcdefghijb=n-1任何一棵非空树是一个二

6、元组任何一棵非空树是一个二元组 Tree = (root,F)其中其中:root 被称为根结点被称为根结点 F 被称为子树森林被称为子树森林森林森林(forest):是是m(m0)棵互不棵互不相交的树的集合相交的树的集合ArootBCDEFGHIJMKLF二叉树二叉树1 二叉树的定义与基本操作二叉树的定义与基本操作定义定义： 满足以下两个条件的树称做二叉树满足以下两个条件的树称做二叉树(Binary Tree): （1）每个结点的度都不大于）每个结点的度都不大于2；（2）每个结点的孩子结点次序不能任意颠倒。）每个结点的孩子结点次序不能任意颠倒。 二叉树或为空树空树, 或是由一个根结点根结点加上

7、两两棵棵分别称为左子树左子树和右子树右子树的、互不交的互不交的二叉二叉树树组成。注意注意:二叉树是有序树有序树,它的子树有左右之分。二叉树的度数不超过二二叉树的度数不超过二,但度数不超过二的树但度数不超过二的树未必是二叉树。未必是二叉树。ABCDEFGHK根结点左子树左子树右子树右子树二叉树的五种基本形态二叉树的五种基本形态:N空树空树只含根结点只含根结点NNNLRR右子树为空树右子树为空树L左子树为空树左子树为空树左右子左右子树均非树均非空树空树用归纳法证明用归纳法证明: 归纳基归纳基: 归纳假设归纳假设: 归纳证明归纳证明:i = 1 层时层时,只有一个根结点只有一个根结点: 2i-1 =

8、 20 = 1 命题成立命题成立;假设假设 i-1 命题成立命题成立,即即: 第第i-1层至多有结点层至多有结点= 2i-1-1 = 2i-2 个个; 二叉树每个结点至多有两棵子树二叉树每个结点至多有两棵子树,则则第第i 层至多有结点层至多有结点 = 2i-2 2 = 2i-1 个。个。2 二叉树的重要特性二叉树的重要特性性质性质1 :二叉树第二叉树第 i 层上至多有层上至多有2i-1 个结点。个结点。证明证明: 基于性质基于性质1, 深度为深度为 k 的二叉树上的结点总数的的二叉树上的结点总数的最大值是将二叉树每层上结点的最大值相加，所以最大值是将二叉树每层上结点的最大值相加，所以深度为深度

9、为 k 的二叉树上含的二叉树上含 结点数至多为：结点数至多为： 20+21+ +2k-1 = 2k-1 性质性质 2 : 深度为深度为 k 的二叉树上至多含的二叉树上至多含 2k-1 个结点个结点(k1)。证明证明:设设 二叉树上结点总数：二叉树上结点总数： n = n0 + n1 + n2再根据树的性质：再根据树的性质： b = n-1 = n0 + n1 + n2 - 1由有二叉树分支总数：由有二叉树分支总数： b = n1+2n2两式右边相等得两式右边相等得: n0 = n2 + 1 。性质性质 3 : 对任何一棵二叉树对任何一棵二叉树,若它含有若它含有n0 个叶子结点、个叶子结点、n2

10、 个个度为度为 2 的结点的结点, 则必存在关系式则必存在关系式:n0 = n2+1。也可以用归纳法证明也可以用归纳法证明两类两类特殊特殊的二叉树的二叉树满二叉树满二叉树完全二叉树完全二叉树 满二叉树 在一个二叉树中，若第i层的结点数为2i-1，则称此层的结点数是满的，当树中的每一层都是满的，则称此二叉树为满二叉树。 即如果一个二叉树中，除最下一层的各结点度数为0以外，其它各层结点的度数均等于2，则此二叉树为满二叉树。 满二叉树的第一层有一个结点（即根结点），第二层有两个结点，依此类推。每一层的结点数都是上一层结点数的二倍。所以，在满二叉树的第i层共有2i-1个结点（i1），一个深度为h的满二

11、叉树的结点总数为2h-1。满二叉树满二叉树: 深度为深度为 k 且含有且含有2k-1个结点的二叉树。可从根个结点的二叉树。可从根起按层自上到下从左至右对结点连续编号。起按层自上到下从左至右对结点连续编号。123456789 10 11 12 13 14 15 完全二叉树 如果一个二叉树各层都是“满”的，只是最下面一层从右边起连续缺n个结点，这种二叉树叫做完全二叉树。 例如上图的满二叉树，如果缺少从第11号至第15号结点，就是一个完全二叉树。 设完全二叉树的结点数为n，它与树的深度之间的关系为： 2h-1-11，则其父结点编号为 。 2) 如果2in，则其左儿子结点编号为2i；若2in，则无左儿

12、子结点。 3) 如果（2i+1）n，则其右儿子结点编号为（2i+1）；反之，则无右儿子结点。2/ i完全二叉树完全二叉树: 树中所含的树中所含的 n 个结点和满二叉树中个结点和满二叉树中编号为编号为 1 至至 n 的结点的结点一一对应。一一对应。abcdefghij 性质性质 4 : 具有具有 n 个结点的完全二叉树的深度为个结点的完全二叉树的深度为 log2n +1 。证明证明: 设完全二叉树的深度为设完全二叉树的深度为 k 则根据性质则根据性质2得得 2k-1 -1 n 2k -1 则则 2k-1 n 2k 即即 k-1 log2 n 1 ,分两种情况讨论分两种情况讨论: (1) 设第设第

13、k (1k log2n )层第层第1个结点为个结点为 i,则则 i=2k-1其左其左孩子必为第孩子必为第k+1层第层第1个结点个结点,编号为编号为2k =2i,若若2in则无则无左孩子左孩子;其右孩子必为第其右孩子必为第k+1层第层第2个结点个结点, 编号为编号为2i+1,若若2i+1n 则无右孩子。则无右孩子。 (2) 设第设第k (1k log2n )层某个结点为层某个结点为i (2k-1i data); -data); /访问根结点访问根结点 PreOrderPreOrder(bt-LChild(bt-LChild); ); /遍历左子树遍历左子树 PreOrderPreOrder(bt

14、-RChild(bt-RChild); ); /遍历右子树遍历右子树 2) 2) 中序遍历中序遍历void void InOrderInOrder(BiTree bt(BiTree bt) ) / /* *中序遍历根指针为中序遍历根指针为btbt的二叉树的二叉树* */ / if(bt if(bt!=NULL)!=NULL) InOrderInOrder(bt-LChild(bt-LChild); ); /遍历左子树遍历左子树Visit(btVisit(bt-data); -data); /访问根结点访问根结点InOrderInOrder(bt-RChild(bt-RChild); ); /遍

15、历右子树遍历右子树 3) 3) 后序遍历后序遍历void void PostOrderPostOrder(BiTree bt(BiTree bt) ) / /* * 后序遍历根指针为后序遍历根指针为btbt的二叉树的二叉树 * */ / if(bt if(bt!=NULL)!=NULL) PostOrderPostOrder(bt-LChild(bt-LChild); ); /遍历左子树遍历左子树PostOrderPostOrder(bt-RChild(bt-RChild); ); /遍历右子树遍历右子树Visit(btVisit(bt-data); -data); /访问根结点访问根结点 按

16、层次遍历的算法按层次遍历的算法LevelOrderTraverse(BiTree T) if (T) InitQueue(Q); EnQueue(Q, T); /根结点的指针T入队列 while ( ! QueueEmpty (Q) ) DeQueue(Q, p); /从队头取一个指针 Visit(p-data); if (p-lchild) EnQueue(Q, p-lchild); if (p-rchild) EnQueue(Q, p-rchild); /LevelOrderTraverseAB CD ETEABCD 利用遍历结果确定二叉树问题 先序序列+中序序列 中序序列+后序序列 先序

17、序列+后序序列 (x) 利用遍历结果确定二叉树问题思考：层序+先序/中序/后序 能否确定？如何做？ 仅知二叉树的先序序列仅知二叉树的先序序列 abcdefgabcdefg 不能唯一不能唯一确定一棵二叉树确定一棵二叉树, ,如果如果同时同时已知二叉树的中序序已知二叉树的中序序列列 cbdaegfcbdaegf,则会如何？则会如何？ 由先序和中序序列确定由先序和中序序列确定二叉树树二叉树的先序序列二叉树的先序序列二叉树的中序序列二叉树的中序序列 左子树左子树左子树左子树 右子树右子树右子树右子树根根根根a b c d e f gc b d a e g f例如例如: :aab bccddeeffgg

18、abcdefg先序序列中序序列四四、遍历算法的应用举例遍历算法的应用举例1、统计二叉树中叶子结点的个数、统计二叉树中叶子结点的个数 (先序遍历先序遍历)2、求二叉树的深度、求二叉树的深度(后序遍历后序遍历)1、统计二叉树中叶子结点的个数、统计二叉树中叶子结点的个数算法基本思想算法基本思想: : 先序(或中序或后序)遍历二叉树,在遍历过程中查找叶子结点,并计数。因此需在遍历算法中增添一个“计数计数”的参的参数数, ,并将算法中“访问结点”的操作改为:若是叶子若是叶子, ,则计数器增则计数器增1 1。练习：练习：/ /* * LeafCount LeafCount保存叶子结点数目的全局变量保存叶子

19、结点数目的全局变量, ,调用之调用之前初始化值为前初始化值为0 0 * */ /void leaf(BiTreevoid leaf(BiTree root) root) if(root if(root!=NULL)!=NULL) leaf(root-LChild leaf(root-LChild);); leaf(root-RChild leaf(root-RChild);); if(root-LChild=NULL&root-RChild if(root-LChild=NULL&root-RChild=NULL)=NULL) LeafCount LeafCount+;+; 2

20、、求二叉树的深度、求二叉树的深度(后序遍历后序遍历)算法基本思想算法基本思想: : 从二叉树深度的定义可知从二叉树深度的定义可知,二叉树的深度二叉树的深度应为其左、右子树深度的最大值加应为其左、右子树深度的最大值加1。按后序。按后序遍历编写遍历编写深度函数深度函数, 先分别求得左、右子树的先分别求得左、右子树的深度深度,再将其中再将其中访问结点访问结点的操作改为的操作改为: 深度深度=左、右子树深度最大值左、右子树深度最大值+1 首先分析二叉树的深度和它的左、右子首先分析二叉树的深度和它的左、右子树深度之间的关系。树深度之间的关系。练习：练习：int PostDepth(BiTree btin

21、t PostDepth(BiTree bt) ) int int hl,hr,max; hl,hr,max; if(bt if(bt=NULL) return(0=NULL) return(0); /); /空树返回空树返回0 0 hl=PostDepth(bt-LChild hl=PostDepth(bt-LChild);/);/求左子树的深度求左子树的深度 hr=PostDepth(bt-RChildhr=PostDepth(bt-RChild);/);/求右子树的深度求右子树的深度 max=hlhr?hl:hrmax=hlhr?hl:hr; /; /求左右子树深度较大者求左右子树深度较大

22、者 return(max+1); / return(max+1); / 返回树的深度返回树的深度 后序遍历求二叉树的深度后序遍历求二叉树的深度abcdef 基本概念基本概念 如何对二叉树线索化？如何对二叉树线索化？ 查找结点查找结点p p的前驱的前驱 / /后继结点后继结点 线索链表的遍历算法线索链表的遍历算法6.5 线索二叉树线索二叉树一、一、基本概念基本概念遍历二叉树的结果是得到结点线性序列。遍历二叉树的结果是得到结点线性序列。例如:先序先序序列序列: : A B C D E F G H K中序中序序列序列: : B D C A H G K F E后序后序序列序列: : D C B H K

23、 G F E A可用结点中可用结点中空指针域空指针域指向线性序列中的指向线性序列中的“前驱前驱”和和“后继后继”ABCDEFGHK练习：练习：与其相应的二叉树,称作 “线索二叉树线索二叉树”包含 “线索” 的存储结构,称作 “线索链表线索链表”先序先序序列:A B C D E F G H K D C B E D 利用结点中存储null的指针域指针域指向该线性序列中的“前驱”和“后继”, 该指针指针称作“线索线索”。二叉树中存null的指针域共有结点数+1个Ltag=0 LChild域指向其左子树域指向其左子树(指针指针 Link) Ltag=1 LChild域指向其域指向其“前驱前驱” (线索

24、线索 Thread) Rtag=0 RChild域指向其右子树域指向其右子树(指针指针 Link) Rtag=1 RChild域指向其域指向其“后继后继”(线索线索 Thread) 如此定义的二叉树的存储结构构成一个链表如此定义的二叉树的存储结构构成一个链表,该链表称作该链表称作“线索链表线索链表”。LChildLtagDataRtagRChild 为了区分孩子结点和前驱、后继结点，为结为了区分孩子结点和前驱、后继结点，为结点结构增设两个标志域，如下图所示：点结构增设两个标志域，如下图所示： 在中序遍历过程中修改当前结点的在中序遍历过程中修改当前结点的左、右空指针域左、右空指针域,以保存该结点

25、的以保存该结点的“前驱前驱”和和“后继后继”信息。此过程称为对二叉树信息。此过程称为对二叉树的线索化。遍历过程中的线索化。遍历过程中, 附设指针附设指针p指向指向当前访问的结点当前访问的结点, 指针指针pre指向它的前驱。指向它的前驱。二、如何对二叉树线索化？二、如何对二叉树线索化？ABCDEnullnull中序序列： BDAECvoid Inthread(BiTree btvoid Inthread(BiTree bt) ) /对对btbt进行中序线索化进行中序线索化/公有变量公有变量prepre始终指向刚访问过的结点始终指向刚访问过的结点, ,初值为初值为NULLNULL if(bt if

26、(bt!=NULL)!=NULL) Inthread(bt-LChild Inthread(bt-LChild); ); /线索化左子树线索化左子树 if(bt-LChildif(bt-LChild=NULL)=NULL) bt-Ltag=1; bt-LChile bt-Ltag=1; bt-LChile=pre; =pre; /置前驱线索置前驱线索 if(pre!=NULL & pre-RChildif(pre!=NULL & pre-RChild=NULL)=NULL) pre-Rtag=1; pre-RChild=bt pre-Rtag=1; pre-RChild=bt;

27、/置后继线索置后继线索 pre=btpre=bt； Inthread(bt-RChildInthread(bt-RChild); ); /线索化右子树线索化右子树 （1）中序线索二叉树）中序线索二叉树 p的后继 若p-RTag=1，则p-rchild即为所求； 若p-RTag=0，则从其右子沿着左链走到LTag=1 的那个结点就是。 p的前驱 若p-LTag=1，则p-lchild即为所求； 若p-LTag=0，则从其左子沿着右链走到RTag=1 的那个结点就是。pL D RLDRLDR三、查找结点三、查找结点p的前驱的前驱 /后继结后继结点点（2）后序线索二叉树）后序线索二叉树 p的前驱 若

28、p-LTag=1，则p-lchild即为所求； 若p-LTag=0， 则若p-RTag=0， 则p-rchild即为所求 若p-RTag=1， 则p-lchild即为所求 p的后继 与双亲结点有关，因二叉链表中没有指向双亲结点的指针，就可能需通过二叉树的后序遍历才可确定，因而后序线索二叉树在此问题上并不比普通二叉树有效。（3）先序线索二叉树）先序线索二叉树 与后序线索二叉树对偶p中序线索二叉树可以方便地查找一个结点的前驱中序线索二叉树可以方便地查找一个结点的前驱/ /后继结点。后继结点。L R DLRD四、线索链表的遍历算法四、线索链表的遍历算法 由于在线索链表中添加了遍历中得到的由于在线索链

29、表中添加了遍历中得到的“前驱前驱”和和“后继后继”的信息的信息,从而简化了遍历从而简化了遍历的算法。的算法。 在线索树上遍历在线索树上遍历,只要先找到第一个结点只要先找到第一个结点,然后依次找结点的后继直到后继为空时为止。然后依次找结点的后继直到后继为空时为止。例如例如: 对中序线索化链表的遍历算法对中序线索化链表的遍历算法 中序遍历的第一个结点中序遍历的第一个结点 在中序线索化链表中结点的后继在中序线索化链表中结点的后继左子树上处于左子树上处于最左下最左下(ltag=1无左子树无左子树)的结点。的结点。若若 rtag=1 无右子树无右子树, 则为则为后继线索所指结点后继线索所指结点;否则为否

30、则为对其右子树进行中序遍历时的第一个结点。对其右子树进行中序遍历时的第一个结点。 0 A A 0 0 B B 1 1 C C 1 1 D D 0 1 E E 1 bt遍历中序线索树遍历中序线索树6.6树和森林树和森林 树转换为二叉树树转换为二叉树 1)在兄弟间加一连线 2)对每一结点，去掉它与孩子的连线(最左子除外) 3)以根为轴心将整棵树顺时针转450 A B C DE F G*ABECFDG特点：无右子树左支是孩子右支是兄弟数据结构-第六章 树和二叉树66森林转换为二叉树森林转换为二叉树 1)先将森林里的每一棵树转换成一棵二叉树 2)从最后一棵树开始，把后一棵树的作为前一棵树的根的右子 A

31、 E G B C D F H I 二叉树转换为树二叉树转换为树/森林森林 ABEC F G D HI6.7树和森林的遍历树和森林的遍历一、树的遍历一、树的遍历: 有两种搜索路径有两种搜索路径先根先根(次序次序)遍历遍历:后根后根(次序次序)遍历遍历: 若树不空若树不空,则先访问根结点则先访问根结点,然后依次先根然后依次先根遍历各棵子树。遍历各棵子树。 若树不空若树不空,则先依次后根遍历各棵子树则先依次后根遍历各棵子树,然然后访问根结点。后访问根结点。ABCDFGEIHJ 先根遍历时顶点的先根遍历时顶点的访问次序访问次序:A B E H I J C D F G 后根遍历时顶点的后根遍历时顶点的访

32、问次序访问次序:H I J E B C F G D AABECDGHIJF 后根遍历对应二叉后根遍历对应二叉树中序访问次序树中序访问次序:H I J E B C F G D AABCDFGEIHJ1森林中第一棵树森林中第一棵树的根结点的根结点; ;2森林中第一棵森林中第一棵树的子树森林树的子树森林; ;3森林中其它树构森林中其它树构成的森林。成的森林。森林由三部分构成森林由三部分构成: B C D E F GH I J1. 先序遍历先序遍历:二、二、森林的遍历森林的遍历 若森林不空若森林不空,则则访问访问森林中第一棵树的根结点森林中第一棵树的根结点;先序遍历先序遍历森林中第一棵树的子树森林森林

33、中第一棵树的子树森林;先序遍历先序遍历森林中森林中(除第一棵树之外除第一棵树之外)其其 余树构成的森林。余树构成的森林。即即:依次从左至右依次从左至右对森林中的对森林中的 每一棵树每一棵树进行进行先根遍历先根遍历。. 中序遍历中序遍历: 若森林不空若森林不空,则则中序遍历中序遍历森林中第一棵树的子树森林森林中第一棵树的子树森林;访问访问森林中第一棵树的根结点森林中第一棵树的根结点;中序遍历中序遍历森林中森林中(除第一棵树之外除第一棵树之外)其其 余树构成的森林。余树构成的森林。即即:依次从左至右依次从左至右对森林中的对森林中的 每一棵树每一棵树进行进行后根遍历后根遍历。3. 后序遍历后序遍历:

34、 若森林不空若森林不空,则则后序遍历后序遍历森林中第一棵树的子树森林森林中第一棵树的子树森林;后序遍历后序遍历森林中森林中(除第一棵树之外除第一棵树之外)其其 余树构成的森林。余树构成的森林。访问访问森林中第一棵树的根结点森林中第一棵树的根结点;先序遍历先序遍历森林森林的访问次序的访问次序:A B C D E F G H I J中序遍历中序遍历森林森林的访问次序的访问次序:B C D A F E I H J G A E GB C D F H J IAEBCDFGHJI后序遍历后序遍历森林森林的访问次序的访问次序:D C B F I J H G E A 树和森林的遍历和二叉树和森林的遍历和二叉树

35、遍历的对应关系树遍历的对应关系 ？先根遍历先根遍历后根遍历后根遍历树树二叉树二叉树森林森林先序遍历先序遍历先序遍历先序遍历中序遍历中序遍历中序遍历中序遍历后序遍历后序遍历后序遍历后序遍历6.8树的存储结构树的存储结构树的存储结构树的存储结构多重链表表示法多重链表表示法 结点结构 data child1 child2 childm 数据域 指针域 (m: 树的度)#define TREE_DEGREE 100typedef struct MultiTNode TElemType data; struct MultiTNode * ptrTREE_DEGREEMultiTNode, * Multi

36、Tree;双亲表示法双亲表示法 用顺序存储（一维数组）存储树的信息 结点序号 data parent 0 A -1 1 B 0 2 C 0 3 D 2 4 E 2 5 F 20 A1 B 2 C3 D 4 E 5 F#define MAX_TREE_SIZE 100typedef struct PTNode TElemType data; int parent;PTNode;typedef struct PTNode nodesMAX_TREE_SIZE; int r, n; /根的位置和结点数PTree;孩子链表表示法孩子链表表示法 顺序（一维数组）+单链表 结点下标 data firstc

37、hild 0 A 1 2 1 B 2 C 3 4 5 3 D 4 E 5 F #define MAX_TREE_SIZE 100typedef struct CTNode /孩子结点 int child; struct CTNode * next；CTNode, * ChildPtr;typedef struct /向量结点 TElemType data; ChildPtr firstchild;CTBox; typedef struct CTBox nodesMAX_TREE_SIZE; int r, n; /根的位置和结点数CTree;0 A1 B 2 C3 D 4 E 5 F结点结构 f

38、ch data nsib fch: 指向该结点的第一个孩子结点 nsib: 指向该结点的下一个兄弟结点孩子兄弟表示法孩子兄弟表示法(二叉链表表示法二叉链表表示法) A B C D E FTA BC D E F 访问某个结点的所有孩子结点访问某个结点的所有孩子结点：从fch链找到第一个孩子，沿第一 个孩子的nsib链找第二个孩子， ，直至nsib链为空。typedef struct CSNode TElemType data; struct CSNode * fch,*nsib;CSNode, * CSTree ;带右链的先根序表示法带右链的先根序表示法主体顺序按树的先根序遍历，右链指向兄弟。带

39、左链的层次序列表示法带左链的层次序列表示法A B E C D F G0 4 0 5 0 7 01 2 3 4 5 6 7A B C D E F G2 5 0 6 0 0 01 2 3 4 5 6 7主体顺序按树的层次遍历，左链指向孩子。ABCEFGD6.9 哈夫曼树与哈夫曼树与 哈夫曼编码哈夫曼编码 电文的字符集电文的字符集(a,b,c,d,e),它们在电文中出现它们在电文中出现的频度分别为的频度分别为(5,6,2,9,7)。问：如何对字符集编码，使得问：如何对字符集编码，使得译码时不会错译码时不会错电文总长最短？电文总长最短？ 例：电文字符编码例：电文字符编码9527166713290000

40、111100b01e10d110a111c 编码编码:右分支右分支:1左分支左分支:0得到各叶结得到各叶结点的点的编码表编码表 叶结点代表叶结点代表 (a,b,c,d,e), 权值为权值为(5,6,2,9,7);建立建立哈文曼编码，如上图。比如：电文哈文曼编码，如上图。比如：电文dadebedbca的码文的码文:10110100100011000111110。 最优前缀编码不等长但译码时不会错最优前缀编码不等长但译码时不会错电文总长最短。电文总长最短。哈夫曼编码哈夫曼编码树的路径长度树的路径长度定义为：定义为： PL=树中每个结点的路径长度之和。树中每个结点的路径长度之和。 结点的路径长度结点

41、的路径长度定义为：定义为： 从根结点到该结点的路径上分支的数目。从根结点到该结点的路径上分支的数目。结点带权路径长度结点带权路径长度定义为：定义为： 结点的路径长度与该结点权值结点的路径长度与该结点权值(正数正数)的乘积。的乘积。树的带权路径长度树的带权路径长度定义为：定义为： 树中所有树中所有叶子结点叶子结点的带权路径长度的带权路径长度之和即之和即结点到根的路径长度权值其中：记作：kknkkklwlwwpl1术语术语最优树：最优树：由给定的n 个带权叶子结点所构成的所有 m 叉树中，必存在一棵其带权路径长度取最带权路径长度取最小值小值的树，称为“最优树最优树”。最优二叉树最优二叉树(哈夫曼树

42、哈夫曼树)：带权路径长度带权路径长度WPL最最小的二叉树。小的二叉树。 显然显然, 在最优二叉树中没有度数为在最优二叉树中没有度数为 1的结点的结点; 再根据二叉树性质：再根据二叉树性质：任何二叉树任何二叉树, 若它含若它含n0 个叶个叶结点、结点、n2 个度为个度为 2 的结点的结点, 则必存在关系式：则必存在关系式： n0 = n2+1。 由此得出结论：由此得出结论：含含 n个叶子结个叶子结点的最优二叉树的总结点数为点的最优二叉树的总结点数为 2* *n- -1 。例例 有4个结点，权值分别为7，5，2，4，构造有4个 叶子结点的二叉树。abcd7524dcab2475abcd7524WP

43、L=7*2+5*2+2*2+4*2=36WPL=7*3+5*3+2*1+4*2=46WPL=7*1+5*2+2*3+4*3=35基本思想基本思想 使权值大的结点靠近根结点。 (1)根据给定的根据给定的 n 个权值个权值 w1, w2, , wn ,构造构造 n 棵二叉树的集合棵二叉树的集合 F = T1, T2, , Tn， 其中每棵二叉树中均只含一个带权值为其中每棵二叉树中均只含一个带权值为 wi 的根结点，其左、右子树为空树；的根结点，其左、右子树为空树；如何构造最优二叉树如何构造最优二叉树(哈夫曼树哈夫曼树) (哈夫曼算法哈夫曼算法) ： 在在 F 中选取其根结点的权值为最小的两棵中选取

44、其根结点的权值为最小的两棵二叉树二叉树,分别作为左、右子树构造一棵新的二分别作为左、右子树构造一棵新的二叉树叉树,并置这棵新的二叉树根结点的权值为其并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和；左、右子树根结点的权值之和；(2)从从F中删去这两棵树中删去这两棵树,并加入刚生成的新树；并加入刚生成的新树； 重复重复 (2) 和和 (3) ,直至直至 F 中只含一棵树为止。中只含一棵树为止。(3)(4)87 14142935 111123111100010001108 815151919292942425858100100例例例例 w=5, 29, 7, 8, 14, 23, 3, 1151429 7823 3111429 7823 1135887151429233581111358191429238715113581929 2314871529291487152911358