第02章算法与数据结构-04树和二叉树1

1、第第2章章 树和二叉树树和二叉树树的概念和基本术语二叉树 二叉树遍历二叉树的计数树与森林霍夫曼树 树的概念和基本术语树的概念和基本术语树的定义树的定义树是由树是由 n (n 0) 个结点的有限集合。如个结点的有限集合。如果果 n = 0，称为空树；如果，称为空树；如果 n 0，则，则 有且仅有一个特定的称之为根有且仅有一个特定的称之为根(Root)的结的结点，它只有直接后继，但没有直接前驱；点，它只有直接后继，但没有直接前驱； 当当n 1，除根以外的其它结点划分为，除根以外的其它结点划分为 m (m 0) 个互不相交的有限集个互不相交的有限集 T1, T2 , Tm，其中每个集合本身又是一棵树

2、，并且称为其中每个集合本身又是一棵树，并且称为根的子树根的子树(SubTree)ACGBDEFKLHMIJ例如例如A只有根结点的树只有根结点的树有有13个结点的树个结点的树其中：其中：A是根；其余结点分成三个互不相交的子集，是根；其余结点分成三个互不相交的子集，T1=B,E,F,K,L； T2=C,G； T3=D,H,I,J,M,T1,T2,T3都是根都是根A的子树，且本身也是一棵树的子树，且本身也是一棵树树的基本术语树的基本术语1层2层4层3层height= 4ACGBDEFKLHMIJ二叉树二叉树 (Binary Tree)定义定义五种形态五种形态一棵二叉树是结点的一个有限集合，一棵二叉树

3、是结点的一个有限集合，该集合或者为空，或者是由一个根结点加该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不上两棵分别称为左子树和右子树的、互不相交的二叉树组成。相交的二叉树组成。LLRR特点特点每个结点至多只有两棵子树（二叉树中每个结点至多只有两棵子树（二叉树中不存在度大于不存在度大于2的结点）的结点）性质性质1 在二叉树的第在二叉树的第 i 层上至多有层上至多有 2i 1个结点。个结点。(i 1) 证明用归纳法证明用归纳法证明：当证明：当i=1时，只有根结点，时，只有根结点，2 i-1=2 0=1。假设对所有假设对所有j，ij 1，命题成立，即第，命题成立，即第j层层

4、上至多有上至多有2 j-1 个结点。个结点。由归纳假设第由归纳假设第i-1 层上至多有层上至多有 2i 2个结点。个结点。由于二叉树的每个结点的度至多为由于二叉树的每个结点的度至多为2，故在，故在第第i层上的最大结点数为第层上的最大结点数为第i-1层上的最大结层上的最大结点数的点数的2倍，即倍，即2* 2i 2= 2 i-1。性质性质性质性质2 深度为深度为 k 的二叉树至多有的二叉树至多有 2 k- -1个结点个结点(k 1)。证明：由性质证明：由性质1可见，深度为可见，深度为k的二叉树的的二叉树的最大结点数为最大结点数为 kii11220 + 21 + + 2 k-1 = 2 k- -1k

5、ii1(层上的最大结点数）第性质性质3 对任何一棵二叉树对任何一棵二叉树T, 如果其叶如果其叶结点数为结点数为 n0, 度为度为2的结点数为的结点数为 n2,则则n0n21.证明：若度为证明：若度为1的结点有的结点有 n1 个，总结点个个，总结点个数为数为 n，总边数为，总边数为 e，则根据二叉树的定，则根据二叉树的定义，义， n = n0 + n1 + n2 e = 2n2 + n1 = n - - 1因此，有因此，有 2n2 + n1 = n0 + n1 + n2 - - 1 n2 = n0 - - 1 n0 = n2 + 1 定义定义1 满二叉树满二叉树 (Full Binary Tre

6、e) 一棵深度为一棵深度为k且有且有2 k-1个结点的二叉树称为个结点的二叉树称为满二叉树。满二叉树。两种特殊形态的二叉树两种特殊形态的二叉树621754389 10 1113 14 1512满二叉树满二叉树215436 7216543非完全二叉树非完全二叉树定义定义2 完全二叉树完全二叉树 (Complete Binary Tree) 若设二叉树的高度为若设二叉树的高度为h，则共有，则共有h层。除层。除第第 h 层外，其它各层层外，其它各层 (0 h- -1) 的结点数都的结点数都达到最大个数，第达到最大个数，第 h 层层从右向左从右向左连续缺若干连续缺若干结点，这就是完全二叉树。结点，这就

7、是完全二叉树。621754389 10 11 12完全二叉树完全二叉树性质性质4 具有具有 n (n 0) 个结点的完全二叉树个结点的完全二叉树的深度为的深度为 log2(n) 1证明：证明：设完全二叉树的深度为设完全二叉树的深度为 h，则根据性，则根据性质质2和完全二叉树的定义有和完全二叉树的定义有2h1 - - 1 n 2h- - 1或或 2h1 n 2h取对数取对数 h1 1, 则则 i 的双亲为的双亲为 i /2 n 若若2*i =n, 则则 i 的左子女为的左子女为 2*i，若，若2*i+1- leftChild ); destroy ( current - rightChild )

