树和二叉树第六章幻灯片

《树和二叉树第六章幻灯片》由会员分享，可在线阅读，更多相关《树和二叉树第六章幻灯片（104页珍藏版）》请在装配图网上搜索。

1、2021/8/51第六章 树和二叉树6.1树的定义和基本术语6.2二叉树6.3遍历二叉树和线索二叉树6.4树和森林6.6赫夫曼树及其应用2021/8/52 6.1 树的定义和基本术语树(Tree)：是n(n=0)个结点的有限集。在任意一个非空树中：有且仅有一个特定的称为根(Root)的结点；当n=1时，其余结点可分为m(m0)个互不相交的有限集T1,T2,Tm,其中Ti是一棵树，称为根结点子树例:(a)是只有一个根结点的树.(b)是有13个结点的树，A是根，其余结点分成三个互不相交的子集：T1=(B,E,F,K,L);T2=(C,G);T3=(D,H,I,J,M).T1,T2,T都是根A的子树

2、，本身也是一棵树2021/8/53AAFLDJGEBIKHMC(a)只有根结 点的树T1T2T3(b)一般的树 A是根，T1,T2,T3是三棵子树2021/8/54ADT Tree 数据对象D:D是具有相同特性的数据元素的集合. 数据关系R: 若D为空集，则称为空树； 若D仅含一个数据元素，则R为空集，否则R=H, H是如下二元关系： (1)在D中存在唯一的称为根的数据元素root，它在 关系H下无前驱； 抽象类型树的定义2021/8/55 (2)若D-root=，则存在D-root的一个划分D1 D2, Dn(m0),对任意j=k(1=j,k=m)有Dj Dk=,且对 任意的i(1=i=m)

3、,唯一存在数据元素xi Di，有 H;对应于D-root的划分，H-,有唯一的一个划分H1, H2, Hn(m0),对任意的j=k(1=j,k=m)有Hj Hk=，且对任意i(1=i=m), Hi是Di上的二元关系，(Di,Hi)是一棵符合本定义的树，称为根root的子树。 2021/8/56基本操作P:InitTree(&T);操作结果：构造空树T DestroyTree(&T);初始条件：树T存在操作结果：销毁树T树的基本操作2021/8/57CreatTree(&T,definition);初始条件：definition给出树T的定义操作结果：按definition树构造树T Clear

4、Tree(&T)初始条件：数T存在操作结果：将树T清为空树TreeEmpty(T);初始条件：树T存在操作结果：若T为空树，则返回TRUE，否则FALSE2021/8/58TreeDepth(T);初始条件：树T存在操作结果：返回T的深度Root(T);初始条件：树T 存在操作结果：返回T的根Value(T,cur_e);初始条件：树T存在，cur_e是T中某个结点操作结果：返回cur_e的值2021/8/59Assign(T,cur_e,value);初始条件：树T存在，cur_e是T中某个结点操作结果：结点cur_e赋值 为valueParent(T,cur_e);初始条件：树T存在，cu

5、r_e是T中某个结点操作结果：若cur_e是T的非根结点，则返回它的双亲，否则函数值为“空”LeftChild(T,cur_e);初始条件：树T存在，cur_e是T中某个结点操作结果：若cur_e是T的非叶子结点，则返回它的最左孩子，否则返回“空”2021/8/510RightSibling(T,cur_e);初始条件：树T存在，cur_e是T中某个结点操作结果：若cur_e有右兄弟，则返回它的右兄弟，否则 函数值为 “空”InsertChild(&T,&P,i,c);初始条件：树T存在，P指向T中某个结点，1=i=P所指结点的度+1,非空树c 与T不相交操作结果：插入c为T中p指结点第i棵子

6、树2021/8/511DeleteChild(&T,&P,i);初始条件：树T存在,p指向T中某个结点，1=i=0)棵互不相交的树的集合2021/8/517 6.2 二叉树定义：是一棵或为空树，或树中每个结点的度数 =2有序树特点：每个结点至多有两棵子树 二叉树的子树有左右之分,其次序不能 任意互换2021/8/518(a)(b)(c)(d)(e)(a)空 二叉树(b)仅有根结点的二叉树(c )右子树为空的二叉树(d)左，右子树均非空的 二叉树(e)左子树为空的二叉树二叉树的五中基本形态：2021/8/519InitBiTree(&T);操作结果：构造空二叉树T DestroyBiTree(&

7、T);初始条件：二叉树T存在操作结果：销毁二叉树T二叉树的基本操作2021/8/520CreatBiTree(&T,definition);初始条件：definition给出二叉树T的定义操作结果：按definition树构造二叉树T ClearBiTree(&T)初始条件：二叉树T存在操作结果：将二叉树T清为空树BiTreeEmpty(T);初始条件：二叉树T存在操作结果：若T为空二叉树，则返回TRUE，否则FALSE2021/8/521BiTreeDepth(T);初始条件：二叉树T存在操作结果：返回T的深度Root(T);初始条件：二叉树T 存在操作结果：返回T的根Value(T,e);

