数据结构与算法-东北林业大学 第六章树与二叉树.ppt

1、1,DATA,10,65,865,姓名 学号 成绩 班级 李红 9761059 95 机97.6,主讲：王阿川,数据结构,2,第六章 树和二叉树,3,6.1 树的结构定义和基本术语 6.2 二叉树 6.2.1 二叉树的定义 6.2.2 二叉树的性质 6.2.3 二叉树的存储结构 6.3 遍历二叉树和线索二叉树 6.3.1 遍历二叉树 6.3.2 线索二叉树6.4 树和森林的遍历 6.5 哈夫曼树及其应用 5.5.1 最优二叉树(哈夫曼树) 5.5.2 哈夫曼编码,4,6.1 树的定义和基本术语,5,数据对象 D：,D是具有相同特性的数据元素的集合。,若D为空集，则称为空树； 否则: (1) 在

2、D中存在唯一的称为根的数据元素root, (2) 当n1时，其余结点可分为m (m0)个互 不相交的有限集T1, T2, , Tm, 其中每一 棵子集本身又是一棵符合本定义的树， 称为根root的子树。,数据关系 R：,6,A( B(E, F(K, L), C(G), D(H, I, J(M) ),T1,T3,T2,树根,(b),(a),上面是图的广义表表示形式 图的嵌套形式表示和凹入表示法见图6.2,例如：,7,基本操作：,查 找 类,插 入 类,删 除 类,8,Root(T) / 求树的根结点,查找类：,Value(T, cur_e) / 求当前结点的元素值,Parent(T, cur_e

3、) / 求当前结点的双亲结点,LeftChild(T, cur_e) / 求当前结点的最左孩子,RightSibling(T, cur_e) / 求当前结点的右兄弟,TreeEmpty(T) / 判定树是否为空树,TreeDepth(T) / 求树的深度,TraverseTree( T, Visit() ) / 遍历,9,InitTree( Value(T, e); Parent(T, e); LeftChild(T, e); RightChild(T, e); LeftSibling(T, e); RightSibling(T, e); BiTreeEmpty(T); BiTreeDepth

4、(T); PreOrderTraverse(T, Visit(); InOrderTraverse(T, Visit(); PostOrderTraverse(T, Visit(); LevelOrderTraverse(T, Visit();,23,InitBiTree(,24,ClearBiTree(,25,6.2.2二叉树的特性,26,性质 1 在二叉树的第 i 层上至多有2i-1 个结点。 (i1),用归纳法证明： 归纳基： 归纳假设： 归纳证明：,i = 1 层时，只有一个根结点， 2i-1 = 20 = 1；,假设对所有的 j，1 j i，命题成立;,二叉树上每个结点至多有两棵子树

5、， 则第 i 层的结点数 = 2i-2 2 = 2i-1 。,27,性质 2 ：深度为 k 的二叉树上至多含 2k-1 个结点（k1）,证明：,基于上一条性质，深度为 k 的二叉树上的结点数至多为 20+21+ +2k-1 = 2k-1,28,性质 3 ： 对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0 = n2+1,证明：,设 二叉树上结点总数,n = n0 + n1 + n2,b = n1+2n2,而 b = n-1 = n0 + n1 + n2 - 1,由此， n0 = n2 + 1,又 二叉树上分支总数,29,两类特殊的二叉树：,满二叉树：指

6、的是深度为k且含有2k-1个结点的二叉树。,完全二叉树：树中所含的 n 个结点和满二叉树中编号为 1 至 n 的结点一一对应。,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,a,b,c,d,e,f,g,h,i,j,30,性质4：具有 n 个结点的完全二叉树的深度为 log2n +1,证明：,设 完全二叉树的深度为 k 则根据第二条性质得 2k-1-1 n 2k -1 或： 2k-1 n 2k 即 k-1 log2 n k 因为 k 只能是整数，因此， k =log2n + 1,31,性质 5 ：,若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号

7、，则对完全二叉树中任意一个编号为 i 的结点：(1) 若 i=1，则该结点是二叉树的根，无双亲, 否则，编号为 i/2 的结点为其双亲结点; (2) 若 2in，则该结点无左孩子， 否则，编号为 2i 的结点为其左孩子结点；(3) 若 2i+1n，则该结点无右孩子结点， 否则，编号为2i+1 的结点为其右孩子结点。,32,复习一下上节课我们所学习的内容，主要讲了： 1、树的定义、术语等。 2、介绍了二叉树、二叉树的特性、二叉树与树的异同。 3、介绍了二叉树的5个性质、满二叉树、完全二叉树等内容。,33,6.2.3 二叉树的存储结构,二、二叉树的链式存储表示,一、 二叉树的顺序存储表示,34,一

8、、 二叉树的顺序存储表示,用一组地址连续的存储单元存储完全二叉树的数据元素。即将完全二叉树中编号为i的结点的数据元素存放在分量bti-1中。但这种顺序存储结构仅适合于完全二叉树,而一般二叉树按这种形式存储将造成存贮浪费。,35,1 2 3 4 5 6 7 8 9 10 11 12,完全二叉树,a,b,c,d,e,f,g,h,i,j,k,l,36,二叉树顺序存储描述,#define MAX_TREE_SIZE 100 / 二叉树的最大结点数typedef TElemType SqBiTreeMAX_ TREE_SIZE; SqBiTree bt;,37,一般二叉树,存在的问题？无法进行二叉树的操

9、作。,38,A,B,C,D,E,F,2,4,1,6,3,5,一般二叉树,39,A,B,C,D,E,F,2,5,1,14,3,7,一般二叉树,4,6,8,9,10,11,13,12,40,二、二叉树的链式存储表示,1. 二叉链表,2三叉链表,41,lchild data rchild,root,A,D,E,B,C,F,结点结构:,1. 二叉链表,42,typedef struct BiTNode / 结点结构 TElemType data; struct BiTNode *lchild, *rchild; / 左右孩子指针 BiTNode, *BiTree;,lchild data rchild

10、,结点结构:,C 语言的类型描述如下:,43,A,D,E,B,C,F,root,2三叉链表,parent lchild data rchild,结点结构:,44,typedef struct TriTNode / 结点结构 TElemType data; struct TriTNode *lchild, *rchild; / 左右孩子指针 struct TriTNode *parent; /双亲指针 TriTNode, *TriTree;,parent lchild data rchild,结点结构:,C 语言的类型描述如下:,45,6.3遍历二叉树和线索二叉树,46,一、问题的提出,二、先左

11、后右的遍历算法,三、算法的递归描述,四、中序遍历算法的非递归描述,五、遍历算法的应用举例,6.3.1 遍历二叉树,47,顺着某一条搜索路径巡访二叉树 中的结点，使得每个结点均被访问一 次，而且仅被访问一次。,一、问题的提出,“访问”的含义可以很广，如：输出结 点的信息等。,48,“遍历”是任何类型均有的操作， 对线性结构而言，只有一条搜索路 径(因为每个结点均只有一个后继)， 故不需要另加讨论。而二叉树是非 线性结构，,每个结点有两个后继， 则存在如何遍历即按什么样的搜索 路径遍历的问题。,49,对“二叉树”而言，可以有三条搜索路径：,1先上后下的按层次遍历； 2先左（子树）后右（子树）的遍历

12、； 3先右（子树）后左（子树）的遍历。,50,二、先左后右的遍历算法 假如以L、D、R分别表示遍历左子树、遍历根结点和遍历右子树，遍历整个二叉树则有DLR、LDR、LRD、DRL、RDL、RLD六种遍历方案。若规定先左后右，则只有前三种情况，即：,DLR先（根）序遍历， LDR中（根）序遍历， LRD后（根）序遍历。,51,若二叉树为空树，则空操作；否则， （1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树。,先（根）序的遍历算法：,52,先序: A B D C E G F,53,54,VLR输出序列：A B D E G HI J C F,55,若二叉树为空树，则空操作；否则，

13、（1）中序遍历左子树； （2）访问根结点； （3）中序遍历右子树。,中（根）序的遍历算法：,56,先序: A B D C E G F,中序: B D A E G C F,57,VLR输出序列：A B D E G HI J C F LVR输出序列：D B G EI H J A C F,58,若二叉树为空树，则空操作；否则， （1）后序遍历左子树； （2）后序遍历右子树； （3）访问根结点。,后（根）序的遍历算法：,59,先序: A B D C E G F 中序: B D A E G C F 后序: D B G E F C A,60,VLR输出序列：A B D E G HI J C F LVR输出

14、序列：D B G EI H J A C F LRV输出序列：D G I JH E B F C A,61,例如： 先序遍历如图所示之二叉树,按访问结点的先后次序将结点排列起来,其先序序列为：,-+a*b-cd/ef,按中序遍历,其中序序列为：,a+b*c-d-e/f,按后序遍历,其后序序列为：,abcd-*+ef/-,分别称之为前缀、中缀、后缀表示,62,二叉树的先序序列“abcdefg”能不能唯一确定一棵二叉树？,由二叉树的先序和中序序列建树,如果同时已知二叉树的中序序列“cbdaegf”,则会如何？,二叉树的先序序列,二叉树的中序序列,左子树,左子树,右子树,右子树,根,根,63,a b c

15、 d e f g,c b d a e g f,例如:,a,a,b,b,c,c,d,d,e,e,f,f,g,g,a,b,c,d,e,f,g,先序序列中序序列,64,三、算法的递归描述 1、先序遍历（ inorder traversal）,void Preorder (BiTree T) / 先序遍历二叉树 if (T) / 访问结点 printf(T-data); / 遍历左子树 Preorder(T-lchild); / 遍历右子树 Preorder(T-rchild); ,65,三、算法的递归描述,void Preorder (BiTree T, void( *visit)(TElemTyp

16、e/ 遍历右子树 ,66,2、中序遍历（ inorder traversal）,Status InOrderTraverse(BiTree T,Status (* Visit)(TElemType e) if(T) InOrderTraverse(T-lchild, Visit ); Visit(T-data); InOrderTraverse(T-rchild,Visit); return OK; ,67,3、后序遍历（ preorder Traversal）,Status PostOrderTraverse(BiTree T,Status (* Visit)(TElemType e) if

17、(T) PostOrderTraverse(T-lchild, Visit ); PostOrderTraverse(T-rchild,Visit); Visit(T-data); return OK; ,68,四、二叉树遍历算法的非递归描述 递归算法是通过栈来实现的，因此可仿照算法执行过程中工作栈的状态变化状况写出相应的非递归算法。以中序遍历为例，算法如下：,69,四、二叉树遍历算法的非递归描述,1、递归算法中栈的使用,执行过程中栈的情况和current的变化举例,当左向递归则current的值进栈 若current = = NULL，则出栈，current以栈顶值去执行右向递归 直到栈空（

18、top = -1）和current = = NULL为止,70,2、利用栈的前序和中序遍历非递归算法,void PreOrder (BiTtree T ) InitStack(st); BiTree p =T; do while (p != NULL) printf(p - data); Push (st,p); p = p -lChild; if (! StackEmply (st ) GetTop (st,p); Pop (st,q ); p = p - rchild; while (p != NULL | | !StackEmplty (st ); ,四、二叉树遍历算法的非递归描述,st

19、ack,71,算法描述 p不空则p进栈，沿左子树方向传递指针 若p空但栈不空，出栈，p以栈顶值沿右子树方向传递指针 循环下去，直到p和栈都空为止 执行中栈的情况和指针的变化与递归程序相同 对于中序遍历只需调整输出语句位置即可,72,3.二叉树非递归中序遍历 Void InOrderTraverse(BiTree T) InitStack(S); p=T; while(p | !StackEmpty(S) if(p) Push(S,p); p=p-lchild; Else Pop(S,p); printf(p-data); P=p-rchild; ,四、二叉树遍历算法的非递归描述,73,Stat

20、us InOrderTraverse(BiTree T, Status (*visit)(TelemType e) InitStack(S);Push(S,T); while(!StackEmpty(S) while(GetTop(S,p) / InOrderTraverse,四、二叉树遍历算法的非递归描述,74,4.二叉树后根非递归算法 void pasorder1(TNode *t) struct TNode *pp; int tag; ssN; int top; TNode *p; top=0; p=t; while(p | top0) while(p) top+; sstop.tag=

21、0; sstop.pp=p; p=p-lchild; ,if(top0) if(sstop.tag=0) sstop.tag=1; p=sstop.pp; p=p-rchild; else p=sstop.pp; coutdata ; top-; p=NULL; ,四、二叉树遍历算法的非递归描述,75,5、层次遍历,void LevelOrder (BiTree ,四、二叉树遍历算法的非递归描述,76,五、遍历算法的应用举例,1、统计二叉树中叶子结点的个数 (先序遍历),2、建立二叉树的存储结构,“遍历”是二叉树各种操作的基础。如在遍历过程中统计叶子结点的数目；可在遍历过程中生成结点从而建立二

22、叉树的存储结构。,77,1、统计二叉树中叶子结点的个数,算法基本思想:,先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。 由此，需在遍历算法中增添一个“计数”的参数，并将算法中“访问结点” 的操作改为:若是叶子，则计数器增1。,78,void CountLeaf (BiTree T, int / if / CountLeaf,2、建立二叉树的二叉链表结构,建立二叉链表的算法依赖于按哪种形式输入二叉树的逻辑结构信息。,80,以字符串的形式 按先序序列建立 一棵二叉树,例如:,A,B,C,D,以空白字符“ ”表示,A(B( ,C( , ),D( , ),空树,只含一个根结点的二叉

23、树,A,以字符串“A ”表示,以下列字符串表示,81,Status CreateBiTree(BiTree / CreateBiTree,82,A B C D,A,B,C,D,上页算法执行过程举例如下:,A,T,B,C,D,83,6.3.2线索二叉树,何谓线索二叉树？ 线索链表的遍历算法 如何建立线索链表？,84,一、何谓线索二叉树？,遍历二叉树实质上是对一个非线性结构进行线性化操作的过程，由此可方便地得到某一结点的前驱、后继信息。,A,B,C,D,E,F,G,H,K,例如:,先序序列: A B C D E F G H K,中序序列: B D C A H G K F E,后序序列: D C B

24、 H K G F E A,85,为了在以二叉链表作存储结构的操作中保存遍历所得信息，可在二叉链表中增加两个指针域。,。,若ltag=0，则lchild指示其左孩子；若ltag=1，则lchild指示其前驱； 若rtag=0，则rchild指示其右孩子；若rtag=1，则rchild指示其后继；,86,这种结构的二叉链表称为线索链表，指向结点前驱和后继的指针为线索，加上线索的二叉树为线索二叉树。对二叉树以某种次序进行遍历使其变为线索二叉树的过程叫线索化。画示意图时以虚线表示线索，以实线表示指向左右子树的指针。,87,A,B,C,D,E,先序序列: A B C D E,中序、后序请自己练习。,88

25、,typedef struct BiThrNod TElemType data; struct BiThrNode *lchild, *rchild; / 左右指针 PointerThr LTag, RTag; / 左右标志 BiThrNode, *BiThrTree;,线索链表的类型描述：,typedef enum Link, Thread PointerThr; / Link=0:指针，Thread=1:线索,89,1、如何在线索树中寻找结点的前驱、后继？(中序）2、如何进行线索二叉树的遍历？3、如何进行二叉树的线索化？线索化的过程实质上是在遍历的过程中修改空指针的过程。算法见P134算法

26、6.6,90,二、线索链表的遍历算法:,for ( p = firstNode(T); p; p = Succ(p) ) Visit (p);,由于在线索链表中添加了遍历中得到的“前驱”和“后继”的信息，从而简化了遍历的算法。,91,例如: 对中序线索化链表的遍历算法, 中序遍历的第一个结点 ？, 在中序线索化链表中结点的后继 ？,左子树上处于“最左下” 的结点（该结点没有左子树）,若无右子树，则为后继线索所指结点,否则为对其右子树进行中序遍历时访问的第一个结点,92,void InOrderTraverse_Thr(BiThrTree T, void (*Visit)(TElemType e

27、) p = T-lchild; / p指向根结点 while (p != T) / 空树或遍历结束时，p=T while (p-LTag=Link) p = p-lchild; / 第一个结点 if (! Visit(p-data) return ERROR; while (p-RTag=Thread ,93,在中序遍历过程中修改结点的 左、右指针域，以保存当前访问结 点的“前驱”和“后继”信息。遍历过 程中，附设指针pre, 并始终保持指 针pre指向当前访问的由指针p所指 结点的前驱。,三、如何建立线索链表？,94,void InThreading(BiThrTree p) if (p)

28、/ 对以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); / 右子树线索化 / if / InThreading,95,Status InOrderThreading(BiThrTree / 添加头结点, ,中序遍历建立中序

29、线索链表的算法,96,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,97,6.4 树和森林6.4.1 树的三种存储结构,98,一、双亲表示法,二、孩子链表表示法,三、树的二叉链表(孩子-兄弟） 存储表示法,99,A,B,C,D,E,F,G,0 A -1 1 B 0 2 C 0 3 D 0 4

30、E 2 5 F 2 6 G 5,r=0 n=6,data parent,一、双亲表示法:,100,typedef struct PTNode Elem data; int parent; / 双亲位置域 PTNode;,data parent,#define MAX_TREE_SIZE 100,结点结构:,C语言的类型描述:,101,typedef struct PTNode nodes MAX_TREE_SIZE; int r, n; / 根结点的位置和结点个数 PTree;,树结构:,102,二、孩子链表表示法:,1、多重链表表示法：每个结点有多个指针域，其中每个指针指向一棵子树根结点。有

31、两种表示方式； a) 非固定大小结点结构 b) 链表中结点同构，链表中域的数目为树的度。,103,A,B,C,D,E,F,G,0 A -1 1 B 0 2 C 0 3 D 0 4 E 2 5 F 2 6 G 5,r=0 n=6,1 2 3,4 5,6,-1 0 0 0 2 2 4,2、单链表表示法：把每个结点的孩子排列起来，看成一个线性表，且以单链表作存储结构。则n个结点有n个孩子链表。,104,typedef struct CTNode int child; struct CTNode *next; *ChildPtr;,孩子结点结构:,child next,C语言的类型描述:,105,ty

32、pedef struct Elem data; ChildPtr firstchild; / 孩子链的头指针 CTBox;,双亲结点结构,data firstchild,106,typedef struct CTBox nodesMAX_TREE_SIZE; int n, r; / 结点数和根结点的位置 CTree;,树结构:,107,三、树的二叉链表 (孩子-兄弟）存储表示法：又称二叉链表表示法。链表中结点的两个域分别指向该结点的第一个孩子结点和下一个兄弟结点。,108,A,B,C,D,E,F,G,A B C E D F G,root,A B C E D F G,109,typedef st

33、ruct CSNode Elem data; struct CSNode *firstchild, *nextsibling; CSNode, *CSTree;,C语言的类型描述:,结点结构:,firstchild data nextsibling,110,6.4.2 森林与二叉树的转换,111,树转化为二叉树 以二叉链表为媒介可导出树与二叉树之间的一个对应关系。即，给定一棵树，可以找到唯一的一棵二叉树 与之对应。用一棵二叉树表示一棵树，可以很好地解决树的存储问题。 树转化为二叉树的方法： 1、在树中个兄弟之间加一连线； 2、对于任一结点，只保留它与最左孩子之间的连线 3、以树的根结点为轴心，

34、将整棵树按顺时针方向旋转成二叉树。,112,A,B,C,D,E,F,G,A B C E D F G,由树转换成的二叉树，其根结点的右子树总是空的。二叉树的根结点即是对应树的根结点，二叉树中任何结点与其左孩子是树中双亲孩子关系，而与其右孩子则是对应树中的兄弟关系。由此我们也可方便地将右子树为空的二叉树转化为树。,将树转换成二叉树 加线：在兄弟之间加一连线 抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系 旋转：以树的根结点为轴心，将整树顺时针转45,树转换成的二叉树其右子树一定为空,将二叉树转换成树 加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，沿分支找到的所有右

35、孩子，都与p的双亲用线连起来 抹线：抹掉原二叉树中双亲与右孩子之间的连线 调整：将结点按层次排列，形成树结构,森林转换成二叉树 将各棵树分别转换成二叉树 将每棵树的根结点用线相连 以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构,二叉树转换成森林 抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树 还原：将孤立的二叉树还原成树,117,森林转化为二叉树： 将森林中的每一棵树依次转换成相应的二叉树，然后将第二棵作为第一棵二叉树的根结点的右子树连接起来，将第三棵又作为第二棵的右子树连接起来.直至把所有的二叉树连接成一棵

36、二叉树。反之我们也可方便地将右子树不为空的二叉树转化为森林。,118,B,C,D,E,F,G,C,I,J,H,L,K,练习：,119,树的各种操作均可对应二叉树的操作来完成。,应当注意的是，和树对应的二叉树，其左、右子树的概念 已改变为： 左是孩子，右是兄弟,120,6.4.3树和森林的遍历,121,一、树的遍历,二、森林的遍历,三、树的遍历的应用,122,树的遍历可有三条搜索路径:,按层次遍历:,先根(次序)遍历:,后根(次序)遍历:,若树不空，则先访问根结点，然后依次先根遍历各棵子树。,若树不空，则先依次后根遍历各棵子树，然后访问根结点。,若树不空，则自上而下自左至右访问树中每个结点。,1

37、23,A B C D E F G H I J K,先根遍历时顶点的访问次序：,A B E F C D G H I J K,后根遍历时顶点的访问次序：,E F B C I J K H G D A,层次遍历时顶点的访问次序：,A B C D E F G H I J K,124,B C D E F G H I J K,1。森林中第一棵树的根结点；,2。森林中第一棵树的子树森林；,3。森林中其它树构成的森林。,森林由三部分构成：,125,1. 先序遍历,森林的遍历,若森林不空，则 访问森林中第一棵树的根结点; 先序遍历森林中第一棵树的子树森林; 先序遍历森林中(除第一棵树之外)其 余树构成的森林。,即

38、：依次从左至右对森林中的每一棵树进行先根遍历。,126,中序遍历,若森林不空，则 中序遍历森林中第一棵树的子树森林; 访问森林中第一棵树的根结点; 中序遍历森林中(除第一棵树之外)其 余树构成的森林。,即：依次从左至右对森林中的每一棵树进行后根遍历。,127,树的遍历和二叉树遍历的对应关系 ？,先根遍历,后根遍历,树,二叉树,森林,先序遍历,先序遍历,中序遍历,中序遍历,树的先根序遍历与后根序遍历可通过对其相应的二叉树的进行先序遍历和中序遍历得到,128,6.8 哈 夫 曼 树 与 哈 夫 曼 编 码,最优树的定义 如何构造最优树 前缀编码,129,一、最优树的定义,树的路径长度定义为： 树中

39、每个结点的路径长度之和。,结点的路径长度定义为： 从根结点到该结点的路径上分支的数目。,路径：从树中一个点到另一个结点之间的分支构成这两个节点的路径。,路径长度：路径上的分支数目,130,树的带权路径长度定义为： 树中所有叶子结点的带权路径长度之和 WPL(T) = wklk (对所有叶子结点),在所有含 n 个叶子结点、并带相同权 值的 m 叉树中，必存在一棵其带权路径 长度取最小值的树，称为“最优树”。,例如：,131,2,7 9,7,5,4,9,2,WPL(T)= 72+52+23+43+92 =60,WPL(T)= 74+94+53+42+21 =89,5,4,132,例 有4个结点，

40、权值分别为7，5，2，4，构造有4个叶子结点的二叉树,WPL=7*2+5*2+2*2+4*2=36,WPL=7*3+5*3+2*1+4*2=46,WPL=7*1+5*2+2*3+4*3=35,133,根据给定的 n 个权值 w1, w2, , wn， 构造 n 棵二叉树的集合 F = T1, T2, , Tn， 其中每棵二叉树中均只含一个带权值 为 wi 的根结点,其左、右子树为空树;,二、如何构造最优树,(1),(赫夫曼算法) 以二叉树为例:,134,在 F 中选取其根结点的权值为最 小的两棵二叉树，分别作为左、 右子树构造一棵新的二叉树，并 置这棵新的二叉树根结点的权值 为其左、右子树根结

41、点的权值之 和;,(2),135,从F中删去这两棵树，同时加入 刚生成的新树;,重复 (2) 和 (3) 两步，直至 F 中只 含一棵树为止。,(3),(4),136,9,例如: 已知权值 W= 5, 6, 2, 9, 7 ,5,6,2,7,5,2,7,6,9,7,6,7,13,9,5,2,7,137,6,7,13,9,5,2,7,9,5,2,7,16,6,7,13,29,0,0,0,0,1,1,1,1,00,01,10,110,111,138,例 w=5, 29, 7, 8, 14, 23, 3, 11,139,Huffman算法实现,Ch5_8.c,一棵有n个叶子结点的Huffman树有2n-1个结点 采用顺序存储结构一维结构数组 结点类型定义,typedef struct int data; int pa,lc,rc; JD;,140,Ch5_8.c,141,#define M 50 #define MAX 100 typedef struct int data; int parent, lchild, rchild; HuffmanTree; void huffman(int n, int w, HuffmanTree t) int i, j, k, x1, x2, m1, m2; for(i=1;i(2*n);i+) ti. parent