数据结构万扣树.pptx

3.1 树的定义一.树的定义 树是n个数据元素的有限集(记为T)，对任意一棵树T有：存在唯一一个称为根的数据元素；当n1时，其它数据元素可分为m(m0)个互不相交的有限集T1,T2,Tm，其中每个集合Ti(i=1,2,m)本身又是一棵树，并称树Ti是根的子树。第1页/共87页3.1 树的定义二.树的表示形式 倒悬树。是最常用的表示形式，如图6-1(b)。嵌套集合。是一些集合的集体，对于任何两个集合，或者不相交，或者一个集合包含另一个集合。图6-2(a)是图6-1(b)树的嵌套集合形式。广义表形式。图6-2(b)是树的广义表形式。凹入法表示形式。见P120 树的表示方法的多样化说明了树结构的重要性。第2页/共87页3.1 树的定义ABDCEGFHIMJNKL(a)一般的树(b)嵌套集合形式HIJDFBKLECMNGA(c)广义表形式A(B(E(K,L),F),C(G(M,N),D(H,I,J)）第3页/共87页3.1 树的定义三.树的基本术语1.树的结点:包含一个DE和指向其子树的所有分支;2.结点的度:一个结点拥有的子树的个数；度为零的结点称为叶结点;3.树的度:树中所有结点的度的最大值Max(D(I)含义:树中最大分支数为树的度4.结点的层次及树的深度:根为第一层,根的孩子为第二层,若某结点为第k层,则其孩子为k+1层；树中结点的最大层次称为树的深度或高度；5.森林:是m(m=0)棵互不相的树的集合；森林与树概念相近,相互很容易转换；第4页/共87页3.1 树的定义1层2层4层3层depth=4DACBIJHGFEMLKheight=4第5页/共87页3.2 二叉树一.二叉树的概念 二叉树是结点数为0或每个结点最多只有左右两棵子树的树。二叉树是一种特殊的树结构，它的特点是：每个结点最多只有两棵子树，即不存在结点度大于2的结点；子树有左右之分，不能颠倒。问题：二叉树和度为问题：二叉树和度为2的树有何不同？的树有何不同？第6页/共87页3.2 二叉树二二.二叉树的性质二叉树的性质性质性质1 1.在二叉树的第在二叉树的第i i层上至多有层上至多有2 2i-1i-1个结点个结点(i1)(i1)。证明证明:用归纳法用归纳法1.1.当当i=1,i=1,即第一层只有一个根结点即第一层只有一个根结点,显然显然 2 2i-1i-1=2 20 0=1=1成立成立2.2.假设对所有的假设对所有的j j上述性质成立上述性质成立,即第即第j j层上至多有层上至多有2 2j-1j-1个结点个结点3.3.要证明要证明i=j+1i=j+1时时,命题也成立。命题也成立。由归纳假设：第由归纳假设：第j j层上至多有层上至多有2 2j-1j-1个结点，又由于二叉树每个个结点，又由于二叉树每个结点的度最大为结点的度最大为2 2，所以第，所以第j+1j+1层上结点总数最多为第层上结点总数最多为第j j层上最大层上最大结点数的结点数的2 2倍。即倍。即2*22*2j-1j-1=2=2(j+1)-1(j+1)-1第7页/共87页3.2 二叉树性质性质2 2.深度为深度为k k的二叉树至多有的二叉树至多有2 2k k-1-1个结点个结点(k1)(k1)。（深度一定，二叉树的最大结点数也确定）（深度一定，二叉树的最大结点数也确定）证明：证明：深度为深度为k k的二叉树的最大结点数是二叉树的二叉树的最大结点数是二叉树中每层上结点的最大数之和。即中每层上结点的最大数之和。即 k k （第（第i i层上结点的最大数）层上结点的最大数）i=1 i=1 k k=2=2i-1 i-1=1+2+2=1+2+22 2+2+2k-1k-1=2=2k k-1(-1(等比级数求和等比级数求和)i=1i=1第8页/共87页3.2 二叉树性质性质3 3.二叉树中二叉树中,终端结点数终端结点数n n0 0与度为与度为2 2的结点数的结点数n n2 2有有如下关系如下关系:n n0=0=n n2 2+1+1证明证明:设二叉树中度为设二叉树中度为i i的结点数为的结点数为n ni i,则则 结点总数结点总数n=nn=n0 0+n+n1 1+n+n2 2 除根结点外除根结点外,每个结点都是另一结点的孩子每个结点都是另一结点的孩子 孩子数孩子数=n-1=n-1；度为度为i i（i=0i=0，1 1，2 2）的结点，有）的结点，有i i个孩子。个孩子。孩子数孩子数=2n=2n2 2+n+n1 1 n-1=2n n-1=2n2 2+n+n1 1 即即 n n0 0+n+n1 1+n+n2 2-1=2n-1=2n2 2+n+n1 1 故故 n n0 0=n n2 2+1 +1 第9页/共87页3.2 二叉树满二叉树满二叉树:深度为深度为k k，且有，且有2 2k k-1-1个结点的二叉树。个结点的二叉树。特点：（特点：（1 1）每一层上结点数都达到最大）每一层上结点数都达到最大 （2 2）度为）度为1 1的结点数的结点数n n1 1=0=0 结点层序编号方法：从根结点起从上到下逐层结点层序编号方法：从根结点起从上到下逐层（层内从左到右）对二叉树的结点进行连续编号。（层内从左到右）对二叉树的结点进行连续编号。1237654k=3n=23-1=7 满二叉树满二叉树 第10页/共87页3.2 二叉树完全二叉树完全二叉树:深度为深度为k k，结点数为，结点数为n n的二叉树，的二叉树，当且仅当每个结点的编号都与相同深度的满二当且仅当每个结点的编号都与相同深度的满二叉树中从叉树中从1 1到到n n的结点一一对应时，称为完全二的结点一一对应时，称为完全二叉树。叉树。452131237654k=3n=23-1=7 满二叉树满二叉树 完全二叉树完全二叉树第11页/共87页3.2 二叉树LHLH2 2=0=0RHRH2 2=1=11324653241LH1=3RH1=1LH1 -RH1=2 非完全二叉树非完全二叉树 非完全二叉树非完全二叉树LH2-RH2=0-1=-1第12页/共87页3.2 二叉树性质性质4.4.结点数为结点数为n n的完全二叉树，其深度为的完全二叉树，其深度为 loglog2 2n n +1+1证明：设深度为证明：设深度为k k，则则 由性质由性质2 2和完全二叉树定义有：和完全二叉树定义有：结点数结点数n n满足：满足：2 2k-1k-1-1-1n2n2k k-1-1 或写为或写为2 2k-1k-1nn2 2k k 于是有：于是有：k-1logk-1log2 2n nk k 因为因为 k-1k-1和和k k均为整数均为整数 显然有显然有loglog2 2n n=k-1,=k-1,故故 k=k=loglog2 2n n +1+1第13页/共87页3.2 二叉树性质性质5.5.在按层序编号的在按层序编号的n n个结点的完全二叉树中，个结点的完全二叉树中，任意一结点任意一结点i(1in)i(1in)有：有：i=1i=1时，结点时，结点i i是树的根；否则是树的根；否则(i1)(i1)，结点，结点i i的的双亲为结点双亲为结点i/2i/2。2i2in n时，结点时，结点i i无左孩子，为叶结点；否则，无左孩子，为叶结点；否则，结点结点i i的左孩子为结点的左孩子为结点2i2i。2i+12i+1n n时，结点时，结点i i无右孩子；否则，结点无右孩子；否则，结点i i的的右孩子为结点右孩子为结点2i+12i+1。第14页/共87页3.2 二叉树三、二叉树的存储结构三、二叉树的存储结构 顺序存储结构顺序存储结构用一组地址连续的存储单元，以层序顺序存放二叉树用一组地址连续的存储单元，以层序顺序存放二叉树的数据元素，结点的相对位置蕴含着结点之间的关系。的数据元素，结点的相对位置蕴含着结点之间的关系。完全二叉树完全二叉树DCGFEBA bt3的双亲为的双亲为3/23/2=1，即在即在b t1中；中；其左孩子在其左孩子在bt2i=bt6中；中；其右孩子在其右孩子在bt2i+1=bt7中。中。1 2 3 4 5 6 7 8 9 10 11 A B C D E F G 0 0 0 0bt第15页/共87页3.2 二叉树一般二叉树也按完全二叉树形式存储一般二叉树也按完全二叉树形式存储,没结点处用没结点处用0表示表示D 二叉树二叉树CGFEBA1 2 3 4 5 6 7 8 9 10 11 A B C D E 0 0 0 0 F G 0 0 0 0这种存储结构适合于完全二叉树，既不浪费存储空这种存储结构适合于完全二叉树，既不浪费存储空间，又能很快确定结点的存放位置、以及结点的双间，又能很快确定结点的存放位置、以及结点的双亲和左右孩子的存放位置，但对一般二叉树，可能亲和左右孩子的存放位置，但对一般二叉树，可能造成存储空间的浪费。造成存储空间的浪费。第16页/共87页3.2 二叉树例如例如，深度为深度为k k，且只有，且只有k k个结点的右单枝树个结点的右单枝树(每个非叶结点只有右孩子每个非叶结点只有右孩子)，需，需2 2k k-1-1个单元，个单元，即有即有2 2k k-1-k-1-k个单元被浪费。个单元被浪费。1k第17页/共87页3.2 二叉树 链式存储结构 设计不同的结点结构，可以构成不同的链式存储结构。常用的有：n 二叉链表n 三叉链表n 线索链表 用空链域存放指向前驱或后继的线索 第18页/共87页3.2 二叉树D 二叉树二叉树CEBAACBDE二叉链表二叉链表leftChild data rightChilddataleftChildrightChild用于二叉树存储的链表结构，常见的有二叉链表和三叉链表用于二叉树存储的链表结构，常见的有二叉链表和三叉链表 二叉链表二叉链表的每个结点的结构描述如下：的每个结点的结构描述如下：struct BTNode int data;/数据域数据域 BTNode *lch;/左指针域左指针域 BTNode *rch;/右指针域右指针域 第19页/共87页3.2 二叉树三叉链表三叉链表的每个结点的结构描述如下：的每个结点的结构描述如下：struct node3 int data;/数据域数据域 node3 *lch,*par，*rch;/par是双亲指针域是双亲指针域 ;leftChild data parent rightChildparentdataleftChildrightChild第20页/共87页(2)二叉树的链式存储形式二叉树的链式存储形式 例有一棵一般的二叉树，如图例有一棵一般的二叉树，如图6-8(a)所示。以二叉链所示。以二叉链表和三叉链表方式存储的结构图分别如图表和三叉链表方式存储的结构图分别如图6-8(b)、6-8(c)所示。所示。图6-8 二叉树及其链式存储结构(a)二叉树afedcbg(c)三叉链表 a b c d e f g T(b)二叉链表 a b c d e g f T第21页/共87页3.2 二叉树性质性质6 6.含有含有n n个结点的二叉链表中，有个结点的二叉链表中，有n+1n+1个空链域。个空链域。证明：空链域数证明：空链域数=2n=2n0 0+n+n1 1 因为因为 n=nn=n0 0+n+n1 1+n+n2 2 （1 1）又有又有 n n0 0=n=n2 2+1 +1 即即 -1=n-1=n2 2-n-n0 0 （2 2）（1 1）-（2 2）得）得 n+1=2nn+1=2n0 0+n+n1 1 故空链域数故空链域数=n+1=n+1第22页/共87页3.3 遍历二叉树二叉树最主要、最基本的运算是遍历。二叉树最主要、最基本的运算是遍历。遍历二叉树是指以一定的次序访问二叉树中的每个结点，是指以一定的次序访问二叉树中的每个结点，并且每个结点仅被访问一次。并且每个结点仅被访问一次。访问结点是指对结点进行各种操作的简称。是指对结点进行各种操作的简称。例如，查询结点数据域的内容，或输出它的值，或找出结例如，查询结点数据域的内容，或输出它的值，或找出结点位置，或是执行对结点的其他操作。点位置，或是执行对结点的其他操作。遍历二叉树的过程遍历二叉树的过程实质实质是把二叉树的结点进行线性排列的是把二叉树的结点进行线性排列的过程。过程。第23页/共87页3.3 遍历二叉树二叉树的遍历就是按某种次序访问树中的结二叉树的遍历就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。点，要求每个结点访问一次且仅访问一次。设设访问根结点访问根结点记作记作 V 遍历根的左子树遍历根的左子树记作记作 L 遍历根的右子树遍历根的右子树记作记作 R则可能的遍历次序有则可能的遍历次序有 前序前序 VLR 中序中序 LVR 后序后序 LRV第24页/共87页3.3 遍历二叉树对于二叉树的遍历，分别讨论递归遍历算法和非递归遍历算法。递归遍历算法具有非常清晰的结构，但初学者往往难以接受或怀疑，不敢使用。实际上，递归算法是由系统通过使用堆栈来实现控制的。而非递归算法中的控制是由设计者定义和使用堆栈来实现的。第25页/共87页3.3 遍历二叉树第26页/共87页先序遍历二叉树1 递归算法递归算法算法的递归定义是：算法的递归定义是：若二叉树为空，则遍历结束；否则若二叉树为空，则遍历结束；否则 访问根结点；访问根结点；先序遍历左子树先序遍历左子树(递归调用本算法递归调用本算法)；先序遍历右子树先序遍历右子树(递归调用本算法递归调用本算法)。第27页/共87页遍历二叉树先序遍历的递归算法void PreorderTraverse(BTNode *T)if(T!=NULL)visit(T-data);/*访问根结点 */PreorderTraverse(T-Lchild);PreorderTraverse(T-Rchild);说明：visit()函数是访问结点的数据域，其要求视具体问题而定。树采用二叉链表的存储结构，用指针变量T来指向。第28页/共87页遍历二叉树第29页/共87页遍历二叉树/fe-dcb*a+第30页/共87页遍历二叉树2 非递归算法非递归算法设T是指向二叉树根结点的指针变量，非递归算法是：若二叉树为空，则返回；否则，令p=T；访问p所指向的结点；q=p-Rchild，若q不为空，则q进栈；p=p-Lchild，若p不为空，转(1)，否则转(4)；退栈到p，转(1)，直到栈空为止。算法实现：第31页/共87页#define MAX_NODE 50void PreorderTraverse(BTNode *T)BTNode *StackMAX_NODE,*p=T,*q;int top=0;if (T=NULL)cout data);q=p-Rchild;if (q!=NULL)stack+top=q;p=p-Lchild;if(p=NULL&top0)p=stacktop;top-;while(p!=NULL);第32页/共87页中序遍历二叉树1 递归算法递归算法算法的递归定义是：算法的递归定义是：若二叉树为空，则遍历结束；否则若二叉树为空，则遍历结束；否则 中序遍历左子树中序遍历左子树(递归调用本算法递归调用本算法)；访问根结点；访问根结点；中序遍历右子树中序遍历右子树(递归调用本算法递归调用本算法)。第33页/共87页中序遍历二叉树中序遍历的递归算法void InorderTraverse(BTNode *T)if (T!=NULL)InorderTraverse(T-Lchild);visit(T-data);/*访问根结点 */InorderTraverse(T-Rchild);/*图6-8(a)的二叉树，输出的次序是：cbegdfa*/第34页/共87页中序遍历二叉树2 非递归算法非递归算法设T是指向二叉树根结点的指针变量，非递归算法是：若二叉树为空，则返回；否则，令p=T 若p不为空，p进栈，p=p-Lchild；否则(即p为空)，退栈到p，访问p所指向的结点；p=p-Rchild，转(1)；直到栈空为止。算法实现：第35页/共87页#define MAX_NODE 50void InorderTraverse(BTNode *T)BTNode *StackMAX_NODE,*p=T;int top=0,bool=1;if (T=NULL)printf(“Binary Tree is Empty!n”);else do while(p!=NULL)stack+top=p;p=p-Lchild;if (top=0)bool=0;else p=stacktop;-top;visit(p-data);p=p-Rchild;while(bool!=0);第36页/共87页后序遍历二叉树1 递归算法递归算法算法的递归定义是：算法的递归定义是：若二叉树为空，则遍历结束；否则若二叉树为空，则遍历结束；否则 后序遍历左子树后序遍历左子树(递归调用本算法递归调用本算法)；后序遍历右子树后序遍历右子树(递归调用本算法递归调用本算法)；访问根结点访问根结点。第37页/共87页后序遍历的递归算法void PostorderTraverse(BTNode *T)if (T!=NULL)PostorderTraverse(T-Lchild);PostorderTraverse(T-Rchild);visit(T-data);/*访问根结点 */*图6-8(a)的二叉树，输出的次序是：cgefdba */遍历二叉树的算法中基本操作是访问结点，因此，无论是哪种次序的遍历，对有n个结点的二叉树，其时间复杂度均为O(n)。第38页/共87页后序遍历二叉树 如图6-9所示的二叉树表示表达式：(a+b*(c-d)-e/f)按不同的次序遍历此二叉树，将访问的结点按先后次序排列起来的次序是：其先序序列为：-+a*b-cd/ef 其中序序列为：a+b*c-d-e/f 其后序序列为：abcd-*+ef/-/fe-dcb*a+图6-9 表达式(a+b*(c-d)-e/f)二叉树第39页/共87页后序遍历二叉树2 非递归算法非递归算法 在后序遍历中，根结点是最后被访问的。因此，在在后序遍历中，根结点是最后被访问的。因此，在遍历过程中，当搜索指针指向某一根结点时，不能立即遍历过程中，当搜索指针指向某一根结点时，不能立即访问，而要先遍历其左子树，此时根结点进栈。当其左访问，而要先遍历其左子树，此时根结点进栈。当其左子树遍历完后再搜索到该根结点时，还是不能访问，还子树遍历完后再搜索到该根结点时，还是不能访问，还需遍历其右子树。所以，此根结点还需再次进栈，当其需遍历其右子树。所以，此根结点还需再次进栈，当其右子树遍历完后再退栈到到该根结点时，才能被访问。右子树遍历完后再退栈到到该根结点时，才能被访问。因此，设立一个状态标志变量因此，设立一个状态标志变量tag：0：结点暂不能访问1：结点可以被访问tag=第40页/共87页 其次，设两个堆栈S1、S2，S1保存结点，S2保存结点的状态标志变量tag。S1和S2共用一个栈顶指针。设T是指向根结点的指针变量，非递归算法是：若二叉树为空，则返回；否则，令p=T；第一次经过根结点p，不访问：p进栈S1，tag 赋值0，进栈S2，p=p-Lchild。若p不为空，转(1)，否则，取状态标志值tag：若tag=0：对栈S1，不访问，不出栈；修改S2栈顶元素值(tag赋值1)，取S1栈顶元素的右子树，即p=S1top-Rchild，转(1)；若tag=1：S1退栈，访问该结点；直到栈空为止。第41页/共87页算法实现：#define MAX_NODE 50void PostorderTraverse(BTNode *T)BTNode *S1MAX_NODE,*p=T;int S2MAX_NODE,top=0,bool=1;if (T=NULL)coutLchild;if (top=0)bool=0;第42页/共87页 else if (S2top=0)p=S1top-Rchild;S2top=1;else p=S1top;top-;visit(p-data);p=NULL;/*使循环继续进行而不至于死循环使循环继续进行而不至于死循环*/while(bool!=0);第43页/共87页3.4 层次遍历二叉树层次遍历二叉树，是从根结点开始遍历，按层次次序“自上而下，从左至右”访问树中的各结点。为保证是按层次遍历，必须设置一个队列，初始化时为空。设T是指向根结点的指针变量，层次遍历非递归算法是：若二叉树为空，则返回；否则，令p=T，p入队；队首元素出队到p；访问p所指向的结点；将p所指向的结点的左、右子结点依次入队。直到队空为止。第44页/共87页#define MAX_NODE 50void LevelorderTraverse(BTNode *T)BTNode *QueueMAX_NODE,*p=T;int front=0,rear=0;if (p!=NULL)Queue+rear=p;/*根结点入队根结点入队 */while(frontdata);if(p-Lchild!=NULL)Queue+rear=p-Lch;/*左结点入队左结点入队 */if(p-Rchild!=NULL)Queue+rear=p-Rch;/*右结点入队右结点入队 */第45页/共87页3.5 二叉树遍历算法的应用“遍历”是二叉树最重要的基本操作，是各种其它操作的基础，二叉树的许多其它操作都可以通过遍历来实现。如建立二叉树的存储结构、求二叉树的结点数、求二叉树的深度等。第46页/共87页3.5 二叉树遍历算法的应用1 二叉树的二叉链表创建 按满二叉树方式建立(补充)在此补充按满二叉树的方式对结点进行编号建立链式二叉树。对每个结点，输入i、ch。i：结点编号，按从小到大的顺序输入ch：结点内容，假设是字符 在建立过程中借助一个一维数组Sn，编号为i的结点保存在Si中。算法实现：第47页/共87页#define MAX_NODE 50struct BTNode char data;struct BTNode*Lchild,*Rchild;BTNode *Create_BTree(void)/*建立链式二叉树，返回指向根结点的指针变量建立链式二叉树，返回指向根结点的指针变量 */BTNode *T,*p,*sMAX_NODE;char ch;int i,j;while(1)cini;if (i=0)break;/*以编号以编号0作为输入结束作为输入结束 */else ch=getchar();第48页/共87页 p=new BTNode;pdata=ch;pLchild=pRchild=NULL;si=p;if(i=1)T=p;else j=i/2;/*j是是i的双亲结点编号的双亲结点编号 */if(i%2=0)sj-Lchild=p;else sj-Rchild=p;return(T);第49页/共87页3.5 二叉树遍历算法的应用 按先序遍历方式建立对一棵二叉树进行“扩充”，就可以得到有该二叉树所扩充的二叉树。有两棵二叉树T1及其扩充的二叉树T2如图6-10所示。图6-10 二叉树T1及其扩充二叉树T2ABCDEFG(a)二叉树T1(b)T1的扩充二叉树T2ABCDEFG?第50页/共87页3.5 二叉树遍历算法的应用二叉树的扩充方法是：在二叉树中结点的每一个空链域处增加一个扩充的结点(总是叶子结点，用方框“”表示)。对于二叉树的结点值：是char类型：扩充结点值为“？”；是int类型：扩充结点值为0或-1；下面的算法是二叉树的前序创建的递归算法，读入一棵二叉树对应的扩充二叉树的前序遍历的结点值序列。每读入一个结点值就进行分析：若是扩充结点值：令根指针为NULL；若是(正常)结点值：动态地为根指针分配一个结点，将该值赋给根结点，然后递归地创建根的左子树和右子树。第51页/共87页#define NULLKY?#define MAX_NODE 50struct BTNode char data;struct BTNode*Lchild,*Rchild;BTNode *Preorder_Create_BTree(BTNode *T)/*建立链式二叉树，返回指向根结点的指针变量建立链式二叉树，返回指向根结点的指针变量 */char ch;ch=getchar();getchar();if (ch=NULLKY)T=NULL;return(T);第52页/共87页3.5 二叉树遍历算法的应用else T=new BTNode;Tdata=ch;Preorder_Create_BTree(T-Lchild);Preorder_Create_BTree(T-Rchild);return(T);当希望创建图当希望创建图6-10(a)所示的二叉树时，输入的字符所示的二叉树时，输入的字符序列应当是：序列应当是：ABD?E?G?CF?第53页/共87页3.5 二叉树遍历算法的应用2 求二叉树的叶子结点数求二叉树的叶子结点数 可以直接利用先序遍历二叉树算法求二叉树的叶子结点可以直接利用先序遍历二叉树算法求二叉树的叶子结点数。只要将先序遍历二叉树算法中数。只要将先序遍历二叉树算法中vist()函数简单地进函数简单地进行修改就可以。行修改就可以。(递归与非递归递归与非递归)#define MAX_NODE 50int search_leaves(BTNode *T)BTNode *StackMAX_NODE,*p=T;int top=0,num=0;if (T!=NULL)第54页/共87页 stack+top=p;while(top0)p=stacktop-;if(p-Lchild=NULL&p-Rchild=NULL)num+;if (p-Rchild!=NULL)stack+top=p-Rchild;if (p-Lchild!=NULL)stack+top=p-Lchild;return(num);第55页/共87页3.5 二叉树遍历算法的应用3求二叉树的深度int Depth(BTNode*T)if(T=NULL)depthval=0;else depthLeft=Depth(T-Lchild);depthRight=Depth(T-Rchild);depthval=1+max(depthLeft,depthRight);return depthval;第56页/共87页3.5 二叉树遍历算法的应用3 求二叉树的深度求二叉树的深度 利用层次遍历算法可以直接求得二叉树的深度。利用层次遍历算法可以直接求得二叉树的深度。#define MAX_NODE 50int search_depth(BTNode *T)BTNode *StackMAX_NODE,*p=T;int front=0,rear=0,depth=0,level;/*level总是指向访问层的最后一个结点在队列的位置总是指向访问层的最后一个结点在队列的位置 */if (T!=NULL)Queue+rear=p;/*根结点入队根结点入队 */level=rear;/*根是第根是第1层的最后一个节点层的最后一个节点 */第57页/共87页while(frontLchild!=NULL)Queue+rear=p-Lchild;/*左结点入队左结点入队 */if(p-Rchild!=NULL)Queue+rear=p-Rchild;/*右结点入队右结点入队 */if(front=level)/*正访问的是当前层的最后一个结点正访问的是当前层的最后一个结点 */depth+;level=rear;第58页/共87页3.6哈夫曼树的构造哈夫曼树（哈夫曼树（Huffman）树是一类带权路径长度最短的树）树是一类带权路径长度最短的树一、一、Huffman树（最优二叉树）树（最优二叉树）1、概念概念 两结点间的路径：从一个结点到另一个结点之间的分支两结点间的路径：从一个结点到另一个结点之间的分支 路径长度：路径上的分支数目路径长度：路径上的分支数目 树的路径长度：从根到每一结点的路径长度之和树的路径长度：从根到每一结点的路径长度之和2763415例例-为结点为结点1到到5之间的路径，其路之间的路径，其路径长度为径长度为2，树的路径长度树的路径长度=l12+l13+l14+l15+l16+l17 =1+1+2+2+2+2=10第59页/共87页3.6哈夫曼树的构造 完全二叉树是路径长度最短的二叉树。完全二叉树是路径长度最短的二叉树。考虑带权时：设树中有考虑带权时：设树中有m个叶结点，每个叶结个叶结点，每个叶结点带一个权值点带一个权值W且根到叶结点且根到叶结点i的路径长度为的路径长度为 Li(=1，2，m），则），则树的带权路径长度树的带权路径长度为树中为树中所有叶结点的权值与路径长度的乘积的总和。所有叶结点的权值与路径长度的乘积的总和。m即：即：kk k=1第60页/共87页3.6哈夫曼树的构造 例：例：使使WPL最小的二叉树最小的二叉树称为最优二叉树称为最优二叉树 (Huffman 树树)完全二叉树完全二叉树dcab7 5 2 4 cdba2475WPLa=2*7+2*5+2*2+2*4 WPLb=7*3+5*3+2*1+4*2 =36 =46第61页/共87页3.6哈夫曼树的构造Huffman 树树WPLc=7*1+5*2+2*3+4*3 =35bdca7524（1）完全二叉树并不一定是Huffman树；（2）HT是权值越大的越靠近根结点；（3）HT不唯一，但WPL一定相等。第62页/共87页3.6哈夫曼树的构造2构造构造 Huffman树算法树算法(1)以权值分别为以权值分别为W1,W2的个结点，构成的个结点，构成n棵二棵二叉树叉树T1,T2,Tn并组成森林并组成森林F=T1,T2,Tn,其中每棵其中每棵二叉树二叉树 Ti仅有一个权值为仅有一个权值为 Wi的根结点；的根结点；(2)在在F中选取两棵根结点权值最小的树作为左右子树构造一中选取两棵根结点权值最小的树作为左右子树构造一棵新二叉树，并且置新二叉树根结点权值为左右子树上根结棵新二叉树，并且置新二叉树根结点权值为左右子树上根结点的权值之和（根结点的权值点的权值之和（根结点的权值=左右孩子权值之和，叶结点的左右孩子权值之和，叶结点的权值权值=Wi）；）；(3)从从F中删除这两棵二叉树，同时将新二叉树加入到中删除这两棵二叉树，同时将新二叉树加入到F中中;(4)重复重复(2)()直到直到F中只含一棵二叉树为止，这棵二叉树中只含一棵二叉树为止，这棵二叉树就是就是Huffman 树。树。第63页/共87页3.6哈夫曼树的构造abcd7 5 2 4例例:F=abF=cd 7 5 6 2 4F=abcd116425F=abcd1164257187第64页/共87页3.6哈夫曼树的构造HT不唯一性不唯一性,可能出现在可能出现在:（1）构造新树时，左、右孩子未作规定。）构造新树时，左、右孩子未作规定。（2）当有多个权值相同的树，可作为候选树）当有多个权值相同的树，可作为候选树时，选择谁未作规定。时，选择谁未作规定。第65页/共87页3.6哈夫曼树的构造1 Huffman编码编码 在电报收发等数据通讯中在电报收发等数据通讯中，常需要将传送的文字转常需要将传送的文字转换成由二进制字符换成由二进制字符0、1组成的字符串来传输组成的字符串来传输。为了使收为了使收发的速度提高发的速度提高，就要求电文就要求电文编码要尽可能地短编码要尽可能地短。此外，。此外，要设计要设计长短不等长短不等的编码，还必须保证的编码，还必须保证任意字符的编码都任意字符的编码都不是另一个字符编码的前缀不是另一个字符编码的前缀，这种编码称为，这种编码称为前缀编码前缀编码。Huffman树可以用来构造编码长度不等且译码不产树可以用来构造编码长度不等且译码不产生二义性的编码生二义性的编码。设电文中的字符集设电文中的字符集C=c1,c2,ci,cn，各个字符，各个字符出现的次数或频度集出现的次数或频度集W=w1,w2,wi,wn。第66页/共87页3.6哈夫曼树的构造Huffman编码方法编码方法 以以字符集字符集C作为叶子结点作为叶子结点，次数或频度集，次数或频度集W作为结作为结点的权值点的权值来构造来构造 Huffman树树。规定。规定Huffman树中左分树中左分支代表支代表“0”，右分支代表，右分支代表“1”。从根结点到每个叶子结点所经历的路径分支上的从根结点到每个叶子结点所经历的路径分支上的“0”或或“1”所组成的字符串所组成的字符串，为该结点所对应的编码为该结点所对应的编码，称之为称之为Huffman编码编码。由于每个字符都是叶子结点，不可能出现在根结点由于每个字符都是叶子结点，不可能出现在根结点到其它字符结点的路径上，所以一个字符的到其它字符结点的路径上，所以一个字符的Huffman编编码不可能是另一个字符的码不可能是另一个字符的Huffman编码的前缀编码的前缀。第67页/共87页 若字符集若字符集C=a,b,c,d,e,f所对应的权值集合为所对应的权值集合为W=8,3,4,6,5,5，如图，如图6-25所示所示，则字符，则字符a,b,c,d,e,f所对应的所对应的Huffman编码分别是编码分别是：10，010，011，00，110，111。2 Huffman编码算法实现编码算法实现(1)数据结构设计数据结构设计 Huffman树中没有度为树中没有度为1的结点棵有的结点棵有n个叶子结点个叶子结点的的Huffman树共有树共有2n-1个结点个结点，则可存储在大小为，则可存储在大小为2n-1的一维数组中。实现编码的结点结构如图的一维数组中。实现编码的结点结构如图6-26所示所示。原因：原因：求编码需从叶子结点出发走一条从叶子到根的路求编码需从叶子结点出发走一条从叶子到根的路径；径；第68页/共87页 译码需从根结点出发走一条到叶子结点的路径。结点类型定义：#define MAX_NODE 200 /*Max_Node2n-1 */typedef struct unsigned int Weight;/*权值域 */unsinged int Parent,Lchild,Rchild;HTNode;Weight Parent Lchild RchildWeight：权值域；Parent：双亲结点下标Lchild,Rchild：分别标识左、右子树的下标图6-26 Huffman编码的结点结构第69页/共87页(2)Huffman树的生成树的生成算法实现算法实现void Create_Huffman(unsigned n,HTNode HT,unsigned m)/*创建一棵叶子结点数为创建一棵叶子结点数为n的的Huffman树树 */unsigned int w;int k,j;for(k=1;km;k+)if (k=n)printf(“n Please Input Weight:w=?”);scanf(“%d”,&w);HTk.weight=w;/*输入时输入时，所有叶子结点都有权值所有叶子结点都有权值 */else HTk.weight=0;/*非叶子结点没有权值非叶子结点没有权值*/第70页/共87页HTk.Parent=HTk.Lchild=HTk.Rchild=0;/*初始化向量初始化向量HT*/for(k=n+1;km;k+)unsigned w1=32767,w2=w1;/*w1,w2分别保存权值最小的两个权值分别保存权值最小的两个权值 */int p1=0,p2=0;/*p1,p2保存两个最小权值的下标保存两个最小权值的下标 */for(j=1;j=k-1;j+)if(HTk.Parent=0)/*尚未合并尚未合并*/if(HTj.Weightw1)w2=w1;p2=p1;w1=HTj.Weight;p1=j;第71页/共87页 else if(HTj.Weightw2)w2=HTj.Weight;p2=j;/*找到权值最小的两个值及其下标找到权值最小的两个值及其下标 */HTk.Lchild=p1;HTk.Rchild=p2;HTk.weight=w1+w2;HTp1.Pare