第7章树形结构(最新修改)

1、第第7 7章章 树形结构树形结构7.1 7.1 树的基本概念树的基本概念 7.2 7.2 二叉树概念和性质二叉树概念和性质7.3 7.3 二叉树存储结构二叉树存储结构7.4 7.4 二叉树的遍历二叉树的遍历7.5 7.5 二叉树的基本运算及其实现二叉树的基本运算及其实现7.6 7.6 二叉树的构造二叉树的构造7.8 7.8 哈夫曼树哈夫曼树 本章小结本章小结7.7 7.7 线索二叉树线索二叉树7.9 7.9 并查集并查集 7.1 7.1 树的基本概念树的基本概念 7.1.1 7.1.1 树的定义树的定义 7.1.3 7.1.3 树的基本术语树的基本术语 7.1.2 7.1.2 树的表示树的表示

2、7.1.4 7.1.4 树的性质树的性质7.1.5 7.1.5 树的基本运算树的基本运算7.1.6 7.1.6 树的存储结构树的存储结构数据结构数据结构可分为可分为线性结构线性结构和和非线性结构非线性结构两大类。在第两大类。在第3，4，5章章讨论的都是线性结构，本章和下一章讨论非线性结构。讨论的都是线性结构，本章和下一章讨论非线性结构。 线性结构线性结构(线性表线性表, 栈栈,队列等队列等)：数据元素之间是一对一的关系，：数据元素之间是一对一的关系，除了第一个数据元素外，其它每个元素都有且只有一个直接前驱；除了第一个数据元素外，其它每个元素都有且只有一个直接前驱；除了最后一个数据元素，其它每个

