6 树和二叉树(4)

1、ABCDEFG llink data rlink ABCDEFG2000000003456701234567 struct sbtnode datatype data; int llink, rlink; treen+1 ; /n：结点数结点数6.6 huffman6.6 huffman树及应用树及应用6.6.1 6.6.1 二叉树的二叉树的带权路径长度带权路径长度 二叉树的带权路径长度：二叉树的带权路径长度： n WPL = wklk k=1其中，其中，n:n:叶子结点个数，叶子结点个数， w wk k : :第第k k个叶个叶子子的权，的权， l lk k : :第第k k个叶个叶子到根的

2、路径长度子到根的路径长度。 从一个结点从一个结点到另一个结点之间到另一个结点之间的分支序列。的分支序列。从一个结从一个结点到另一个结点所点到另一个结点所经过的分支数目。经过的分支数目。6.6.2 Huffman6.6.2 Huffman树树 对于有对于有n n个叶子，可以构造出多个二叉树。个叶子，可以构造出多个二叉树。 HuffmanHuffman树是一个带权路径长度最小的二叉树，树是一个带权路径长度最小的二叉树，又称又称最优二叉树最优二叉树。一、一、HuffmanHuffman树的构造方法树的构造方法 （1 1）将）将ww1 1,w,w2 2, ,.,w.,wn n 看成看成n n个二叉树；

3、个二叉树； （2 2）选择）选择 2 2 个根结点的值最小的二叉树，个根结点的值最小的二叉树，构造构造1 1个新的二叉树；个新的二叉树；. .；直至剩；直至剩1 1个树止。个树止。二、示例二、示例例例6-6-1：给定权值给定权值 7, 5, 2和和4，构造哈夫曼树。，构造哈夫曼树。1.75242462.3.115246524674.5.71152467115246186.例6-6-2 某系统在通信联络中只可能出现8个字符， 其出现概率分别为: Z K F CUDLE 2 7 24 32374242120 构造 huffman 树。1 12 23 34 45 56 67 78 89 914235

4、067weightllink rlink plink14000230007000600050000 0 0 0 0 三、存储结构三、存储结构 静态三叉链静态三叉链#define n 5#define n 5struct htnode struct htnode float weight; float weight; int llink; int llink; int rlink; int rlink; int plink; int plink;struct htnode ht2struct htnode ht2* *n;n;ht1 12 23 34 45 56 67 78 89 9（1）初值：

5、）初值： 将将n个叶子看作个叶子看作n个二叉树个二叉树在静态三叉链中构造在静态三叉链中构造huffman树树14235067weightllink rlink plink14000230007000600050000 0 0 0 0 ht1 12 23 34 45 56 67 78 89 9(2) 找两个根结点的值最小的二找两个根结点的值最小的二叉树叉树 6和和7 构造一个新的二叉树。构造一个新的二叉树。在静态三叉链中构造在静态三叉链中构造huffman树树1423506713weightllink rlink plink1400023000700660065000013430 0 0 0 s

6、lsrht1 12 23 34 45 56 67 78 89 9(2) 找两个根结点的值最小的二找两个根结点的值最小的二叉树叉树 13 和和 14 构造一个新的二构造一个新的二叉树。叉树。在静态三叉链中构造在静态三叉链中构造huffman树树142350671327weightllink rlink plink140072300070066006500001343727610 0 0 slsrht1 12 23 34 45 56 67 78 89 9(2) 找两个根结点的值最小的二找两个根结点的值最小的二叉树叉树 23 和和 27构造一个新的二构造一个新的二叉树。叉树。在静态三叉链中构造在静态

7、三叉链中构造huffman树树14235067132750weightllink rlink plink14007230087006600650000134372761850270 0 slsrhtweightllink rlink plink1400723008700660065000913437276185027958010014235067132750(2) 找两个根结点的值最小的二叉树找两个根结点的值最小的二叉树 50 和和 50,构造一个新的二叉树。构造一个新的二叉树。100在静态三叉链中构造在静态三叉链中构造huffman树树1 12 23 34 45 56 67 78 89 9s

