第六章1树及二叉树.ppt

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,第六章 树和二叉树,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.5 赫夫曼树及其应用,6.5.1 最优二叉树（赫夫曼树）,6.5.2 赫夫曼编码,树,型,结构是一类重要的非线性结构。树型结构是结点之间有分支，并且具有层次关系的结构，它非常类似于自然界中的树。树结构在客观世界是大量存在的，例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程。等等。,(,2)其余的结点可分为,m(m=0),个互不相交的子集,T,1,T,2,T,3,T,m,，,其中每个子集又是一棵树，并称其为子树(,Subtree,)。,定义：树(,Tree),是,n(n=0),个结点的有限集,T，T,为空时称为空树，否则它满足如下两个条件：,（1）有且仅有一个特定的称为根(,Root),的结点,6.1 树的定义和基本术语,A,A,B,C,D,E,G,F,H,I,J,K,L,M,(a),(b),层次,1,2,3,4,图,6.1 树的示例,(,a),只有根结点的树 (,b),一般的树,树,结构中的基本术语,树,的,结点：包含一个数据元素及若干指向其子树的分支。,结点的度：结点拥有的子树数。,叶子（终端结点）：度为0的结点。,非终端结点（分支结点）：度不为0的结点。,内部结点：除根结点外，分支结点也称为内部结点。,树的度：树内各结点的度的最大值。,孩子与双亲：结点的子树的根称为该结点的孩子，相应地，该结 点称为孩子的双亲。,树,结构中的基本术语,兄弟：同一个双亲的孩子之间互称为兄弟。,结点的祖先：从根到该结点所经分支上的所有结点。,子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。,结点的层次：从根开始定义起，根为第一层，根的孩子为第二层,堂兄弟：其双亲在同一层的结点互为堂兄弟。,树的深度：树中结点的最大层次称为树的深度。,有序树和无序树：如果将树中结点的各子树看成从左至右是有次序的（即不能互换），则称该树为有序树，否则称为无序树。,森林：是,m（m0）,棵互不相交的树的集合。,6.2 二叉树,二叉树在树结构的应用中起着非常重要的作用，因为对二叉树的许多操作算法简单，而任何树都可以与二叉树相互转换，这样就解决了树的存储结构及其运算中存在的复杂性。,6.2.1 二叉树的定义,定义：二叉树是,由,n(n=0),个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。,这也是一个,递归,定义。二叉树可以是空集合，根可以有空的左子树或空的右子树。二查树不是树的特殊情况，它们是两个概念。,二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。这是二叉树与树的最主要的差别。图6.8列出二差树的5种基本形态，图6.8(,C),和图6.8（,d）,是不同的两棵二叉树。,(a),空二叉树,A,A,B,A,B,A,C,B,(,b),根和空的左右子树,(,c),根和左子树,(,d),根和右子树,(,e),根和左右子树,图,6.8 二叉树的5种形式,6.2.2 二叉树的性质,二叉树具有下列重要性质：,性质1：,在二叉树的第,i,层上至多有2,i-1,个结点(,i=1)。,采用归纳法证明此性质。,当,i=1,时，只有一个根结点，2,i-1,=2,0,=1,命题成立。,现在假定对所有的,j，1=j=1).,深度为,k,的二叉树的最大的结点数为二叉树中每层上的最大结点数之和，由性质1得到每层上的最大结点数：,由于这些分支都是由度为1和2的结点射出的，所有有：,Bn1+2*n2,NB1n12n21 （62),由式（61）和（62）得到：,n0+n1+n2=n1+2*n2+1,n0n21,下面介绍两种特殊形态的二叉树：满二叉树和完全二叉树。,一棵深度为,k,且由2,k,-1,个结点的二叉树称为满二叉树。图6.9就是一棵满二叉树，对结点进行了顺序编号。,如果深度为,k、,有,n,个结点的二叉树中每个结点能够与深度为,k,的顺序编号的满二叉树从1,到,n,标号的结点相对应，,图6.9 满二叉树,2,4,5,3,6,7,1,则称这样的二叉树为完全二叉树，图6.10（,b）、（c）,是2棵非完全二叉树。满二叉树是完全二叉树的特例。,1,2,3,4,5,6,1,2,3,4,5,7,1,2,3,6,7,(,a),完全二叉树,(,b),非完全二叉树,(,c),非完全二叉树,图,6.10 完全二叉树,（1)所有的叶结点都出现在第,k,层或,k1,层。,（2）对任一结点，如果其右子树的最大层次为,L，,则其左子树的最大层次,为,L,或,L1。,性质4：,具有,n,个结点的完全二叉树的深度为,log2n 1。,符号,x,表示不大于,x,的最大整数。,证明：假设此二叉树的深度,为,k，,则根据性质2及完全二叉树的定义得到：2,k-1,1n=2,k,-1,或 2,k-1,=n2,k,取对数得到：,k1log2nk,因为,k,是整数。所以有：,k log2n 1。,完全二叉树的特点是：,性质5：,如果对一棵有,n,个结点的完全二叉树的结点按层序编号（从第1层到第,log2n+1,层，每层从左到右),则对任一结点,i（1=i1，,则其双亲是结点,i/2。,（2）,如果2,in，,则结点,i,为叶子结点，无左孩子；否则，其左孩子是结点2,i。,（3）,如果2,i1n，,则结点,i,无右孩子；否则，其右孩子是结点2,i1。,i/2,i,i+1,2i,2i+1,2(,i+1),2i+3,i+1,2(,i+1),2i+3,i,2i,2i+1,图,6.11 完全二叉树中结点,I,和,i+1,(,a)I,和,i+1,结点在同一层,(,b)I,和,i+1,结点不在同一层,如图6.11所示为完全二叉树上结点及其左右孩子在结点之间的关系。,在此过程中，可以从（2）和（3）推出（1），所以先证明（2）和（3）。,对于,i1，,由完全二叉树的定义，其左孩子是结点2，若2,n，,即不存在结点2，此时，结点,i,无孩子。结点,i,的右孩子也只能是结点3，若结点3不存在，即3,n，,此时结点,i,无右孩子。,对于,i1，,可分为两种情况：,（1）设第,j（1=jn，,则无左孩子；其右孩子必定为第,j1,层的第二个结点，编号为2,i1。,若2,i+1n，,则无右孩子。,（2）假设第,j（1=j=log2n),层上的某个结点编号为,i,（2,(j-1),=i=2,j,-1),且2,i11,时，如果,i,为左孩子，即2（,i/2)=i,则,i/2,是,i,的双亲；如果,i,为右孩子，,i2p+1,i,的双亲应为,p，p（i1）/2=i/2.,证毕。,一、顺序存储结构,它是用一组连续的存储单元存储二叉树的数据元素。因此，必须把二叉树的所有结点安排成为一个恰当的序列，结点在这个序列中的相互位置能反映出结点之间的逻辑关系，用编号的方法：,#,define max-tree-size 100,/,二叉树的最大结点数,Typedef telemtype sqbitree,max-tree-size;,Sqbitree,bt,/0,号单元存储根结点,6.2.3 二叉树的存储结构,从树根起，自上层至下层，每层自左至右的给所有结点编号。缺点是有可能对存储空间造成极大的浪费，在最坏的情况下，一个深度为,h,且只有,h,个结点的右单支树却需要2,h,-1,个结点存储空间。而且，若经常需要插入与删除树中结点时，顺序存储方式不是很好！,a,b,c,d,e,f,g,h,i,j,k,l,1 2 3 4 5 6 7 8 9 10 11 12,完全二叉树,a,b,c,d,e,f,g,h,i,j,k,l,A,B,C,D,E,F,G,表示该处没有元素存在仅仅为了好理解,A,B,C,D,E,F,G,一般二叉树,顺序存储结构的算法：,Status,CreateBiTree,(,BiTree,*T),scanf,(&,ch,);,if(,ch,=)T=NULL;,else,if(!(T=(,BiTNode,*),malloc,(,sizeof,(,BiTNode,),exit(OVERFLOW);,Tdata=,ch,;,CreateBiTree,(T,lchild,);,CreateBiTree,(T,rchildd,);,return OK;,二、链式存储结构,1、二叉树的结点及其存储结构,PARENT,DATA,LCHILD,RCHILD,lchild,data,rchild,(,a),二叉树的结点,(,b),含有两个指针域的结点结构,lchild,data,parent,rchild,(,c),含有三个指针域的结点结构,2、二,叉,链表法,存储二叉树经常用二叉链表法,A,B,C,D,E,F,G,H,lchild,Data,rchild,二叉树的二叉链表存储表示,Typedef struct BiTNode,TelemType,data;,struct BiTNode,*,lchild,*,rchild,;,BiTNode,*,BiTree,;,有时也可用数组的下标来模拟指针,即开辟三个一维数组,Data,lchild,rchild,分别存储结点的元素及其左,右指针域;,在二叉树的一些应用中，常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理。这就引入了遍历二叉树的问题，即如何按某条搜索路径巡访树中的每一个结点，使得每一个结点均被访问一次，而且仅被访问一次。,6.3 遍历二叉树和线索二叉树,6.3.1遍历二叉树,遍历对线性结构是容易解决的，而二叉树是非线性的，,因而需要寻找一种规律，以便使二叉树上的结点能排,列在一个线性队列上，从而便于遍历。,(,右子树),b,c,a,(,根结点,),(,左子树,),由,二叉树的递归定义，,二叉树的三个基本组成单元是：根结点、左子树和右子树。,假如以,L、D、R,分别表示遍历左子树、遍历根结点和,遍历右子树，遍历整个二叉树则有,DLR、LDR、LRD、,DRL、RDL、RLD,六种遍历方案。若规定先左后右，则只有前三种情况，分别规定为：,DLR,先（根）序遍历，,LDR,中（根）序遍历，,LRD,后（根）序遍历。,1、,先序遍历二叉树,的操作定义为：,若二叉树为空，则空操作；否则,（1）访问根结点；,（2）先序遍历左子树；,（3）先序遍历右子树。,2、,中序遍历二叉树,的操作定义为：,若二叉树为空，则空操作；否则,（1）中序遍历左子树；（2）访问根结点；,（3）中序遍历右子树。,3、,后序遍历二叉树,的操作定义为：,若二叉树为空，则空操作；否则,（1）后序遍历左子树；,（2）后序遍历右子树；,（3）访问根结点。,例如图（1）所示的二叉树表达式,(,a+b*(c-d)-e/f),若先序遍历此二叉树,按访问结点的先后次序将结点排列起来,其先序序列为：,-+,a*b-,cd,/,ef,按中序遍历,其中序序列为：,a+b*c-d-e/f,按后序遍历,其后序序列为：,abcd,-*+,ef,/-,人喜欢中缀形式的算术,表达式,对于计算机,使,用后缀易于求值,图（1）,*,a,/,b,-,d,c,f,e,TREENODE*,creat,_tree(),TREENODE *t;,char c;,c=,getchar,();,if(c=#)return(NULL);,else,t=(TREENODE*),malloc,(,sizeof,(TREENODE),t data=c;,t,lchild,=create_tree();,t,rchild,=create tree();,return(t);,中序遍历算法:,#,include,#include,#define NULL 0,Typedef struct,node,char data;,struct,node*,lchild,*,rchild,;,TREENODE;,TREENODE*root;,TREENODE*,creat,_tree();,Void,inorder,(TREENODE*);,Void,inorder,(TREENODE*p),if(p!=NULL),inorder,(p,lchild,);,printf,(“%c”,pdata),inorder,(p,rchild,);,（3）,三叉链表,为了便于找到结点的双亲，可在结点结构中增加一个指向其双亲结点的指针域。这样的结构称为三叉链表。如下图所示：,lchild,data,parent,rchild,A,B,C,D,E,F,G,A,B,C,D,E,F,G,线索二叉树：,当以二叉链表作为存储结构时,只能找到结点的左右孩子的信息,而不能找到结点的任一序列的前驱与后继信息,这种信息只有在遍历的动态过程中才能得到,为了能保存所需的信息,可增加标志域;,其中:,0,lchild,域指示结点的左孩子,ltag,=,1,lchild,域,指示结点的前驱,0,rchild,域,指示结点的右孩子,rtag,=,1,rchild,域指示结点的后继,以这种结构构成的二叉链表作为二叉树的存储结构,叫做线索链表,其中指向结点前驱与后继的指针叫做线索.加上线索的二叉树称之为线索二叉树,lchild,ltag,data,rtag,rchild,对,二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。,在,线索树上进行遍历，只要先找到序列中的第一个结点，然后依次找结点后继直至其后继为空时而止。,在,线索树中找结点的前驱和后继：,（,1）中序线索树：树中所有叶子结点的右链是线索，则右链域直接指示了结点的后继。树中所有非终端结点的右链均为指针，根据中序遍历的规律可知，结点的后继应是遍历其右子树时访问的第一个结点，即右子树中最左下的结点。反之，在中序线索树中找结点前驱的规律是：若其左标志为“1”，则左链为线索，指示其前驱，否则遍历左子树时最后访问的一个结点（左子树中最右下的结点）为其前驱。,二叉树的二叉线索存储表示:,Typedef enum,Link,Thread,PointerTag,;,/Link=0:,指针,Thread=1:,线索,Typedef struct BiThrNode,TElemType,data;,struct BiTreeNode,*,lchild,*,rchild,;,PointerTag LTag,Rtag,;,BiTreeNode,*,BiThrTree,;,模仿线性表的存储结构,在二叉树的线索链表上也添加一个头结点,令其,lchild,域的指针指向二叉树的根结点,其,rchild,域的指针指向中序遍历时访问的最后一个结点;同时,令二叉树中序序列中的第一个结点,lchild,域的指针和最后一个结点,rchild,域,的指针均指向头结点;就像为二叉树建立了一个双向线索链表。,Status,InorderTraverse,_,Thr,(,BiThrTree,T,status(*visit)(,TElemType,e),/T,指向头结点,头结点的,lchild,左链指向根结点,/,中序遍历二叉线索树的非递归算法,对每个数据元素调用函数,Visit,P=T,lchild,;,while(p!=T),while(p,LTag,=Link)p=p,lchild,;,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,Status,InorderThreading,(,BiThrTree,&,Thrt,BiThrTree,T),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;,return OK;,/,InorderThreading,P,134,:,Void,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;,InThreading,(p,rchild,);,6.4,树和森林,6.4.1 树的存储结构,一、双亲表示法,二、孩子表示法,三、孩子兄弟表示法,6.4.2 森林与二叉树的转换,6.4.3 树和森林的遍历,树的,存储结构,双亲表示法,/-树的双亲表存储表示-,#,typedef,MAX_TREE_SIZE 100,Typedef,struct,PTNode,TElemType,data;,int,parent;/,双亲位置域,PTNode,;,Typedef,struct,PTNode,nodesMAX_TREE_SIZE;,int,n;/,结点数,Ptree,;,树的双亲表示法示例,R,A,B,C,D,E,F,G,H,K,0,R,-1,1,A,0,2,B,0,3,C,0,4,D,1,5,E,1,6,F,3,7,G,6,8,H,6,9,K,6,PARENT（T，x）,ROOT（x）,孩子表示法,由于树中每个结点可能有多棵子树，则可用多重链表，即每个结点有多个指针域，其中每个指针指向一棵子树的根结点，此时链表中的结点可以有如下两种结点格式：,data,child1,child2,childd,data,degree,child1,child2,childd,由于树中很多结点的度小于,d，,所以链表中有很多空链域，空间较浪费。在一棵有,n,个结点度为,k,的树中必有,n(k-1)+1,个空链域。,结点同构,结点是不同构的，其中,d,为结点的度，,degree,域的值同,d。,此时，虽能节约存储空间，但操作不方便。,孩子链表表示法,把每个结点的孩子结点排列起来，看成是一个线性表，且以单链表作存储结构，则,n,个结点有,n,个孩子链表(叶子的孩子链表为空表)。而,n,个头指针又组成一个线性表。,/树的孩子链表存储表示,typedef struct CTNode,/,孩子结点,int,child;,struct,CTNode,*next;,*,ChildPtr,;,typedef struct,TElemType,data;,ChildPtr firstChild,;/,孩子链表头指针,CTBox,;,typedef struct,CTBox,nodesMAX_TREE_SIZE;,int,n,r;/,结点数和根的位置,CTree,;,孩子链表表示法,0,A,1,B,2,C,3,D,4,R,5,E,6,F,7,G,8,H,9,K,3,5,6,0,1,2,7,8,9,(,a),孩子链表,孩子链表表示法,0,4,A,1,4,B,2,4,C,3,0,D,4,-1,R,5,0,E,6,2,F,7,6,G,8,6,H,9,6,K,3,5,6,0,1,2,7,8,9,(,a),带双亲的孩子链表,孩子兄弟表示法（又称二叉树表示法，或二叉链表表示法,链表中结点的两个域分别指向该结点的第一个结点和下一个兄弟结点。定义如下：,/树的二叉链表（孩子-兄弟）存储表示,Typedef struct CSNode,ElemType,data;,struct,CSNode,*,firstchild,*,nextsibling,;,CSNode,*,CSTree,;,孩子兄弟表示法（又称二叉树表示法，或二叉链表表示法,R,A,D,B,E,C,F,G,H,K,森林与二叉树的转换,由于二叉树和树都可用二叉链表作为存储结构，则以二叉链表作为媒介可导出树与二叉树之间的一个对应关系。也就是说，给定一棵树，可以找到唯一的一棵二叉树与之对应，从物理结构来看，它们的二叉链表是相同的，只是解释不同而已。任何一棵和树对应的二叉树，其右子树必空。若把森林中第二棵树的根结点看成是第一棵树的根结点的兄弟，则同样可导出森林和二叉树的对应关系。,树与二叉树的对应关系,A,C,E,B,D,A,B,C,D,E,对应,树,二叉树,A,B,C,D,E,A,B,C,E,D,A,B,C,D,E,解释,存储,存储,解释,森林与二叉树的对应关系,A,C,D,B,A,B,C,D,森林,树与二叉树对应,E,F,G,H,I,J,E,F,G,H,I,J,树根相连,A,B,E,C,D,F,H,G,I,J,森林与二叉树对应,森林与二叉树转换,一、森林转换成二叉树,如果,F=T,1,，T,2,，T,m,是森林，按如下规则转换成一棵二叉树,B=(root,LB,RB)。,（1）,若,F,为空，即,m=0，,则,B,为空树；,（2）若,F,非空，即,m0，,则,B,的根,root,即为森林中第一棵树的根,ROOT（T,1,）；B,的左子树,LB,是从,T,1,根,结点的子树森林,F1=T,11,，T,12,，T,1m1,转换而成的二叉树；其右子树,RB,是从森林,F=T,2,，T,3,，T,m,转换而成的二叉树。,二、二叉树转换成森林,如果,B=(root,LB,RB),是一棵二叉树，按如下规则转换成森林,F=T,1,，T,2,，T,m,。,（1）,若,B,为空，即,m=0，,则,F,为空；,（2）若,B,非空，即,m0，,则,F,的第一棵树的根,ROOT（T,1,）,即为二叉树,B,的,root；T,1,中根结点的子树森林,F1,是由,B,的左子树,LB,转换而成的森林；,F,中除之外其余树组成的森林,F=T,2,，T,3,，T,m,是由,B,的右子树,RB,转换而成的森林。,树和,森林的遍历,一、树的遍历,先根遍历树,：先访问树的根结点，然后依次先根遍历根的每棵子树；,后根,遍历树,：先依次后根遍历每棵子树，然后访问根结点。,二、森林的遍历,先序遍历森林：,（1）访问森林中第一棵树的根结点；,（2）先序遍历第一棵树中根结点的子树森林；,（3）先序遍历除去第一棵树之后剩余的书构成的森林。,中序遍历森林：,（1）中序遍历第一棵树中根结点的子树森林；,（2）访问森林中第一棵树的根结点；,（3）中序遍历除去第一棵树之后剩余的书构成的森林。,习题解析,1、假设二叉树中所有非叶子结点都有左、右子树，则对这种二叉树：,（1）试问：有,n,个叶子结点的树中共有多少个结点？,（2）试证明,其中：,n,为叶子结点的个数，,li,表示第,I,个叶子结点所在的层次数（设根结点所在的层次数为1）。,解,：(1),依题意，这种二叉树中没有度为1 的结点，度为2的结点数,n,2,和度为0的结点数,n,0,之间满足关系：,n2=n0-1；,所以总的结点数=,n2+n0=n0-1+n0=2n0-1=2n-1。,(2),证明：采用归纳法,当,n=1,时，,l1=1，,则,只有一个根结点，等式成立。,假设,nm-1,时有,只需证明,n=m,时该等式成立即可。,当,n=m,时，假设在有,m-1,个叶子结点的二叉树的,hi,层上的叶子结点上加上两个儿子结点，则总的叶子结点个数增加1个，这样构成一个有,m,个叶子结点的二叉树。,由于在该,m,个叶子结点的二叉树中所有叶子结点的,之和等于原来,m-1,个叶子结点的二叉树中,所有叶子结点的,之和减去添加两个儿子的,叶子结点的,加上该两个儿子的2+,所以：,练习,1、已知一棵二叉树的中序序列为,cbedahgijf,后序序列为,cedbhjigfa,画出该二叉树的先序线索二叉树。,a,b,f,c,d,g,e,h,i,j,NULL,练习,2、设二叉树,bt,的,存储结构如下：,1,2,3,4,5,6,7,8,9,10,left,0,0,2,3,7,5,8,0,10,1,data,j,h,f,d,b,a,c,e,g,i,right,0,0,0,9,4,0,0,0,0,0,(,1)画出二叉树,bt,的逻辑结构；,(2)写出按先序、中序和后序遍历二叉树,bt,所得的结点序列；,(3)画出二叉树,bt,的后线索化树。,6.5 赫夫曼树及其应用,一、最优二叉树（赫夫曼树）,1.基本术语,路径和路径长度：若在一棵树中存在着一个结点序列,k1,k2,kj,使得,ki,是,ki,+1,的父亲(1,ij),则称该结点序列是从,k1,到,kj,的路径。从,k1,到,kj,所,经过的分支数称为这两点之间的路径长度。,树的路径长度：从树根到每一结点的路径长度之和。,结点的权和带权路径长度：树中的结点上赋予的一定意义的实数称之为该结点的权。从树根结点到该结点之间的路径长度与该结点上权的乘积称为该结点的带权路径长度。,一、最优二叉树（赫夫曼树）,1.基本术语,树的带权路径长度：树中所有叶子结点的带权路径长度之和。记为：,其中,n,表示叶子结点个数，,wi,和,li,分别表示叶子结点,ki,的权值和根到,ki,之间的路径长度。,Huffman,树：又称最优二叉树，它是,n,个带权叶子结点构成的所有二叉树中，带权路径长度,WPL,最小的二叉树。,一、最优二叉树（赫夫曼树）,a,b,c,d,7 5 2 4,c,d,a,b,2,4,7,5,a,b,c,d,7,5,2,4,图6.22 具有不同带权路径长度的二叉树,(a),(b),(c),WPL=,72+5 2+2 2+4 2=36,WPL=,73+5 3+2 1+4 2=46,WPL=,73+5 3+2 1+4 2=46,2.构造,Huffman,树,根据与,n,个权值,w1,w2,wn,对应的,n,个结点构成,n,个结点构成,n,棵二叉树的森林,F=T1,T2,Tn,其中每棵二叉树,Ti(1in),都只有一个权值为,wi,的根结点，其左右子树均为空；,在森林,F,中选出两棵根结点的权值最小的树作为一棵新树的左右子树，且置新树的附加根结点的权值为其左右子树上根结点的权值之和。,从,F,中删除这两棵树，同时把新树加入,F,中。,重复(2)和(3),直到,F,中只含有一棵树为止，此树便是,Huffman,树。,2.构造,Huffman,树,b,c,d,7,5,2,4,(a),a,a,b,7,5,c,d,6,(b),a,c,d,b,7,11,c,d,b,(c),(d),二、赫夫曼编码,Huffman,编码的应用很广泛，利用,Huffman,树,构造的用于通信的二进制编码称为,Huffman,编码。例如：有一段电文“,CAST,TAT,A,SA”。,统计电文中字母的频度,f(C)=1,f(T)=3,f(,)=3,f(A)=4。,用频度1,2,3,3,4为权值生成,Huffman,树，并在每个叶子上注明对应的字符。树中从根到每个叶子都有一条路径，对路径上的各分支约定指向左子树根的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符的编码，这就是,Huffman,编码。,二、赫夫曼编码,13,6,7,3,3,3,4,1,2,C,S,T,A,0,0,0,1,1,1,1,0,000,001,01,10,11,Huffman,编码树,二、赫夫曼编码,由于,Huffman,树中没有度为1的结点，则一棵有,n,个叶子结点的,Huffman,树,共有2,n-1,个结点，可以存储在一个大小为2,n-1,的一维数组中。,结点结构的选择：,由于在构成,Huffman,树,之后，为求编码需从叶子结点出发走一条从叶子到根的路径；而为译码需从根出发走一条从根到叶子的路径。则对每个结点而言，既需知道双亲的信息，又需知道孩子结点的信息。,二、赫夫曼编码,Huffman,树和,Huffman,编码的存储表示,Typedef,struct,unsigned,int,weight;,unsigned,int,parent,lchild,rchild,;,HTNode,*,HuffmanTree,;,/,动态分配数组存储,Huffman,树,Typedef,char *,HuffmanCode,;,/,动态分配数组存储,Huffman,编码表,求,Huffman,编码的算法：,Void,HuffmanCoding,(,HuffmanTree,&HT,HuffmanCode,&HC,int,*w,int,n),/w,存放,n,个字符的权值（均0），构造,Huffman,树,HT，,并求出,n,个字符的,Huffman,编码,HC。,If(n=1)return;,m=2*n-1;,HT=(,HuffmanTree,),malloc,(m+1)*,sizeof,(,HTNode,);,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)/,建,Huffman,树,/在,HT1.i-1,选择,parent,为0且,weight,最小的两个结点,求,Huffman,编码的算法：,Select(HT,i-1,s1,s2);,HTs1.parent=i;HTs2.parent=i;,HTi.,lchild,=s1;Hti.,rchild,=s2;,HTi.weight=HTs1.weight+HTs2.weight;,/,从叶子到根逆向求每个字符的,Huffman,编码,HC=(,HuffmanCode,),malloc,(n+1)*,sizeof,(char*);,Cd,=(char*),malloc,(n*,sizeof,(char);,Cd,n-1=“0”;,For(I=1;I=n;+I),start=n-1;,求,Huffman,编码的算法：,for(c=I,f=HTI.parent;f!=0;c=f,f=HTf.parent),if(HTf.,lchild,=c),cd,-start=“0”;,else,cd,-start=“1”;,HCI=(char*),malloc,(n-start)*,sizeof,(char);,strcpy,(HCI,&,cd,start);,free(,cd,);,向量,HT,的前,n,个分量表示叶子结点，最后一个分量表示根结点。各字符的编码长度不同，所以按实际长度分配空间。,/-无栈非递归遍历,Huffman,树，求,Huffman,编码,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=0),HTp.,weigt,=1;,if(HTp.,lchild,!=0),p=HTp.,lchild,;,cd,cdlen,+=“0”;,else if(HTp.,rchild,=0),HCp=(char*),malloc,(,cdlen,+1)*,sizeof,(char);,cd,cdlen,=“0”;,strcpy,(HCp,cd,);,/-无栈非递归遍历,Huffman,树，求,Huffman,编码,else if(HTp.weight=1),HTp.weight=2;,if(HTp.,rchild,!=0),p=HTp.,rchild,;,cd,cdlen,+=“1”;,else,HTp.weight=0;p=HTp.parent;-,cdlen,;,练习,1.根据,Huffman,编码，编写一个程序在用户输入结点权重的基础上建立它的,Huffman,编码。,解：依题意，构造一棵,Huffman,树，由此得到的二进制前缀便为,Huffman,编码。由于,Huffman,树没有度为1的结点，则一棵有,n,个叶结点的,Huffman,树共有2,n-1,个结点。设计一个结构数组，存储 2,n-1,个结点的值，包括权重、父结点、左结点和右结点等。,C,程序,运行程序,练习,2.有一份电文中共使用5个字符：,a、b、c、d、e，,它们出现的频率依次为4、7、5、2、9，试画出对应的,Huffman,树（请按左子树根结点的权小于等于右子树根结点的权的次序构造），并求出每个字符的,Huffman,编码。,3.设给定权集,w=2,3,4,7,8,9，,试构造关于,w,的一棵,Huffman,树，并求出其加权路径长度,WPL。,