数据结构课件PPT110章全 第六章 树和二叉树.ppt 69页

'第六章树和二叉树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.4.3树和森林的遍历6.6赫夫曼树及其应用6.6.1最优二叉树（赫夫曼树）6.6.2赫夫曼编码 树型结构是一类重要的非线性结构。树型结构是结点之间有分支，并且具有层次关系的结构，它非常类似于自然界中的树。树结构在客观世界是大量存在的，例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程。等等。6.1树的定义和基本术语定义：树(Tree)是n(n>=0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：（1）有且仅有一个特定的称为根(Root)的结点； (2)其余的结点可分为m(m>=0)个互不相交的子集T1,T2,T3…TmT1,T2,T3…Tm，其中每个子集又是一棵树，并称其为子树(Subtree)。如图6.1树还有其他的表示形式，如图6.2的三种表示法：（1）嵌套集合（2）广义表的形式（3）凹入表示法下面是树结构的一些基本术语：度：结点拥有的子树称为结点的度。叶子（终端结点）：度为0的结点。其余结点称为非终端结点或分支结点。树的度：树内各结点的度的最大值。孩子：结点的子树的根称为该结点的孩子。相应地，该结点称为双亲。同一个双亲的孩子称为兄弟。依此可以递归定义祖先和子孙的概念。 结点的层次：从根开始定义，根为第一层，根的孩子为第二层。若某个结点在第l层，则其子树的根就在第l+1层。双亲在同一层的结点互为堂兄弟。树中结点的最大层次称为树的深度或高度。有序树：如果该树中结点的各子树看成从左至右是有次序的，则该树称为有序树。否则称为无序树。森林：是m（m>=0）棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。由此，可以森林和树相互递归的定义来描述树。Tree=(root,F)，其中F是m棵树的森林。F=(T1,T2,T3…Tm)，其中Ti称做根root的第i棵子树。 6.2二叉树二叉树在树结构的应用中起着非常重要的作用，因为对二叉树的许多操作算法简单，而任何树都可以与二叉树相互转换，这样就解决了树的存储结构及其运算中存在的复杂性。6.2.1二叉树的定义定义：二叉树是由n(n>=0)个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树，且次序不能任意颠倒。这也是一个递归定义。二叉树可以是空集合，根可以有空的左子树或空的右子树。二叉树不是树的特殊情况，它们是两个概念。 二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。这是二叉树与树的最主要的差别。图6.8列出二差树的5种基本形态，图6.8(C)和图6.8（d）是不同的两棵二叉树。(a)空二叉树AABABACB(b)根和空的左右子树(c)根和左子树(d)根和右子树(e)根和左右子树图6.8二叉树的5种形式 6.2.2二叉树的性质二叉树具有下列重要性质：性质1：在二叉树的第i层上至多有2i-1个结点(i>=1)。采用归纳法证明此性质。当i=1时，只有一个根结点，2i-1=20=1,命题成立。现在假定对于所有的j，1<=j=1).深度为k的二叉树的最大的结点数`为二叉树中每层上的最大结点数之和，由性质1得到每层上的最大结点数：EkI=1（第i层上的最大结点数）=EkI=12i-1=2k–1性质3：对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0＝n2＋1。设二叉树中度为1的结点数为n1，二叉树中总结点数为N，因为二叉树中所有结点均小于或等于2，所以有：N＝n0＋n1＋n2(6-1)再看二叉树中的分支数，除根结点外，其余结点都有一个进入分支，设B为二叉树中的分支总数，则有：N＝B＋1。 由于这些分支都是由度为1和2的结点射出的，所有有：B＝n1+2*n2N＝B＋1＝n1＋2×n2＋1（6－2)由式（6－1）和（6－2）得到：n0+n1+n2=n1+2*n2+1n0＝n2＋1下面介绍两种特殊形态的二叉树：满二叉树和完全二叉树。一棵深度为k且有2k-1个结点的二叉树称为满二叉树。下图6.9就是一棵满二叉树，对结点进行了顺序编号。 如果深度为k、由n个结点的二叉树中个结点能够与深度为k的顺序编号的满二叉树从1到n标号的结点相对应，2453671图6.9满二叉树 12345612345712367(a)完全二叉树(b)非完全二叉树(c)非完全二叉树图6.10完全二叉树则称这样的二叉树为完全二叉树，图6..10（b）、c）是2棵非完全二叉树。满二叉树是完全二叉树的特例。 完全二叉树的特点是：（1)所有的叶结点都出现在第k层或k－1层。（2）任一结点，如果其右子树的最大层次为1，则其左子树的最大层次为1或l＋1。性质4：具有n个结点的完全二叉树的深度为【log2n】＋1。符号【x】表示不大于x的最大整数。假设此二叉树的深度为k，则根据性质2及完全二叉树的定义得到：2k-1－11，则其双亲是结点【i/2】。（2）如果2i>n，则结点i为叶子结点，无左孩子；否则，其左孩子是结点2i。（3）如果2i＋1>n，则结点i无右孩子；否则，其右孩子是结点2i＋1。 [I/2]iI+12i2i+12(I+1)2i+3I+12(I+1)2i+3i2i2i+1图6.11完全二叉树中结点I和i+1(a)I和i+1结点在同一层(b)I和i+1结点不在同一层如图6.11所示为完全二叉树上结点及其左右孩子在结点之间的关系。 在此过程中，可以从（2）和（3）推出（1），所以先证明（2）和（3）。对于i＝1，由完全二叉树的定义，其左孩子是结点2，若2>n，即不存在结点2，此时，结点i无左孩子。结点i的由孩子也只能是结点3，若结点3不存在，即3>n，此时结点i无右孩子。对于i>1，可分为两种情况：（1）设第j（1<=j<=【log2n】)层的第一个结点的编号为i，由二叉树的性质2和定义知i＝2j-1结点i的左孩子必定为j＋1层的第一个结点，其编号为2j＝2×2j-1＝2i。如果2i>n，则无左孩子： 其右孩子必定为第j＋1层的第二个结点，编号为2i＋1。若2i+1>n，则无右孩子。（2）假设第j（1<=j<=【log2n】)层上的某个结点编号为i（2(j-1)<=i<=2j-1),且2i＋11时，如果i为左孩子，即2×（i/2)=i,则i/2是i的双亲；如果i为右孩子，i＝2p+1,i的双亲应为p，p＝（i－1）/2=【i/2】.证毕。 6.2.3二叉树的存储结构1.顺序存储结构它是用一组连续的存储单元存储二叉树的数据元素。因此，必须把二叉树的所有结点安排成为一个恰当的序列，结点在这个序列中的相互位置能反映出结点之间的逻辑关系，用编号的方法：#defineMAX-TREE-SIZE100typedefTElemTypeSqBiTree[MAX-TREE-SIZE];SqBiTreebt;从树根起，自上层至下层，每层自左至右的给所有结点编号缺点是有可能对存储空间造成极大的浪费，在最坏的情况下，一个深度为h且只有h个结点的右单支树确需要2h-1个结点存储空间。而且，若经常需要插入与删除树中结点时，顺序存储方式不是很好！ ABCDEFGHIJKL123456789101112完全二叉树abcdefghijkl ABCDEFGØØØØØ表示该处没有元素存在仅仅为了好理解ABCDEØØØØFG一般二叉树 （2）二叉链表法存储二叉树经常用二叉链表法A^BC^D^E^F^^G^^H^lchilddatarchild 二叉树的二叉链表存储表示TypedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;有时也可用数组的下标来模拟指针,即开辟三个一维数组data,lchild,rchild分别存储结点的元素及其左,右指针域;有时，为了便于找到结点的双亲，则还可在结点结构中增加一个指向其双亲结点的指针域，这种结构称为三叉链表，如下图。lchilddataparentrchild 6.3遍历二叉树和线索二叉树6.3.1遍历二叉树在二叉树的一些应用中，常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理。这就引入了遍历二叉树的问题，即如何按某条搜索路径巡访树中的每一个结点，使得每一个结点均被访问一次，而且仅被访问一次。遍历对线性结构是容易解决的，而二叉树是非线性的，因而需要寻找一种规律，以便使二叉树上的结点能排列在一个线性队列上，从而便于遍历。bca(根结点)(右子树)(左子树)由二叉树的递归定义，二叉树的三个基本组成单元是：根结点、左子树和右子树。 假如以L、D、R分别表示遍历左子树、遍历根结点和遍历右子树，遍历整个二叉树则有DLR、LDR、LRD、DRL、RDL、RLD六种遍历方案。若规定先左后右，则只有前三种情况，分别规定为：DLR——先（根）序遍历，LDR——中（根）序遍历，LRD——后（根）序遍历。1、先序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。2、中序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则（1）中序遍历左子树；（2）访问根结点； （3）中序遍历右子树。3、后序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。 voidPreorderTraverse(T){if(T){printf("%dt",T->data);preorder(T->lchild);preorder(T->rchild);}}主程序Pre(T)返回返回pre(TR);返回返回pre(TR);ACBDTBprintf(B);pre(TL);BTAprintf(A);pre(TL);ATDprintf(D);pre(TL);DTCprintf(C);pre(TL);C返回T>左是空返回pre(TR);T>左是空返回T>右是空返回T>左是空返回T>右是空返回pre(TR);先序序列：ABDC 例如下图所示的二叉树表达式(a+b*(c-d)-e/f)若先序遍历此二叉树,按访问结点的先后次序将结点排列起来,其先序序列为：-+a*b-cd/ef按中序遍历,其中序序列为：a+b*c-d-e/f按后序遍历,其后序序列为：abcd-*+ef/-有人喜欢中缀形式的算术表达式,对于计算机,使用后缀易于求值。－＋*a/b-dcfe 从上述二叉树遍历的定义可知，3种遍历算法之不同处仅在于访问根结点和遍历左、右子树的先后关系。如果在算法中暂且抹去和递归无关的Visit语句，则3个遍历算法完全相同。如图6.10（b）用带箭头的虚线表示了这3种遍历算法的递归执行过程。其中，虚线边的三角形、圆形和方形内的字符分析表示在先序、中序和后序遍历二叉树过程中访问结点时输出的信息。只要沿虚线将沿途所见的三角形（或圆形或方形）内的字符记下，便得遍历二叉树的先序（或中序、或后序）序列。 为了写出非递归遍历算法，我们可以观察到递归工作栈的状态变化。（1）当线顶记录中的指针非空时，应遍历左子树，即指向左子树根的指针进栈。（2）若栈顶记录中的指针值为空，则应退至上一层，若是从左子树返回，则应访问当前层即栈顶指针上指针所指的根结点；（3）若是从右子树返回，则表明当前层的遍历结束，应继续退栈。由此可得以下两个中序遍历二叉树的非递归算法，先序遍历二叉树的非递归算法与此类似，但后序遍历二叉树的非递归算法要相对复杂一点。 非递归算法：中序ABCDEFGpiP->A(1) StatusInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){InitStack(S);Push(S,T);//根指针进栈while(!StackEmpty(S)){while(GetTop(S,p)&&p)Push(S,plchild);//向左走到尽头Pop(S,p);//空指针退栈if(!StackEmtpy(S)){//访问结点，向右一步Pop(S,p);if(!Visit(pdata))returnERROR;Push(S,prchild);}//if}//whilereturnOK;} StatusInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){InitStack(S);p=T;while(p||!StackEmpty(S)){if(p){Push(S,p);p=plchild;}//根指针进栈，遍历左子树else{//Pop(S,p);if(!Visit(pdata))returnERROR;p=prchild;}}returnOK;} “遍历”是二叉树各种操作的基础，可以在遍历过程中对结点进行各种操作，如按先序序列建立二叉树的二叉链表算法：StatusCreateBiTree(BiTree&T){scanf(&ch);if(ch==")T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);T–>data=ch;CreateBiTree(T–>lchild);CreateBiTree(T–>rchildd);}returnOK;} 遍历算法应用按先序遍历序列建立二叉树的二叉链表，已知先序序列为：ABCDEGFABCDEFGA^B^C^D^E^F^^G^ 6.3.2线索二叉树：当以二叉链表作为存储结构时,只能找到结点的左右孩子的信息,而不能得到结点的任一序列的前驱与后继信息,这种信息只有在遍历的动态过程中才能得到,为了能保存所需的信息,可增加标志域;0lchild域指示结点的左孩子LTag={1lchild域指示结点的前驱0rchild域指示结点的右孩子RTag={1rchild域指示结点的后驱以这种结构构成的二叉链表作为二叉树的存储结构,叫做线索链表,其中指向结点前驱与后继的指针叫做线索.加上线索的二叉树称之为线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。lchildLTagdataRTagrchild ABCDEABDCET先序序列：ABCDE先序线索二叉树00001111^11 ABCDEABDCET中序序列：BCAED中序线索二叉树00001111^11^ ABCDEABDCET后序序列：CBEDA后序线索二叉树0000111111^ 图6.11为中序线索二叉树及其存储结构：（1）寻找结点后继：若结点右标志为“1”，则右链表线索，指示其后继；否则遍历右子树时访问的第一个结点（即右子树最左下结点）为其后继。（2）寻找结点前驱：若结点左标志为“1”，则左链表线索，指示其前驱；否则遍历左子树时最后访问的结点（即左子树最右下结点）为其前驱。在后序线索树中寻找后继较复杂些，可分3种情况：（1）结点x是二叉树的根，则其后继为空；（2）结点x是其双亲的右孩子，或是其双亲的左孩子且其双亲没有右子树，则其后继为双亲结点；（3）结点x是其双亲的左孩子，且其双亲有右子树，则其后继为双亲的右子树上按后序遍历列出的第一个结点。如图6.12。可见在后序线索化树上找后继时需知道结点双亲，即需要带标志域的三叉链表作存储结构。 StatusInorderTraverse_Thr(BiThrTreeT,status(*visit)(TElemType)){//T指向头结点,头结点的lchild左链指向根结点//中序遍历二叉线索树的非递归算法,对每个数据元素调用//函数VisitP=T–>lchild;while(p!=T){while(p–>LTag==Link)p=p–>lchild;if(!visit(p–>data))returnerror;while(p–>RTag==Thread&&p–>rchild!=T){p=p–>rchild;Visit(p–>data);}p=p–>rchild;}returnOK;}//InorderTraverse_Thr 中序遍历建立中序线索化链表的算法：StatusInorderThreading(BiThrTree&Thrt,BiThrTreeT){if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode))))exit(OVERFLOW);Thrt–>LTag=Link;Thrt–>RTag=Thread;Thrt–>rchild=Thrt;if(!T)Thrt–>lchild=Thrt;else{Thrt–>lchild=T;pre=Thrt;InThrTreading(T);pre–>rchild=Thrt;pre–>RTag=Thread;Thrt–>rchild=pre;}returnOK;}//InorderThreading VoidInThreading(BiThrTreep){if(p){InThreading(p–>lchild);if(!p–>lchild){p–>LRag=Thread;plchild=pre;}if(!pre–>rchild){pre–>RTag=Thread;pre–>rchild=p;}pre=p;InThreading(p–>rchild);}} 6.4树和森林6.4.1树的存储结构：1、双亲表示法以一组连续空间存储树的结点，并在每个结点中附设一个指示器指示其双亲结点在链表中的位置：#defineMAX_TREE_SIZE100typedefstructPTNode{TElemTypedata;intparent;//双亲位置域}PTNode;typedefstruct{PTNodenodes[MAX_TREE_SIZE];intr,n;//根的位置和结点数}PTree; abcdefhgiacdefghib-1011244406012345789dataparent如何找孩子结点 利用这种结构可以很方便地求出结点的双亲及其根，但是，在这种表示法中，求结点的孩子时需要遍历整个结构。 2、孩子表示法由于孩子每个结点可能有多棵子树，则可用多重链表，即每个结点有多个指针域，其中每个指针指向一棵子树的根结点，此时链表中的结点可以有如下两种结点格式：若采用第一种结点格式，则多重链表中的结点是同构的，其中d为树的度。由于树中很多结点的度小于d，所以链表中有很多空链域，空间较浪费。若采用第二种结构，则多重链表中的结点是不同构的。其中degree为每个结点的度。然而，这也造成了操作的不方便。datachild1child2……childddatachild1child2……childddegree 另一种办法是把每个结点的孩子结点排列起来，看成一个线性表，且以单链表作存储结构，则n个结点有n个孩子链表。n个头指针又组成一个线性表，为了便于查找，可采用顺序存储结构。typedefstructCTNode{intchild;structCTNode*next;}*ChildPtr;typedefstruct{TElemTypedata;ChildPtrfirstchild;}CTBox;typedefstruct{CTBoxnodes[MAX_TREE_SIZE];intn,r;}CTree; abcdefhgi6012345789acdefghibdatafc12^34^^867^5^^^^^如何找双亲结点 带双亲的孩子链表501234678acdefghibdatafc12348675^^^^^^^^^012235551parentabcdefhgi 孩子兄弟表示法（二叉树表示法）实现：用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点特点操作容易破坏了树的层次typedefstructCSNode{TElemTypedata;structCSNode*firstchild,*nsib;}CSNode;abcdefhgiabcdefghi^^^^^^^^^^ 利用这种结构，易于找到结点的孩子。例如：要访问结点x的第i个孩子，则只要先从firstchild域找到第1个孩子结点，然后沿着孩子结点的nextsibling域连续走i-1步，便可找到结点x的第i个孩子。如果每个结点增设一个PARENT域，则同样能方便地实现PARENT(T,x)操作。树也可以用二叉树的存储方式来存储。这意味着，树与二叉树之间存在某种关联关系。 6.4.2森林与二叉树的转换由于二叉树和树都可用二叉链表作为存储结构，它们两者的物理结构相同，只是解释不同而已。图6.16直观地展示出树与二叉树的对应关系。由树的二叉链表定义可知，任何一棵和树对应的二叉树，其右子树必空。若把森林中第二棵树的根结点看成是第一棵树的根结点的兄弟，则同样可导出森林和二叉树的对应关系。如图6.17。这个一一对应的关系使得森林与二叉树可以相互转换，其形式定义如下： 森林转换成二叉树：如果F={T1,T2,…,Tm}是森林，则可按如下规则转换成一棵二叉树B={root,LB,RB)。（1）若F为空，即m=0，则B为空树。（2）若F非空，即m<>0，则B的根root即为森林中第一棵树的根ROOT（T1）；B的左子树LB是从T1中根结点的子树森林F1={T11,T12,…,T1m1}转换而成的二叉树；其右子树RB是从森林F‘={T2,…,Tm}转换而成的二叉树。二叉树转换成森林：略。 6.4.3树和森林的遍历由树的结构引发两种次序遍历树的方法：例图6.16一种是先根（次序）遍历：ABCDE一种是后根（次序）遍历：BDCEA森林和树相互递归的定义，我们可以推出森林的两种遍历方法：1、先序遍历森林：(1)访问森林中第一棵树的根结点；(2)先序遍历第一棵树中根结点的子树森林；(3)先序遍历除去第一棵树之后剩余的树构成的森林对于图6.17，先序序列为：ABCDEFGHIJ 2、中序遍历森林：(1)中序遍历第一棵树中根结点的子树森林；(2)访问森林中第一棵树的根结点(3)中序遍历除去第一棵树之后剩余的树构成的森林图6.17的中序序列为：BCDAFEHJIG森林遍历与二叉树遍历的对应关系：森林的先序和中序遍历分别对应二叉树的先序和中序遍历。由此可见，相当部分森林与树的操作，可以归结为二叉树的操作。 6.6赫夫曼树及其应用赫夫曼树(Huffman)，又称最优树，是一类带权路径长度最短的树，有着广泛的应用。6.6.1最优二叉树（赫夫曼树）路径长度：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称为路径长度。树的路径长度：从树根到每一结点的路径长度之和。完全二叉树就是这种路径长度最短的二叉树。树的带权路径长度：考虑带权值的结点。树中所有叶子结点的带权路径长度之和，记作WPL(WeightedPathLength)=w1l1+w2l2+…+wnln。 例有4个结点，权值分别为7，5，2，4，构造有4个叶子结点的二叉树abcd7524WPL=7*2+5*2+2*2+4*2=36dcab2475WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=35 Huffman树应用最佳判定树等级分数段比例ABCDE0~5960~6970~7980~8990~1000.050.150.400.300.10a<60a<90a<80a<70EYNDYNCYNBYNA70a<80a<60CYNBYNDYNEYNA80a<9060a<70EADECa<80a<70a<60a<90EYNDYNCYNBYNA 那么如何构造赫夫曼树，以下给出赫夫曼算法：(1)根据给定的n个权值{w1,w2,…,wn}构成n棵二叉树的集合F={T1,T2,…,Tn}，其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树为空。(2)在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的权值为其左、右子树上根结点的权值之和。(3)在F中删除这两棵树，同时将新得到的二叉树加入F中。(4)重复(2)和(3)，直到F只含一棵树为止。这棵树便为赫夫曼树。图6.24展示了图6.22(c)的赫夫曼树的构造过程。 例a7b5c2d4a7b5c2d46a7b5c2d4611a7b5c2d461118 例w={5,29,7,8,14,23,3,11}51429782331114297823113588715142923358111135819142923871511358192923148715292914871529113581923421135819234229148715295811358192342291487152958100 6.6.2赫夫曼编码－－赫夫曼树的应用之一使用电报进行远程通信，需要将需传送的文字转换成二进制的字符字符组成的字符串。例如，需要传送的电文为’ABACCDA’，总共只有4个字符，可以编码为：ABCD00011011则上述电文便为’00010010101100’，总长14位，对方接收时，可以两位一组进行译码。当然，在传送电文时，希望总长尽可能地短，如果对每个字符设计长度不等的编码，且让电文中出现次数较多的字符采用尽可能短的编码，则传送电文的总长便可减少，如： ABCD000101这样，上述电文便可编码为总长为9：’000011010’。但这时候，又可能带来歧义。比如对于’0000’就有多种译法，可以是’AAAA’，也可以是’ABA’等。因此，若要设计长短不一的编码，则必须是任一个字符的编码都不是另一个字符的编码的前缀，这种编码称为前缀编码。可以利用二叉树来设计二进制的前缀编码。如图6.25所示的二叉树，其4个叶子结点分别表示A、B、C和D这4个字符，且约定左分支表示字符’0’，右分支表示字符’1’，则可以从根结点到叶子结点的路径上分支字符组成的字符串作为该叶子结点的编码。A(0)B(10)C(110)D(111) 如何得到使电文总长最短的二进制编码呢？假设每种字符在电文中出现的次数为wi，其编码长度为li，电文中只有n种字符，则电文编码总长为w1l1+w2l2+…+wnln。对应到二叉树上，若置wi为叶子结点的权，li为从根到叶子的路径长度。则w1l1+w2l2+…+wnln恰为二叉树上带权路径长度WPL。由此可见，设计电文总长最短的二进制前缀编码即为以n种字符出现的频率作权，设计一棵赫夫曼树的问题，由此得到的二进制前缀编码便称为赫夫曼编码。以下讨论具体做法。 算法分析由于赫夫曼树中没有度为1的结点（这类树又称为正则二叉树），则一棵有n个叶子结点的赫夫曼树共有2n-1个结点，可以存储在一个大小为2n-1的一维数组中。如何选定结点结构？由于在构成赫夫曼树之后，为求编码需从叶子结点出发走一条从叶子结点到根结点的路径；而为译码需从根出发走一条从根到叶子结点的路径。则对每个结点而言，需知道结点的双亲信息和孩子信息。故可设定下述存储结构：typedefstruct{unsignedintweight;unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;//赫夫曼树typedefchar**HuffmanCode;//赫夫曼编码表 wpalcrc12345670000000752400000000000000000(1)s1=3,s2=4m1=2,m2=475246000000300000040000550001234567k(2)wpalcrc123456700003207524611000004500655600ks1=2,s2=5m1=5,m2=6(3)wpalcrc1234567000032175246111800004567655670ks1=1,s2=6m1=7,m2=11(4)wpalcrc 赫夫曼编码的算法描述：输入：w存放n个字符的权值输出：赫夫曼树HT，求赫夫曼编码HC[初始化]总结点数为m=2*n-1；申请m个结点空间的赫夫曼树HT；用w为前n个结点的权值赋值；后面的结点权值初始为0。这些结点的双亲和孩子皆为0。[建赫夫曼树HT]i从n+1到m，执行如下循环：在HT[1..i-1]中选择父亲信息为0且权值最小的两个结点s1和s2，以i作为它们的双亲，并修改他们的双亲信息为i，修改i的孩子信息为s1和s2，i的权重为s1和s2的权重之和。 [求赫夫曼编码HC]分配n个字符编码的头指针向量HC；i从1到n，执行如下循环：沿着i的父亲信息上溯，直到根：在每一层，如果为左孩子则记下‘0’；在每一层，如果为右孩子则记下‘1’；把上溯过程得到的字符串逆向写入HC[i]。[算法结束]这样由叶子到根，逆向处理，可以得到赫夫曼编码HC。其中，HC的前n个分量表示叶子结点，其余结点为非终端结点，最后一个结点为根结点。 另外，还可以由根出发，遍历整棵赫夫曼树，求得各个叶子所表示的字符的赫夫曼编码，如算法6.13，其中借用结点的weight域来作结点状态标志(weight为0表示向左，1表示向右，2表示退回)：例6－2给出了赫夫曼编码的一个示例。P148'