第六章树和二叉树

1、第 六 章 树和二叉树树和二叉树6.1 树的定义和基本术语6.2 二叉树 6.2.1 二叉树的定义 6.2.2 二叉树的性质 6.2.3 二叉树的存储结构6.3 遍历二叉树和线索二叉树 6.3.1 遍历二叉树 6.3.2 线索二叉树6.4 树和森林 6.4.1 树的存储结构 6.4.2 森林与二叉树的转换6.6 赫夫曼树及其应用 6.6.1 最优二叉树(赫夫曼树) 非线性数据结构。 树的递归定义： 树(tree)是n(n=0)个结点的有限集。 当n0时, (1)有且仅有一个特定的称为根(root)的结点; (2)当n1时,其余结点可分为m(m0)个互不相交的有限集T1,T2,.,Tm,其中每个

2、集合本身又是一棵树。称为子树子树(subtree)(subtree)。第六章 树和二叉树6.1 树的定义和基本术语树的示例空树 n=0层次1234一般的树ABCDEFGHIJKL只有根结点的树 n=1A ADT Tree 数据对象数据对象D：D是具有相同特性的数据元素的集合。 数据关系数据关系R：若D为空集，则称为空树; 若D仅含一个数据元素，则R为空集，否则RH，H是如下二元关系： （1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； （2）若Droot，则存在Droot的一个划分D1, D2, ., Dm （m0），对任意jk（1j,km）有DjDk= ，且对任意的i（1i

3、m），唯一存在数据元素xiDi，有H; （3）对应于Droot的划分，H，.，有唯一的一个划分H1 , H2 ,., Hm （m0），对任意jk（1j,km）有HjHk= ，且对任意的i（1im），Hi 是Di上的二元关系，（Di ,Hi）是一棵符合本定义的树，称为根root的子树。树的抽象数据类型定义： INITTREE（T）； 操作结果：构造空树T。 DESTROYTREE（T）； 初始条件：树T存在。 操作结果：销毁树T。 CREATETREE（T，DEFINITION）； 初始条件：DEFINITION给出树T的定义。 操作结果：按DEFINITION构造树T。 CLEARTREE（T

4、）； 初始条件：树T存在。 操作结果：将树T清为空树。树的抽象数据类型定义：基本操作（之一）基本操作（之一） TREEEMPTY（T） 初始条件：树T存在。 操作结果：若T为空树，则返回TURE，否则FALSE。 TREEDEPTH（T） 初始条件：树T存在。 操作结果：返回T的深度。 ROOT（T） 初始条件：树T存在。 操作结果：返回T的根。 VALUE（T, CUR_E）； 初始条件：树T存在，CURE是T中某个结点。 操作结果：返回CURE的值。树的抽象数据类型定义：基本操作（之二）基本操作（之二） ASSIGN（T，CUR_E，VALUE） 初始条件：树T存在，CURE是T中某个结点

5、。 操作结果：结点CUR_E赋值 为VALUE。 PARENT（T，CURE） 初始条件：树T存在，CURE是T中某个结点。 操作结果：若CURE是T的非根结点，则返回它的双亲，否则函数值为“空”。 LEFTCHILD（T，CURE） 初始条件：树T存在，CURE是T中某个结点。 操作结果：若CURE是T的非叶子结点，则返回它的最左孩子，否则返回“空”。 RIGHTSIBLING（T，CURE） 初始条件：树T存在，CURE是T中某个结点。 操作结果：若CURE有右兄弟，则返回它的右兄弟，否则函数值为“空”。树的抽象数据类型定义：基本操作（之三）基本操作（之三） INSERTCHILD（T，P

