第6章 树和二叉树 （Tree & Binary Tree）

Presentation on theme: "第6章 树和二叉树 （Tree & Binary Tree）"— Presentation transcript:

1 第6章 树和二叉树 （Tree & Binary Tree）
6.1 树的基本概念 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.5 赫夫曼树及其应用

2 6.5 Huffman树及其应用 一、Huffman树 二、Huffman编码 Huffman树 Huffman编码 最优二叉树 不等长编码
带权路径长度最短的树 Huffman树 最优二叉树 是通信中最经典的压缩编码 Huffman编码 不等长编码 2

3 WPL = wklk 经典之例： WPL= 36 WPL= 46 WPL= 35 树的带权路径长度如何计算？
n 树的带权路径长度如何计算？ 树中所有叶子结点的带权路径长度之和 经典之例： a b d c 7 5 2 4 (a) c d a b 2 4 5 7 (b) b d a c 7 5 2 4 (c) WPL= 36 WPL= 46 WPL= 35 Huffman树是WPL 最小的树 3

4 Huffman常译为赫夫曼、霍夫曼、哈夫曼、胡夫曼等
d e b a c f g 一、 Huffman树（最优二叉树） 若干术语： 路 径： 路径长度： 树的路径长度： 带权路径长度： 树的带权路径长度： Huffman树： 由一结点到另一结点间的分支所构成。 路径上的分支数目。 例如：a→e的路径长度＝ 2 10 从树根到每一结点的路径长度之和。 树长度＝ 结点到根的路径长度与结点上权的乘积（WPL） Weighted Path Length 即树中所有叶子结点的带权路径长度之和 带权路径长度最小的树。 Huffman常译为赫夫曼、霍夫曼、哈夫曼、胡夫曼等 4

5 WPL2=1bit×7＋2bit×5+3bit×(2+4)=35
1. 构造Huffman树的基本思想： WPL最小的树 权值大的结点用短路径，权值小的结点用长路径。 讨论：Huffman树有什么用？ 最小冗余编码、信息高效传输 例：设有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树 5

6 2. 构造Huffman树的步骤（即Huffman算法）：
(1) 由给定的 n 个权值{ w1, w2, …, wn }构成n棵二叉树的集合F = { T1, T2, …, Tn } （即森林） ，其中每棵二叉树 Ti 中只有一个带权为 wi 的根结点，其左右子树均空。 (2) 在F 中选取两棵根结点权值最小的树 做为左右子树构造一棵新的二叉树，且让新二叉树根结点的权值等于其左右子树的根结点权值之和。 (3) 在F 中删去这两棵树，同时将新得到的二叉树加入 F中。 (4) 重复(2) 和(3) , 直到 F 只含一棵树为止。这棵树便是Huffman树。 总之，每次合并当前值最小的两个权。 (此树特征：没有度为1的结点) 怎样证明它就是WPL最小的最优二叉树？参考《信源编码》 6

7 具体操作步骤： step1：对权值进行合并、删除与替换 ——在权值集合{7,5,2,4}中，总是合并当前值最小的两个权 a. 初始
c. 合并{5} {6} d. 合并{7} {11} b. 合并{2} {4} 圆框表示内结点（合并后的权值） 谁左谁右？不规定就不会惟一 方框表示外结点（叶子，字符） 7

8 step2：按左“0”右“1” 对Huffman树的所有分支编号
——将 Huffman树 与 Huffman编码 挂钩 1 d a i n Huffman编码结果：d=0, i=10, a=110, n=111 WPL=1bit×7＋2bit×5+3bit(2+4)=35（小于等长码的WPL=36） 特征：每一码不会是另一码的前缀，译码时可惟一复原 Huffman编码也称为前缀码 8

9 二、Huffman编码 Huffman编码 不等长编码 如何将 Huffman树 与 Huffman编码 挂钩?
哈夫曼编码的基本思想是—— 出现概率大的信息用短码，概率小的用长码,最小冗余 是通信中最经典的压缩编码 Huffman编码 不等长编码 如何将 Huffman树 与 Huffman编码 挂钩? 按左“0”右“1” 对Huffman树的所有分支编号

10 本节重点：如何编程实现Huffman编码？
参见教材P147 建议1：Huffman树中结点的结构可设计成4或5分量形式： char weight parent lchild rchild 建议2： Huffman树的存储结构可采用顺序存储结构： 将整个Huffman树的结点存储在一个数组HT[1..n..m]中; （Huffman树内外结点总数m=2n-1） 各叶子结点的编码存储在另一“复合”数组HC[1..n]中。 (n个权值就是n个叶子,将对应n个不同码串) m=n0+n2=n+(n-1)=2n-1 即：先构造Huffman树HT 再求出n个权值/字符的Huffman编码HC

11 Huffman编码举例 例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】 解：先将概率放大100倍，以方便构造哈夫曼树。 放大后的权值集合 w={ 7, 19, 2, 6, 32, 3, 21, 10 }， 按哈夫曼树构造规则（合并、删除、替换），可得到哈夫曼树。