3、元素都有且只有一个直接后继。除了最后一个数据元素，其它每个元素都有且只有一个直接后继。 非线性结构非线性结构: 至少存在一个数据元素有不止一个直接前驱或后至少存在一个数据元素有不止一个直接前驱或后继继(树树,图等图等)7.1 树的定义以及相关术语树的定义以及相关术语BADEFGIHCa一个结点的树一个结点的树3. 广义表表示法广义表表示法(A(B(D),C)4.树的形式化表示方法树的形式化表示方法 树的形式化表示法主要用于树的理论描述。树的形式化表示树的形式化表示法主要用于树的理论描述。树的形式化表示法定义树法定义树T为为T=(D,R)。其中。其中D为为T中结点的集合，中结点的集合，R为树为树

4、T中结中结点之间关系的集合。例如右图所示的树用形式化表示方法表示点之间关系的集合。例如右图所示的树用形式化表示方法表示如下：如下： , （b b）树的基本术语）树的基本术语1. 1. 树的结点树的结点: :数据元素和构造数据元素之间关系的指数据元素和构造数据元素之间关系的指针合起来称作结点针合起来称作结点; ;2. 2. 结点的度结点的度: :一个结点拥有的子树的个数一个结点拥有的子树的个数, ,称作该结称作该结点的度；点的度；3.3.叶子结点叶子结点：度为零的结点称为：度为零的结点称为叶结点叶结点; ;4.4.孩子结点，双亲结点孩子结点，双亲结点：树中一个结点的子树的根结：树中一个结点的子树

5、的根结点称作这个结点的孩子结点，相应地，该结点称为孩点称作这个结点的孩子结点，相应地，该结点称为孩子的双亲结点；子的双亲结点；5.5.兄弟结点，堂兄弟结点兄弟结点，堂兄弟结点：具有相同的双亲结点称为：具有相同的双亲结点称为兄弟结点；其双亲在同一层的结点互为堂兄弟结点；兄弟结点；其双亲在同一层的结点互为堂兄弟结点；6.6.祖先结点祖先结点：从根结点到树中某结点所经过的所有分：从根结点到树中某结点所经过的所有分支结点称作该结点的祖先结点；支结点称作该结点的祖先结点；7.7.子孙结点子孙结点：某一结点的所有孩子结点，以及这些孩：某一结点的所有孩子结点，以及这些孩子结点的孩子结点称为该结点的子孙结点；

6、子结点的孩子结点称为该结点的子孙结点；8. 8. 树的度树的度: :树中所有结点的度的最大值称为该树的度；树中所有结点的度的最大值称为该树的度； 含义含义: :树中最大分支数为树的度树中最大分支数为树的度; ;9. 9. 结点的层次结点的层次: :从根结点到树中某结点所经路径上的从根结点到树中某结点所经路径上的分支数称为该结点的层次。分支数称为该结点的层次。10.10.树的深度树的深度：树中结点的最大层次称为树的深度或：树中结点的最大层次称为树的深度或高度高度11.11.无序树，有序树无序树，有序树：如果将树中结点的各子树看成：如果将树中结点的各子树看成从左到右是有次序的（即不能互换），则称该

7、树为有从左到右是有次序的（即不能互换），则称该树为有序树，否则称为无序树。序树，否则称为无序树。12.12.森林森林: :是是m(m=0)m(m=0)棵互不相交的树的集合。棵互不相交的树的集合。 7.2 二叉树二叉树 二叉树是另外一种树形结构，它的特点是每个结点至二叉树是另外一种树形结构，它的特点是每个结点至多只有两棵子树（即二叉树中不存在大于多只有两棵子树（即二叉树中不存在大于2的结点），并的结点），并且，二叉树的子树有左右之分，其次序不能任意颠倒。由且，二叉树的子树有左右之分，其次序不能任意颠倒。由于二叉树的左右子树也是二叉树，则由二叉树的定义，它于二叉树的左右子树也是二叉树，则由二叉树的

8、定义，它们也可以是空树，由此，二叉树可以有五种基本形态，如们也可以是空树，由此，二叉树可以有五种基本形态，如下图所示。下图所示。（1）二叉树的定义）二叉树的定义二叉树的二叉树的5种基本形态种基本形态（2）满二叉树和完全二叉树的定义）满二叉树和完全二叉树的定义1243567满二叉树：在一棵二叉树中，如果所满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上。并且所有叶子结点都在同一层上。124356完全二叉树：如果一棵具完全二叉树：如果一棵具有有n个结点的二叉树的结构个结点的二叉树的结构与满二叉树的前与满二叉树的前n个结点的

9、个结点的结构相同，这样的二叉树称结构相同，这样的二叉树称作完全二叉树。作完全二叉树。（3）二叉树的性质）二叉树的性质 性质性质1： 若规定根结点的层次为若规定根结点的层次为1，则一颗非空二叉树的第，则一颗非空二叉树的第i层层上最多有上最多有2i-1（i=1)个结点。个结点。 该性质可以用数许归纳法来证明：该性质可以用数许归纳法来证明：第一步：当层次第一步：当层次n=1是，二叉树在根结点只有一个结点，是，二叉树在根结点只有一个结点，21-1=1，结论成立；结论成立；第二步：假设当层次第二步：假设当层次n=t时结论成立，即在第时结论成立，即在第t层上最多有层上最多有2t-1个结个结点；点；第三步：

10、当层次第三步：当层次n=t+1时，根据二叉树的定义，第时，根据二叉树的定义，第t层上的每个结层上的每个结点最多有点最多有2个子结点，所以在第个子结点，所以在第t+1成上最多有成上最多有2*2t-1=2(t+1)-1个结点。个结点。因此，结论成立。因此，结论成立。性质性质2： 若规定空树的深度为若规定空树的深度为0，则，则深度为深度为h的二叉树最大结点个数的二叉树最大结点个数（至多）是（至多）是2h-1个结点（个结点（h00)。证明：证明： 当深度为当深度为=0时是空二叉树，空二叉树应当一个结点也没有；时是空二叉树，空二叉树应当一个结点也没有； 当深度当深度h0时是非空二叉树，要求最大结点个数，

11、只要该时是非空二叉树，要求最大结点个数，只要该二叉树的每一层都达到最大，这样，可以利用性质二叉树的每一层都达到最大，这样，可以利用性质1来计算，来计算，计算过程如下：计算过程如下： i=02i-1=2h-1h第第6层就是满的，且第层就是满的，且第6层的最后八个结点没有孩子结点，其它的层的最后八个结点没有孩子结点，其它的都有左右孩子结点。都有左右孩子结点。 26163第第6层上最多有层上最多有2i12612532 32824 24*2=48 48+63=111性质性质3：对任何一颗二叉树对任何一颗二叉树T，如果其终端结点数如果其终端结点数 为为n0,度为度为2的结点的结点数为数为n2，则则n0=