6、，I，C）； 初始条件：树T存在，P指向T中某个结点，1IP所指结点的度1，非空树C与T不相交。 操作结果：插入C为T中P指结点的第I棵子树。 DELETECHILD（T，P，I）； 初始条件：树T存在，P指向T中某个结点，1IP指结点的度。 操作结果：删除T中P所指结点的第I棵子树。 TRAVERSETREE（T，VISIT（）； 初始条件：树t存在，VISIT是对结点操作的应用函数。 操作结果：按某种次序对T的每个结点调用函数VISIT（）一次且至多一次。一旦VISIT（）失败，则操作失败。 ADT TREE树 的 抽 象 数 据 类 型 定 义 ：基本操作（之四）基本操作（之四） 子树(

7、subtree) 结点 结点的度(degree) 叶子(leaf)(终端结点) 分支结点(非终端结点) 树的度树的基本术语（之一）ABCDFGHIL 孩子(child) 双亲(parent) 兄弟(sibling) 堂兄弟 祖先 子孙树的基本术语（之二）ABCDFGHIL 子树(subtree) 层次(level) 深度(depth) 有序树 无序树 森林: m(m=0)棵互不相交的树的集合.树的基本术语（之三）ABCDFGHIL 二叉树(binary tree): 度不超过2的有序树。 二叉树的五种基本形态6.2 6.2 二叉树二叉树6.2.1 二叉树的定义(a) 空二叉树; (b)仅有根结

8、点的二叉树；(c)右子树为空的二叉树；(d)左、右子树均为非空的二叉树； (e)左子树为空的二叉树。(a)A(b)A(c)A(d)A(e) 性质性质2 2：深度为k的二叉树至多有2k-1个结点(k=1). k-1 Nk = 2i = 2k-1 i = 0 性质性质3 3:对任何一棵二叉树T, 如果其叶结点数为n0, 度为2的结点数为n2, 则 n0 = n2 + 1.6.2.2 二叉树的性质-性质性质1 1：在二叉树的第i层上至多有2(i-1)个结点(i=1).一般的二叉树ABDEFHIJKL层次1234 一棵深度为k且有 2k-1个结点的二叉树称为满二叉树。 k = 3 k = 4满二叉树的

9、定义满二叉树的定义:123456789141011151213 深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。完全二叉树的定义完全二叉树的定义:123456完全二叉树和非完全二叉树举例完全二叉树和非完全二叉树举例:123456789101112完全二叉树123456非完全二叉树完全二叉树性质性质4：具有n个结点的完全二叉树的深度为log2n*+1。性质性质5：如果对一棵有n个结点的完全二叉树（其深度为log2n*+1）的结点按层序编号（从第1层到第log2n*+1层，每层从左到右），则对任一结点i（1in），有（1）

10、如果i1，则结点i是二叉树的根，无双亲；如果i1，则其双亲PARENT（i）是结点 i/2*。（2）如果2in，则结点i无左孩子（结点i为叶子结点），否则其左孩子LCHILD（i）是结点2i。（3）如果2i1n，则结点i无右孩子； 否则其右孩子RCHILD（i）是结点2i+1./-二叉树的顺序存储表示- # define define MAX_TREE_SIZE 100 typedeftypedef TElemType SqBiTreeMAX_TREE_SIZE; SqBiTree bt;上一节完全二叉树的十二个结点的顺序存储为：上一节非完全二叉树的六个结点的顺序存储（需7个存储空间）为：6.

11、2.3 二叉树的存储结构二叉树的存储结构一、顺序存储结构一、顺序存储结构1 21 23 43 45 65 67 87 89 109 10 11 12 11 121 21 23 43 40 5 0 5 6 6最坏情况最坏情况：深度为k的且只有k个结点的单支树需要长度为2k-1的一维数组。typedef struct BiTNode TElemType data; struct BiTNode *lchild,*rchild; /左右孩子指针BiTNode,*BiTree;二、链式存储结构rchilddatalchilddataparentlchildrchilddatalchildrchildp