12 w={ 7, 19, 2, 6, 32, 3, 21, 10 }在机内存储形式为: 双亲parent w p l r 100 左右孩子lchild,rchild 1 7 √ 11 21 19 40 60 32 2 19 √ 3 2 9 √ 28 10 4 6 √ e b g 5 32 √ 11 6 d 6 3 10 7 17 7 21 √ 2 3 5 8 10 √ a h 9 —- 5 3 6 10 11 — √ 12 11 4 9 c f 请注意：哈夫曼树样式不惟一，编程时应该有约定 — 17 1 8 √ 12 — 28 √ 10 11 13 — 40 2 7 60 100

13 对应的哈夫曼编码： 按左0右1标注 10 7 17 2 3 5 28 21 19 40 100 b c a 11 6 d 60 32 e g f h 1 符 编码 频率 a 0.07 b 0.19 c 0.02 d 0.06 e 0.32 f 0.03 g 0.21 h 0.10 符 编码 频率 a 0.07 b 0.19 c 0.02 d 0.06 e 0.32 f 0.03 g 0.21 h 0.10 1110 00 11010 1100 10 11011 01 1111 000 001 010 011 100 101 110 111 Huffman码的WPL＝2( ) + 4( ) +5( ) = =2.61 3( )=3 二进制等长码的WPL＝

14 另一种表示 ：

15 自己上机练习说明：设字符集为26个英文字母，其出现频度如下表所示。
51 48 1 15 63 57 20 32 5 频度 z y x w v u t 字符 16 18 8 23 80 p 21 f q g r 47 h s o n m l k j 103 22 13 64 186 i e d c b a 空格 要求：先建Huffman树，再利用此树对任一字符串文件进行编码和译码——即设计一个Huffman编/译码器

