第七章第七章 树和二叉树树和二叉树7.8 哈夫曼树哈夫曼树7.8.1 哈夫曼树概述哈夫曼树概述7.8.2 哈夫曼树的构造算法哈夫曼树的构造算法7.8.3 哈夫曼编码哈夫曼编码7.77.7 线索二叉树线索二叉树7.7.17.7.1 线索二叉树的概念线索二叉树的概念7.7.27.7.2 线索二叉树线索二叉树上次课的总结：上次课的总结：ABCDE画出该棵二叉树的先序、中序和后序线索二叉树画出该棵二叉树的先序、中序和后序线索二叉树上次课的总结：上次课的总结： A B C E F D G 上次课的总结：上次课的总结：画出该棵二叉树的先序、中序和后序线索二叉树画出该棵二叉树的先序、中序和后序线索二叉树7.7.2 线索化二叉树线索化二叉树 为为了了实实现现线线索索化化二二叉叉树树,将将前前面面二二叉叉树树结结点点的的类类型型定义修改如下：定义修改如下： typedef struct node ElemType data;/*结点数据域结点数据域*/ int ltag,rtag; /*增加的线索标记增加的线索标记*/ struct node *lchild;/*左孩子或线索指针左孩子或线索指针*/ struct node *rchild;/*右孩子或线索指针右孩子或线索指针*/ TBTNode;/*线索树结点类型定义线索树结点类型定义*/ typedef struct node ElemType data;int ltag,rtag; /增加的线索标记增加的线索标记struct node *lchild;struct node *rchild; TBTNode;TBTNode * CreateTBTNode(char *str) /建立二叉树（二叉链表的方式）建立二叉树（二叉链表的方式）TBTNode * CreaThread(TBTNode *b) /中序线索化二叉树中序线索化二叉树ABCDE7.7.2 线索化二叉树线索化二叉树 算法设计算法设计01ABDEC1100110011算法设计算法设计TBTNode *CreaThread(TBTNode *b) /线索化二叉树线索化二叉树ABDEC01增加一个头结点，将整棵树作为他的左孩子增加一个头结点，将整棵树作为他的左孩子选择一种遍历方式，将二叉树线索化，生成某种选择一种遍历方式，将二叉树线索化，生成某种访问顺序的线索化二叉树。访问顺序的线索化二叉树。1100110011TBTNode *CreaThread(TBTNode *b) /*中序线索化二叉树中序线索化二叉树*/ TBTNode *root; root=(TBTNode *)malloc(sizeof(TBTNode); /*创创建建头头结结点点*/ root-ltag=0;root-rtag=1; root-lchild=b; pre=root; Thread(b); pre-lchild=root; pre-rtag=1;root-rchild=pre; return root; 01ABDEC110011001pre1 Thread(p)算法思路是：算法思路是： *p 指向当前访问的结点指向当前访问的结点*pre指向前一访问的结点指向前一访问的结点采用中序遍历的方式采用中序遍历的方式Thread (b-lchild); printf(%c ,b-data); Thread (b-rchild);当前访问结点没有左当前访问结点没有左孩子，就设置为线索，孩子，就设置为线索，指向前驱指向前驱如果访问过的结点没如果访问过的结点没有右孩子，则设置为有右孩子，则设置为线索，指向后继线索，指向后继TBTNode *pre; /*全局变量全局变量*/void Thread(TBTNode *&p) /*对二叉树对二叉树b进行中序线索化进行中序线索化*/ if (p!=NULL) Thread(p-lchild); /*左子树线索化左子树线索化*/if (p-lchild=NULL) /*前驱线索前驱线索*/ p-lchild=pre; p-ltag=1; /*建立当前结点的前驱线索建立当前结点的前驱线索*/else p-ltag=0;if (pre-rchild=NULL) /*后继线索后继线索*/ pre-rchild=p;pre-rtag=1;/*建立前驱结点的后继线索建立前驱结点的后继线索*/else pre-rtag=0; pre=p;Thread(p-rchild); /*递归调用右子树线索化递归调用右子树线索化*/ 中序遍历中序遍历(递归递归)7.87.8 哈夫曼树与哈夫曼编码哈夫曼树与哈夫曼编码 哈夫曼哈夫曼(Huffman)树树，又称最优二叉树，是一，又称最优二叉树，是一类带权路径长度最短的树。类带权路径长度最短的树。概念：概念：两结点间的路径：两结点间的路径：从一结点到另一结点所经过的结点序列。从一结点到另一结点所经过的结点序列。路径长度：路径长度：从树中一个结点到另一个结点之间路径上的分支从树中一个结点到另一个结点之间路径上的分支数。数。树的路径长度：树的路径长度：树根到每一个结点的路径长度之和称为。树根到每一个结点的路径长度之和称为。4123567结点结点1到到5之间的路径之间的路径：（：（1）（）（2）（）（5）结点结点1到到5之间的路径长度之间的路径长度：2树的路径长度树的路径长度：1+1+2+2+2+2+2=10树的带权路径长度树的带权路径长度WPL：设树中有：设树中有M个叶结点，个叶结点，每个叶结点带一个权值每个叶结点带一个权值WK，树根到每一个叶结点树根到每一个叶结点K的路径长度为的路径长度为LK则则WPL =。哈夫曼树：哈夫曼树：哈夫曼树：哈夫曼树：WPLWPL最小的树称为最优二叉树，又称哈夫曼树最小的树称为最优二叉树，又称哈夫曼树最小的树称为最优二叉树，又称哈夫曼树最小的树称为最优二叉树，又称哈夫曼树举例：有举例：有4个叶结点个叶结点a,b,c,d权值分别为权值分别为7，5，4，2，请构造出请构造出哈夫曼树哈夫曼树哈夫曼树哈夫曼树7 A5 B4 C2 DWPL=7*2+5*2+4*2+2*2=36哈夫曼树：哈夫曼树：哈夫曼树：哈夫曼树：WPLWPL最小的树称为最优二叉树，又称哈夫曼树最小的树称为最优二叉树，又称哈夫曼树最小的树称为最优二叉树，又称哈夫曼树最小的树称为最优二叉树，又称哈夫曼树举例：有举例：有4个叶结点个叶结点a,b,c,d权值分别为权值分别为7，5，4，2，请构造出请构造出哈夫曼树哈夫曼树哈夫曼树哈夫曼树DCWPL=1*2+2*4+3*7+3*5=4624AB757 A2 D5 B4 CWPL=7*1+5*2+4*3+2*3=35哈夫曼树的构造过程哈夫曼树的构造过程 abcd7524(a)a7b5cd6(b)a7bcd11( c )abcd18( d )哈夫曼算法（构造哈夫曼树）哈夫曼算法（构造哈夫曼树）(1)根据给定的根据给定的n个权值个权值w1, w2, , wn，构造构造n棵二叉树的集合棵二叉树的集合F = T1, T2, , Tn，其中每棵二叉树中均只含一个带权值为其中每棵二叉树中均只含一个带权值为wi的的根结点根结点,其左、右子树为空树其左、右子树为空树;(2)在在F中选取其根结点的权值为最小的两棵二中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和右子树根结点的权值之和; (3)从从F中删去这两棵树，同时加入刚生成的新中删去这两棵树，同时加入刚生成的新树树; 重复重复(2)和和(3)两步，直至两步，直至F中只含一棵树为中只含一棵树为止。止。哈夫曼树的构造过程哈夫曼树的构造过程 例1：W=5,29,7,8,14,23,3,11哈夫曼编码哈夫曼编码具体构造方法如下：设需要编码的字符集合为具体构造方法如下：设需要编码的字符集合为d1,d2,dn,各个字符在电文中出现的次数集各个字符在电文中出现的次数集合为合为w1,w2,wn,以以d1,d2,dn作为叶结点作为叶结点,以以w1,w2,wn作为各根结点到每个叶结点的作为各根结点到每个叶结点的权值构造一棵最优二叉树权值构造一棵最优二叉树,规定哈夫曼树中的左分规定哈夫曼树中的左分支为支为0,右分支为右分支为1,则从根结点到每个叶结点所经则从根结点到每个叶结点所经过的分支对应的过的分支对应的0和和1组成的序列便为该结点对应组成的序列便为该结点对应字符的编码。这样的编码称为哈夫曼编码。字符的编码。这样的编码称为哈夫曼编码。对应的哈夫曼编码如下：对应的哈夫曼编码如下：1：000 3：001 5：01 7：1哈夫曼编码举例例：已知某系统在通信联络中可能出现例：已知某系统在通信联络中可能出现8种字符，种字符，其概率为其概率为0.05, 0.29, 0.07, 0.08, 0.l4, 0.23, 0.03, 0.11, 试设计哈夫曼编码。试设计哈夫曼编码。解：设权解：设权w=(5,29,7,8,14,23,3,11), 根据根据哈夫曼算法可构造哈夫曼树。哈夫曼算法可构造哈夫曼树。53112378142900000001111111例题假设某电文仅由假设某电文仅由A,B,C,D,E,F,G,H等等8个个字符组成。各个字符在电文中出现的次数字符组成。各个字符在电文中出现的次数分别为分别为5，25，4，7，9，12，30，8.试为这试为这8个字符设计个字符设计哈夫曼编码。哈夫曼编码。7.9 树和森林树和森林主主要要内内容容：树树的的表表示示及及其其遍遍历历操操作作；森林与二叉树的对应关系。森林与二叉树的对应关系。树的三种存储结构树的三种存储结构 1、双亲表示法、双亲表示法 2、双亲孩子表示法、双亲孩子表示法 3、孩子兄弟表示法、孩子兄弟表示法 树的双亲表示法以一组连续空间存储树的结点，每个结点有两个域以一组连续空间存储树的结点，每个结点有两个域data域域-存放结点信息存放结点信息Parent-存放结点双亲的位置存放结点双亲的位置dataParent102131425263缺点：求双亲缺点：求双亲容易，但求结容易，但求结点的孩子时需点的孩子时需要遍历整个结要遍历整个结构构412356双亲孩子表示法把每个结点的孩子结点排列起来，看作一个线性链把每个结点的孩子结点排列起来，看作一个线性链表，且以单链表作存储结构，则表，且以单链表作存储结构，则n个结点有个结点有n个孩子个孩子链表（叶子的孩子链表为空表）链表（叶子的孩子链表为空表）n个头指针又组成一个线性表，采用顺序存储结构个头指针又组成一个线性表，采用顺序存储结构01122223456123456412356孩子兄弟表示法以二叉链表作树的存储结构，又称二叉树表示以二叉链表作树的存储结构，又称二叉树表示法或二叉链表表示法。法或二叉链表表示法。链表中结点的两个链域：左链域指向该结点的链表中结点的两个链域：左链域指向该结点的第一个孩子结点（长子）右链域指向下一个兄第一个孩子结点（长子）右链域指向下一个兄弟结点弟结点dataLR孩子兄弟表示法举例孩子兄弟表示法举例RBCDEFGHKA注注：双亲只管长子，长子连接兄弟：双亲只管长子，长子连接兄弟ABDGECHKFR7.9.1 树与二叉树的转换树与二叉树的转换 由于二叉树和树都可用二叉链表作为存储结由于二叉树和树都可用二叉链表作为存储结构，则通过二叉链表可导出树与二叉树之间构，则通过二叉链表可导出树与二叉树之间的一个对应关系。的一个对应关系。给定一棵树，可以找到唯一的一棵二叉树与给定一棵树，可以找到唯一的一棵二叉树与之对应。之对应。从物理结构看，它们的二叉链表是相同的，从物理结构看，它们的二叉链表是相同的，只是解释不同。只是解释不同。两种转换方式两种转换方式树与树与二叉树的转换方式一二叉树的转换方式一BACEDABCDE任何一棵和树对应的二叉树，其右子树必空任何一棵和树对应的二叉树，其右子树必空ABCDE树与树与二叉树的转换方式二二叉树的转换方式二ABCED（1）在兄弟之间加一连线；）在兄弟之间加一连线；（2）对每一个结点，只保留他与第一个孩子）对每一个结点，只保留他与第一个孩子的连线，去掉与其他孩子的连线；的连线，去掉与其他孩子的连线；（3）以整棵树为轴心，顺时针旋转）以整棵树为轴心，顺时针旋转45度度特点：无右子树特点：无右子树ABCED例题将如下的一棵树转换成二叉树将如下的一棵树转换成二叉树12345678910117.9.3 森林与二叉树的转换森林与二叉树的转换（1）森林转换成二叉树的方法）森林转换成二叉树的方法(1)将森林将森林F=T1,T2Tm的各棵树的各棵树分别转换成二叉树分别转换成二叉树BT1,BT2BTm(2)将将BTi+1作为作为BTi根结根结点点的右子树的右子树F=T1,T2,T3ACDBEFGJIHACDBEFGJIHF=T1,T2,T3ABCDEFGHIJABCDEFGHIJ（2）二叉树转换成森林的方法）二叉树转换成森林的方法(1)将根结点和其左子树作为森林的一棵树，将根结点和其左子树作为森林的一棵树，并将其右子树作为森林的其他子树。并将其右子树作为森林的其他子树。（2）重复上面的直到某结点的右子树为空。）重复上面的直到某结点的右子树为空。ABCDEFGHIJ