8、; free( current); 基本算法基本算法BinTreeNode *Parent ( BinTreeNode * start, BinTreeNode * cuurent ) /找当前结点的双亲结点，并返回找当前结点的双亲结点，并返回 if ( start = NULL ) return NULL; if ( start-leftChild = current | start-rightChild = current ) return start; /找到找到 BinTreeNode *p; /否则否则 if ( p = Parent ( start-leftChild, curre

9、nt )!= NULL ) return p; /在左子树中找在左子树中找 else return Parent(start-rightChild, current); /在右子树中找在右子树中找void BinaryTree Traverse ( BinTreeNode *current) /搜索并输出根为搜索并输出根为current的二叉树的二叉树 if ( current != NULL ) printf（”%d”,current-data）；）； Traverse ( current-leftChild); Traverse ( current-rightChild); void Cr

10、t_BinTree (BinTreeNode &T ) TreeData x; scanf(%d,&x); /读入根结点的值读入根结点的值 if ( x != 0) T =(BinTreeNode* ) malloc(sizeof(BinTreeNode); /建立根结点建立根结点 T-data = x; Crt_BinTree (T-leftChild ); Crt_BinTree (T-rightChild ); else T = NULL; 二叉树遍历二叉树遍历树的遍历就是按某种次序访问树中的结树的遍历就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。点，要

11、求每个结点访问一次且仅访问一次。 设访问根结点记作设访问根结点记作 V 遍历根的左子树记作遍历根的左子树记作 L 遍历根的右子树记作遍历根的右子树记作 R 则可能的遍历次序有则可能的遍历次序有 前序前序 VLR 中序中序 LVR 后序后序 LRV VLR 中序遍历二叉树算法的定义：中序遍历二叉树算法的定义：若二叉树为空，则空操作；若二叉树为空，则空操作；否则否则中序遍历左子树中序遍历左子树 (L)；访问根结点访问根结点 (V)；中序遍历右子树中序遍历右子树 (R)。遍历结果遍历结果 a + b * c - - d - - e / f中序遍历中序遍历 (Inorder Traversal)voi

12、d InOrder ( BinTreeNode *T ) if ( T != NULL ) InOrder ( T-leftChild ); printf(“%d”, T-data); InOrder ( T-rightChild ); 中序遍历二叉树的递归算法中序遍历二叉树的递归算法 前序遍历二叉树算法的定义：前序遍历二叉树算法的定义：若二叉树为空，则空操作；若二叉树为空，则空操作；否则否则访问根结点访问根结点 (V)；前序遍历左子树前序遍历左子树 (L)；前序遍历右子树前序遍历右子树 (R)。遍历结果遍历结果 - - + a * b - - c d / e f前序遍历前序遍历 (Preor

13、der Traversal)前序遍历二叉树的递归算法前序遍历二叉树的递归算法void PreOrder ( BinTreeNode *T ) if ( T != NULL ) printf(“%d”, T-data); PreOrder ( T-leftChild ); PreOrder ( T-rightChild ); 后序遍历二叉树算法的定义：后序遍历二叉树算法的定义：若二叉树为空，则空操作；若二叉树为空，则空操作；否则否则后序遍历左子树后序遍历左子树 (L)；后序遍历右子树后序遍历右子树 (R)；访问根结点访问根结点 (V)。遍历结果遍历结果 a b c d - * + e f / -

14、后序遍历后序遍历 (Postorder Traversal)后序遍历二叉树的递归算法：后序遍历二叉树的递归算法：void PostOrder ( BinTreeNode * T ) if ( T != NULL ) PostOrder ( T-leftChild ); PostOrder ( T-rightChild ); printf(“%d”, T-data); 二叉树遍历应用二叉树遍历应用n以递归方式建立二叉树。以递归方式建立二叉树。n输入结点值的顺序必须对应二叉树结点前输入结点值的顺序必须对应二叉树结点前序遍历的顺序。并约定以输入序列中不可序遍历的顺序。并约定以输入序列中不可能出现的值

15、作为空结点的值以结束递归能出现的值作为空结点的值以结束递归, 此值在此值在RefValue中。例如用中。例如用“”或用或用“- -1”表示字符序列或正整数序列空结点。表示字符序列或正整数序列空结点。 按前序建立二叉树按前序建立二叉树(递归算法递归算法)如图所示的二叉树的前序遍历顺序为如图所示的二叉树的前序遍历顺序为A B C D E G F ABCDEGF void Crt_BinTree (BinTreeNode &T ) TreeData x; scanf(%d,&x); /读入根结点的值读入根结点的值 if ( x != 0 ) T =(BinTreeNode* ) ma

16、lloc(sizeof(BinTreeNode); /建立根结点建立根结点 T-data = x; Crt_BinTree (T-leftChild ); Crt_BinTree (T-rightChild ); else T = NULL; main() bintree bt1; crt_bintree(bt1); inorder(bt1); 建立二叉树的子程序建立二叉树的子程序 建立二叉树的主程序建立二叉树的主程序main() bintree bt1; vrt_bintree(bt1); inorder(bt1); int Count ( BinTreeNode *T ) if ( T =

17、 nil ) return 0; else return 1 + Count ( T-leftChild ) + Count ( T-rightChild );2.计算二叉树结点个数计算二叉树结点个数(递归算法递归算法)int Leaf_Count(Bitree T) /求二叉树中叶子结点的数目求二叉树中叶子结点的数目if(T=nil) return 0; /空树没有叶子空树没有叶子 else if(T-lchild=nil&T-rchild=nil) return 1; /叶子结点叶子结点 else return Leaf_Count(T-lchild)+Leaf_Count(T-r

18、child); /左子树的叶子数加上右子树的叶子数左子树的叶子数加上右子树的叶子数3.求二叉树中叶子结点的个求二叉树中叶子结点的个数数int Height ( BinTreeNode * T ) if ( T = NULL ) return 0 0; elseint m = Height ( T-leftChild );int n = Height ( T-rightChild ) ); return (m n) ? m+1 : n+1; 4.求二叉树高度求二叉树高度(递归算法递归算法)5.复制二叉树复制二叉树(递归算法递归算法)int Copy( BinTreeNode * T ) if (

19、 T = NULL ) return - -1;BinTreeNode * temp=new BinTreeNode; Temp-data=T-data;Temp- leftChild = Copy( T-leftChild ); Temp- rightChild = Copy(T-rightChild ); return temp;6.判断二叉树等价判断二叉树等价(递归算法递归算法)int Equal( BinTreeNode *a, BinTreeNode *b) if ( a = NULL & b = NULL ) return 1; if ( a != NULL & b

20、 != NULL & a-data=b-data & equal( a-leftChild, b-leftChild) & equal( a-rightChild, b- -rightChild) ) return 1; return 0;/如果如果a和和b的子树不等同，则函数返回的子树不等同，则函数返回0中序遍历二叉树中序遍历二叉树(非递归算法非递归算法)用栈实现用栈实现baabcdeadaaa b入栈入栈b退栈退栈访问访问d入栈入栈d退栈退栈访问访问e 退栈退栈 访问访问ecc栈空栈空 a退栈退栈访问访问c e 入栈入栈c 退栈退栈 访问访问 void InOrde

21、r ( BinTree T ) stack S; InitStack( &S ); /递归工作栈递归工作栈 BinTreeNode *p = T; /初始化初始化 while ( p != NULL | !StackEmpty(&S) ) if( p != NULL ) Push(&S, p); p = p-leftChild; if ( !StackEmpty(&S) ) /栈非空栈非空 Pop(&S, p); /退栈退栈 cout -data -rightChild; /if /while return ok;abcde前序遍历二叉树前序遍历二叉树(

22、非递归算法非递归算法)用栈实现用栈实现acabcdedcc访问访问a进栈进栈c左进左进b访问访问b进栈进栈d左进左进空空退栈退栈d访问访问d左进左进空空退栈退栈c访问访问c左进左进e访问访问e左进左进空空退栈退栈 结束结束void PreOrder( BinTree T ) stack S; InitStack(&S); /递归工作栈递归工作栈 BinTreeNode * p = T; Push (&S, NULL); while ( p != NULL ) cout -data -rightChild != NULL ) Push ( &S, p-rightChild

23、 ); if ( p-leftChild != NULL ) p = p-leftChild;/进左子树进左子树 else Pop( &S, p ); abcdev后序遍历二叉树后序遍历二叉树(非递归算法非递归算法)用栈实现用栈实现后序遍历时使用的栈的结点定义后序遍历时使用的栈的结点定义typedef struct BinTreeNode *ptr; /结点指针结点指针 enum tag L, R ; /该结点退栈标记该结点退栈标记 StackNode; 根结点的根结点的 tag = L，表示从左子树退出，表示从左子树退出, 访问右子树。访问右子树。 tag = R, 表示表示从右子树

