第06章-树与二叉树C

第1章绪论第2章线性表第3章栈和队列

第4章串第5章数组和广义表第6章

树和二叉树

第7章图第9章查找第10章排序目录1

教

学

内

容1、树和森林的概念2、二叉树的定义、性质及运算；3、二叉树的存储结构4、遍历二叉树5、线索二叉树6、树、森林、森林与二叉树的转换7、哈夫曼树、哈夫曼编码2本周作业习题集第一次作业：6.7，6.8，6.15,6.16,6.29,6.42,6.45.第二次作业：6.26，6.27,6.29,6.44,6.47，6.656.树和森林树和森林与二叉树的转换树和森林的存储方式树和森林的遍历4方法：加线—抹线—旋转abeidfhgcabeidfhgc兄弟相连长兄为父孩子靠左树和森林与二叉树的转换回顾1：树如何转为二叉树？左孩子—右兄弟表示法5回顾2：二叉树怎样还原为树？abeidfhgc要点：逆操作，把所有右孩子变为兄弟！

abdefhgic6法一：①各森林先各自转为二叉树；②依次连到前一个二叉树的右子树上。讨论1：森林如何转为二叉树？即F={T1,T2,…,Tm}B={root,LB,RB}法二：森林直接变兄弟，再转为二叉树（参见教材P138图6.17，两种方法都有转换示意图）法一和法二得到的二叉树是完全相同的、惟一的。7ABCDEFGHJIABCDEFGHJIABCDEFGHJI森林转二叉树举例：

（用法二，森林直接变兄弟，再转为二叉树）兄弟相连长兄为父头树为根孩子靠左A8ABCDEFGHJI讨论2：二叉树如何还原为森林？要点：把最右边的子树变为森林，其余右子树变为兄弟

即B={root,LB,RB}F={T1,T2,…,Tm}ABCDEFGHJIEFABCDGHJI9树和森林的存储方式树有三种常用存储方式：①双亲表示法②孩子表示法③孩子—兄弟表示法

nextsiblingdatafirstchild指向左孩子指向右兄弟问：树→二叉树的“连线—抹线—旋转”如何由计算机自动实现？答：用“左孩子右兄弟”表示法来存储即可。

存储的过程就是树转换为二叉树的过程！10abecdfhgbacedfgh例如：11树和森林的遍历树的遍历例如：abdec先根序列：后根序列：abcdebdcea深度优先遍历（先根、后根）广度优先遍历（层次）先根遍历访问根结点；依次先根遍历根结点的每棵子树。后根遍历依次后根遍历根结点的每棵子树；访问根结点。树没有中序遍历（因子树不分左右）12讨论：树若采用“先转换，后遍历”方式，结果是否一样？abdec先序遍历：后序遍历：中序遍历：decbaabdecabcdebdcea1.

树的先根遍历与二叉树的先序遍历相同；2.树的后根遍历相当于二叉树的中序遍历；3.树没有中序遍历，因为子树无左右之分。结论：树的先根序列：abcde树的后根序列：bdcea13先序遍历若森林为空，返回；访问森林中第一棵树的根结点；先根遍历第一棵树的根结点的子树森林；先根遍历除去第一棵树之后剩余的树构成的森林。森林的遍历ABCDEFGHJI深度优先遍历（先序、中序）广度优先遍历（层次）中序遍历若森林为空，返回；中根遍历森林中第一棵树的根结点的子树森林；访问第一棵树的根结点；中根遍历除去第一棵树之后剩余的树构成的森林。14讨论：若采用“先转换，后遍历”方式，结果是否相同？例如：ABCDEFGHJI先序序列：中序序列：ABCDEFGHIJB

CDAFEHJIGABCDEFGHJI先序序列：中序序列：ABCDEFGHIJBCDAFEHJIG结论：森林的先序和中序遍历在两种方式下的结果相同。15什么是带权树？abdc7524即叶子带有权值。例如：最优二叉树(哈夫曼树)如果是带权路径长度最短的树167.二叉树的应用与哈弗曼编码7.Huffman树及其应用一、Huffman树的构建二、Huffman编码三、算法实现最优二叉树Huffman树Huffman编码带权路径长度最短的树不等长编码是通信中最经典的压缩编码17树的带权路径长度如何计算？WPL=

wklkk=1nabdc7524(a)cdab2457(b)bdac7524(c)WPL=WPL=WPL=Huffman树是WPL最小的树树中所有叶子结点的带权路径长度之和36463518构造Huffman树的基本思想：权值大的结点用短路径，权值小的结点用长路径。一、Huffman树（最优二叉树）路径：路径长度：树的路径长度：带权路径长度：树的带权路径长度：Huffman树：由一结点到另一结点间的分支所构成。路径上的分支数目。从树根到每一结点的路径长度之和。结点到根的路径长度与结点上权的乘积（WPL）若干术语：debacfg即树中所有叶子结点的带权路径长度之和带权路径长度最小的树。例如：a→e的路径长度＝树长度＝210Huffman常译为赫夫曼、霍夫曼、哈夫曼等WeightedPathLength19构造Huffman树的步骤（即Huffman算法）：由给定的n个权值{w1,w2,…,wn}构成n棵二叉树的集合F={T1,T2,…,Tn

}（即森林），其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树均空。(2)

