数据结构(C语言版)6、树和二叉树.ppt

《数据结构(C语言版)6、树和二叉树.ppt》由会员分享，可在线阅读，更多相关《数据结构(C语言版)6、树和二叉树.ppt（100页珍藏版）》请在三一办公上搜索。

1、第6章 树和二叉树,本章中主要介绍下列内容：树的逻辑定义和基本术语 二叉树的逻辑定义及存储结构 二叉树的基本操作算法（*遍历算法）树、森林和二叉树的转换 哈夫曼树及其应用,6.树的逻辑定义和基本术语6.1 树6.2 二叉树6.3 树、森林与二叉树的转换6.3 哈夫曼树及其应用,6.1 树_TREE,6.1.1 树的定义和基本运算mathematical concept-Abstract data type-Data structure-Implementation-Application1.定义:树是一种常用的非线性结构。我们可以这样定义：树是n（n0）个结点的有限集合。若n=0，则称为空树；

2、否则，有且仅有一个特定的结点被称为根，当n1时，其余结点被分成m（m0）个互不相交的子集T1，T2，.，Tm，每个子集又是一棵树。由此可以看出，树的定义是递归。,图 6-1,E F G H I J,B C D,A,A,(a),(b),(c),结点(node/vertex)数据元素的内容及其指向其子树根的分支统称为结点。结点的度(degree)结点的分支数。终端结点（叶子leaf）度为0的结点。非终端结点 度不为0的结点。结点的层次(level)树中根结点的层次为1，根结点子树的根为第2层，以此类推。树的度 树中所有结点度的最大值。树的深度depth 树中所有结点层次的最大值。有序树(order

3、ed tree)、无序树 如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树。,森林(forest)是m（m0）棵互不相交的树的集合。在树结构中，结点之间的关系又可以用家族关系描述，定义如下：孩子child、双亲parent 结点子树的根称为这个结点的孩子，而这个结点又被称为孩子的双亲。结点的子孙 descendant 以某结点为根的子树中的所有结点都被称为是该结点的子孙。结点的祖先ancestor 从根结点到该结点路径上的所有结点。兄弟sibling 同一个双亲的孩子之间互为兄弟。堂兄弟 双亲在同一层的结点互为堂兄弟。,2.树的基本运算 常用操作：（1）构造

4、一个树 CreateTree(T)（2）清空以T为根的树 ClearTree(T)（3）判断树是否为空 TreeEmpty(T)（4）获取给定结点的第i个孩子 Child(T,node,i)（5）获取给定结点的双亲 Parent(T,node)（6）遍历树Traverse(T)对树遍历的主要目的是将非线性结构通过遍历过程线性化，即获得一个线性序列。树的遍历顺序有两种，一种是先序遍历，即先访问根结点，然后再依次用同样的方法访问每棵子树；另一种是后序遍历，即先依,6.1.2 树的存储结构 应用一段连续的存储空间存储树，要求存储结构能表示逻辑结构，即满足树的定义，即同一结点有多个不同的后继，或多个结

5、点具有同一前驱，并且不存在相交的子树。1.双亲表示法:树的双亲表示法主要描述的是结点的双亲关系，不但要存储树中结点数据元素本身的值，而且要存储结点双亲所在的位置。如图2所示：,图 6-2根结点A存储于第0位置，无双亲，故双亲的存储位置标志设置为-1,结点B C D依次存储于1 2 3位置，其双亲所在位置是0;.,类型定义：#define MAX_TREE_NODE_SIZE 100typedef struct ParentNode EelemType info;/树中数据元素数据类型 int parent;/其双亲结点的存储位置;typedef struct ParentTree Parent

6、Node itemMAX_TREE_NODE_SIZE;int n;/树中当前的结点数目;,这种存储方法的特点是寻找结点的双亲很容易，但寻找结点的孩子比较困难。算法实现举例,求双亲结点所在位置：int Parent(ParentTree T,int node)/返回第node个结点的双亲所在的位置 if(node=T.n)return-1;else printf(“parent elem is:%?”,T.itemparent.info);return T.itemnode.parent;,双亲表示法数据类型进一步解释：ParentTree数据类型有两个域，即 ParentTree.item