24、退出从右子树退出, 访问根。访问根。ptr tagL,R vvoid PostOrder ( BinTree T ) stack S; InitStack(&S); StackNode w; BinTreeNode * p = T; do while ( p != NULL ) /向左子树走向左子树走 w.ptr = p; w.tag = L; Push (&S, w); p = p-leftChild; int continue = 1; /继续循环标记继续循环标记 while ( continue & !StackEmpty(&S) ) Pop (&

25、S, w); p = w.ptr; switch ( w.tag ) /判断栈顶判断栈顶tag标记标记 case L : w.tag = R; Push (&S, w); continue = 0; p = p-rightChild; break; case R : cout -data endl; while ( p != NULL | !StackEmpty(&S) ); cout -leftChild; p-leftChild = p-rightChild; p-rightChild = temp; unknown ( p-leftChild ); unknown ( p

26、-rightChild ); void unknown ( BinTreeNode * T ) BinTreeNode *p = T, *temp; while ( p != NULL ) temp = p-leftChild; p-leftChild = p-rightChild; p-rightChild = temp; unknown ( p-leftChild ); p = p-rightChild; 不用栈消去递归算法中的第二个递归语句不用栈消去递归算法中的第二个递归语句 使用栈消去递归算法中的两个递归语句使用栈消去递归算法中的两个递归语句void unknown ( BinTree

27、Node * T ) BinTreeNode *p, *temp; stack S; InitEmpty (&S); if ( T != NULL ) push(&S, T); while ( ! StackEmpty(&S) ) Pop(&S, p); /栈中退出一个结点栈中退出一个结点 temp = p-leftChild; /交换子女交换子女 p-leftChild = p-rightChild; p-rightChild = temp; if ( p-rightChild != NULL ) push (&S, p-rightChild ); i