在F中选取两棵根结点权值最小的树做为左右子树构造一棵新的二叉树，且让新二叉树根结点的权值等于其左右子树的根结点权值之和。(3)在F中删去这两棵树，同时将新得到的二叉树加入F中。(4)重复(2)和(3),直到F只含一棵树为止。这棵树便是Huffman树。20对权值进行合并、删除与替换——在权值集合{7,5,2,4}中，总是合并当前值最小的两个权具体操作步骤：a.初始b.合并{2}{4}c.合并{5}{6}d.合并{7}{11}谁左谁右？不规定就不会惟一219例题：已知权值W={5,6,2,9,7},建立对应的Huffman树562792571667132922Huffman树的应用：例：设有4个字符d,i,a,n，出现的频度分别为7,5,2,4，怎样编码才能使它们组成的报文长度最短？法1：等长编码（如二进制编码）令d=00，i=01，a=10，n=11，则：WPL1＝2bit×(7＋5＋2＋4）＝36法2：不等长编码（如Huffman编码）令d=0;i=10,a=110,n=111，则：WPL2=1bit×7＋2bit×5+3bit×(2+4)=35明确：要实现Huffman编码，就要先构造Huffman树讨论：Huffman树有什么用？频度高的信息用短码，低的用长码，传输效率肯定高！最小冗余编码、信息高效传输23按左“0”右“1”

对Huffman树的所有分支编号dain111000Huffman编码结果：d=0,i=10,a=110,n=111WPL=1bit×7＋2bit×5+3bit×(2+4)=35（小于等长码的WPL=36）特征：每一码不会是另一码的前缀，译码时可惟一复原Huffman编码也称为前缀码Huffman编码24哈夫曼编码

哈夫曼树的应用很广，哈夫曼编码就是其在电讯通信中的应用之一。在电讯通信业务中，通常用二进制编码来表示字母或其他字符，并用这样的编码来表示字符序列。例：如果需传送的电文为‘ABACCDA’，它只用到四种字符，用两位二进制编码便可分辨。假设A,B,C,D的编码分别为00,01,10,11，则上述电文便为‘00010010101100’（共14位），译码员按两位进行分组译码，便可恢复原来的电文。能否使编码总长度更短呢？

25实际应用中各字符的出现频度不相同数据的最小冗余编码问题用短（长）编码表示频率大（小）的字符使得编码序列的总长度最小，使所需总空间量最少若假设A,B,C,D的编码分别为0，00，1，01，则电文‘ABACCDA’便为‘000011010’（共9位）。可译为‘BBCCDA’、‘ABACCDA’、‘AAAACCACA’存在多义性26要求任一字符的编码都不能是另一字符编码的前缀！这种编码称为前缀编码（其实是非前缀码）。

译码的惟一性问题

利用最优二叉树可以很好地解决上述两个问题在编码过程要考虑两个问题数据的最小冗余编码问题译码的惟一性问题27

以电文中的字符作为叶子结点构造二叉树。然后将二叉树中

结点引向其左孩子的分支标‘0’，引向其右孩子的分支标‘1’；

每

个字符的编码即为从根到每个叶子的路径上得到的

0,1

序列。如

此得到的即为二进制前缀编码。

用二叉树设计二进制前缀编码例：

ABCD010101编码：A：0B：10C：110D：111任意一个叶子结点都不可能在其它叶子结点的路径中。28假设各个字符在电文中出现的次数（或频率）为wi

，其编码长度为li，电文中只有n种字符，编码总长为：叶子结点的权从根到叶子的路径长度设计电文总长最短的编码设计哈夫曼树（以n

种字符出现的频率作权）

用哈夫曼树设计总长最短的二进制前缀编码

由哈夫曼树得到的二进制前缀编码称为哈夫曼编码

29解：

ACBD000111编码：A：0C：10B：110D：111例：如果需传送的电文为‘ABACCDA’，即：A,B,C,D

的频率（即权值）分别为0.43,0.14,0.29,0.14，试构造哈夫曼编码。则电文‘ABACCDA’便为‘0110010101110’（共13位）。30解：

EBD编码：A：11C：10E：00B：010D：011例：如果需传送的电文为‘ABCACCDAEAE’，即：A,B,C,D,E的频率（即权值）分别为

0.36,0.1,0.27,0.1,0.18，试构造哈夫曼编码。则电文‘ABCACCDAEAE’便为‘110101011101001111001100’（共24位，比33位短）。CA1111000031

译码

从哈夫曼树根开始，对待译码电文逐位取码。若编码是“0”，则向左走；若编码是“1”，则向右走，一旦到达叶子结点，则译出一个字符；再重新从根出发，直到电文结束。

00110110

T

;

A

C

S电文为“1101000”译文只能是“CAT”32严习题集6.26：设通信用的电文由字符集{a,b,c,d,e,f,g,h}中的字母构成，这8个字母在电文中出现的概率分别为{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}，试为这8个字母设计哈夫曼编码。330.070.190.020.060.320.030.210.100.070.190.020.060.320.030.210.100.050.070.190.020.060.320.030.210.100.050.110.070.190.020.060.320.030.210.100.050.110.17340.070.190.020.060.320.030.210.100.050.110.170.280.070.190.020.060.320.030.210.100.050.110.170.280.40350.070.190.020.060.320.030.210.100.050.110.170.280.400.60a0.07b0.19c0.02d0.06e0.32f0.03g0.21h0.100.050.110.170.280.400.601.0000000001111111a=1010b=00c=10000d=1001e

=11f=10001g=01h=101136WPL=2.61typedefstruct{ unsignedintweight; unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;//动态分配数组存储赫夫曼树typedefchar**HuffmanCode;建立Huffman树及求Huffman编码的算法Huffman树没有度为1的结点

一棵有n0个叶子结点的Huffman树共有2n0-1个结点设共有n个节点，则n=n0+n2;(没有度为1的节点，n1=0)度之和=n-1=2n2

n-1=2(n-n0)n=2n0-1

可以存储在一个大小为2n-1的一维数组中。

节点权值，父节点，左孩子节点和右孩子节点37voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn){//w存放n个字符的权值，构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC

if(n<=1)return;//n为字符数目，

m=2*n-1;

//m为结点数目

HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//HT存放Huffman树结构，0号单元未用,其余前n个单元

//存放树的叶子结点，n-1个单元存放内部结点

for(p=HT,i=1;i<=n;++i,++p,++w)

{p->weight=*w;p->parent=0;p->lchild=0;p->rchild=0;}

//*p={*w,0,0,0}；初始化HT中的叶结点循环退出时i=n+1;38for(;i<=m;++i,++p){p->weight=0;p->parent=0;p->lchild=0;p->rchild=0;}

//*p={0,0,0,0};初始化HT中的内部结点

for(i=n+1;i<=m;++i)

//建赫夫曼树，(建立HT静态链表中的链){Select(HT,i-1,s1,s2);//在HT[1～i-1]中选择parent//为0且weight最小的两个结点，序号分别为s1和s2 HT[s1].parent=i;HT[s2].parent=i; HT[i].lchild=s1;HT[i].rchild=s2; HT[i].weight=HT[s1].weight+HT[s2].weight;}39

//从叶子到根逆向求赫夫曼编码

HC=(HuffmanCode)malloc((n+1)*sizeof(char*));cd=(char*)malloc(n*sizeof(char));cd[n-1]=‘\0’;//编码结束符

for(i=1;i<=n;++i)//逐个字符求赫夫曼编码

{start=n-1;//编码结束符位置

for(c=i,f=HT[c].parent;f!=0;c=f,f=HT[f].parent)//从叶子到根逆向求编码

if(HT[f].lchild==c)cd[--start]='0';

elsecd[--start]='1';HC[i]=(char*)malloc((n-start)*sizeof(char));strcpy(HC[i],&cd[start]);//从cd复制编码串到HC}

free(cd);//释放工作空间}//HuffanCoding40Huffman编码举例解：先将概率放大100倍，以方便构造哈夫曼树。放大后的权值集合w={7,19,2,6,32,3,21,10}，按哈夫曼树构造规则（合并、删除、替换），可得到哈夫曼树。例1【严题集6.26③】：假设用于通信的电文仅由8个字母{a,b,c,d,e,f,g,h}构成，它们在电文中出现的概率分别为{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10

}，试为这8个字母设计哈夫曼编码。如果用0～7的二进制编码方案又如何？【类同P148例2】0000—00—2810010717000—000—000—000—000—-00000000r0010002100300320060020019007lpw13121011987654321116235211940bcadegfh√√599√√111010491728√√√√√√40√√60100361811111212101132602713131515√√141451213141415w={7,19,2,6,32,3,21,10}请注意：哈夫曼树样式不惟一！w={7,19,2,6,32,3,21,10}在机内存储形式为:2810010717000—000—000—000—000—-00000000r0010002100300320060020019007lpw13121011987654321116235211940badegfh√√599√√111010491728√√√√√√40√√60100361811111212101132602713131515√√1414512131401415如何形成编码?例如:c的编码:

从叶结点开始，找到其双亲，判定是双亲的左孩子或右孩子，确定编码，直到根结束。c对应的哈夫曼编码：符编码频率a0.07b0.19c0.02d0.06e0.32f0.03g0.21h0.10符编码频率a0.07b0.19c0.02d0.06e0.32f0.03g0.21h0.101110001101011001011011011111000001010011100101110111Huffman码的WPL＝2(0.19+0.32+0.21)+