16 Huffman树和Huffman树编码的存储表示：
typedef struct{ unsigned int weight；//权值分量（可放大取整） unsigned int parent，lchild，rchild； //双亲和孩子分量 }HTNode，*HuffmanTree；//用动态数组存储Huffman树 typedef char**HuffmanCode； //动态数组存储Huffman编码表 *HuffmanTree或 HT向量样式： 指针型指针 双亲 r 9 2 19 7 l p w 3 1 HT[3].parent=9 ……

17 Huffman编码的实现： 先构造Huffman树HT， 再求出N个字符的Huffman编码HC。 *w存放n个字符的权值
int *w是表明w是一个指向int数组的指针,*w即取一个int,w++后*w取下一个元素……w这里和数组名(即指向该int数组的指针)等价。 void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n){ if (n<=1)return; m=2*n-1; //n 个叶子的HuffmanTree共有2n-1个结点； HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //0单元未用 for(p=HT+1,i=1; i<=n; ++i,++p,++w)*p={*w,0,0,0}; //给前n个单元初始化(原教材有误) for(；i<=m; ++i,++p)*p ={0,0,0,0}; //对叶子之后的存储单元清零 for(i=n+1;i<=m; ++i){ //建Huffman树(从n个叶子后开始存内结点) 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;} s2 r s1 9 i 2 7 l p w

18 (续前)再求出n个字符的Huffman编码HC
见P149图 (续前)再求出n个字符的Huffman编码HC HC=(HuffmanCode)malloc((n+1)*sizeof(char*)); //分配n个字符编码的头指针向量（一维数组） sizeof()可以对变量或变量类型运算,sizeof(char*)是一个char型指针的空间大小,如定义char *p,那么sizeof(p)就是结果,和sizeof(char*)等价。 cd=(char*) malloc(n*sizeof(char)); //分配求编码的临时最长空间 cd[n-1]=“\0”; //编码结束符（从cd[0]~cd[n-1]为合法空间） for(i=1;i<=n;++i) //逐个字符求Huffman编码 { start=n-1; //编码结束符位置 for(c=i,f=HT[i].parent; f!=0; c=f, f=HT[f].parent) //从叶子到根逆向求编码 if(HT[f].lchild==c) cd[--start]=“0”; else cd[--start]=“1”; HC[i]=(char*)malloc((n-start)*sizeof(char));//为第i个字符编码分配空间，并以数组形式存放各码串指针 strcpy(HC[i],&cd[start]); //从cd复制编码串到HC所指空间 } free(cd); //释放临时空间 }//HuffmanCoding

19 附：二叉树若干典型算法 （习题） 4例

20 A B C D E 1. 如何求二叉树的深度，或从某个结点开始的子树深度？
算法思路：只查各结点后继链表指针，若左(右)孩子的左(右)指针非空，则层次数加1；否则函数返回。 算法见附1 2. 如何按层次输出二叉树中所有结点？ 算法思路：既然要求从上到下，从左到右，则利用队列存放各子树结点的指针是个好办法，此时绝不能用递归算法。 技巧：当根结点入队后，令其左、右孩子结点入队，而左孩子出队时又令它的左右孩子结点入队，……由此便可产生按层次输出的效果。 A B C D E 算法见附2

21 算法思路：完全二叉树的特点是：没有左子树空而右子树单独存在的情况(前k-1层都是满的，且第k层左边也满）。
3.如何判别给定二叉树是否为完全二叉树？ 算法思路：完全二叉树的特点是：没有左子树空而右子树单独存在的情况(前k-1层都是满的，且第k层左边也满）。 技巧:按层次遍历方式，先把所有结点（不管当前结点是否有左右孩子）都入队列.若为完全二叉树,则层次遍历时得到的肯定是一个连续的不包含空指针的序列。如果序列中出现了空指针，则说明不是完全二叉树。 算法见附3 4 中序遍历的非递归算法如何实现？ 算法思路：若不用递归，则要实现二叉树遍历的“嵌套”规则，必用堆栈(迭代方式) 。可直接用while语句和push/pop操作。参见教材P 程序。 算法见附4

22 附1：求二叉树的深度的算法 严题集6.44 ④ 法1：从根开始向下计算层次(比从叶子往上计算更简单)
附1：求二叉树的深度的算法 严题集6.44 ④ 法1：从根开始向下计算层次(比从叶子往上计算更简单) Void ABC(Bitree p, int l, int &h) { if p≠NIL then { l=l+1; if l>h then h=l; ABC(p->Lchild, l, h); ABC(p->Rchild, l, h); } l、h分别表示二叉树的层次数和深度。 想一想，l和h的初始值应设为多少？ 开始调用时，应当用ABC（p, 0, 0） 若去掉h形参中的“&”号，则h不变化，算出的更深层数不能正确返回, h将永远为 0。

23 法2：递归时从叶子开始向上计数，层深者保留。
int BTreeDepth(Btree *BT) //*BT为二叉树某结点的指针 { int leftdep, rightdep; //设左右两个深度/层次计数器 if(BT==NULL) return(0); //当前结点指针为空则立即返回 else { leftdep= BTreeDepth(BT->left); //遍历当前结点左子树 rightdep=BTreeDepth(BT->right); //遍历当前结点右子树 if( leftdep>rightdep)return(leftdep+1); //从叶子起计数 else return(rightdep+1); } } //BTreeDepth

24 附2：层次遍历算法(需要利用队列) 严题集6.47 ④
附2：层次遍历算法(需要利用队列) 严题集6.47 ④ void LayerOrder(Bitree T) //层序遍历二叉树 { InitQueue(Q); //建一个空队（初始化队列）   EnQueue(Q,T); //将一个结点插入队尾的函数 while( !QueueEmpty(Q) ) { DeQueue(Q, &p); //队首结点出队(送入p) visit(p); if(p->lchild) EnQueue(Q,p->lchild); //p的左孩子入队 if(p->rchild) EnQueue(Q,p->rchild); //p的右孩子入队 } }//LayerOrder 当孩子为空时不要将空指针入队

25 附3：判别给定二叉树是否为完全二叉树 严题集6.49 ④
int IsFull_Bitree(Bitree T)//是完全二叉树返回1,否则返0 { InitQueue(Q); //建队（初始化队列） flag=0; //标志初始化 EnQueue(Q,T); //结点T入队（空指针也要入队） while(!QueueEmpty(Q)) { DeQueue(Q,&p); //队首结点出队(送入p) if(!p) flag=1; //队首结点为空则标志变，但也许是队尾？ else if(flag)return 0; //下一轮才能确定是不是完全二叉树 else { EnQueue(Q,p->lchild); //不管孩子是否为空,都入队列 EnQueue(Q,p->rchild); } }//while return 1; //执行至此必为队空且中间无空指针，完全二叉 }//IsFull_Bitree

26 附4：中序遍历的非递归算法(或称迭代算法)见教材P131
Status InOrderTrav( BiTree T, Status(*Visit)(TElemType e) ) { //此处Visit意思是对元素e的一种操作 InitStack（S）；p=T; //初始化栈 while( p || !StackEmpty(S) ) //树不空或栈不空则开始遍历 { if( p ){Push(S,p);p=p->lchild;}//根指针进栈，遍历左子树 else{ Pop(S,p)； //根指针退栈 if(! Visit(p->data))return ERROR; //访问根结点 p=p->rchild; //遍历右子树 } //else } //while return OK; } //InOrderTrav

27 本 章 小 结 第6章结束 存储结构 遍历 1、定义和性质 1:2， 性质有3+2条 树 森林 2、存储结构 3、遍历 遍历
先序遍历 后序遍历 孩子—兄弟 本 章 小 结 存储结构 遍历 1、定义和性质 1:2， 性质有3+2条 树 二叉树 森林 顺序结构 链式结构 2、存储结构 二叉链表 三叉链表 中序遍历 后序遍历 先序遍历 层次遍历 3、遍历 遍历 Huffman树 应用 先序线索树 中序线索树 后序线索树 先 序 遍 历 中 4、线索化 线索树 Huffman编码 第6章结束