数据结构第6章 树二叉树.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第六章 树和二叉树,本章主要内容,一、树的基本概念,二、二叉树,三、二叉树的遍历,三、线索二叉树,四、树和森林,六、哈夫曼树,七、本章主要要求,6.1,树,的基本概念,1.,定义：,是一种常非线性结构树是,n,（,n0,）个结点的有限集合。若,n=0,，则称为空树；否则，有且仅有一个特定的结点被称为根，当,n1,时，其余结点被分成,m,（,m0,）个互不相交的子集,T1,，,T2,，,.,，,Tm,，每个子集又是一棵树。,递归定义的,树的几种形态,2.,树的特点,（,1,）树的根结点没有前驱结点，除根结点之外的所有结点有且只有一个前驱结点,（,2,）树中所有结点可以有零个或多个后继结点,3.,树的相关概念,1),结点,数据元素的内容及其指向其子树根的分支统称为结点,2),结点的度,结点的分支数。,3),终端结点（叶子）,度为,0,的结点。,4),非终端结点,度不为,0,的结点。,5),结点的层次,树中根结点的层次为,1,，根结点子树的根为第,2,层，以此类推。,6),树的度,树中所有结点度的最大值。,7),树的深度,树中所有结点层次的最大值。,8),有序树、无序树,如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序,树。,9),森林,是,m,（,m0,）棵互不相交的树的集合。,在树结构中，结点之间的关系又可以用家族关系描述，定义如下：,10),孩子、双亲,结点子树的根称为这个结点的孩子，而这个结点又被称为孩子的双亲。,11),子孙,以某结点为根的子树中的所有结点都被称为是该结点的子孙。,12),祖先,从根结点到该结点路径上的所有结点。,13),兄弟,同一个双亲的孩子之间互为兄弟。,14),堂兄弟,双亲在同一层的结点互为堂兄弟。,4.,树的表示法,直观表示法,嵌套集合表示法,凹入表示法,/,不清晰,广义表表示法,(1),(2),(3),(4),返回,6.2,二,叉树,1.,定义：,叉树是,n,（,n0,）个结点的有限集合。当,n=0,时，称为空二叉树；当,n0,时，有且仅有一个结点为二叉树的根，其余结点被分成两个互不相交的子集，一个称为左子集，另一个称为右子集，每个子集又是一个二叉树,递归定义的,2.,二叉树的五种形态,例,3.,二叉树的性质,在二叉树的第,i,层上最多有,2,i,-1,个结点（,i1,）,深度为,K,的二叉树最多有,2,K,-1,个结点（,K1,）,对于任意一棵二叉树,BT,，如果度为,0,的结点个数为,n,0,，度为,2,的结点个数为,n,2,，则,n,0,=n,2,+1,二叉树的总度数,n,1,+2n,2,二叉树的节点数,n,0,n,1,n,2,二叉树的总度数二叉树的节点数,1,n1+2n,2,=n,0,n,1,n,2,-1,即：,n0=n2+1,具有,n,个结点的完全二叉树的深度为,log,2,n,+1,证明：假设具有,n,个结点的完全二叉树的深度为,K,，则根据性质,2,可以得出：,2,K-1,-1n2,K,-1,将不等式两端加,1,得到：,2,K,-1n2,K,取以,2,为底的对数，化简：,K-1log,2,nn,，则结点,i,没有左孩子；否则其左孩子结点的编号为,2i,。,如果,2i+1n,，则结点,i,没有右孩子；否则其右孩子结点的编号为,2i+1,。,证明：采用数学归纳法，请大家自行阅读教材,4.,二叉树的存储,顺序存储结构,链式存储结构,通常二叉树可以用下面两种方式存储：,下页介绍,(1),顺序存储结构,适用完全二叉树，用一组连续的存储单元按照完全二叉树的每个结点编号的顺序存放结点内容,如下图所示：,下页给出,C,实现,#define MaxTreeNodeNum 100,typedef struct,DataType dataMaxTreeNodeNum;/*,根存储在下标为,1,的数组单元中,*,/,int n;/*,当前完全二叉树的结点个数*,/,QBTree;,顺序存储特点：,二叉树是完全二叉树时，空间利用率高、寻找孩子和双亲比较容易。,若二叉树不是完全二叉树，需要将空缺的位置用特定的符号填补，造成空间利用率的下降,引出链式存储,(2),链式存储结构,注：,Lchild,和,Rchild,是分别指向该结点左孩子和右孩子的指针,下页,C,实现,typedef char DataType,/*,设结点内容的数据类型为字符型*,/,typedef struct bnode,DataType data;,struct bnode*lchild,*rchild;,Bnode,*BTree;,二叉树链接存储的节点,定义,返回,6.3,二,叉树的遍历,定义：按照一定规则访问二叉树的所有节点一次,先序遍历,TLR,、,中序遍历,LTR,和,后序遍历,LRT,层次遍历,下页分述,T,L,R,(1),先序遍历,TLR,若二叉树为空，则结束遍历操作；否则,访问根结点；,先序遍历根的左子树先序遍历根的右子树,递归算法，思考它所对应的非递归算法,先看遍历的结果,下页,C,实现,void PreOrder(BTree t),if (t),visite(t-data);/*,访问结点内容*,/,PreOrder(t-lchild);/*,遍历左子树*,/,PreOrder(t-rchild);/*,遍历右子树*,/,思考：,1.visite,函数能做什么？,2.visite(t-data),这条语句执行次数？,3.,如何计算结点个数、叶子个数？,4,.,改变,visite,(t-data),这条语句的,位置会产生,什么效果,?,思考如何得到中序和后序遍历的算法？,（,2,）中序遍历和后序遍历算法,中序遍历,void InOrder(BTree t),if(t),InOrder(t-lchild);,Visite(t-data);,InOrder(t-rchild);,后序遍历,void PostOrder(BTree t),if(t),PostOrder(t-lchild);,PostOrder(t-rchild);,Visite(t-data);,三种访问序列的结果,（,3,）,三种遍历的非递归算法,树的定义是递归的，容易实现遍历的递归算法,思考遍历算法的执行过程,找出它们所对应的非递归算法,？,1,),先,序遍历的非递归算法,void PreOrder(BTree t),PSeqStack S;,BTree p=t;,/*,初始化*,/,S=Init_SeqStack();,/*,栈初始化*,/,while(p|!Empty_SeqStack(S),if(p),Visite(p-data);,Push_SeqStack(S,p);,/*,预留,p,指针在栈中*,/,p=p-lchild;,else,Pop_SeqStack(S,p=p-rchild;,/*,左子树为空,进右子树*,/,/end while,/end preorder,2,),中序遍历的非递归算法,将上述算法稍微改动就能写出中序遍历的非递归算法,请读者思考两个算法的差异,.,void InOrder(BTree T),PSeqStack S;,BTree p=t;,S=Init_SeqStack();,/*,初始化*,/,while(p|!Empty_SeqStack(S),if(p),Push_SeqStack(S,p);,/*,预留,p,指针在栈中*,/,p=p-lchild;,else,Pop_SeqStack(S,Visite(p-data);,p=p-rchild;,/*,左子树为空,进右子树*,/,3,),后序遍历的非递归算法,先思考如下问题,:,*,在先序中序遍历中,每个结点,(,结点地址,),进栈几次,?,出栈几次,?,*,在后序遍历中,每个结点,(,结点地址),进栈几次,?,出栈几次,?,*,为什么后序遍历特殊呢,?,*,如何区别结点的第,1,次和第,2,次进,(,出,),栈,?,3,),后,序遍历的非递归算法,typedef struct ,Bnode *node;,int flag;,DataType;,void PostOrder(BTree t),PSeqStack S;,DataType Sq;,int tag;BTree p=t;,S=Init_SeqStack();/*,栈初始化*,/,while(p|!Empty_SeqStack(S),if(p),Sq.flag=0;Sq.node=p;,Push_SeqStack(S,Sq)/*,将,p,指针以及,flag,压入栈中*,/,p=p-lchild;,else,Pop_SeqStack(S,p=Sq.node;,if(Sq.flag=0),Sq.flag=1;,Push_SeqStack(S,Sq);,/*,二次压栈*,/,p=p-rchild;,else,Visite(p-data);,p=null;/,思考为什么？,/*,把,p,赋空从栈中弹出下个结点*,/,/endif,/end if,/endwhile,end postorder,（,4,）层次遍历二叉树,定义：按照树深度的次序从左到右依次访问二叉树的所有节点,下页给出,C,实现,层次遍历算法,void LevelOrder(BTree T),BTree p=T;,if(P),Init_SeqQueue(Q);,/,初始化队列,Visite(p);In_SeqQueue(Q,p);,/,访问根结点，并将根结点入队,while(!Empty_SeqQueue(Q),/,当队非空时重复执行下列操作,Out_SeqQueue(Q,/,出队,if(p-Lchild)Visite(p-Lchild);In_SeqQueue(Q,p-Lchild);/,处理左孩子,if(p-Rchild)Visite(p-Rchild);In_SeqQueue(Q,p-Rchild);/,处理右孩子,(5),二,叉树遍历算法的应用,二叉树是递归定义，可以写出它的递归遍历算法，同时借助遍历算法可以实现一些基本的应用，如：,节,点,计数,创,建二,叉树,计,算二叉树的高,度等,例,1,：创建二叉树,有多种创建二叉树的方法,(,按先序建,按层次建,按中序和先序遍历结果建等,),以下算法按先序建,在,输入先序序列时，需要在空节点填补一个特殊的字符，比如，,#,。如果读入的字符是,#,，则在相应的位置上构造一棵空二叉树；否则，创建一个新结点。,采用先序遍历递归算法为基础，二叉树中结点之间的指针连接是通过指针参数在递归调用返回时完成,下页给出,C,实现,创建二叉树,BTree CreateBinTree(),/*,以加入空结点的先序序列输入，构造二叉链表*,/,char ch;BTree t;,ch=getchar();,if(ch=,)t=null;/*,读入时，将相应结点指针置空*,/,else,t=(BTree)malloc(sizeof(Bnode);/*,生成结点空间*,/,t-data=ch;,t-lchild=CreateBinTree();/*,构造二叉树的左子树*,/,t-rchild=CreateBinTree();/*,构造二叉树的右子树*,/,return t;,？,思考：,1.,如何输入？,2.,能否中序建树和后序建,树？,例,2,：求二叉树每层结点个数,思路：,二叉树中每个结点都对应一个层次,如果当前结点,T,对应的层次是,L,则,T-Lchild,和,T-Rchild,所对应的层次就是,L+1,利用这个特性,我们很容易用遍历算法求出结果,设,置一个数组，数组的下标表示树的层数，该下标元素的值记录该层元素的个数；通过树的遍历算法来得到最终数组元素的值,下页给出,C,实现,void Levcoun(BTree t,int L,int num ),/*,求链式存储的二叉树,t,中每层,结点个数,L,表示当前,t,所指结点的层次，当,t,初值为根时，,L,初值为,1,，,num,数组元素初始化,0*/,if(t),Visite(t-data);,/,访问当前结点,numL+;/,当前,t,所指结点的层次数增加,1,Levcoun(t-lchild,L+1,num);,/,递归左子树,Levcoun(t-rchild,L+1,num,);/,递归右子树,例,3,：计算二叉树的高度,树的高度定义：树中节点深度的最大值,思路：,二叉树的高度是左右子树的最大高度,+1,，所以先计算出左右子树高度的较大值，左右子树高度的求法和原二叉树高度的求法一样，所以采用递归方法。,下页给出,C,实现,int Height(BTree t),int h1,h2;,if(t=null)return 0;,else,h1=Height(t-lchild);,/*,求左子树的高度*,/,h2Height(t-rchild);,/*,求右子树的高度*,/,if(h1h2)return h1+1;,else return h2+1;,int Height(BTree t),int h1,h2;,if(t=null)return 0;,return(h1=Height(t-lchild),h2=Height(t-rchild)?h1+1:,h2+1);,例,4,复制二叉树,已知一棵二叉树用链式存储结构，要求将此二叉树复制成另外一棵二叉树,思路：复制包括复制根节点，左子树，右子树，并且把复制的左右子树挂到复制的根节点上,采用递归的思想来实现复制树,下页给出,C,实现,BTree CopyTree(BTree t),BTree,p,q,s;,if,(t=null)return(null);,p=CopyTree(t-,lchild);,/*,复制左子树*,/,q=CopyTree(t-rchild);,/*,复制左子树*,/,s=(Bnode*)malloc(sizeof(Bnode);,/*,复制根结点*,/,s-data=t-data;,s-lchild=p;,s-,rchild=q;,return s;,例,5,交,换二叉树的左右子树,要求：将二叉树中所有的左右子树交换,void change_left_right(BTree t),if(t),change_left_right(t-lchild);,change_left_right(t-rchild);,t-lchildt-rchild;,交换的简写,返回,6.4,线,索二叉树,问题的提出：二叉树中有很多,(,思考：到底有多少？,),闲置的指针，能否利用它们为访问二叉树提供便利，如下图所示：,如：求解某结点在某种遍历次序下的前驱,或后 继,结点,求前驱和后继的方法：,遍历,通过指定次序的遍历发现结点的前驱或后继，费时间，低效,增设前驱和后继指针,在每个结点中增设两个指针，分别指示该结点在指定次序下的前驱或后继。增加空间开销,利用二叉链表中的空指针域（,n,个结点的二叉树,有,n+1,个空指针域,），将二叉链表中的空的指针域改为指向其前驱和后继：空的左孩子指针指向其前驱，空的右孩子指针指向其后继,比较好的方法,线索化,为什么？,？,一般采用加区分标志的线索化,ltag=0,：,lchild,指示该结点的左孩子,ltag=1,：,lchild,指针该结点的前趋。,rtag=0,：,rchild,指示该结点的右孩子,rtag=1,：,rchild,指针该结点的后继。,有线索标志的二叉树,A,B,C,D,E,A,B,D,C,E,T,中序序列：,BCAED,0,0,0,0,1,1,1,1,1,1,中序线索二叉树,1.,线索二叉树的实现（中序）,线索二叉链表结构描述如下：,typedef char DataType,；,/*,不妨设数据类型为字符型*,/,typedef struct Threadnode,int ltag,rtag;,DataType data;,struct Threadnode *lchild,*rchild;,Threadnode,，*,ThreadTree;,采用递归的思想,中序线索化算法,void InThread(ThreadTree t,ThreadTree pre),/*,递归中序线索化二叉树；函数调用前,pre,为空,pre,为,t,的前驱*,/,if (t),InThread(t-lchild,pre);/*,中序线索化左子树*,/,if(t-lchild=null),/*,建立前驱线索*,/,t-ltag=1;,t-lchild=pre;/*,左孩子域指向前驱*,/,if(t-rchild=null),t-rtag=1;/*,为下次后继线索做准备*,/,if(pre)&(pre-rtag=1)/*,建立后继线索*,/,pre-rchild=t;,pre=t;,InThread(t-rchild,pre);,/*,中序线索化右子树*,/,/endif,如何写出非递归的中序线索程序？,2.,中序线索二叉树的遍历算法,（不用栈）,void InOrderTh(ThreadTree t),/*,对中序线索二叉树进行中序遍历*,/,ThreadTree p;,if(t),p=t;,while(p-ltag=0)p=p-lchild;,/*,找最左下的结点，即中序遍历的第一个结点*,/,while(p),/*,访问当前结点并找出当前结点的中序后继*,/,visite(p-data);,/*,访问当前结点*,/,p=InPostNode(p);,/*,在中序线索二叉树上寻找结点,p,的中序后 继结点*,/,如何实现,Inpostnode,？,3.,中序线索下求前驱和后继,结点的左标志为,1,，那么其左指针域所指向的结点便是它的前驱结点,如果该结点的左标志为,0,，表明该结点有左孩子，它的前驱结点是以该结点的左孩子为根结点的子树的最右结点，即沿着其左子树的右指针链向下查找，当某结点的右标志为,1,时，就是所要找的前驱结点,求,前,驱,（,1,）,若,ltag=1,则,lchild,域直接指向其前驱,（,2,）若,ltag=0,则结点的前驱应是其左子树的右链尾（,rtag=1),的结点,示例：,在,中序线索二叉树中找结点前驱,A,B,C,D,E,F,G,H,C,0,0,0,1,1,1,1,1,1,A,B,D,F,T,E,G,0,1,0,0,0,H,1,1,pre,A-ltag=0?,例：求,A,结点的前驱,pre-rtag=0?,pre-rtag=0?,pre-rtag=0?,中序线索中找前驱算法,ThreadTree InPreNode,（,ThreadTree p,）,/*,在中序线索二叉树上寻找结点,p,的中序前驱结点，假设,p,非空*,/,ThreadTree pre;,pre=p-lchild;,if(p-ltag=1)return pre;,while(,pre-rtag=0,)pre=pre-rchild;,return(pre);,?,中序线索下的后继,如结点的右标志为,1,，那么其右指针域所指向的结点便是它的后继结点,如果该结点的右标志为,0,，表明该结点有右孩子，它的后继结点是以该结点的右孩子为根结点的子树的最左结点，即沿着其右子树的左指针链到达某结点的左标志为,1,时，即是要找的后继结点,求,后,继,示例：在中序线索二叉树中找结点后继,（,1,）若,rtag=1,则,rchild,域直接指向其后继,（,2,）若,rtag=0,则结点的后继应是其右子树的左链尾（,ltag=1),的结点,A,B,C,D,E,F,G,H,C,0,0,0,1,1,1,1,1,1,A,B,D,F,T,E,G,0,1,0,0,0,H,1,1,B-rtag=0?,例：求,B,结点的后继,post,post-rtag=0?,post-rtag=0?,中序线索找后继算法,ThreadTree,InPostNode,（,ThreadTree p,）,/*,在中序线索二叉树上寻找结点,p,的中序后继结点，假设,p,非空*,/,ThreadTree post;,post=p-rchild;,if (p-rtag=1)return post;,while(,post-ltag=0,)post=post-lchild;,return(post);,?,中序线索二叉树上查找值为,x,的结点,在中序线索二叉树上查找值为,x,的结点，实质上就是在线索二叉树上进行遍历，对访问到的结点进行判断即可：,ThreadTree Search(ThreadTree t,，,DataType x),ThreadTree p;,p=t;,if(p),while(p-ltag=0)p=p-lchild;/*,找最左下结点中序遍历,的第一个结点*/,while(p&p-data!=x),p=InPostNode(p);/*,在中序线索二叉树上寻找结点,p,的,中序后继结点*,/,return p;,返回,6.5,树,和森林,1.,树的逻辑定义：,是,n,（,n0,）个有限数据元素的集合。当,n,0,时，称这棵树为空树。在一棵非空树,T,中：,（,1,）有一个特殊的数据元素称为树的根结点，根结点没有前驱结点。,（,2,）若,n1,，除根结点之外的其余数据元素被分成,m,（,m0,）个互不相交的集合,T1,，,T2,，,，,Tm,，其中每一个集合,Ti,（,1im,）本身又是一棵树。树,T1,，,T2,，,，,Tm,称为这个根结点的子树如何存储树？,2.,树的存储结构,（,1,）双亲表示法：存储每个节点的信息，记起双亲节点的位置，一般用顺序存储结构,找双亲易，找子难,C,实现,用,C,类型定义如下：,#define MaxNodeNum 100,typedef struct,DataType data;,int parent;,Parentlist;,typedef struct,Parentlist elemMaxNodeNum;,int n;/*,树中当前的结点数目*,/,ParentTree;,（,2,）孩子表示法,类似于图的邻接表表示，把节点的所有孩子用指针串起来,C,实现,特点：找子易，找双亲难,#define MaxNodeNum 100,typedef struct tnode /,孩子结点描述,int elem;,struct tnode *next;,Tnode;,typedef struct bnode/,首结点描述,DataType data;,Tnode *firstchild;/,指向第一个孩子,Bnode;,typedef struct,Bnode Tree_AYMaxNodeNum;,int n;/*,树中当前的结点数目*,/,Tree,*PTree;,改进：,或者在每个节点增加一个保存父节点位置的信息字段,增加,DataType,Parent_postion,（,3,）孩子兄弟表示法,每个节点中存储自己,的第,一个孩子和兄弟的地址（连接所有的兄弟,），属于链式存储,存储结构如下,:,typedef struct tnode ,DataType data;,struct tnode *firstson,*nextbrother;,Tnode;,3.,树、森林和二叉树的转换,树和森林的存储表示复杂，实施具体的算法很困难，而二叉树的算法的比较丰富，牵涉到树和森林的问题，一般转换成对应的二叉树，通过二叉树来解决,树转换成二叉树,森林转换成二叉树,二叉树转换成树,二叉树转换成森林,树,转换成二叉树,将一棵树转换为二叉树的方法是：,树中所有相邻兄弟之间加一条连线。,对树中的每个结点，只保留它与第一个孩子结点之间的连线，删去它与其它孩子结点之间的连线。,以树的根结点为轴心，将整棵树顺时针转动一定的角度，使之结构层次分明,转换过程示意图：,4.,树和森林的遍历,树的遍历：,有先根遍历和后根遍历两种,思考：,树的遍历有没有中根遍历？,先根遍历：,访问根结点,按照从左到右的顺序先根遍历根结点的每一棵子树,后根遍历：,按照从左到右的顺序后根遍历根结点的每一棵子树,访问根结点,遍历的结果,？,先根遍历结果：,A,B,E,F,I,G,先,根遍,历,：,先访问树的根结点，然后,依次,先根遍,历根 的,每棵子树,D,A,B,D,E,F,G,I,后,根遍,历,：,先依次后根遍历每棵子树然后访问根结点,A,B,D,E,F,G,I,后根遍,历：,E,I,F,G,B,D,A,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,先根遍历：,后根遍历：,A,B,E,F,I,G,C,D,H,J,K,L,N,O,M,E,I,F,G,B,C,J,K,N,O,L,M,H,D,A,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,例,树：,对应二叉树：,先序遍历：,A,B,E,F,I,G,C,D,H,J,K,L,N,O,M,中序遍历：,E,I,F,G,B,C,J,K,N,O,L,M,H,D,A,树的先根遍历与对应二叉树的先序遍历结果相同！,树的后根遍历与对应二叉树的中序遍历结果相同！,6.6,哈,夫曼树,1.,问题的提出：在通信系统中，要发送由,A,，,B,，,C,，,D,四个字符组成的信息，,A,出现的,概率,为,0.5,，,B,出现的,概率,为,0.25,，,C,出现的,概率,为,0.1,，,D,出现的,概率,为,0.15,。如何对,A,、,B,、,C,、,D,四个字符进行编码，能使总的编码长度最短？,思路,另一种编码方案,类似,3,8,译码器,第二种编码方案优于第一种编码方案,是否有规律可循？,2.,与哈夫曼树相关的一些概念,1),路,径 从树中一个结点到另一个结点,之间的分支,构成两个结点之间的路径。,2),路,径长度 路径上的,分支数目,。,3),树,的路径长度 根结点到每个叶子结点的路径长度之和。,4),树,的带权路径长度 树中所有叶子结点的带权路径长度之和。,记作,:,其中，,w,i,是第,i,个叶子结点的权值，,l,i,为从根到第,i,个叶子结点的路径长度，,m,为树的叶子结点的个数,3.,哈夫曼树的定义,最优二叉树 设有,m,个权值,w,1,w,2,w,m,，构造一棵有,m,个叶子结点的二叉树，第,i,个叶子结点的权值为,w,i,，则带权路径长度,WPL,最小的二叉树被称作,最优二叉树,这种最优二叉树也称之为,哈夫曼树,哈夫曼树举例,权值的计算：,b,是哈夫曼树,4.,建立哈夫曼树的算法,(1),根据给定的,m,个权值,w1,w2,wm,，构成,m,棵二叉树的集合,T=T1,T2,Tm,，其中每个,Ti,只有一个带权为,wi,的根结点，其左右子树均空。,(2),从,T,中选两棵根结点的权值最小的二叉树，不妨设为,Ti,、,Tj,并作为左右子树构成一棵新的二叉树,Tk,，并且置新二叉树的根值为其左右子树的根结点的权值之和。,(3),将新二叉树,Tk,并入到,T,中，同时从,T,中删除,Ti,、,Tj,。,(4),重复,(2),、,(3),，直到,T,中只有一棵树为止。这棵树便是哈夫曼树。,构造过程,:,假,设有一组权值,5,29,7,8,14,23,3,11,，下面我们将利用这组权值演示构造哈夫曼树的过程。,第一步：以这,8,个权值作为根结点的权值构造具有,8,棵树的森林,5 29 7 8 14 23 3 11,第二步：从中选择两个根的权值最小的树,3,，,5,作为左右子树构造一棵新树，并将这两棵树从森林中删除，并将新树添加进去,3 5,29 7 8 14 23 11,8,第三步：重复第二步过程，直到森林中只有一棵树为止,选择,7,，,8,29 14 23 11,7 8,15,3 5,8,29 14 23,7 8,15,8,3 5,19,11,选,择,8,，,11,选,择,14,，,15,选,择,19,，,23,29,15,7 8,29,14,3 5,8,42,23,19,11,选择,29,，,29,7 815,58,29,29,14,3 5,8,42,23,19,11,选择,42,，,58,100,7 8,15,58,29,29,14,3 5,8,42,23,19,11,这就是以上述,8,个权值为叶子结,点权,值,构成的哈夫曼树，它的带权,的路,径,长度为：,WPL=(23+29)*2+(11+14)*3+(3+5+7+8)*4=271,5.,哈夫曼树的,特点,特点,1,：,若一棵二叉树是哈夫曼树，则该二叉树不存在度为,1,的结点。,特点,2,：,若给定权值的叶子结点个数为,n,，则所构造的哈夫曼树中的结点数是,2n-1,。,说明：由特点,1,和二叉树的性质,3,可得,特点,3,：,任一棵哈夫曼树的带权路径长度等于所有分支结点值的累加和。,思考为什么？可以证明么，如何证明？,树中所有叶子结点的带权路径长度之和,6.,哈,夫曼编码,前缀编码（何为前缀编码？）方式，能实现一组指定出现频率字符编码长度之和最小,A:0,T:10,C:110,S:111,前缀编码得到的字符编码,返回,#,define N 20,/*,叶子结点数*,/,typedef,int DataType;,typedef,struct ,char,ch;,DataType,weight;,/*,假设叶子权值为整型*,/,int,lchild,rchild,parent,;,Htnode;,/*,哈夫曼树结点类型*,/typedef,struct,char,*code;,char,leaf;,int,length;,/*,编码的长度*,/,CodeType;,/*,叶编码类型*,/,哈夫曼算法的,C,实现,类,型,定,义,定义,Htnode,类型的数组用来存储哈夫曼树,哈夫曼算法,void Hufcoding(Htnode huftree,CodeType cd,int w,int n),/*,哈夫曼树存放在静态链表,huftree,中,w,存放结点权重,n,是叶子个数,最后的编码放在,cd*/,int i,j,k,s1,s2,s,m,f,c,sum;,char tempN;/*,暂存叶子编码字符串，最后需要转置,*,/,m=2*n-1;,/*,计算哈夫曼树的结点总数*,/,for(i=1;i=n;i+)/*,初始化每个结点自成一棵树,*,/,huftreei.weight=wi-1;,huftreei.lchild=huftreei.rchild=huftreei.parent=-1;,huftreei.ch=getch();,构造哈夫曼树算法,for(i=n+1;i=m;i+),/*,初始化*,/,huftreei.weight=-1;,huftreei.lchild=huftreei.rchild=huftreei.parent=-1;,for(i=1;i=n-1;i+)/*,生成,n-1,个非叶子结点的循环,*,/,selectsort(huftree,n+i-1,/*,对数组,huftree,1.n+i-1,中无双亲的结点权值进行排序，,s1,s2,将是,无双亲且权 重最小的两个结点下标*,/,sum=huftrees1.weight+huftrees2.weight;,huftreen+i.weight=sum;,huftrees1.parent=huftrees2.parent=n+i;,huftreen+i.lchild=s1;huftreen+i.rchild=s2;,对叶子编码算法,for(i=1;i=0)cdi.codek+=tempc-,-;/*,将,temp,转置到,cd,中 *,/,cdi.leaf=huftreei.ch;,cdi.length=k;,/*end for*/,/*end for*/,