28、f ( p-leftChild != NULL ) push (&S, p-leftChild ); LeftThread=0, LeftChild为为左子女指针左子女指针LeftThread=1, LeftChild为为前驱线索前驱线索RightThread=0, RightChild为为右子女指针右子女指针RightThread=1, RightChild为为后继指针后继指针LeftThreadRightThreadv线索二叉树线索二叉树 (Threaded Binary Tree)结点结构结点结构template class ThreadNode friend class Thr

29、eadTree;private: int leftThread, rightThread; ThreadNode *leftChild, *rightChild; Type data;public: ThreadNode ( const Type item ) : data (item), leftChild (NULL), rightChild (NULL), leftThread (0), rightThread (0) ;中序线索二叉树的类定义中序线索二叉树的类定义template class ThreadTree; vtemplate class ThreadTree private:

30、 ThreadNode * root; /根根 InThread ( ThreadNode * current, ThreadNode * pre ); /建树建树public: ThreadTree ( ) : root (NULL) ; /构造函数构造函数 ThreadNode * First ( ThreadNode * current ); ThreadNode * Last ( ThreadNode * current ); ThreadNode * Next ( ThreadNode * current ); ThreadNode * Prior ( ThreadNode * cu

31、rrent ); 通过中序遍历建立中序线索化二叉树通过中序遍历建立中序线索化二叉树template void ThreadTree :InThread ( ThreadNode * current, ThreadNode *& pre ) if ( current != NULL ) InThread ( current-leftChild, pre ); /递归递归, 左子树线索化左子树线索化 if ( current-leftChild = NULL ) current-leftChild = pre; current-leftThread = 1; /建立当前结点的前驱线索建立当

32、前结点的前驱线索 if ( pre != NULL & pre-rightChild = NULL ) pre-rightChild = current; pre-rightThread = 1; /建立前驱结点的后继线索建立前驱结点的后继线索pre = current;/前驱跟上当前指针前驱跟上当前指针InThread ( current-rightChild, pre ); /递归递归, 右子树线索化右子树线索化 q树的存储结构树的存储结构双亲表示：以一组连续空间存储树的结点，双亲表示：以一组连续空间存储树的结点，同时在同时在结点中附设一个指针，存放双亲结点结点中附设一个指针，存放

