《第7章树形结构4.ppt》由会员分享，可在线阅读，更多相关《第7章树形结构4.ppt（33页珍藏版）》请在三一文库上搜索。
1、第七章 树和二叉树,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;
2、 /*左孩子或线索指针*/ 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,算法设计,
3、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-r
4、child=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)树，又称最优二叉树
5、，是一类带权路径长度最短的树。 概念： 两结点间的路径：从一结点到另一结点所经过的结点序列。 路径长度：从树中一个结点到另一个结点之间路径上的分支数。 树的路径长度：树根到每一个结点的路径长度之和称为。,结点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+
6、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，其中每棵二叉树中均只含一
7、个带权值为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作为各根结点到每个叶结点的权值构造一棵最优二叉树,规定哈夫曼树中
8、的左分支为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,
9、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个孩子链表（叶子的孩子链表为空表）
10、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 树与二叉树的转换,由于二叉树和树都可用二叉链表作为存储结构，则通过二叉链表可导出树与二叉树之间的一个对应关系。 给定一棵树，可以找到唯一的一棵二叉树与之对应。 从物理结构看，它们的二叉链表是相同的，只是解释不同。 两种转换方式,树
11、与二叉树的转换方式一,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）重复上面的直到某结点的右子树为空。,