1、第六章第六章树和二叉树树和二叉树16.6 6.6 赫夫曼树及其应用赫夫曼树及其应用6.1 6.1 树的定义和基本术语树的定义和基本术语6.2 6.2 二叉树二叉树6.3 6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树6.4 6.4 树和森林树和森林 2 6.4 6.4 树和森林树和森林6.4.1 6.4.1 树的存储结构树的存储结构6.4.2 6.4.2 森林与二叉树的转换森林与二叉树的转换6.4.3 6.4.3 树和森林的遍历树和森林的遍历36.4.1 6.4.1 树的存储结构树的存储结构一、一、双亲表示法双亲表示法二、二、孩子链表表示法孩子链表表示法三、三、孩子兄弟存储表示法孩子兄弟
2、存储表示法4ABCDEFGr=0n=70 A -11 B 02 C 03 D 04 E 2 5 F 26 G 5data parent一、双亲表示法一、双亲表示法:5 typedef struct PTNode ElemType data;int parent;/双亲位置域 PTNode;data parent#define MAX_TREE_SIZE 100结点结构结点结构:C语言的类型描述语言的类型描述:6typedef struct PTNode nodes MAX_TREE_SIZE;int r,n;/根结点的位置和结点个数 PTree;树结构树结构:7 data child1chil
3、d2child3childd二、孩子二、孩子(链表链表)表示法表示法:其中其中d d是结点的度是结点的度;由于每个结点的子女个数是不限由于每个结点的子女个数是不限制的制的,则如按照度最大的结点的度分配则如按照度最大的结点的度分配子女指针的个数子女指针的个数,则在实际应用中则在实际应用中,会有会有很多空指针域很多空指针域,造成空间的浪费。造成空间的浪费。8r=0n=7 data firstchildABCDEFG0 A -11 B 02 C 03 D 04 E 25 F 26 G 464 5 1 2 39typedef struct CTNode int child;struct CTNode*
4、next;*ChildPtr;孩子结点结构孩子结点结构:child nextC语言的类型描述语言的类型描述:10 typedef struct ElemType data;ChildPtr firstchild;/孩子链的头指针 CTBox;双亲结点结构双亲结点结构 data firstchild11typedef struct CTBox nodesMAX_TREE_SIZE;int n,r;/结点数和根结点的位置 CTree;树结构树结构:12ABCDEFGroot AB C E D F G AB C E D F G 三、树的孩子三、树的孩子-兄弟兄弟(二叉链表二叉链表)表示法表示法131
5、4typedef struct CSNode ElemType data;struct CSNode *firstchild,*nextsibling;CSNode,*CSTree;C语言的类型描述语言的类型描述:结点结构结点结构:firstchild data nextsibling15 6.4.26.4.2 森林与二叉树的转换森林与二叉树的转换设设森林森林 F=(T1,T2,Tn);T1=(root，t11,t12,t1m);二叉树二叉树 B=(LBT,Node(root),RBT);16由森林转换成二叉树由森林转换成二叉树的转换规则为:若 F=，则 B=;由 ROOT(T1)对应得到No
6、de(root);否则，由(t11,t12,t1m)对应得到 LBT;由(T2,T3,Tn)对应得到 RBT。17T1T11,T12,T1mT2,TnLBTRBTroot1819T1 T2 T3T1 T2 T3AFBCDEGHIKJAFHBC DGIJEK3 棵树的森林各棵树的二叉树表示ABCEDHIKJFG森林的二叉树表示20由二叉树转换为森林由二叉树转换为森林的转换规则为:由LBT 对应得到(t11,t12,，t1m);若 B=,则 F=;否则，由 Node(root)对应得到 ROOT(T1);由RBT 对应得到(T2,T3,Tn)。21 22 T1 T2 T3AFHBCDGIJEK3
7、棵树的森林ABCEDHIKJFG森林的二叉树表示23 由此，树和森林的各种操作均可与二叉树的各种操作相对应。应当注意的是，应当注意的是，和树对应的二叉树，其左、右子树的概念已改变为：左是孩子，右是兄弟左是孩子，右是兄弟246.4.36.4.3树和森林的遍历树和森林的遍历25一、树的遍历一、树的遍历二、森林的遍历二、森林的遍历26树的遍历树的遍历:先根先根(次序次序)遍历遍历:后根后根(次序次序)遍历遍历:若树不空，则先访问根结点，然后若树不空，则先访问根结点，然后依次按依次按各棵子树。各棵子树。若树不空，则先依次按若树不空，则先依次按各各棵子树，然后访问根结点。棵子树，然后访问根结点。27 A
8、 B C DE F G H I J K 先根遍历时结点的先根遍历时结点的访问次序：访问次序：A B E F C D G H I J K 后根遍历时结点的后根遍历时结点的访问次序：访问次序：E F B C I J K H G D A28 B C DE F G H I J K1.森林中第一棵树的根结点；2.森林中第一棵树的子树森林；3.森林中其它树构成的森林。可以分解成三部分：森林森林29 若森林不空，则访问访问森林中第一棵树的根结点;先序遍历先序遍历森林中第一棵树的子树森林;先序遍历先序遍历森林中(除第一棵树之外)其 余树构成的森林。先序遍历先序遍历森林的遍历森林的遍历即：依次从左至右依次从左至
9、右对森林中的每一棵树树进行先根遍历先根遍历。30 中序遍历中序遍历 若森林不空，则中序遍历中序遍历森林中第一棵树的子树森林;访问访问森林中第一棵树的根结点;中序遍历中序遍历森林中(除第一棵树之外)其 余树构成的森林。即：依次从左至右依次从左至右对森林中的每一棵树树进行后根遍历后根遍历。31 树的遍历和二叉树遍历树的遍历和二叉树遍历的对应关系的对应关系？先根遍历先根遍历后根遍历后根遍历树树二叉树二叉树森林森林先序遍历先序遍历先序遍历先序遍历中序遍历中序遍历中序遍历中序遍历32设树的存储结构为孩子兄弟链表设树的存储结构为孩子兄弟链表typedef struct CSNode ElemType da
10、ta;struct CSNode*firstchild,*nextsibling;CSNode,*CSTree;一、求树的深度一、求树的深度二、输出树中所有从根到叶子的路径二、输出树中所有从根到叶子的路径三、建树的存储结构三、建树的存储结构33Int Depth(CSTree T)If(T=NULL)return 0;ElseD1=Depth(T-firstchild);D2=Depth(T-nextsibling);Return Maxd1+1,d234int TreeDepth(CTree T)/T 是树的孩子链表存储结构，/返回该树的深度 if(T.n=0)return 0;else r
11、eturn Depth(T,T.r);/TreeDepth一、求树的深度的算法：一、求树的深度的算法：35int Depth(CTree T,int root)max=0;p=T.nodesroot.firstchild;while(p)h=Depth(T,p-child);if(h max)max=h;p=p-nextchild;/while return max+1;36二、二、输出树中所有从根到叶子的路径的算法输出树中所有从根到叶子的路径的算法:A B C DE F G H I J K例如：对左图所示的树，其输出结果应为：A B EA B FA CA D G H IA D G H JA
12、D G H K37void AllPath(BiTree T,Stack&S)if(T)Push(S,T-data);if(!T-Lchild&!T-Rchild)PrintStack(S);else AllPath(T-Lchild,S);AllPath(T-Rchild,S);Pop(S);/if(T)/AllPath/输出二叉树上从根到所有叶子结点的路径输出二叉树上从根到所有叶子结点的路径38void OutPath(Bitree T,Stack&S)while(!T)Push(S,T-data);if(!T-firstchild)Printstack(S);else OutPath(T
13、-firstchild,S);Pop(S);T=T-nextsibling;/while/OutPath/输出森林中所有从根到叶的路径3940三、建树的存储结构的算法三、建树的存储结构的算法:和二叉树类似，不同的定义相应有不同的算法。假设以二元组(F,C)的形式自上而下自上而下、自左而右自左而右依次输入树的各边，建立树的孩子孩子-兄弟链表兄弟链表。41ABCDEFG例如例如:对下列所示树的输入序列应为:(#,A)(A,B)(A,C)(A,D)(C,E)(C,F)(E,G)ABCD(#,A)(A,B)(A,C)(A,D)(C,E)可见，算法中需要一个队列队列保存已建好的结点的指针指针42void
14、 CreatTree(CSTree&T)T=NULL;for(scanf(&fa,&ch);ch!=;scanf(&fa,&ch);)p=GetTreeNode(ch);/创建结点EnQueue(Q,p);/指针入队列if(fa=)T=p;/所建为根结点 else /非根结点的情况 /for/CreateTree 43GetHead(Q,s);/取队列头元素(指针值)while(s-data!=fa)/查询双亲结点 DeQueue(Q,s);GetHead(Q,s);if(!(s-firstchild)s-firstchild=p;r=p;/链接第一个孩子结点else r-nextsiblin
15、g=p;r=p;/链接其它孩子结点 446.6 6.6 赫夫曼树及其应用赫夫曼树及其应用 6.6.2 赫夫曼编码赫夫曼编码6.6.1 最优二叉树最优二叉树(赫夫曼树赫夫曼树)45 6.6.1 最优二叉树（赫夫曼树）最优二叉树（赫夫曼树）树的路径长度树的路径长度定义为：从树根到每个结点的路径长度之和。路径长度路径长度定义为：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目叫做路径长度路径长度。46 树的带权路径长度树的带权路径长度定义为：WPL(T)=wklk(对所有叶子结点)在所有含 n 个叶子结点、并带相同权值的二叉树中，必存在一棵其带权路径带权路径长度取最小值
16、长度取最小值的二叉树，称为最优二叉最优二叉树树或赫夫曼树赫夫曼树。例如：例如：4727 9 75492WPL(T)=72+52+23+43+92 =60WPL(T)=74+94+53+42+21 =89 544822244455577749 根据给定的根据给定的 n 个权值个权值 w1,w2,wn，构造构造 n 棵二叉树的集合棵二叉树的集合 F=T1,T2,Tn，其中每棵二叉树中均只含一个带权值其中每棵二叉树中均只含一个带权值 为为 wi 的根结点的根结点,其左、右子树为空树其左、右子树为空树;如何构造赫夫曼树如何构造赫夫曼树(1)50 在在 F 中选取其根结点的权值为最中选取其根结点的权值为
17、最 小的两棵二叉树，分别作为左、小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并右子树构造一棵新的二叉树，并 置这棵新的二叉树根结点的权值置这棵新的二叉树根结点的权值 为其左、右子树根结点的权值之为其左、右子树根结点的权值之 和和;(2)51 从从F中删去这两棵树，同时加入中删去这两棵树，同时加入 刚生成的新树刚生成的新树;重复重复(2)和和(3)两步，直至两步，直至 F 中只中只 含一棵树为止。含一棵树为止。(3)(4)这棵树便是赫夫曼树这棵树便是赫夫曼树529例如:已知权值 W=5,6,2,9,7 562752769767139527(1)(2)(3)536713952795271
18、66713(4)(3)54952716671329(5)55F:7 5 2 4F:7 5 67524初始合并2 4F:7 11 752475246611合并5 6F:18 5合并5 627461118566.6.2 赫夫曼编码赫夫曼编码 在电文传输中，需要将电文中出现的在电文传输中，需要将电文中出现的每个字符进行二进制编码。在设计编码时需每个字符进行二进制编码。在设计编码时需要遵守两个原则：要遵守两个原则：（1 1）发送方传输的二进制编码，到接收发送方传输的二进制编码，到接收方解码后必须具有唯一性，即解码结果与发方解码后必须具有唯一性，即解码结果与发送方发送的电文完全一样；送方发送的电文完全一
19、样；（2 2）发送的二进制编码尽可能地短。下发送的二进制编码尽可能地短。下面我们介绍两种编码的方式。面我们介绍两种编码的方式。571.等长编码 这种编码方式的特点是每个字符的编码长度相同（编码长度就是每个编码所含的二进制位数）。假设字符集只含有4个字符A，B，C，D，用二进制两位表示的编码分别为00，01，10，11。若现在有一段电文为：ABACCDA，则应发送二进制序列：00010010101100，总长度为14位。当接收方接收到这段电文后，将按两位一段进行译码。这种编码的特点是译码简单且具有唯一性，但编码长度并不是最短的。58 2.2.不等长编码不等长编码 在传送电文时，为了使其二进制位数
20、尽可能地在传送电文时，为了使其二进制位数尽可能地少，可以将每个字符的编码设计为不等长的，使用少，可以将每个字符的编码设计为不等长的，使用频度较高的字符分配一个相对比较短的编码，使用频度较高的字符分配一个相对比较短的编码，使用频度较低的字符分配一个比较长的编码。例如，可频度较低的字符分配一个比较长的编码。例如，可以为以为A A，B B，C C，D D四个字符分别分配四个字符分别分配0 0，0000，1 1，0101，并可将上述电文用二进制序列：并可将上述电文用二进制序列：000011010000011010发送，其发送，其长度只有长度只有9 9个二进制位，但随之带来了一个问题，个二进制位，但随之
21、带来了一个问题，接收方接到这段电文后无法进行译码，因为无法断接收方接到这段电文后无法进行译码，因为无法断定前面定前面4 4个个0 0是是4 4个个A A，1 1个个B B、2 2个个A A，还是，还是2 2个个B B，即译，即译码不唯一，因此这种编码方法不可使用。码不唯一，因此这种编码方法不可使用。59 前缀编码前缀编码:任何一个字符的编码任何一个字符的编码都不是另一个字符的编码的前缀都不是另一个字符的编码的前缀。利用赫夫曼树可以构造一种不等长利用赫夫曼树可以构造一种不等长的二进制编码，并且构造所得的的二进制编码，并且构造所得的赫夫赫夫曼编码曼编码是一种是一种最优前缀编码最优前缀编码，即使所，
22、即使所传传电文的总长度最短电文的总长度最短。60 主要用途是实现数据压缩。主要用途是实现数据压缩。设给出一段报文：设给出一段报文：CAST CAST SAT AT A TASA 字符集合是字符集合是 C,A,S,T，各个字符出现的频，各个字符出现的频度度(次数次数)是是 W 2,7,4,5。若给每个字符以等长编码若给每个字符以等长编码 A:00 T:10 C:01 S:11则总编码长度为则总编码长度为(2+7+4+5)*2=36.若按各个字符出现的概率不同而给予不等长编若按各个字符出现的概率不同而给予不等长编码，可望减少总编码长度。码，可望减少总编码长度。因各字符出现的概率为因各字符出现的概率
23、为 2/18,7/18,4/18,5/18。61629527166713290000111100011110010163typedef struct unsigned int weight;unsigned int parent,lchild,rchild;HTNode,*HuffmanTree;/动态分配数组存储赫夫曼树动态分配数组存储赫夫曼树typedef char *HuffmanCode;/动态分配数组存储赫夫曼编码表动态分配数组存储赫夫曼编码表/串数组类型串数组类型64void HuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int *w,in
24、t n)/W W存放存放n n个字符的权值个字符的权值,构造赫夫曼树构造赫夫曼树HTHT/并求出并求出n n个字符的赫夫曼编码个字符的赫夫曼编码HCHC HuffmanTree p;char*cd;int m,i,s1,s2,start;unsigned int c,f;if(n=1)return;/n为字符树木，为字符树木，m为结点树木为结点树木 m=2*n 1;HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);/0号单元未用号单元未用65 for(p=HT,i=1;i=n;+i,+p,+w)*p=*w,0,0,0;for(;i=m;+i,+p)*p=0,
25、0,0,0;for(i=n+1;i=m;+i)/建赫夫曼树建赫夫曼树 /在在HT1.i-1选择选择parent为为0且且weight最小的两个结点最小的两个结点,/其序号分别为其序号分别为s1和和s2。Select(HT,i-1,s1,s2);HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;66/从叶子到根逆向求赫夫曼编码 HC=(HuffmanCode)malloc(n+1)*sizeof(char*);cd=(char*)malloc(n*sizeof(ch
26、ar);cdn-1=0;for(i=1;i=n;+i)start=n 1;for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)if(HTf.lchild=c)cd-start=0;else cd-start=1;HCi=(char*)malloc(n-start)*sizeof(char);strcpy(HCi,&cdstart);printf(%sn,HCi);free(cd);/HuffmanCoding671.熟练掌握二叉树的结构特性二叉树的结构特性，了解相应的证明方法。2.熟悉二叉树的各种存储结构存储结构的特点及适用范围。3.遍历二叉树遍历二叉树是二叉
27、树各种操作的基础。实现二叉树遍历的具体算法与所采用的存储结构有关。掌握各种遍历策略的递归算递归算法法，灵活运用遍历算法灵活运用遍历算法实现二叉树的其它操作。层次遍历层次遍历是按另一种搜索策略进行的遍历。684.理解二叉树线索化的实质线索化的实质是建立结点与其在相应序列中的前驱或后继之间的直接联系，熟练掌握二叉树的线索线索化过程化过程。二叉树的线索化过程线索化过程是基于基于对二叉树进行遍历遍历，而线索二叉树上的线线索又为相应的遍历提供索又为相应的遍历提供了方便方便。695.熟悉树的树的各种存储结构存储结构及其特点，掌握树和森林与二叉树的转换树和森林与二叉树的转换方法。建立存储结构是进行其它操作的前提，因此读者应掌握掌握 1 至 2 种建立建立二叉树和树的存储存储结构的方法结构的方法。6.学会编写实现树的各种操作实现树的各种操作的算法。7.了解最优最优二叉树的特性树的特性，掌握建立建立最优最优二叉树和哈夫曼编码树和哈夫曼编码的方法。70本章作业本章作业 6.22,6.26 6.42,6.43 71