8、初始条件：二叉树T存在，e是T中某个结点操作结果：返回e的值2021/8/522Assign(T,cur_e,value);初始条件：树T存在，cur_e是T中某个结点操作结果：结点cur_e赋值 为valueParent(T,e);初始条件：二叉树T存在，e是T中某个结点操作结果：若e是T的非根结点，则返回它的双亲，否则返回“空”LeftChild(T,e);初始条件：二叉树T存在，e是T中某个结点操作结果：返回e的左孩子，若无左孩子.返回“空”2021/8/523RightChild(T,e);初始条件：二叉树T存在，e是T中某个结点操作结果：返回e的右孩子若无右孩子.返回“空”LeftS

9、ibling(T,cur_e);初始条件：二叉树T存在，e是T中某个结点操作结果：返回e的左兄弟，否则函数值为 “空”2021/8/524RightSibling(T,e);初始条件：二叉树T存在，e是T中某个结点操作结果：返回e的右兄弟，否则函数值为 “空”InsertChild(T,P,LR,c);初始条件：二叉树T存在，P指向T中某个结点，LR为0或者1,非空二叉树c 与T不相交并且右子树为空.操作结果：根据 LR为0或1,插入c为T中p指结点左或右子树.P所指结点的原有左或者右子树则成为c的右子树2021/8/525DeleteChild(T,P,LR);初始条件：二叉树T存在,p指向

