第7章树形结构4.ppt
第七章 树和二叉树,7.8 哈夫曼树7.8.1 哈夫曼树概述7.8.2 哈夫曼树的构造算法7.8.3 哈夫曼编码,7.7 线索二叉树,7.7.1 线索二叉树的概念,7.7.2 线索二叉树,上次课的总结：,画出该棵二叉树的先序、中序和后序线索二叉树,上次课的总结：,上次课的总结：,画出该棵二叉树的先序、中序和后序线索二叉树,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)/中序线索化二叉树,7.7.2 线索化二叉树 算法设计,1,算法设计,TBTNode*CreaThread(TBTNode*b)/线索化二叉树,增加一个头结点，将整棵树作为他的左孩子,选择一种遍历方式，将二叉树线索化，生成某种访问顺序的线索化二叉树。,TBTNode*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;,pre,1,Thread(p)算法思路是：*p 指向当前访问的结点*pre指向前一访问的结点采用中序遍历的方式Thread(b-lchild);printf(%c,b-data);Thread(b-rchild);,当前访问结点没有左孩子，就设置为线索，指向前驱如果访问过的结点没有右孩子，则设置为线索，指向后继,TBTNode*pre;/*全局变量*/void Thread(TBTNode*/*递归调用右子树线索化*/,中序遍历(递归),7.8 哈夫曼树与哈夫曼编码,哈夫曼(Huffman)树，又称最优二叉树，是一类带权路径长度最短的树。概念：两结点间的路径：从一结点到另一结点所经过的结点序列。路径长度：从树中一个结点到另一个结点之间路径上的分支数。树的路径长度：树根到每一个结点的路径长度之和称为。,结点1到5之间的路径：（1）（2）（5）,结点1到5之间的路径长度：2,树的路径长度：1+1+2+2+2+2+2=10,树的带权路径长度WPL：设树中有M个叶结点，每个叶结点带一个权值WK，树根到每一个叶结点K的路径长度为LK则WPL=。,哈夫曼树：WPL最小的树称为最优二叉树，又称哈夫曼树,举例：有4个叶结点a,b,c,d权值分别为7，5，4，2，请构造出哈夫曼树,WPL=7*2+5*2+4*2+2*2=36,哈夫曼树：WPL最小的树称为最优二叉树，又称哈夫曼树,举例：有4个叶结点a,b,c,d权值分别为7，5，4，2，请构造出哈夫曼树,D,C,WPL=1*2+2*4+3*7+3*5=46,2,4,A,B,7,5,WPL=7*1+5*2+4*3+2*3=35,哈夫曼树的构造过程,a,b,c,d,7,5,2,4,(a),a,7,b,5,c,d,6,(b),a,7,b,c,d,11,(c),a,b,c,d,18,(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),根据哈夫曼算法可构造哈夫曼树。,5,3,11,23,7,8,14,29,0,0,0,0,0,0,0,1,1,1,1,1,1,1,例题,假设某电文仅由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-存放结点双亲的位置,缺点：求双亲容易，但求结点的孩子时需要遍历整个结构,双亲孩子表示法,把每个结点的孩子结点排列起来，看作一个线性链表，且以单链表作存储结构，则n个结点有n个孩子链表（叶子的孩子链表为空表）n个头指针又组成一个线性表，采用顺序存储结构,3,5,6,1,2,3,4,5,6,孩子兄弟表示法,以二叉链表作树的存储结构，又称二叉树表示法或二叉链表表示法。链表中结点的两个链域：左链域指向该结点的第一个孩子结点（长子）右链域指向下一个兄弟结点,data,L,R,孩子兄弟表示法举例,R,B,C,D,E,F,G,H,K,A,注：双亲只管长子，长子连接兄弟,7.9.1 树与二叉树的转换,由于二叉树和树都可用二叉链表作为存储结构，则通过二叉链表可导出树与二叉树之间的一个对应关系。给定一棵树，可以找到唯一的一棵二叉树与之对应。从物理结构看，它们的二叉链表是相同的，只是解释不同。两种转换方式,树与二叉树的转换方式一,B,任何一棵和树对应的二叉树，其右子树必空,树与二叉树的转换方式二,（1）在兄弟之间加一连线；（2）对每一个结点，只保留他与第一个孩子的连线，去掉与其他孩子的连线；（3）以整棵树为轴心，顺时针旋转45度特点：无右子树,A,B,C,E,D,例题,将如下的一棵树转换成二叉树,7.9.3 森林与二叉树的转换,（1）森林转换成二叉树的方法(1)将森林F=T1,T2Tm的各棵树分别转换成二叉树BT1,BT2BTm(2)将BTi+1作为BTi根结点的右子树F=T1,T2,T3,F=T1,T2,T3,（2）二叉树转换成森林的方法(1)将根结点和其左子树作为森林的一棵树，并将其右子树作为森林的其他子树。（2）重复上面的直到某结点的右子树为空。,