33、双亲结点在链表中的位置。在链表中的位置。树与森林树与森林ABCDEFGdataparentA B C D E F G- -1 0 0 0 1 1 30 1 2 3 4 5 6用双亲表示实现的树定义用双亲表示实现的树定义#define MaxSize /最大结点个数最大结点个数typedef char TreeData; /结点数据结点数据typedef struct /树结点定义树结点定义 TreeData data; int parent; TreeNode;TreeNode TreeMaxSize; /树树ABCDEFG左子女左子女- -右兄弟表示法右兄弟表示法第一种解决方案第一种解决方案

34、 等数量的链域等数量的链域 data child1child2child3childdABCDEFG 空链域n(k-1)+1个结点结构结点结构 datafirstChildnextSiblingABCDEFG空链域n+1个第二种解决方案第二种解决方案 树的左子女树的左子女- -右兄弟表示右兄弟表示（二叉链表表示）（二叉链表表示）BCDGFE A typedef char TreeData;typedef struct node TreeData data; struct node *firstChild, *nextSibling; TreeNode;typedef TreeNode * Tr

35、ee;用左子女用左子女- -右兄弟表示实现的树定义右兄弟表示实现的树定义T1 T2 T3T1 T2 T3AFHB C DGIJEKAFBCDEGHIKJABCEDHIKJFG3 棵树的森林各棵树的二叉树表示森林的二叉树表示q森林与二叉树的转换森林与二叉树的转换树的二叉树表示树的二叉树表示:q树的遍历树的遍历n深度优先遍历深度优先遍历u 先根次序遍历先根次序遍历u 后根次序遍历后根次序遍历ABCDE FGABCEDGF深度优先遍历深度优先遍历n当树非空时当树非空时u 访问根结点访问根结点u 依次先根遍历根的各棵依次先根遍历根的各棵 子树子树n树先根遍历树先根遍历 ABEFCDGn对应二叉树前序遍

36、历对应二叉树前序遍历 ABEFCDGn树的先根遍历结果与其对应二叉树树的先根遍历结果与其对应二叉树 表示的前序遍历结果相同表示的前序遍历结果相同n树的先根遍历可以借助对应二叉树的前序遍历树的先根遍历可以借助对应二叉树的前序遍历算法实现算法实现ABCEDGF树的树的先根次序先根次序遍历遍历树的树的后根次序后根次序遍历遍历:n当树非空时当树非空时u依次后根遍历根的各棵依次后根遍历根的各棵 子树子树u访问根结点访问根结点n树后根遍历树后根遍历 EFBCGDAn对应二叉树中序遍历对应二叉树中序遍历 EFBCGDAn树的后根遍历结果与其对应二叉树树的后根遍历结果与其对应二叉树 表示的中序遍历结果相同表示

37、的中序遍历结果相同n树的后根遍历可以借助对应二叉树的中序遍历算树的后根遍历可以借助对应二叉树的中序遍历算法实现法实现ABCEDGF二叉树的计数二叉树的计数由二叉树的前序序列和中序序列可唯一由二叉树的前序序列和中序序列可唯一地确定一棵二叉树。地确定一棵二叉树。 例例, 前序序列前序序列 ABHFDECKG 和中序序和中序序列列 HBDFAEKCG , 构造二叉树过程如下：构造二叉树过程如下：HBDFEKCGAEKCGABHDFKCGEKCGABHDFEKCGABHFDEABHFDEABHFDCKG 如果前序序列固定不变，给出不同的中序如果前序序列固定不变，给出不同的中序序列，可得到不同的二叉树。

38、序列，可得到不同的二叉树。612345789612375849固定前序排列固定前序排列,选择所有可能的中序排列选择所有可能的中序排列,可以构造多少种不同的二叉树？可以构造多少种不同的二叉树？例如例如, 有有 3 个数据个数据 1, 2, 3 ，可得，可得 5 种不种不同的二叉树。它们的前序排列均为同的二叉树。它们的前序排列均为 123，中，中序序列可能是序序列可能是 321 ， 231， 213， 132，123.123123123123123具有具有n个结点不同形态的树的数目和具有个结点不同形态的树的数目和具有n-1个结点互不相似的二叉树的数目相同。个结点互不相似的二叉树的数目相同。有有0个