12、n2+1. 证明：设二叉树度为证明：设二叉树度为1的结点个数为的结点个数为n1，二叉树的结点总数为二叉树的结点总数为n， 则有：则有： n=n0+n1+n2 具有具有n个结点的二叉树共有个结点的二叉树共有n-1个分支，这个分支，这n-1个分支分别是由度为个分支分别是由度为1和度为和度为2的结点发出的，其中每个度为的结点发出的，其中每个度为1的结点发出一个分支，度的结点发出一个分支，度为为2的结点发出的结点发出2个分支，因此，有个分支，因此，有 n-1=0*n0+1*n1+2*n2.由由1.2.两个方程，可以得到两个方程，可以得到 n0=n2+1。举例：证明由举例：证明由n个叶子结点的哈夫曼树共

13、有个叶子结点的哈夫曼树共有2n-1个结点。个结点。 设二叉树中所有非叶子结点均有非空左右设二叉树中所有非叶子结点均有非空左右子二叉树，并且叶子结点数目为子二叉树，并且叶子结点数目为n，问：二，问：二叉树中共有多少个结点？叉树中共有多少个结点？ n+n2=m (1) 2n2=m-1 (2) 联合（联合（1）（）（2），解方程可得：），解方程可得： m=2n-1性质性质4： 具有具有n(n0)个结点的完全二叉树的深度个结点的完全二叉树的深度k不超过不超过ln2(n+1)证明：由性质证明：由性质2和完全二叉树的定义可知，对于有和完全二叉树的定义可知，对于有n个结点的深度个结点的深度为为k的完全二叉树

14、有的完全二叉树有 2k-1-1n=2k-1 2k-1n+1=2k k-1log2(n+1)1,i1,则其双亲则其双亲PARENT(i)PARENT(i)是结点是结点i/2.i/2. 2) 2)如果如果2in,2in,则结点则结点i i左孩子结点序号未左孩子结点序号未2i2i；否则序号为否则序号为i i的结点无左孩子的结点无左孩子; ; 3) 3)如果如果2i+1n2i+1n，则结点，则结点i i的右孩子结点的序号为的右孩子结点的序号为2i2i1 1；否则没有右孩子。否则没有右孩子。(4)二叉树的存储结构二叉树的存储结构 1）顺序存储结构）顺序存储结构ABDCEFGA B C D E F G 0

15、 1 2 3 4 5 6ABDCEFG 在最坏的情况下，一个深度为在最坏的情况下，一个深度为k并且只有并且只有k个结点的个结点的一路右偏的单支树（树中不存在度为一路右偏的单支树（树中不存在度为2的结点）却需要的结点）却需要长度为长度为2k-1的的 一维数组。一维数组。 结论：顺序存储适合完全二叉树（当然包括满二叉结论：顺序存储适合完全二叉树（当然包括满二叉树。）树。）AB C D E0 000 F G0 1 2 3 4 5 6 7 8 9 10 深度为深度为h的二叉树，以一维数组的二叉树，以一维数组BT12h-1作为存储结构。编写一算法，作为存储结构。编写一算法，求该二叉树的叶子结点的个数。求

16、该二叉树的叶子结点的个数。 【北航【北航1996】 int leafcount(int BT,ing h) len=pow(2,h); /计算出结点的个数计算出结点的个数2h count=0; for(int i=1;idata); /*访问根结点访问根结点*/ PreOrder(b-lchild); PreOrder(b-rchild); （b）中遍历二叉树）中遍历二叉树中序遍历二叉树中序遍历二叉树算法思想算法思想: : 若二叉树非空，则：若二叉树非空，则：(1) 中序遍历左子树中序遍历左子树(2) 访问根结点访问根结点(3) 中序遍历右子树中序遍历右子树ABDECGFvoid InOrde