12、arent链式存储结构示例树的二叉两链表示。三叉链表示略ABCDGEFABCDEFGBDAEFGC0123456123456 Status CreateBiTree(BiTree &T);/按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树，/构造二叉链表表示的二叉树T。 S t a t u s P r e O r d e r T r a v e r s e ( B i T r e e T, Status(*Visit)(TElemType e);/采用二叉链表存储结构,Visit是对结点操作的应用函数/先序遍历二叉树T，对每个结点调用函数Visit一次且仅一次。/一旦Visit(

13、) 失败，则操作失败。基本操作的函数原型说明(一) S t a t u s I n O r d e r T r a v e r s e ( B i T r e e T , Status(*Visit)(TElemType e);/采用二叉链表存储结构,Visit是对结点操作的应用函数。/中序遍历二叉树T，一旦Visit( ) 失败，则操作失败。 S t a t u s P o s t O r d e r T r a v e r s e ( B i T r e e T, Status(*Visit)(TElemType e);/采用二叉链表存储结构,Visit是对结点操作的应用函数。/后序遍历二

14、叉树T，一旦Visit( ) 失败，则操作失败。 S t a t u s L e v e l O r d e r Tr a v e r s e ( B i Tr e e T, Status(*Visit)(TElemType e);/采用二叉链表存储结构,Visit是对结点操作的应用函数。/层序遍历二叉树T，一旦Visit( ) 失败，则操作失败。基本操作的函数原型说明(二) 6.3.1遍历二叉树 如果按某条搜索路径巡访树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。6.3遍历二叉树和线索二叉树ABCDGEF 若二叉树为空，则空操作；否则 （1）访问根结点； （2）先序遍历左子树；

15、（3）先序遍历右子树。 A B C D F E G先序遍历二叉树的操作定义为：ABCDGEFStatus PreOrderTraverse(BiTree T, Status(* Visit)(TElemType e) if (T) if (Visit(T-data) if (PreOrderTraverse(T-lchild,Visit) if (PreOrderTraverse(T-rchild,Visit) return OK; return ERROR; else return OK;/PreOrderTraverse先序遍历二叉树的递归算法若二叉树为空，则空操作；否则 （1）中序遍历左

16、子树； （2）访问根结点； （3）中序遍历右子树。 C B D F A G E中序遍历二叉树的操作定义为：ABCDGEF中序遍历二叉树得:a+b*(c-d)-e/f中序遍历二叉树示例-+a*e/-fbdcStatus InOrderTraverse(BiTree T, Status(* Visit)(TElemType e) if (T) if (InOrderTraverse(T-lchild,Visit) if (Visit(T-data) if (InOrderTraverse(T-rchild,Visit) return OK; return ERROR; else return OK

17、;/InOrderTraverse中序遍历二叉树的递归算法 若二叉树为空，则空操作；否则 （1）后序遍历左子树； （2）后序遍历右子树； （3）访问根结点。 C F D B G E A后序遍历二叉树的操作定义为：ABCDGEFStatus PostOrderTraverse(BiTree T, Status(* Visit)(TElemType e) if (T) if (PostOrderTraverse(T-lchild,Visit) if (PostOrderTraverse(T-rchild,Visit) if (Visit(T-data) return OK; return ERRO

18、R; else return OK;/PostOrderTraverse后序遍历二叉树的递归算法Status InOrderTraverse(BiTree T, Status(* Visit) (TElemType e) InitStack(S); Push(S,T); while(!StackEmpty(S) while(GetTop(S,p) & p)Push(S,p-lchild); Pop(S, p); if (!StackEmpty(S) Pop(S,p); if (!Visite(p-data) return ERROR; Push(S,p-rchild); return OK;/

19、InOrderTraverse中序遍历二叉树的非递归算法 C B D F A G E中 序 遍 历 二 叉 树 的 非 递 归 算 法示意图ABCDGEFABCNULLSGetTopdata = ch ; CreateBiTree(T-lchild); CreateBiTree(T-rchild); return OK;/CreateBiTree构 造 二 叉 链 表 表 示 的 二 叉 树的递归算法构造二叉链表ABCDGEF按下列次序输入字符按下列次序输入字符:ABCDEGF(其中其中表示空格字符表示空格字符)可建立如右图的二叉链表可建立如右图的二叉链表. 遍 历 是 非 线 性 结 构 的

20、 线 性 化 操 作保留遍历过程的顺序信息 - 线索二叉树的表示: 若结点有左子树，则其LCHILD域指示其左孩子，否则令LCHILD域指示其前驱； 若结点有右子树，则其RCHILD域指示其右孩子，否则令RCHILD域指示其后继。6.3.2 线索二叉树 0 lchild域指示其左孩子ltag = 1 lchild域指示其前驱 0 rchild域指示其右孩子rtag = 1 rchild域指示其后继线索二叉树线索化线索链表线索线索二叉树结点的结构:datalchildrchildrtagltag中序线索二叉树-+a*e/-fbdcNILNILb*11 + /f00 e 如何在中序线索二叉树中找结

21、点的后继： rtag = 1时，rchild所指的结点即为后继； rtag = 0时，其后继为遍历其右子树时的第一个结点（最左下结点）。如结点 “*”的后继是“c” 。 如何在中序线索二叉树中找结点的前驱：ltag = 1时，lchild所指的结点即为前驱；ltag = 0时，其前驱为遍历其左子树时的最后一个结点（最右下结点）。如根结点 “-”的前驱是“d” 。中序线索二叉树中查找结点的后继和前驱:中序线索二叉树/ 二叉树的二叉线索存储表示二叉树的二叉线索存储表示typedef enum Link,Thread PointerTag; /Link=0:指针指针,Thread=1:线索线索typ

22、edef struct BiThrNode TElemType data; struct BiThrNode *lchild,*rchild; /左右孩子指针左右孩子指针 PointerTag LTag,RTag; /左右标左右标志志BiThrNode, *BiThrTree;Status InOrderThreading(BiThrTree &Thrt, BiThrTree T) / Thrt指向头结点。 if (!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode) exit (OVERFLOW); Thrt-LTag=Link; Thrt-RTag=Thre

23、ad; /建头结点 Thrt-rchild=Thrt; /右指针回指 if (!T)Thrt-lchild=Thrt; /若二叉树空，则左指针回指 else Thrt-lchild=T; pre=Thrt; InThreading(T); /中序遍历进行中序线索化 pre-rchild=Thrt; pre-RTag=Thread; /最后一个结点线索化 Thrt-rchild=pre; return OK;/InOrderThreading中序遍历二叉树T，并将其中序线索化:(为了记下遍历过程中访问结点的先后次序，附设一个全程指针pre)void InThreading(BiThrTree p

24、) / 一个全程指针pre if (p) InThreading(p-lchild); /左子树线索化 if (!p-lchild) p-LTag=Thread;p-lchild=pre; /前驱线索 if (!pre-rchild) pre-RTag=Thread; pre-rchild=p; /后继线索 pre=p; /保持pre指向p的前驱 InThreading(p-rchild); /右子树线索化 /InThreading中序遍历进行中序线索化例如:将下列二叉链表改为中序线索链表InfoABCDEFGHIJKLMNLtagLchild 24607010012 130000RtagRc

25、hild 35008911000140001 2 3 4 5 6 7 8 9 10 11 12 13 14上例树的形态Info LtagLchildRtag RchildA0203B0405C061ThrtD1Thrt12E0708F1109G010011H1511I01213J01317K17014L1619M12110N11115Thrt10 1234567891011121314ABDEFCHIGKJMNLStatus InOrderTraverse_Thr(BiThrTree T, Status(*Visit)(TElemType e) / T指向头结点，头结点的左链lchild 指向

26、根结点， /可参见线索化算法。中序遍历二叉线索树T的非递归算法， / 对每个数据元素调用函数Visit. p=T-lchild; /p指向根结点 while(p!=T) /空树或遍历结束时，p=T while(p-LTag=Link)p=p-lchild;/p寻找最左下结点 if (!Visit(p-data) return ERROR; /访问其左子树为空的结点 while(p-RTag=Thread&p-rchild!=T) p=p-rchild; Visit(p-data); /访问后继结点 p=p-rchild; return OK;/InOrderTraverse_Thr中序遍历二叉

27、线索树T的非递归算法:b用链表实现二叉树的几种基本操作：初用链表实现二叉树的几种基本操作：初始化，遍历始化，遍历b以二叉链表作为二叉树的存储结构，编以二叉链表作为二叉树的存储结构，编写以下算法：写以下算法：b（1）统计二叉树的叶结点个数）统计二叉树的叶结点个数b（2）分别以先序、中序以及后序遍历）分别以先序、中序以及后序遍历二叉树并输出二叉树的节点二叉树并输出二叉树的节点 已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为( )A-A+B*C/DE B. -A+B*CD/E C-+*ABC/DE D. -+A*BC/DE 设有一表示算术表达式的二叉树（

28、见下图），它所表示的算术表达式是（ ）A. A*B+C/(D*E)+(F-G) B. (A*B+C)/(D*E)+(F-G) C. (A*B+C)/(D*E+（F-G）) D. A*B+C/D*E+F-GEFDGAB/+*-C* 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）A9 B11 C15 D不确定 具有10个叶结点的二叉树中有（ ）个度为2的结点A8 B9 C10 D1l 一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）A 250 B 500 C254 D505 E以上答案都不对 某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,

29、D,C,A,F,G,E 则前序序列是：AE,G,F,A,C,D,B BE,A,C,B,D,G,F CE,A,G,C,F,B,D D上面的都不对 一、双亲表示法（顺序存储） /-树的双亲表存储表示-/ #define MAX_TREE_SIZE 100 typedef struct PTNode TElemType data; int parent; /双亲位置域 PTNode; typedef struct PTNode nodesMAX_TREE_SIZE; int n; /结点数 PTree;64 树和森林树和森林 6.4.1树的存储结构双亲表示法举例RADEFCBGKHR -1 A 0

30、B 0 C 0 D 1 E 1 F 3 G 6 H 6 K 6 0123456789数组下标数组下标:* 便于涉及双亲的操作；便于涉及双亲的操作；* 求结点的孩子时需要遍历整棵树。求结点的孩子时需要遍历整棵树。 #define MAX_TREE_SIZE 100 typedef struct PTNode TElemType data; int child1; /第1个孩子位置域 int child2; /第2个孩子位置域 . int childd; /第d个孩子位置域 PTNode; typedef struct PTNode nodesMAX_TREE_SIZE; int n; /结点数

31、PTree;6.4.1树的存储结构二、孩子表示法（顺序存储）孩子表示法举例RADEFCBGKH0123456789数组下标数组下标:* 便于涉及孩子的操作；求双亲不方便；便于涉及孩子的操作；求双亲不方便；* 采用同构的结点，空间浪费。采用同构的结点，空间浪费。R 1 A 4 B 0 C 6 D 0 E 0 F 7 G 0 H 0 K 0 2 3 5 0 0 0 0 0 0 0 0 0 8 9 0 0 0 0 0 0 孩子链表存储表示（链式存储） typedef struct CTNode /孩子结点孩子结点 int child; struct CTNode *next; *ChildPtr;

32、typedef struct TElemType data; ChildPtr firstchild; /孩子链表头指针孩子链表头指针 CTBox; typedef struct CTBox nodesMAX_TREE_SIZE; int n, r; /结点数和根的位置结点数和根的位置 CTree;孩子链表存储表示举例RADEFCBGKH0123456789数组下标数组下标:* 便于涉及孩子的操作；便于涉及孩子的操作；* 求结点的双亲时不方便。求结点的双亲时不方便。R A B / C D / E / F G / H / K /1 2 3 / 4 5 / 6 / 7 8 9 / T.nodes

33、; T.n=10; T.r = 0;例1: 设树T以孩子链表为存储结构,寻找值为x的双亲结点的算法如下:Status parent(Ctree T, TElemType x)/ 当值为当值为x的结点不存在时返回的结点不存在时返回-2; / 当值为当值为x的结点为根结点时返回的结点为根结点时返回-1, / 否则返回否则返回x结点的双亲结点的下标值结点的双亲结点的下标值. if(T.nodesT.r.data = x) return 1; /值为值为x的结点为根结点的结点为根结点; for(i=0;ichild.data != x) p = p-next; if(p) return (i); /

34、找到找到x的双亲结点的双亲结点 return 2; / 值为值为x的结点不存在的结点不存在例2: 删除值为x的结点的第i棵子树的算法delete如下：void deletej(Ctree &T, int j)/ 删除树删除树T的第的第j号结点及其子树号结点及其子树 if(!T.nodesj.firstchild) / 删除叶结点删除叶结点 for(i=j; inext;i = s-child; free(s);deletej(T, i); / 递归删除第递归删除第i号结点及其子树号结点及其子树 Status delete(Ctree &T, TElemType x, int i) / 当值为当

35、值为x的结点不存在时返回的结点不存在时返回-2;当值为当值为x的结点为的结点为 /叶结点或无第叶结点或无第i 棵子树时返回棵子树时返回-1, 否则返回否则返回1. for(k=0; k=T.n) return 2; / 值为值为x的结点不存在的结点不存在 p= T.nodesk.firstchild; j = 1; if(!p) return 1; / x结点为叶结点结点为叶结点 if(i=1) / 删除长子时删除长子时,特殊处理特殊处理 j =p-child; / 记住要删除子树的下标记住要删除子树的下标 T.nodesk.firstchild = p-next; free(p); else

36、 while(p-next & jnext ; j+; if(ji-1 | !p-next) return 1; / 无第无第i 棵子树棵子树 / p指向第指向第i-1 个儿子个儿子 j = p-next-child; / 记住要删除子树的下标记住要删除子树的下标 s = p-next; p-next = s-next; free(s); deletej(T, j); / 递归删除第递归删除第j号结点及其子树号结点及其子树 return 1; /-树的二叉链表(孩子兄弟)存储表示- typedef struct CSNode ELemType data; struct CSNode *firs

37、tchild,*nextsibling; CSNode, *CSTree;三.孩子兄弟表示法-树的二叉树表示法(二叉链表示法)RADEFCBGKHRADECHFGBK孩子兄弟表示法示例：孩子兄弟表示法示例： 如果F=T1,T2, ,Tm是森林,则可按如下规则转换成一棵二叉树B=(root,LB,RB)。 (1)若F为空，即m=0,则B为空树； (2)若F非空，即m0，则B的根root即为森林中第一棵树的根ROOT(T1)； B的左子树LB是从T1中根结点的子树森林F1=T11,T12, ,T1m1转换而成的二叉树; 其右子对RB是从森林F=T2,T3, ,Tm 转换而成的二叉树.6.4.2 森

38、林与二叉树的转换森林与二叉树的转换一.森林转换成二叉树 如果B=(root,LB,RB)是一棵二叉树,则可按如下规则转换成森林F=T1,T2, ,Tm： (1)若B为空，则F为空； (2)若B非空，则F中第一棵树T1的根ROOT(T1)即为二叉树B的根root； T1中的根结点的子树森林 F1是由B的左子树LB转换而成的森林; F中除T1之外其余树组成的森林F=T2,T3, ，Tm是由B的右子树RB转换而成的森林。二. 二叉树转换成森林 树的两种遍历方法： 一、先根遍历： （1）访问树的根结点； （2）依次先根遍历每棵子树。 R A D E B C F G H K 二、后根遍历： （1）依次后

39、根遍历每棵子树。 （2）访问树的根结点； D E A B G H K F C R 6.4.3 树和森林的遍历树和森林的遍历RADEFCBGKH 一、先序遍历森林： 若森林非空，则 （1）访问森林中第一棵树的根结点； （2）先序遍历第一棵树的根结点的子树森林； （3）先序遍历除去第一棵树之后的森林。 二、中序遍历森林： 若森林非空，则 （1）中序遍历第一棵树的根结点的子树森林； （2）访问森林中第一棵树的根结点； （3）中序遍历除去第一棵树之后的森林。森林的两种遍历方法： 路径长度路径长度: 从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径,路径上的分支数目称做路径长度。 树的路径长

40、度树的路径长度: 树的路径长度是从树根到每一结点的路径长度之和。 树的带权路径长度树的带权路径长度: 树的带权路径长度为树中所有叶子结点(k)的带权路径长度kk之和, 通常记作： n WPL= kk。 k=1 6.6 赫夫曼树及其应用6.6.1最优二叉树(赫夫曼树) 假设有n个权值1, 2, , n，试构造一棵有n个叶子结点的二叉树,每个叶子结点带权为i, 则其中： 带权路径长度WPL最小的二叉树称做 最优二叉树最优二叉树 或赫夫曼树赫夫曼树.最优二叉树或赫夫曼(Huffman)树的定义例1：下面三棵二叉树的四个叶子结点a,b,c,d的权值为7、5、2、4abcd7524abcd7524cda

41、b7524(a)WPL=7x2+5x2+2x2+4x2 = 36(b)WPL=7x3+5x3+2x1+4x2 = 46(c)WPL=7x1+5x2+2x2+4x2 = 35例2 最佳判定方法(p.144)(a)WPL=10 x4+30 x4+40 x3+15x2+5x1=315(b)WPL=5x3+15x3+40 x2+30 x2+10 x2=22010c90ed51540ba30607080NNNNYYYYY107090ec54015ba3060d0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC. if(n=1) return;m=2*n-1;HT=(HuffmanTree)mallo

42、c(m+1)*sizeof(HTNode);/0号单未用 for(p=HT,i=1;i=n;+i,+p,+w) *p=*w,0,0,0; for(;i=m;+i,+p) *p=0,0,0,0;求赫夫曼编码的算法如下: for(i=n+1;i=m;+i) /建赫夫曼树 /在HT1.i-1选择parent为0且weight最小的两个结点, / 其序号分别为s1和s2. select(HT,i-1,s1,s2); HTs1.parent=i;HTs2.parent=i; HTi.lchild=s1;HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight;

43、/-从叶子到根逆向求每个字符的赫夫曼编码- Hc=(HffmanCode)malloc(n+1*sizeof(char *); /分配n个字符编码的头指针向量 cd=(char *)malloc(n*sizeof(char);/分配求编码的工作空间 cdn-1=/0; /编码结束符.求赫夫曼编码的算法（续一）: for(i=1;i=n;+i)/逐个字符求赫夫曼编码 start=n-1;/编码结束符位置 for(c=i,f=HTi;f!=0;c=f,f=Htf.parent) /从叶子至根逆向求编码 if(HTf.lchild=c) cd-start=0; else cd-start=1; Hc

44、i=(char *)malloc(n-start)*sizeof(char); /为第i个字符编码分配空间 strcpy(HCi,&cdstart); /从cd复制编码(串)到HC free(cd); /释放工作空间 /HuffanCoding 求赫夫曼编码的算法（续二）: /-无栈非递归遍历赫夫曼树,求赫夫曼编码 HC=(HuffmanCode)malloc(n+1)*sizeof(char *); p=m;cdlen=0; for(i=1;i=m;+i) HTi.weight=0; /遍历赫夫曼树时用作结点状态标志 while(p) if(HTp.weight=o)/向左 Htp.weight=1; if(HTp.lchild!=0)p=HTp.lchild;cdcdlen+=0; else if(HTp.rchild=0)/登记叶子结点的字符的编码 HCp=(char *)malloc(cdlen+1) *sizeof(char); cdcdlen=0;strcpy(HCp,cd);/复制编码(串) 求赫夫曼编码的算法如下: else if (H