39、个, 1个个, 2个个, 3个结点的不同二叉树如下个结点的不同二叉树如下b0 =1b1 =1b2 =2b3 =5 b4 =14!)!(211112nnnnnbCnnnv计算具有计算具有 n 个结点的不同二叉树的棵数个结点的不同二叉树的棵数最终结果：最终结果：1101niininbbb霍夫曼树霍夫曼树 (Huffman Tree)路径长度路径长度 (Path Length)两个结点之间的路径长度两个结点之间的路径长度 PL 是连接两结是连接两结点的路径上的分支数。点的路径上的分支数。 树的外部路径长度是各叶结点树的外部路径长度是各叶结点(外结点外结点)到到根结点的路径长度之和根结点的路径长度之和

40、 EPL。 树的内部路径长度是各非叶结点树的内部路径长度是各非叶结点(内结点内结点)到根结点的路径长度之和到根结点的路径长度之和 IPL。 树的路径长度树的路径长度 PL = EPL + IPL123456782345678树的外部路径长度树的外部路径长度EPL = 3*1+2*3 = 9树的外部路径长度树的外部路径长度EPL = 1*1+2*1+3*1+4*1 = 101带权路径长度带权路径长度 (Weighted Path Length, WPL)二叉树的带权二叉树的带权 (外部外部) 路径长度是树的各路径长度是树的各叶结点所带的权值叶结点所带的权值 wi 与该结点到根的路径长与该结点到根

41、的路径长度度 li 的乘积的和。的乘积的和。10niiilwWPLWPL = 2*2+ WPL = 2*1+ WPL = 7*1+ 4*2+5*2+ 4*2+5*3+ 5*2+2*3+ 7*2 = 36 7*3 = 46 4*3 = 35 222444555777带权带权( (外部外部) )路径路径长度达到最小长度达到最小霍夫曼树霍夫曼树n带权路径长度达到最小的二叉树即为霍夫带权路径长度达到最小的二叉树即为霍夫曼树。曼树。n在霍夫曼树中，权值大的结点离根最近。在霍夫曼树中，权值大的结点离根最近。(1) 由给定的由给定的 n 个权值个权值 w0, w1, w2, , wn-1，构造具有构造具有

42、n 棵扩充二叉树的森林棵扩充二叉树的森林 F = T0, T1, T2, , Tn-1 ，其中每棵扩充二叉树，其中每棵扩充二叉树 Ti 只有一只有一 个带权值个带权值 wi 的根结点的根结点, 其左、右子树均为空。其左、右子树均为空。 霍夫曼霍夫曼算法算法(2) 重复以下步骤重复以下步骤, 直到直到 F 中仅剩下一棵中仅剩下一棵树为止：树为止： 在在 F 中选取两棵根结点的权值最小的中选取两棵根结点的权值最小的扩充二叉树扩充二叉树, 做为左、右子树构造一棵新做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。为其左、

43、右子树上根结点的权值之和。 在在 F 中删去这两棵二叉树。中删去这两棵二叉树。 把新的二叉树加入把新的二叉树加入 F。F : 7 5 2 4F : 7 5 6F : 7 11 7524初始合并2 475246F : 18 1175246合并5 65合并7 11 27461118举例霍夫曼树的构造过程举例霍夫曼树的构造过程5274Weight parent leftChild rightChild7 -1 -1 -15 -1 -1 -12 -1 -1 -14 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -10123456上例存储结构上例存储结构初初 态态52746Weigh

44、t parent leftChild rightChild 7 -1 -1 -1 5 -1 -1 -1 2 -1 -1 -1 4 -1 -1 -1 6 -1 -1 -1 -1 -1 -1 -1 -1 -10123456p1p24423i过过 程程5274611Weight parent leftChild rightChild 7 -1 -1 -1 5 -1 -1 -1 2 4 -1 -1 4 4 -1 -1 6 -1 2 311 -1 -1 -1 -1 -1 -10123456p1p25514i5274611Weight parent leftChild rightChild 7 -1 -1 -1 5 5 -1 -1 2 4 -1 -1 4 4 -1 -1 6 5 2 311 -1 1 418 -1 -1 -10123456p1p26605i18终终 态态const int n = 20;/叶结点数叶结点数const int m = 2*n - -1;/结点数结点数 typedef struct float weight; int parent, leftChild, rightChild; HTNode;typedef HTNode HuffmanTreem;霍夫曼树的定义霍夫曼树的定义建立霍夫曼树的算法建立霍夫曼树的算法vo