17、r(BTNode *b) /*中序遍历的递归算法中序遍历的递归算法*/ if (b!=NULL) InOrder(b-lchild); printf(%c ,b-data); /*访问根结点访问根结点*/ InOrder(b-rchild); 二叉树中序遍历的递归算法实现如下：二叉树中序遍历的递归算法实现如下：（c）后遍历二叉树）后遍历二叉树后序遍历二叉树后序遍历二叉树算法思想算法思想: : 若二叉树非空，则：若二叉树非空，则：(1) 后序遍历左子树后序遍历左子树(2) 后序遍历右子树后序遍历右子树(3) 访问根结点访问根结点ABDECGF二叉树后序遍历的递归算法实现如下：二叉树后序遍历的递归

18、算法实现如下：void PostOrder(BTNode *b) /*后序遍历递归算法后序遍历递归算法*/ if (b!=NULL) PostOrder(b-lchild); PostOrder(b-rchild); printf(%c ,b-data); /*访问根结点访问根结点*/ （d）二叉树的层次遍历）二叉树的层次遍历从根结点至叶结点，从左子树至右子树的次序访问二叉树的结点。从根结点至叶结点，从左子树至右子树的次序访问二叉树的结点。ABDECGF这颗二叉树的层次遍历序列为这颗二叉树的层次遍历序列为ABCDEFG,遍历的具体算法如下：遍历的具体算法如下： 算法实现：算法实现： (1)初始

19、化一个队列，并把根结点入队列；初始化一个队列，并把根结点入队列； (2)当队列非空时，循环执行（当队列非空时，循环执行（3）（）（5）；否）；否则执行（则执行（6）；）； (3)出队列取得一个结点，访问该结点；出队列取得一个结点，访问该结点； (4)如果该结点的左子树非空，则将左子树入队如果该结点的左子树非空，则将左子树入队列；列； (5)如果该结点的右子树非空，则将右子树入队如果该结点的右子树非空，则将右子树入队列；列； (6)结束结束 具体实现的算法的如下：具体实现的算法的如下：void LevelOrder(BTNode *b) BTNode *p; BTNode *quMaxSize;

20、/*定义环形队列定义环形队列,存放结点指针存放结点指针*/ int front,rear;/*定义队头和队尾指针定义队头和队尾指针*/ front=rear=-1;/*置队列为空队列置队列为空队列*/ rear+; qurear=b;/*根结点指针进入队列根结点指针进入队列*/ while (front!=rear)/*队列不为空队列不为空*/ front=(front+1)%MaxSize; p=qufront;/*队头出队列队头出队列*/ printf(%c ,p-data);/*访问结点访问结点*/if (p-lchild!=NULL)/*有左孩子时将其进队有左孩子时将其进队*/ rea

21、r=(rear+1)%MaxSize; qurear=p-lchild; if (p-rchild!=NULL)/*有右孩子时将其进队有右孩子时将其进队*/ rear=(rear+1)%MaxSize; qurear=p-rchild; 例例7.2 假设二叉树采用二叉链存储结构存储假设二叉树采用二叉链存储结构存储,试设试设计一个算法计一个算法,输出一棵给定二叉树的所有叶子结点。输出一棵给定二叉树的所有叶子结点。 解：输出一棵二叉树的所有叶子结点的递归模型解：输出一棵二叉树的所有叶子结点的递归模型f()如下：如下： f(b)：不做任何事件：不做任何事件 若若b=NULL f(b)：输出：输出*b

22、结点的结点的data域域 若若*b为叶子结点为叶子结点 f(b)：f(b-lchild);f(b-rchild) 其他情况其他情况 void DispLeaf(BTNode *b) if (b!=NULL) if (b-lchild=NULL & b-rchild=NULL) printf(%c ,b-data); else DispLeaf(b-lchild); DispLeaf(b-rchild); 课堂练习课堂练习 一、已知一颗二叉树是以二叉链表的形式一、已知一颗二叉树是以二叉链表的形式 存储的，其结点结构说明如下：存储的，其结点结构说明如下： struct node int d