10、T中某个结点，LR为0或1.操作结果： 根据LR为0或1,删除T中P所指结点的左或者右子树PreorderTraverse(T,Visit();初始条件：二叉树T存在,Visit是对结点操作的应用函数操作结果：按先序遍历二叉树T,对T的每个结点调用函数visit()一次且至多一次，一旦visit()失败，则操作失败2021/8/526InorderTraverse(T,Visit();初始条件：二叉树T存在,Visit是对结点操作的应用函数操作结果：中序遍历树T,对T的每个结点调用函数visit()一次且至多一次，一旦visit()失败，则操作失败. PostTraverse(T,Visit(

11、);初始条件：二叉树T存在,Visit是对结点操作的应用函数操作结果：后序遍历树T,对T的每个结点调用函数visit()一次且至多一次，一旦visit()失败，则操作失败2021/8/527LevelTraverseT(T,Visit();初始条件：二叉树T存在,Visit是对结点操作的应用函数操作结果：层次遍历树T,对T的每个结点调用函数visit()一次且至多一次，一旦visit()失败，则操作失败.ADT Binarytree2021/8/528性质1 在二叉树的第i层上至多有2i-1各结点证明：用归纳法证明 i=1时，只有一个根结点.显然，2i-1= 20=1是对的 设当n=k-1时，

12、第k-1层上至多有2k-2个结点 则当n=k时，每个结点至多有两棵子树 所以：k层结点数最多为k-1层的2倍 所以：S=1)由性质1可知，深度为k的二叉树的最大结点数为i=1 k(第i层上的最大结点数)= i=1 k2i-1=2k-12021/8/530性质3 对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0= n2+1 证明：设n1为二叉树T中度为1的结点数。因为二叉树中所有结点的度均小于或等于2，所以结点总数为 n= n0+n1+ n2 (1) 对二叉树的分支数，除了根结点外，其余结点都有一个分支进入，设B为分支总数，则n=B+1。由于这些分支是由度为1或2的结点射

13、出的，所以又有B=n1+2n2 得出：n=n1+2n2+1 (2) 由式(1)和式(2)得: n0=n2+1 2021/8/531特殊形态的二叉树满二叉树：深度为k,具有2k-1个结点得二叉树完全二叉树：对深度为k，n个结点的二叉树，当且仅当其每个结点都与深度为k的完整二叉树结点为编号从1到n结点一一对应2021/8/532 特殊形态的二叉树图示6175432165432满二叉树完全二叉树2021/8/533性质4 具有n个结点的完全二叉树的深度为 log2n +1证明：假设深度为k，则根据性质2和完全二叉树的定义有 2k-1-1n=2k-1 于是k-1= log2nk 因为 k是整数 所以原

14、题得证 完全二叉树的两个重要特性2021/8/534性质5 如果对一棵有n个结点的完全二叉树，则对任一结点i(1=n)有如果i=1，则结点i是二叉树的根，无双亲;如果i1,则其双亲PARENT(i)是结点 i/2 。如果2in,则结点i无左孩子（结点i为叶子结点);否则其左孩子LCHILD(i)是结点2i.如果2i+1n,则结点i无右孩子;否则其右孩子RCHILD(i)是结点2i+12021/8/535顺序存储结构：15643271 2 3 4 5 6 7对应顺序存储结构完全二叉树二叉树的存储结构2021/8/53613564271 2 3 4 5 0 0 0 0 6 7一般二叉树顺序存储结构

15、2021/8/537二叉树的顺序存储表示#define MAX_TREE_SIZE 100 /二叉树的最大结点数Typedef TElemType SqBiTreeMAX_TREE_SIZE; /0号单元存储根结点SqBiTree bt;2021/8/538链式存储结构二叉链表 结点结构lchilddatarchild左指针域 数据域 右指针域2021/8/539二叉树的二叉链表存储表示nTypedef struct Bitnode TElemType data; struct BiTNode *lchild,*rchild; /左,右孩子指针 BiTNode,*BiTree;2021/8/5

16、40三叉链表 结点结构lchildDataParent rchild双亲结点域ADCBABCD单支树的二叉链表2021/8/541ADFEBCGABDCFEG二叉链表2021/8/542ACBDFEGA B CD F E G三叉链表2021/8/5436.3遍历二叉树和线索二叉树遍历二叉树：访问每个结点，一次仅且一次先序遍历二叉树的操作定义为： 若二叉树为空，则空操作；否则 访问根结点 先序遍历左子树 先序遍历右子树中序遍历二叉树的操作定义为： 若二叉树为空，则空操作；否则 中序遍历左子树 访问根结点； 中序遍历右子树2021/8/544后序遍历二叉树的操作定义 若二叉树为空，则空操作；否则

17、后序遍历左子树 后序遍历右子树 访问根结点层次遍历二叉树的操作定义 若二叉树为空，则空操作； 否则从上到下,从左到右依次访问各个结点2021/8/545例：如图所示的二叉树，表示下述表达式 a+b*(cd)e/f若先序遍历此树，得到前缀表达式（波兰式） +a*bcd/ef若中序遍历二叉树，得到中缀表达式 a+b*cde/f若后序遍历二叉树，的到后缀表达式（逆波兰式） a b c d *+ e f/fe/+a*bdc2021/8/546算法6.1Status PreOrderTraverse(BiTree T,Status (*Visit) (TElemType e)If (T) if (Vis

18、it (T-data) if(PreorderTraverse(T-lchild,Visit) if(PreorderTraverse(T-rchild,Visit) return OK; return ERROR;else return OK;/PreorderTraverse先序遍历二叉树的递归算法2021/8/547层次遍历二叉树的算法n用队列辅助实现Status leverOrderTraverse(BiTree T,Statut (*Visit) (TElemType e) InitQueue(Q); EnQueue(Q,T); while(!QueueEmpty(Q) DelQue

19、ue(Q,p); if (p!=NULL) visit(p-data); EnQueue(Q,p-lchild); EnQueue(Q,p-rchild);/whileReturn OK;2021/8/548二叉树遍历的非递归算法n一.先序遍历非递归算法 先序遍历的特点是:首先访问根结点,访问完根后访问左子树,所以对每一个结点,访问完该结点后,沿其左孩子链访问下去,直到左链为空.这时,所有访问过的结点进栈.然后结点出栈,对于每一个出栈结点,即表示该结点和其左子树已经被访问结束,按先序遍历定义,应该访问该结点的右子树2021/8/549n算法思想:n1.当前指针指向根结点.n2.访问当前结点,并

20、且进栈,当前指针指向当前结点的左孩子,重复2,直到左孩子为空n3. 依次退栈,将当前指针指向出栈结点的右孩子.n4.若栈非空,或者当前指针非空,执行2,否则结束.2021/8/550Status preorder(BiTreeT,status(*visit() initstack(s); push(s,T); while (!stackempty(s) while( gettop(s,p)&p) if (visit(p-data) reture ERROR; push(s,p-lchild);2021/8/551 pop(s,p); if(!stackempty(s) pop(s,p); pu

21、sh(s,p-rchild); /if /whileReturn OK;2021/8/552二.中序遍历非递归算法n二.中序遍历非递归算法n中序的 特点是:首先访问左子树,所以对每一个结点,沿左链走下去,直到左链为空,所有经过的结点进栈.然后结点出栈,对于每一个出栈结点,表示该结点的左子树访问结束.按中序遍历的定义,应该访问该结点(根),访问完该结点后,访问该结点的右子树.2021/8/553n1.当前指针指向根结点.n2.当前结点进栈,当前指针指向其左孩子,重复2,直到左孩子为空.n3.依次退栈,退栈指针成为当前指针,访问当前结点.n4.将当前指针指向右孩子.n5.若栈非空或者当前指针非空,

22、执行2;否则结束.2021/8/554nStatus inorder(Bitree T,status(*visit() initstack(s); push(s,t); while(!stackEmpt(s) while(gettop(s,p)&p) push(s,p-lchild); pop(s,p);2021/8/555n if(!stackEmpty(s) pop(s,p); if (!visit(p-data) return ERROR; push (s,p-rchild); /if /whileReturn OK;2021/8/556三.后序遍历非递归算法n三.后序遍历非递归算法 在

23、后序遍历中,当当前指针指向某个结点时,不能马上进行访问,而先要遍历左子树,所以要求该结点进栈保存.当访问完它的左子树后,再次搜索该结点时,还不能进行访问,还要遍历其右子树.所以需要再次将此结点入栈保存.为了区别同一结点的两次入栈,需要引进一个入栈次数的标志.我们约定:标志0为该结点首先入栈,标志1为该结点第二次入栈.为此需要设两个栈:一个栈用来存放结点地址,即为结点栈s1m,另一个栈用来存放结点进栈标志,即标志栈s2m,栈指针为同一个.2021/8/557n1.当前指针指向根结点n2.当前结点进栈,所对应的标志为0,当前指针其左孩子,重复2,直到左孩子为空.n3.当栈顶标志为1时,依次退栈,并

24、且访问退栈指针所指结点,直到标志为0n4.将栈顶标志变成为1,将当前指针指向栈顶元素的右孩子,准备遍历右子树.n5.若栈顶非空或者当前指针非空,执行2,否则结束.2021/8/558nVoid postorder(BiTree T,status(*visit() int s2m,top=0; BiTree p,s1m; p=T; do while (p!=NULL) s1top=p; s2top+=0; /p结点首先入栈 p=p-lchild; /遍历左子树 2021/8/559 while(top & s2top-1=1) top-;p=s1top; visit(p-data); If(to

25、p0) s2top-1=1; P=s1top-1-rchild; /修改标志,即处理当前根结点的右子树并且使p指向右子树 while (top0);2021/8/560-bac*表达式(a*b-c)的二叉树-bac*12-*abc-*aabbcc遍历的递归执行过程，其中红色，蓝色，绿色分别表示先序，中序，后序遍历过程中访问结点输出信息2021/8/561方法一：LeftData rightLeftPDataNright指向前驱结点指向某一种遍历下后继结点在二叉链表中增加指向某一种遍历下前驱和后继指针(线索）目的：提高查找某一种遍历下前驱和后继结点效率线索二叉树2021/8/562n方法二：n利

26、用二叉链表中（n+1个）空指针域来作为指向某一种遍历下前趋和后继结点的指针域，为了区别指针的用途，同时在每个结点增加两个标志域Ltag,Rtag2021/8/563 lchild LtagDataRtagrchild其中：Ltag= 0 lchild域指示结点的左孩子 1 lchild域指示结点的前驱Rtag= 0 rchild域指示结点的右孩子 1 rchild域指示结点的后继2021/8/564b/fedc*a+NILNIL中序线索二叉树2021/8/565010 00 / 00 + 01 e 11 f 10*01 a 10 01 b 11 d 11 c 1thrtbt中序线索链表2021

27、/8/566二叉树的二叉线索存储表示二叉树的二叉线索存储表示：Typedef enum Link, Thread PointerTag; /Link= =0:指针 ，Thread= =1;线索Typedef struct BiThrNode TElemType data; struct BiThrNode *lchild,*rchild; /左右孩子指针 PointerTag Ltag,Rtag; /左右标志 BiThrNode, *BiThrTree;2021/8/567 a.只要找到序列中第一个结点，然后依次找结点后继直至其后继为空为止。 如何在中序线索树中找结点的后继的方法：（1）若Rt

28、ag=1，则rchild指的是后继结点（2）若Rtag=0，则右子树的最左孩子为其后继结点在线索树上进行遍历的方法2021/8/568 b. 或只要找到序列中最后一个结点，然后依次找结点前趋直至其前趋为空为止。 如何在中序线索树中找结点前趋的方法：（1）若Ltag=1，则lchild指的是前趋结点（2）若Ltag=0，则左子树的最右孩子为其前趋结点在线索树上进行遍历的方法2021/8/569算法6。5：Status InOrderTraverse_Thr(BiThrTree T, Status(*Visit)(TElemType e) /T指向头结点，头结点的左链Lchhild指向根结点 /中

29、序遍历二叉线索树T的非递归算法， /对每个数据元素调用函数VisitP=T-lchild; /P指向根结点While (P!=T) /空树或遍历结束时，p= =T while (p-Ltag= =Link) p=p-lchild; 中序遍历二叉线索树T的非递归算法2021/8/570 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_T

30、hr2021/8/571在后序线索树中找结点后继，分三种情况：若结点x是二叉树的根，则后继为空；若结点x是其双亲的右孩子或是其双亲的左孩子且其双亲没有右子树，则其后继即为双亲结点若结点x是其双亲的左孩子，且其双亲有右子树，则其后继为双亲的右子树上按后序遍历列出的第一个结点 2021/8/572线索化的实质：是将二叉链表中的空指针改为指向前驱 或后继的线索，而前驱或后继的信息只 有在遍历时才能得到，所以线索化的过 程为遍历过程中修改空指针的过程。设 :pre指针,始终指向刚刚访问过的结点，若p指向当前访问的结点，则pre指向其前驱二叉树的线索化算法2021/8/573算法6.6：Status I

31、norderThreading(BiThrTree&Thrt, BiThrTree T) /中序遍历二叉树T，并将其中中序线索化，Thrt指向头结点 if (!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode) exit(OVERFLOW); Thrt-Ltag=Link; Thrt-Rtag=Thread; /建头结点 Thrt-rchild=Thrt; /右指针回指 if(!T) Thrt-lchild=Thrt; /若二叉树为空，则左指针回指2021/8/574else Thrt-lchild=T; pre= Thrt; InThreading(T); /

32、中序遍历进行中序线索化 pre-rchild=Thrt; pre-RTag=Thread;/最后一个结点线索化 Thrt-rchild=pre;return OK; /InOrderThreading2021/8/575算法6.7Void InThreading(BiThrTree p) 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指

33、向p的前驱 InThreading(p-rchild); /右子树线索化 /InThreading 2021/8/576 6.4树和森林树的存储结构双亲表示法 以一组连续空间存储树的结点，同时在每个结点中附设一个指示器指示其双亲结点在链表中的位置.树的双亲表存储表示：#define MAX_TREE_SIZE 100Typedef struct PTNode TElemType data; int parent; /双亲位置域 PTNode;2021/8/577Typedef struct PTNode nodesMAX_TREE_SIZE; int n; /结点数 Ptree;如图：树的双亲

34、表示法示例REDBACFKHGR-1A0B0C0D1E1F3G6H6K601234567892021/8/578孩子表示法方法一：多重链表法每个结点结构DataChild1Child2childdd树的度DataDegreeChild1 Child2childdd结点度方法二：孩子链表法为每个孩子建立一个孩子链表2021/8/579孩子链表存储结构：Typedef struct CTNode /孩子结点 int child; struct CTNode *next;*ChildPtr;Typedef struct TElemType data; ChildPtr firstchild; /孩子

35、链表头指针CTBox;Typedef struct CTBox nodesMAX_TREE_SIZE; int n,r; /结点数和根的位置Ctree;2021/8/580如图:是图6-13的孩子链表表示法ABCDREFGHK35621098701234567892021/8/581双亲表示法和孩子表示法结合如图：是下图6-14对应的带双亲的孩子链表4A4B4C0D-1R0E2F6G6H6K35621098701234567892021/8/582REDBACFKHG6-142021/8/583三.孩子兄弟表示法以二叉链表作为树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和下

36、一个孩子结点，分别命名为firstchild域和nextsibling域。又称为二叉链表表示法存储表示：Typedef struct CSNode ElemType data; struct CSNode *firstchild,*nextsibling; CSNode,*CSNree; 2021/8/584树转化为二叉树方法：左手拉第一个孩子，右手拉下一个兄弟AECBDEDCBA树二叉树森林与二叉树的转换2021/8/585森林转化为二叉树方法：将森林中每棵树转化为二叉树,第一棵树的根为二叉树的根，森林中各棵树的根是兄弟关系.如图：AJIHGFEDCBADCBFEJIHG森林二叉树2021/

37、8/586树遍历方法：先根(次序)遍历树方法：先访问树的根结点，然后依次先根遍历根的每棵子树后根(次序)遍历方法：先依次后根遍历每棵子树，然后访问根结点树和森林的遍历2021/8/587例：对下图进行先根遍历，得到先根序列为 A B C D E对此树进行后根遍历，得到树的后根序列为 B D C E AADECB2021/8/588先序遍历森林若森林非空，按下述规律遍历：访问森林中第一棵树的根结点；先序遍历第一棵树中根结点的子树森林；先序遍历除去第一棵树之后剩余的树构成的森林。中序遍历森林若森林非空：中序遍历森林中第一棵树的根接点的子树森林；访问第一棵树的根结点；中序遍历除去第一棵树之后剩余的树

38、构成森林。森林遍历方法2021/8/589对下图中森林进行先序遍历和中序遍历，先序序列为： A B C D E F G H I J中序序列为： B C D A F E H J I G如图：AJIHGFEDCBADCBFEJIHG森林二叉树2021/8/590 6.6赫夫曼树及其应用路径长度：路径上的分枝数目称为树的路径长度树的路径长度：从树根到每一结点的路径长度之和树的带权路径长度：树中所有叶子结点的带权路径长度之和，通常记作：WPL=k=1 n wk Lk最优二叉树(haffman树)：带权路径长度WPL最小的二叉树2021/8/591如图中的三棵二叉树，都有4个叶子结点a,b,c,d,分别

39、带权7,5,2,4abcdcbaddcba752475247524(a)(b)(c )2021/8/592它们的带权路径长度分别为(a) WPL=72+5 2+2 2+4 2=36(b) WPL=7 3+5 3+2 1+4 2=46(c) WPL=7 1+5 2+2V3+4 3=352021/8/593根据给定的n个权值w1, w2, wn构成n棵二叉树的集合F=T1,T2,T n,其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树均空在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左，右子树上根结点的权值之和。在F中删除这两棵树，同时

40、将新得到的二叉树加入F中重复(2)和(3)，直到F只含一棵树为止。赫夫曼树构造算法2021/8/594adcb75245b11a718cd624如图：展示了构造赫夫曼树的构造过程。其中，根结点上标注的数字是所赋的权。2021/8/595赫夫曼编码 利用Haffman树进行编码，各叶子结点表示待进行编码的字符,约定二叉树左分枝为0，右分枝为1，从根到叶的编码串就是这个叶子结点字符的Haffman编码2021/8/596例6-2 已知某系统在通信联络中只可能出现八种字符，其概率分别为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11,试设计赫夫曼编码设权w=(5,29,

41、7,8,14,23,3,11),n=8,则m=15,按上述算法棵构造一棵Haffman树如图6-26所示。2021/8/5972311 3 8295 14 701010101010101图6-26的Haffman2021/8/598所得Haffman编码分别为：230 05 31429 811 70 1 00 1 1 00 1 1 11 01 1 01 1 1 01 1 1 1 2021/8/599Typedef struct unsigned int weight; unsigned int parent,lchild,rchild;HTNode,*HuffmanTree; /动态分配数组存

42、储赫夫曼树Typedef char *HuffmanCode; /动态分配数组存储赫夫曼编码表Haffman树和编码的存储表示2021/8/5100求Haffman编码的算法Void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC,int *w,int n) /w存放n个字符的权值,构造赫夫曼树HT， /并求出n个字符的赫夫曼编码HC if (n=1) return; m=2*n-1; HT=(HuffmanTree)malloc(m+1)* sizeof(HTNode); /0号单元未用2021/8/5101For (p=HT,i=1;i=n;+

43、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;2021/8/5102从叶子到根逆向求每个字符的赫夫曼编码HC=(HuffmanCode)malloc(n+1)*s

44、izeof(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.parent;f!=0;c=f,f=HTf.parent） /从叶子到根逆向求编码 2021/8/5103 if(HTf.lchild= =c) cd-start=“0”; else cd-start=“1”; HCi=(char *) malloc(n-start)*sizeof(char); /为第i个字符编码分配空间 strcpy(HCi,&cdstart); /从cd复制编码(串)到HCFree(cd); /释放工作空间/HuffmanCoding部分资料从网络收集整理而来，供大家参考，感谢您的关注！