8、lsrht四、算法设计四、算法设计 void set_haffmantree() void set_haffmantree() for (i=1;illink= hti-rlink=0; /m=2*n-1 for (i=1;i=n;+i) hti.weight=wi; /初始化 for (i=n+1;i=m,+i) /建哈夫曼树 select(i-1,sl,sr); /在htk(1=k=i-1)中选择两个双亲域为零的最小的 / 结点 :sl和sr (sl和sr为最小值所在的下标) htsl.plink= htsr.plink=i; hti.llink=sl; hti.rlink=sr; hti

9、.weight=htsl.weight + htsr.weight ； 前缀编码前缀编码:对每一个字符规定一个对每一个字符规定一个0, 1串作为串作为其代码，并要求任一字符的代码都不是其它字符代其代码，并要求任一字符的代码都不是其它字符代码的前缀。码的前缀。 哈夫曼编码哈夫曼编码:依权值构造哈夫曼树依权值构造哈夫曼树,根据此树得根据此树得到字符集的二进制前缀编码。到字符集的二进制前缀编码。 0左左,1右右一、前缀编码一、前缀编码&哈夫曼编码哈夫曼编码特点特点: 给出现频率高的字符较短的编码，出现频率给出现频率高的字符较短的编码，出现频率 较低的字符以较长的编码，可缩短总码长。较低的字符以较长的

10、编码，可缩短总码长。6.6.3 哈夫曼编码哈夫曼编码二、二、前缀码与等长码的比较前缀码与等长码的比较weightllink rlink plink1400723008700660065000913437276185027958010014235067132750沿叶子结点沿叶子结点到根的路径到根的路径1001 12 23 34 45 56 67 78 89 900001111三三. 构造构造huffman编码编码htweightllink rlink plink1400723008700660065000913437276185027958010014235067132750沿叶子结点沿叶子结

11、点到根的路径到根的路径1001 12 23 34 45 56 67 78 89 9111三三. 构造构造huffman编码编码htweightllink rlink plink1400723008700660065000913437276185027958010014235067132750沿叶子结点沿叶子结点到根的路径到根的路径1001 12 23 34 45 56 67 78 89 901三三. 构造构造huffman编码编码htweightllink rlink plink14007230087006600650009111 01 1011011 014235067132750int h

12、cn+1n; /* hc10-hcn0:存存放放1-n个叶子的编码长度个叶子的编码长度 */1001 12 23 34 45 500001111三三. 构造构造huffman编码编码（一）存储结构（一）存储结构0324411 12 23 34 45 5hthcvoid huffman_code() /*叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码*/ for(i=1;i=n;i+) /*对对n个叶子结点求其哈夫曼编码个叶子结点求其哈夫曼编码*/ k=0; c=i; p=hti.plink; while(p!=0) k+; if(htp.lli

13、nk=c) hcik=0; else hcik=1; c=p; p=htp.plink; hci0=k; 四四. 算法设计算法设计 /*逆向输出逆向输出 huffman编码编码: */ for (i=1;i=1;j-) printf(%d,hcij); printf(n); 例如：abcabcddaabbadabda编码：010101011010001101001100译码：？问题：？为什么？ 设通信用设通信用4个字符个字符a,b,c,d, 分别出现分别出现 7, 5, 2和和4次次 编码分别为：编码分别为：0，1，01，10 结果？结果？思考：思考：等级分数段比例优秀良好中等及格不及格059

14、60697079 8089 90100515403010要编制一个将百分制转换成五级分制（优、良、中、及、不要编制一个将百分制转换成五级分制（优、良、中、及、不及）的程序。显然这程序很简单。如下：及）的程序。显然这程序很简单。如下： if(a60) then printf(“不及格不及格”); else if(a70) then printf(“及格及格”); else if(a80) then printf(“中等中等”); else if(a90) then printf(“良好良好”); else printf(“优秀优秀”);上边的判定过程用下面的图上边的判定过程用下面的图(a)可以表

15、示可以表示:(a)Y(b)例例6-6-4 设包含设包含8个字符的字符集中各字符使个字符的字符集中各字符使用的相对频率分别为用的相对频率分别为 5,29,7,8,14,23,3,11, 试设试设计哈夫曼编码（教材第计哈夫曼编码（教材第146页例页例6-2）。）。1.以给定频率为权构造哈夫曼树；以给定频率为权构造哈夫曼树；514298731123例 w=5, 29, 7, 8, 14, 23, 3, 1151429 7823 3111429 7823 1135887151429233581111358191429238715113581929 231487152929148715291135819

16、23421135819234229148715295811358192342291487152958100 2.在哈夫曼树的所有左分支上编上号码在哈夫曼树的所有左分支上编上号码“0”,右分支上编上号码右分支上编上号码“1”；873511231429 3.将根结点到将根结点到每个叶子结点的每个叶子结点的路径编码串起来路径编码串起来,得到字符集的哈得到字符集的哈夫曼编码。夫曼编码。111111100000001(5):0110 2(29):10 3(7):1110 4(8):11115(14):110 6(23):00 7(3):0111 8(11):010小结小结: : 树形结构的逻辑特点是，每

17、个结点最多只有一个前驱，树形结构的逻辑特点是，每个结点最多只有一个前驱，但可以有多个后继，可以有多个终端结点。但可以有多个后继，可以有多个终端结点。 树和二叉树是两种典型的树形结构。在树中，每个结点树和二叉树是两种典型的树形结构。在树中，每个结点的度数不受限制。在二叉树中，每个结点的度数最多是的度数不受限制。在二叉树中，每个结点的度数最多是2，而且有有左子树和右子树之分。而且有有左子树和右子树之分。 满二叉树和完全二叉树是两种形态特殊的二叉树。高度满二叉树和完全二叉树是两种形态特殊的二叉树。高度为为h的满二叉树一定有的满二叉树一定有2h1个结点。高度为个结点。高度为h的完全二叉树的完全二叉树结

18、点个数大于结点个数大于2h1-1小于等于小于等于2h1，而且最底层的结点都集，而且最底层的结点都集中在该层最左边的若干连续的位置上。中在该层最左边的若干连续的位置上。 双亲数组、孩子链表和二叉链表是树的三种常用的存储双亲数组、孩子链表和二叉链表是树的三种常用的存储结构。结构。 二叉树一般用二叉链表表示。二叉树一般用二叉链表表示。 顺序表示法一般只用于表示完全二叉树。顺序表示法一般只用于表示完全二叉树。小结小结: : 遍历树形结构实际上是一个将树形结构中的结点排成一遍历树形结构实际上是一个将树形结构中的结点排成一个线性序列的过程。这个线性序列与树形结构的存储方法无个线性序列的过程。这个线性序列与

19、树形结构的存储方法无关，但与遍历的具体方法有关。关，但与遍历的具体方法有关。 树的遍历方法常用的有前序遍历、后序遍历和层次遍历树的遍历方法常用的有前序遍历、后序遍历和层次遍历三种。二叉树的遍历方法常用的有前序遍历、中序遍历、后三种。二叉树的遍历方法常用的有前序遍历、中序遍历、后序遍历和层次遍历四种。序遍历和层次遍历四种。 二叉树前序遍历、中序遍历和后序遍历都是以递归的形二叉树前序遍历、中序遍历和后序遍历都是以递归的形式定义的，因此，很容易用递归算法描述。式定义的，因此，很容易用递归算法描述。 用非递归算法描述二叉树的前序遍历、中序遍历和后序用非递归算法描述二叉树的前序遍历、中序遍历和后序遍历，需要定义栈。遍历，需要定义栈。 在二叉树的层次遍历算法中要使用队列。在二叉树的层次遍历算法中要使用队列。 在本章中要求学生熟练掌握二叉树的遍历方法和算法在本章中要求学生熟练掌握二叉树的遍历方法和算法, 并能够灵活应用并能够灵活应用。小结小结: : 线索二叉树也是一种用来表示二叉树的二叉链表。在这线索二叉树也是一种用来表示二叉树的二叉链表。在这种二叉链表中，每个结点的空的左孩子指针域中放入了在