23、ata; /结点的数据结点的数据 struct node *left; /左孩子的地址左孩子的地址 struct node *right; /右孩子的地址右孩子的地址 请在（请在（1）（）（2）两题的空白处进行填空，完成题目要求）两题的空白处进行填空，完成题目要求的功能。注意，每空只能填一个语句，多填为的功能。注意，每空只能填一个语句，多填为0分。（上分。（上海交通大学，海交通大学，2004 三（三（10分）分） （1）求出以）求出以T为根的二叉树或子树的结点个数。为根的二叉树或子树的结点个数。 int size(struct node *T) if( (1) ) return 0; else

24、( (2) ) ; T=NULLreturn(1+size(T-left)+size(T-ringht) （2）求出以）求出以T为根的二叉树或子树的高度。为根的二叉树或子树的高度。 int height(struct node *T) if（T=NULL）( (3) ) ; else( (4) ) ; return 0return (height(T-left)height(T-right)?:height(T-left)+1;height(T-right)+1) 二叉树的宽度：是指二叉树每层结点数的最大值。ABDECGFint BTreeWidth(NODE *root,int k) /求二

25、叉树的宽度求二叉树的宽度if(root=NULL) return 0;elsecountk+;/count数组用来保存每层结点的个数数组用来保存每层结点的个数if(mleft,k+1);BTreeWidth(root-right,k+1);return m;int BTreeWidth(NODE *root,int k) /if(root=NULL) return 0;elsecountk+;/count if(mleft,k+1);BTreeWidth(root-right,k+1);return m; int main() NODE *t; int x; pre(t); x=BTreeWi

26、dth(t,0); coutlc!=NULL&(b=0) EnQueue(Q,p-lc); else if(p-lc!=NULL)&(b=1) return FALSE; else if(p-lc=NULL&b=0) b=1; If(p-rc!=NULL&b=0) EnQueue(Q,p-rc);else if(p-rc!=NULL)&(b=1) return FALSE; else if(p-rc=NULL&b=0) b=1;Return TRUE; （4）在遍历的过程中建立二叉树）在遍历的过程中建立二叉树 “遍历遍历”是二叉树操作的基础，可以

27、在遍历的过程中对结点进行是二叉树操作的基础，可以在遍历的过程中对结点进行各种操作，如：对于一颗已知树可求结点的双亲，求结点的孩子各种操作，如：对于一颗已知树可求结点的双亲，求结点的孩子结点，求判断结点所在层等，反之，也可以在遍历过程中生成节结点，求判断结点所在层等，反之，也可以在遍历过程中生成节点，建立二叉树的存储结构。点，建立二叉树的存储结构。例如下面算法是按先序序列建立二叉树的二叉链表的过程。例如下面算法是按先序序列建立二叉树的二叉链表的过程。void PreOrderC(BTNode * &t)char c; cinc;if(c=0 ) t=NULL;elset=(BTNode*

28、)malloc(sizeof(BTNode); t-data=c; t-lchild=NULL; t-rchild=NULL; PreOrderC(t-lchild);PreOrderC(t-rchild);void levelcreat(BTNode *&t)BTNode *s20;int rear(0),front(0); BTNode *p,*q,*root;char ch,ch1,ch2;coutch;if(ch=0) exit(1);层次遍历建立二叉树层次遍历建立二叉树else root=(BTNode*)malloc(sizeof(BTNode); root-data=c;

29、 root-lchild=NULL; root-rchild=NULL; srear+=root; while(front!=rear)p=s+front;coutch1ch2;if(ch1!=0) q=(BTNode*)malloc(sizeof(BTNode); q-data=c; q-lchild=NULL; q-rchild=NULL; p-lchild=q; s+rear=q; if(ch2!=0) q=(BTNode*)malloc(sizeof(BTNode); q-data=c; q-lchild=NULL; q-rchild=NULL; p-lchild=q; s+rear=

30、q; 已知二叉树的先序序列为ABDGCEF，中序序列为DGBAECF，请画出该二叉树。ABCEDGF int creat(treenode *&root,char pre,char in,int n) int k;char *p;if(ndata=*pre; root-left=NULL;root-right=NULL;for(p=in;pleft,pre+1,in,k); creat(root-right,pre+k+1,p+1,n-k-1); 7.4.3 7.4.3 二叉树遍历非递归算法二叉树遍历非递归算法 1. 1. 中序遍历非递归算法中序遍历非递归算法中序遍历二叉树的非递归算法

31、需要使用栈作为辅助来完成。中序遍历二叉树的非递归算法需要使用栈作为辅助来完成。具体的算法描述如下：具体的算法描述如下：（a）设置一个堆栈并初始化；）设置一个堆栈并初始化；（b）使临时指针）使临时指针p指向根结点；指向根结点；（c）当）当p不为空，不为空，p被赋值为被赋值为p所指结点的左链；所指结点的左链；（d）判断）判断p是否为空，如果为空是否为空，如果为空void inorder(BTNode *&root)BTNode *p,*s20; int top=0;p=root;dowhile(p!=NULL)stop+=p; p=p-lchild;if(top!=0)p=s-top;co

32、utdatarchild;while(top!=0|p!=NULL);（2）先序遍历二叉树的非递归算法实现）先序遍历二叉树的非递归算法实现void preorder(BTNode *&root)BTNode*p,*s20;int top=0;p=root;dowhile(p!=NULL)coutdatalchild;if(p=NULL&top!=0)p=s-top;p=p-rchild;while(top!=0|p!=NULL);（3）后序遍历二叉树的非递归算法）后序遍历二叉树的非递归算法void postorder(BTNode *&root2) BTNode *p,

33、*s120;int s220,top=0,tag;p=root;doif(p!=NULL)s1top=p;s2top+=0;p=p-lchild;else while(top!=0)tag=s2-top;p=s1top;if(tag=0)s1top=p;s2top+=1;p=p-rchild;break;else if(tag=1) coutdata;while(p!=root&top!=0);7.8 哈夫曼树哈夫曼树BGFCDAE例例ABE 为结点为结点A到到E之间的路径，之间的路径，其路径长度为其路径长度为2，（1）路径长度）路径长度 由树中一个结点到另一个结点的分支构成这两由树中

34、一个结点到另一个结点的分支构成这两个结点之间的路径，路径上分支的数目称为路径长度。个结点之间的路径，路径上分支的数目称为路径长度。树的路径长度树的路径长度=lAD +lAE+ lAF +lAG =2+2+2+2=8（2）树的路径长度）树的路径长度 从根结点到每个结点的路径长度之和。从根结点到每个结点的路径长度之和。BGFCDAE例例 （3）结点的带）结点的带权权路径长度路径长度 从根结点到某个结点的路径从根结点到某个结点的路径长度与该结点所带的权值的乘积。长度与该结点所带的权值的乘积。结点结点a的带权路径长度为的带权路径长度为17，结点，结点b的带权路径长度为：的带权路径长度为：25 （4）树

35、的带权路径长度）树的带权路径长度 树中所有叶子结点的带权路径树中所有叶子结点的带权路径长度之和，通常记作：长度之和，通常记作： 该树的带权路径长度为：该树的带权路径长度为：7152234335（5）哈夫曼树）哈夫曼树 考虑带权时：设树中有考虑带权时：设树中有m个叶结点，每个叶结点带一个权值个叶结点，每个叶结点带一个权值w,且根到叶结点且根到叶结点i的路径长度为的路径长度为 Li (=1，2， m），则树），则树的带权路径长度为树中所有叶结点的权值与路径长度的乘积的的带权路径长度为树中所有叶结点的权值与路径长度的乘积的总和。总和。 即：即： 使使WPL最小的二叉树成为最优二叉树最小的二叉树成为最

36、优二叉树(Huffman 树树)B BD DA AC C7 5 2 47 5 2 4A AC C D DB B4 47 75 52 2WPL=7WPL=7* *2+52+5* *2+22+2* *2+42+4* *2=362=36WPL=7WPL=7* *3+53+5* *3+23+2* *1+41+4* *2=462=46例例1： 有有4个结点个结点A，B，C，D，权值分别为，权值分别为7，5，2和和4，分别，分别 以这以这4个结点作为叶子结点，构造不同形态的二叉树并计算其个结点作为叶子结点，构造不同形态的二叉树并计算其WPL值。值。C CA A B BD D4 47 75 52 2WPL=

37、7WPL=7* *1+51+5* *2+22+2* *3+43+4* *3=353=35可以验证，最后这个二叉树为哈夫曼树。可以验证，最后这个二叉树为哈夫曼树。例例2 : 编制一个将百分制转换成五分制的程序。编制一个将百分制转换成五分制的程序。 最直观的方法是利用最直观的方法是利用if语句来实现。可用二叉树描述判定过程。语句来实现。可用二叉树描述判定过程。a a 80 80a a 90 90不及格不及格良好良好中等中等及格及格优秀优秀a a 60 60a a 70 70 设有设有10000个百分制分数要转换，设学生成绩在个百分制分数要转换，设学生成绩在5个等级上的个等级上的分布如下：分布如下：

38、分数分数 0-59 60-69 70-79 80-89 90-1000-59 60-69 70-79 80-89 90-100比例数比例数 0.05 0.15 0.40 0.30 0.100.05 0.15 0.40 0.30 0.10按上图的判定过程按上图的判定过程: 转换一个分数所需的比较次数转换一个分数所需的比较次数= 从根到对应结点的路径长度。从根到对应结点的路径长度。a a 80 80a a 90 90不及格不及格良好良好中等中等及格及格优秀优秀a a 60 60a a 70 70转换转换10000个分数所需的总比较次数个分数所需的总比较次数= 10000 (0.05 1+0.15

39、2+0.4 3+0.3 4+0.1 4） =31500 分数分数 0-59 60-69 70-79 80-89 90-1000-59 60-69 70-79 80-89 90-100比例数比例数 0.05 0.15 0.40 0.30 0.100.05 0.15 0.40 0.30 0.10转换转换10000个分数所需的总比较次数个分数所需的总比较次数= 10000 (0.05 3+0.15 3+0.4 2+0.3 2+0.1 2）=22000分数分数 0-59 60-69 70-79 80-89 90-1000-59 60-69 70-79 80-89 90-100比例数比例数 0.05 0

40、.15 0.40 0.30 0.100.05 0.15 0.40 0.30 0.103 哈夫曼树的构造算法哈夫曼树的构造算法（1）以权值分别为）以权值分别为W1,W2的个结点，构成的个结点，构成n棵二叉棵二叉树树T1,T2,Tn并组成森林并组成森林F=T1,T2,Tn,其中每棵二叉其中每棵二叉树树 Ti仅有一个权值为仅有一个权值为 Wi的根结点；的根结点；（2）在）在F中选取两棵根结点权值最小的树作为左右子树构造一中选取两棵根结点权值最小的树作为左右子树构造一棵新二叉树，并且置新二叉树根结点权值为左右子树上根结点棵新二叉树，并且置新二叉树根结点权值为左右子树上根结点的权值之和；的权值之和；（3

41、）从）从F中删除这两棵二叉树，同时将新二叉树加入到中删除这两棵二叉树，同时将新二叉树加入到F中中;（4）重复）重复(2)()直到直到F中只含一棵二叉树为止，这棵二叉树中只含一棵二叉树为止，这棵二叉树就是就是Huffman 树。树。9例3: 已知权值 W= 5, 6, 2, 9, 7 56272576976713925767139257925716671329HT不唯一性不唯一性,可能出现在可能出现在:（1）构造新树时，左、右孩子未作规定。）构造新树时，左、右孩子未作规定。（2）当有多个权值相同的树可作有候选树时，选择）当有多个权值相同的树可作有候选树时，选择谁未作规定。谁未作规定。257697

42、4 4 哈夫曼编码（哈夫曼编码（ HuffmanHuffman树的应用之二树的应用之二在通信中）在通信中）（1）问题的提出）问题的提出 通讯中常需要将文字转换成二进制字符串通讯中常需要将文字转换成二进制字符串“电文电文”进进行传送。文字行传送。文字 反之，收到电文后要将电文转换成原来的文字，反之，收到电文后要将电文转换成原来的文字，电文电文电文，称为电文，称为编码编码。文字，称为文字，称为译码译码。例如：需将文字例如：需将文字“ABACCDA”转换成电文。文之转换成电文。文之中有四种字符，用中有四种字符，用2位二进制便可分辨。位二进制便可分辨。 A B C D00 01 10 11编码方案编码

43、方案1：则上述文字的电文为：则上述文字的电文为：00010010101100 共共14位。位。译码时，只需每译码时，只需每2位一译即可。位一译即可。特点：等长等频率编码，译码容易，但电文不一定最短特点：等长等频率编码，译码容易，但电文不一定最短。 A B C D0 00 1 01编码方案编码方案2： 采用不等长编码，让出现次数多的字符用短码。采用不等长编码，让出现次数多的字符用短码。 则上述文字则上述文字ABACCDA”的电文为：的电文为：000011010 共共9位。位。 但无法译码，它即可译为但无法译码，它即可译为BBCCACA，也可译为，也可译为AAAACCDA等。等。 A B C D0

44、 110 10 111编码方案编码方案3： 采用不等长编码，让出现次数多的字符用短码，采用不等长编码，让出现次数多的字符用短码，且任一编码不能是另一编码的前缀。且任一编码不能是另一编码的前缀。前缀编码前缀编码则上述文字则上述文字ABACCDA”的电文为：的电文为：0110010101110 共共13位。位。设有设有n种字符，每种字符出现的次数为种字符，每种字符出现的次数为Wi ,其编码长度为其编码长度为Li (i=1,2,n)，则整个电文总长度为则整个电文总长度为 Wi Li ，要得到最短的电文，即使得要得到最短的电文，即使得 Wi Li最小。最小。也就是以字符出现的次数为权值，构造一棵也就是

45、以字符出现的次数为权值，构造一棵 Huffman树，并树，并规定左分支编码位规定左分支编码位0，右分支编码为，右分支编码为1，则字符的编码就是从，则字符的编码就是从根到该字符所在的叶结点的路径上的分支编号序列。根到该字符所在的叶结点的路径上的分支编号序列。用构造用构造Huffman树编出来的码，称为树编出来的码，称为Huffman编码。编码。 例例5 已知某系统在通信联络中只可能出现八种字符，其概率已知某系统在通信联络中只可能出现八种字符，其概率分别为分别为0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11，试设，试设计哈夫曼编码。计哈夫曼编码。2342871514

46、292958100001111901538011111000编码：编码：0.05 00010.29 100.07 11100.08 11110.14 1100.23 01 0.03 00000.11 0015 5 哈夫曼编码问题数据结构设计哈夫曼编码问题数据结构设计 哈夫曼树的特点是不存在度为哈夫曼树的特点是不存在度为1的最优二叉树，且哈夫曼编码的最优二叉树，且哈夫曼编码问题主要涉及到父结点，左右孩子结点的操作，因此用一维数问题主要涉及到父结点，左右孩子结点的操作，因此用一维数组顺序存储哈夫曼树，此数组为结构体数组。组顺序存储哈夫曼树，此数组为结构体数组。 有有n个叶子结点的哈夫满树，共有多少

47、个结点？个叶子结点的哈夫满树，共有多少个结点？ 上图所示二叉树的存储结构的初始状态为图一所示，其终结状上图所示二叉树的存储结构的初始状态为图一所示，其终结状态为图二所示。态为图二所示。？2n-101234567891011121314weight parent lchild rchild flag图图101234567891011121314weight parent lchild rchild flag图图2void haffman(int weight,int n,haffnode hafftree)int j,m1,m2,x1,x2;for(int i=0;i2*n-1;i+)if(in) hafftreei.weight=weighti;else hafftreei.weight=0;hafftreei.parent=0;hafftreei.flag=0;hafftreei.leftchild=-1;hafftreei.rightchild=-1;for(i=0;in-1;i+)m1=m2=maxvalue;x1=x2=0;for(j=0;jn+i;j+)if(hafftree