7、和ParentTree.n;每一个item i有两个域，即数据元素的数值info和双亲所在位置parent;结合图 6-2存储示意图如下：ParentTree.n=10/树中有10个结点ParentTree.item 域示意图如下：,2.孩子表示法 孩子表示法主要描述的是结点的孩子关系。由于每个结点的孩子个数不定，所以利用链式存储结构更加适宜。举例：,图 6-3 孩子表示法结构示意图 显然ChildNode和TNode不时同类型的结点.,0 A 1 2 3 1 B 4 5 2 C 3 D 4 E 5 F 6 G 7 8 9 7 H 8 I 9 J,ChildNode,TNode,ChildTr

8、ee,在C语言中，这种存储形式定义如下：#define MAX_TREE_NODE_SIZE 10typedef struct ChildNode int child;/该孩子结点在一维数组中的下标值 struct ChileNode*next;/指向下一个孩子结点;typedef struct TNode TElemType data;/结点信息 ChildNode*firstchild;/指向第一个孩子结点的指针;,typedef struct ChildTree TNode itemMAX_TREE_NODE_SIZE;int n,root;/n为树中当前结点的数目，root为根结点在一

9、维数组中的位置;这种存储结构的特点是寻找某个结点的孩子比较容易，但寻找双亲比较麻烦，所以，在必要的时候，可以将双亲表示法和孩子表示法结合起来，即将一维数组元素增加一个表示双亲结点的域parent，用来指示结点的双亲在一维数组中的位置。,孩子表示法数据类型进一步解释:,ChildTree结构体数据类型包含三个域:TNode类型的一维数组、树中当前结点的总数n、树根所在的位置root,示意图如下：,数组中的每一个数据元素有2个域：结点本身的数值data,指向第一个孩子的指针；,next指针所指向的存储空间ChildNode又有两个域：孩子结点所在数组的下标值，指向下一个孩子结点的指针。,获取给定结

10、点第i个孩子的操作算法实现：int Child(ChildTree T,int node,int i)/求树T中第node个结点的第i个孩子所在的位置 if(node=T.n)return-2；p=T.itemnode.firstchild;j=1;while(p/返回第i个孩子所在的位置,3.孩子兄弟表示法(树、森林转换为二叉树的方法)孩子兄弟表示法也是一种链式存储结构。它通过描述每个结点的一个孩子和兄弟信息来反映结点之间的层次关系，其结点结构为：,其中，firstchild为指向该结点第一个孩子的指针，nextsibling为指向该结点的下一个兄弟，item是数据元素内容。举例：,树型结构

11、如下：,孩子兄弟表示法存储结构示意图如下：,图 6-4 孩子兄弟标示方法一个结点的左子树当作是该结点的孩子，右子树当作是该结点的兄弟；,在C语言中，这种存储形式定义如下：typedef struct CSNode ElemType item;struct CSNode*firstchild,*nextsibling;*CSTree;/CSTree存放的是CSNode这种结点的地址；void AllChild(CSTree T,CSTree p)/输出树中p指针所指结点的所有孩子信息/输出结点的第一个孩子及第一个孩子的兄弟 q=p-fisrtchild;while(q)printf(“%c”,q

12、-item);q=q-nextsibling;,.2 二叉树(Binary tree),.2.1 二叉树的定义和基本运算1.定义 定义：二叉树是另一种树形结构。它与树形结构的区别是：（1）每个结点最多有两棵子树；（2）子树有左右之分。二叉树也可以用递归的形式定义。即：二叉树是n（n0）个结点的有限集合。当n=0时，称为空二叉树；当n0时，有且仅有一个结点为二叉树的根，其余结点被分成两个互不相交的子集，一个作为左子集，另一个作为右子集，每个子集又是一个二叉树。,图 6-6 二叉树示意图,G H,D E F,B C,A,二叉树的5种形态：,图 6-7,(a),(b),(c),(d),(e),2.二

13、叉树的基本运算（1）构造一棵二叉树 CreateBTree(BT)（2）清空以BT为根的二叉树 ClearBTree(BT)（3）判断二叉树是否为空 BTreeEmpty(BT)（4）获取给定结点的左孩子和右孩子LeftChild(BT,node)，RightChild(BT,node)（5）获取给定结点的双亲 Parent(BT,node)（6）遍历二叉树Traverse(BT),2二叉树的性质二叉树具有下列5个重要的性质。【性质1】在二叉树的第i层上最多有2i-1个结点（i1）。二叉树的第1层只有一个根结点，所以，i=1时，2i-1=21-1=20=1成立。假设对所有的j，1ji成立，即第

14、j层上最多有2j-1个结点成立。若j=i-1，则第j层上最多有2j-1=2i-2个结点。由于在二叉树中，每个结点的度最大为2，所以可以推导出第i层最多的结点个数就是第i-1层最多结点个数的2倍，即2i-2*2=2i-1。,【性质2】深度为K的二叉树最多有2K-1个结点（K1）。由性质1可以得出，1至K层各层最多的结点个数分别为：20,21,22,23,.,2K-1。这是一个以2为比值的等比数列，前n项之和的计算公式为：,其中 a1为第一项，an为第n项，q为比值。可以得到，该数列前K项之和为：,【性质3】对于任意一棵二叉树BT，如果度为0的结点个数为n0，度为2的结点个数为n2，则n0=n2+

15、1。证明：假设度为1的结点个数为n1，结点总数为n，B为二叉树中的分支数。因为在二叉树中，所有结点的度均小于或等于2，所以结点总数为：n=n0+n1+n2（1）再查看一下分支数。在二叉树中，除根结点之外，每个结点都有一个从上向下的分支指向该结点，所以，总的结点个数n与分支数B之间的关系为：n=B+1。,又因为在二叉树中，度为1的结点产生1个分支，度为2的结点产生2个分支，所以分支数B可以表示为：B=n1+2n2。将此式代入上式，得：n=n1+2n2+1（2）用（1）式减去（2）式，并经过调整后得到：n0=n2+1。满二叉树：如果一个深度为K的二叉树拥有2K-1个结点，则将它称为满二叉树。,图

16、6-8,8 9 10 11 12 13 14 15,4 5 6 7,2 3,1,完全二叉树：有一棵深度为h，具有n个结点的二叉树，若将它与一棵同深度的满二叉树中的所有结点按从上到下，从左到右的顺序分别进行编号，且该二叉树中的每个结点分别与满二叉树中编号为1n的结点位置一一对应，则称这棵二叉树为完全二叉树。,【性质4】具有n个结点的完全二叉树的深度为 log2n+1。其中，log2n 的结果是不大于log2n的最大整数。证明：假设具有n个结点的完全二叉树的深度为K，则根据性质2可以得出：2K-1-1n2K-1 将不等式两端加1得到：2K-1n2K 将不等式中的三项同取以2为底的对数，并经过化简后

17、得到：K-1log2nK 由此可以得到：log2n=K-1。整理后得到：K=log2n+1。,【性质5】对于有n个结点的完全二叉树中的所有结点按从上到下，从左到右的顺序进行编号，则对任意一个结点i（1in），都有：（1）如果i=1，则结点i是这棵完全二叉树的根，没有双亲；否则其双亲结点的编号为 i/2。（2）如果2in，则结点i没有左孩子；否则其左孩子结点的编号为2i。（3）如果2i+1n，则结点i没有右孩子；否则其右孩子结点的编号为2i+1。下面我们利用数学归纳法证明这个性质。我们首先证明（2）和（3）。当i=1时，若n3，则根的左、右孩子的编号分别是2，3；若n3，则根没有右孩子；若n2，

18、则根将没有左、右孩子；以上对于（2）和（3）均成立。假设：对于所有的1ji 结论成立。即：结点j的左孩子编号为2j；右孩子编号为2j+1。,图 6-10,2i+2,2i 2i+1 2i+2 2i+3 i+1 2i 2i+1,i,i i+1,由完全二叉树的结构可以看出：结点i+1或者与结点i同层且紧邻i结点的右侧，或者i位于某层的最右端，i+1位于下一层的最左端。可以看出，i+1的左、右孩子紧邻在结点i的孩子后面，由于结点i 的左、右孩子编号分别为2i和2i+1，所以，结点i+1的左、右孩子编号分别为2i+2和2i+3，经提取公因式可以得到：2(i+1)和2(i+1)+1，即结点i+1的左孩子编

19、号为2(i+1)；右孩子编号为2(i+1)+1。又因为二叉树由n个结点组成，所以，当2(i+1)+1n，且2(i+1)=n时，结点i+1只有左孩子，而没有右孩子；当2(i+1)n，结点i+1既没有左孩子也没有右孩子。,以上证明得到（2）和（3）成立。下面利用上面的结论证明（1）。对于任意一个结点i，若2in，则左孩子的编号为2i，反过来结点2i的双亲就是i，而 2i/2=i；若2i+1n，则右孩子的编号为2i+1，反过来结点2i+1的双亲就是i，而(2i+1)/2=i，由此可以得出（1）成立。,二叉树的存储结构 二叉树也可以采用两种存储方式：顺序存储结构和链式存储结构。1.顺序存储结构 这种存

20、储结构适用于完全二叉树。其存储形式为：用一组连续的存储单元按照完全二叉树的每个结点编号的顺序存放结点内容。下面是一棵二叉树及其相应的存储结构。,图 6-11,8,4 5 6 7,2 3,1,二叉树的顺序存储数据类型说明：,#define MAX_TREE_SIZE 100typedep Telemtype SqbiTreeMAX_TREE_SIZE/0号单元存放二叉树中结点总数SqbiTree bt;/bt是一维数组,（1）构造一棵有n个结点的完全二叉树SqbiTree*CreateBTree(TelemType item,int n)if(n=MAX_TREE_NODE_SIZE)n=MAX

21、_TREE_NODE_SIZE-1;/不允许超过最大结点数 for(i=1;i=n;i+)scanf(“%?”,/&item0,（2）获取给定结点的左孩子 int LeftCHild(TelemType*BT,int node)/BT是一维数组的首地址 if(2*nodeBT0)return 0;else return BT2*node;RightChild(BT,node)与这个操作类似，读者可试着自行完成。,（3）获取给定结点的双亲 int Parent(QBTree*BT,int node)if(node=1)printf(“root no parent!n”);exit(-1)if(1

22、node,32 链式存储结构 在顺序存储结构中，利用编号表示元素的位置及元素之间孩子或双亲的关系，因此对于非完全二叉树，需要将空缺的位置用特定的符号填补，若空缺结点较多，势必造成空间利用率的下降。在这种情况下，就应该考虑使用链式存储结构。常见的二叉树结点结构如下所示：,图 6-12,其中，Lchild和Rchild是分别指向该结点左孩子和右孩子的指针，item是数据元素的内容。在C语言中的类型定义为：typedef struct BTNode ElemType item;struct BTNode*Lchild,*Rchlid;BTNode,*BTree;/树根地址BTree 下面是一棵二叉树

23、及相应的链式存储结构。,图 6-13,G H,D E F,B C,A,G H,D E F,B C,A,BT,这种存储结构的特点是寻找孩子结点容易，双亲比较困难。因此，若需要频繁地寻找双亲，可以给每个结点添加一个指向双亲结点的指针域，其结点结构如下所示。,图 6-14,有关二叉树在链式存储结构下的操作算法将在随后介绍。,5.2.4 遍历二叉树 二叉树是一种非线性的数据结构，在对它进行操作时，总是需要逐一对每个数据元素实施操作，这样就存在一个操作顺序问题，由此提出了二叉树的遍历操作。所谓遍历二叉树就是按某种顺序访问二叉树中的每个结点一次且仅一次的过程。这里的访问可以是输出、比较、更新、查看元素内容

24、等等各种操作。二叉树的遍历方式分为两大类：一类按根、左子树和右子树三个部分进行访问；另一类按层次访问。下面我们将分别进行讨论。,1.按根、左子树和右子树三部分进行遍历 遍历二叉树的顺序存在下面6种可能：TLR（根左右）,TRL（根右左）LTR（左根右）,RTL（右根左）LRT（左右根）,RLT（右左根）其中，TRL、RTL和RLT三种顺序在左右子树之间均是先右子树后左子树，这与人们先左后右的习惯不同，因此，往往不予采用。余下的三种顺序TLR、LTR和LRT根据根访问的位置不同分别被称为先序遍历、中序遍历和后序遍历。,（1）先序遍历若二叉树为空，则结束遍历操作；否则访问根结点；先序遍历左子树；先

25、序遍历右子树。（2）中序遍历若二叉树为空，则结束遍历操作；否则中序遍历左子树；访问根结点；中序遍历右子树。,（3）后序遍历若二叉树为空，则结束遍历操作；否则后序遍历左子树；后序遍历右子树；访问根结点。下面是一棵二叉树及其经过三种遍历得到的相应序列。,G H,D E F,B C,A,先序序列：ABDGCEFH中序序列：DGBAECHF后序序列：GDBEHFCA,图 6-15,下面我们再给出两种遍历二叉树的方法：（1）对一棵二叉树中序遍历时，若我们将二叉树严格地按左子树的所有结点位于根结点的左侧，右子树的所有结点位于根右侧的形式绘制，就可以对每个结点做一条垂线，映射到下面的水平线上，由此得到的顺序

26、就是该二叉树的中序遍历序列。,D G B A E C H F,G H,D E F,B C,A,图 6-16,（2）任何一棵二叉树都可以将它的外部轮廓用一条线绘制出来，我们将它称为二叉树的包线，这条包线对于理解二叉树的遍历过程很有用。,G H,D E F,B C,A,图 6-17,由此可以看出：（1）遍历操作实际上是将非线性结构线性化的过程，其结果为线性序列，并根据采用的遍历顺序分别称为先序序列、中序序列或后序序列；（2）遍历操作是一个递归的过程，因此，这三种遍历操作的算法可以用递归函数实现。（1）先序遍历递归算法 void PreOrder(BTree BT)if(BT)Visit(BT);P

27、reOrder(BT-Lchild);PreOrder(BT-Rchild);,（2）中序遍历递归算法void InOrder(BTree BT)if(BT)InOrder(BT-Lchild);Visit(BT);InOrder(BT-Rchild);,（3）后序遍历递归算法void PostOrder(BTree BT)if(BT)PostOrder(BT-Lchild);PostOrder(BT-Rchild);Visit(BT);,2.按层次遍历二叉树 实现方法为从上层到下层，每层中从左侧到右侧依次访问每个结点。下面我们将给出一棵二叉树及其按层次顺序访问其中每个结点的遍历序列。,图 6

28、-19,按层次遍历该二叉树的序列为：ABCDEFGH,二叉树用顺序存储结构表示时，按层遍历的算法实现,(a),(b),图 6-20,void LevelOreder(QBTree BT)for(i=1;i=BT.n;i+)if(BT.itemi!=#)Visite(BT.itemi);二叉树用链式存储结构表示时，按层遍历的算法实现,访问过程描述如下：访问根结点，并将该结点记录下来；若记录的所有结点都已处理完毕，则结束遍历操作；否则重复下列操作。取出记录中第一个还没有访问孩子的结点，若它有左孩子，则访问左孩子，并将记录下来；若它有右孩子，则访问右孩子，并记录下来。,在这个算法中，应使用一个队列结

29、构完成这项操作。所谓记录访问结点就是入队操作；而取出记录的结点就是出队操作。这样一来，我们的算法就可以描述成下列形式：（1）访问根结点，并将根结点入队；（2）当队列不空时，重复下列操作：从队列退出一个结点；若其有左孩子，则访问左孩子，并将其左孩子入队；若其有右孩子，则访问右孩子，并将其右孩子入队；,void LevelOrder(BTree*BT)if(!BT)exit;InitQueue(Q);p=BT;/初始化 Visite(p);EnQueue(/处理右孩子,6.2.5 典型二叉树的操作算法 1.输入一个二叉树的先序序列，构造这棵二叉树 为了保证唯一地构造出所希望的二叉树，在键入这棵树的

30、先序序列时，需要在所有空二叉树的位置上填补一个特殊的字符，比如，#。在算法中，需要对每个输入的字符进行判断，如果对应的字符是#，则在相应的位置上构造一棵空二叉树；否则，创建一个新结点。整个算法结构以先序遍历递归算法为基础，二叉树中结点之间的指针连接是通过指针参数在递归调用返回时完成。,【算法6-12】BTree Pre_Create_BT()getch(ch);if(ch=#)return NULL;/构造空树 else BT=(BTree)malloc(sizeof(BTNode);/构造新结点 BT-data=ch;BT-lchild=Pre_Create_BT();/构造左子树 BT-r

31、child=Pre_Create_BT();/构造右子树 return BT;,2.计算一棵二叉树的叶子结点数目 这个操作可以使用三种遍历顺序中的任何一种，只是需要将访问操作变成判断该结点是否为叶子结点，如果是叶子结点将累加器加1即可。下面这个算法是利用中序遍历实现的。,【算法6-13】void Leaf(BTree BT,int*count)if(BT)Leaf(BT-child,/计算右子树的叶子结点个数,63 交换二叉树的左右子树 许多操作可以利用三种遍历顺序的任何一种，只是某种遍历顺序实现起来更加方便一些。而有些操作则不然，它只能使用其中的一种或两种遍历顺序。将二叉树中所有结点的左右子

32、树进行交换这个操作就属于这类情况。void change_left_right(BTree BT)if(BT)change_left_right(BT-lchild);change_left_right(BT-rchild);BT-lchildBT-rchild;,64 求二叉树的高度 这个操作使用后序遍历比较符合人们求解二叉树高度的思维方式。首先分别求出左右子树的高度，在此基础上得出该棵树的高度，即左右子树较大的高度值加1。int hight(BTree BT)/h1和h2分别是以BT为根的左右子树的高度 if(BT=NULL)return 0;else h1=hight(BT-lchild

33、);h2=hight(BT-right);return maxh1,h2+1;,6.2.6 树、森林与二叉树的转换 1.树、森林转换成二叉树 将一棵树转换成二叉树的方法：将一棵树转换成二叉树实际上就是将这棵树用孩子兄弟表示法存储即可，此时，树中的每个结点最多有两个指针：一个指针指向第一个孩子，另一个指针指向右侧第一个兄弟。当你将这两个指针看作是二叉树中的左孩子指针和孩子右指针时，就是一棵二叉树了。,特点：一棵树转换成二叉树后，根结点没有右孩子。将森林转换成二叉树的方法与一棵树转换成二叉树的方法类似，只是把森林中所有树的根结点看作兄弟关系，并对其中的每棵树依依地进行转换。,2.二叉树还原成树或森

34、林 这个过程实际上是树、森林转换成二叉树的逆过程，即将该二叉树看作是树或森林的孩子兄弟表示法。比如，若二叉树为空，树也为空；否则，由二叉树的根结点开始，延右指针向下走，直到为空，途经的结点个数是相应森林所含树的棵数；若某个结点的左指针非空，说明这个结点在树中必有孩子，并且从二叉树中该结点左指针所指结点开始，延右指针向下走，直到为空，途经的结点个数就是这个结点的孩子数目。,6.3 哈夫曼树及其应用,1哈夫曼树的定义,图 6-26,G H,D E F,B C,A,在二叉树中，一个结点到另一个结点之间的分支构成这两个结点之间的路径。在路径上的分支数目被称为路径长度。用公式可表示为：,Wk:结点的权重

35、,Lk:路径长度;,带权的路径长度最小的二叉树称为哈夫曼二叉树或最优二叉树。,5,4,8,图6-27 叶子结点带权值的二叉树,下面我们讨论一下权值、树形与带权的路径长度之间的关系。假设有6个权值分别为3，6，9，10，7，11，以这6个权值作为叶子结点的权值可以构造出下面三棵二叉树。,3 6 7 9,10 11,(a),图 6-28,11,10,9,7,6,3,11,10,3,6,7,9,(b),(c),这三棵二叉树的带权路径长度分别为：WPL1=10*2+11*2+3*3+6*3+7*3+9*3=117WPL2=3*1+6*2+7*3+9*4+10*5+11*5=177WPL3=9*1+7*

36、2+6*3+3*4+10*5+11*5=158,构造哈夫曼树的过程：（1）将给定的n个权值w1,w2,.,wn作为n个根结点的权值构造一个具有n棵二叉树的森林T1,T2,.,Tn，其中每棵二叉树只有一个根结点；（2）在森林中选取两棵根结点权值最小的二叉树作为左右子树构造一棵新二叉树，新二叉树的根结点权值为这两棵树根的权值之和；（3）在森林中，将上面选择的这两棵根权值最小的二叉树从森林中删除，并将刚刚新构造的二叉树加入到森林中；,（4）重复上面（2）和（3），直到森林中只有一棵二叉树为止。这棵二叉树就是哈夫曼树。假设有一组权值5,29,7,8,14,23,3,11，下面我们将利用这组权值演示构造

37、哈夫曼树的过程。第一步：以这8个权值作为根结点的权值构造具有8棵树的森林,5 29 7 8 14 23 3 11,第二步：从中选择两个根的权值最小的树3，5作为左右子树构造一棵新树，并将这两棵树从森林中删除，并将新树添加进去,3 5,29 7 8 14 23 11,8,第三步：重复第二步过程，直到森林中只有一棵树为止选择7，8,29 14 23 11,7 8,15,3 5,8,选择8，11选择14，15选择19，23,3 5,29,15,7 8,29,14,8,42,23,19,11,选择29，29,7 8,15,58,29,29,14,3 5,8,42,23,19,11,选择42，58,10

38、0,7 8,15,58,29,29,14,3 5,8,42,23,19,11,这就是以上述8个权值为叶子结点权值构成的哈夫曼树，它的带权的路径长度为：WPL=(23+29)*2+(11+14)*3+(3+5+7+8)*4=271,6.3.2 判定树 在很多问题的处理过程中，需要进行大量的条件判断，这些判断结构的设计直接影响着程序的执行效率。例如，编制一个程序，将百分制转换成五个等级输出。大家可能认为这个程序很简单，并且很快就可以用下列形式编写出来：if(socre60)printf(“bad”);else if(socre70)printf(“pass”);else if(score80)pr

39、intf(“general”);else if(score90)printf(“good”);esle printf(“very good”);在实际应用中，往往各个分数段的分布并不是均匀的。下面就是在一次考试中某门课程的各分数段的分布情况：,下面我们就利用哈夫曼树寻找一棵最佳判定树，即总的比较次数最少的判定树。,图 6-29,very good,bad,pass,general,good,80,90,70,60,首先，将各分数段的比例数值作为权值构造一棵哈夫曼树。,very good,bad,pass,general,good,60.69,.59,80.89,70.79,图 6-30,图 6

40、-31,70,90,80,general,good,very good,bad,pass,60,6.3.3 前缀编码 在电文传输中，需要将电文中出现的每个字符进行二进制编码。在设计编码时需要遵守两个原则：（1）发送方传输的二进制编码，到接收方解码后必须具有唯一性，即解码结果与发送方发送的电文完全一样；（2）发送的二进制编码尽可能地短。下面我们介绍两种编码的方式。1.等长编码,2.不等长编码 在传送电文时，为了使其二进制位数尽可能地少，可以将每个字符的编码设计为不等长的，使用频度较高的字符分配一个相对比较短的编码，使用频度较低的字符分配一个比较长的编码。例如，可以为A，B，C，D四个字符分别分配

41、0，00，1，01，并可将上述电文用二进制序列：000011010发送，其长度只有9个二进制位，但随之带来了一个问题，接收方接到这段电文后无法进行译码，因为无法断定前面4个0是4个A，1个B、2个A，还是2个B，即译码不唯一，因此这种编码方法不可使用。,（1）利用字符集中每个字符的使用频率作为权值构造一个哈夫曼树；（2）从根结点开始，为到每个叶子结点路径上的左分支赋予0，右分支赋予1，并从根到叶子方向形成该叶子结点的编码。假设有一个电文字符集中有8个字符，每个字符的使用频率分别为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11，现以此为例设计哈夫曼编码。哈夫曼编码设计过程为：（1）为方便计算，将所有字符的频度乘以100，使其转换成整型数值集合，得到5,29,7,8,14,23,3,11；（2）以此集合中的数值作为叶子结点的权值构造一棵哈夫曼树，如图5-27所示；,（3）由此哈夫曼树生成哈夫曼编码，如图5-28所示。最后得出每个字符的编码为：,接收方可以准确地通过译码得到：。,