第5章 树和二叉树PPT演示课件

第5章树和二叉树,5.1树5.2二叉树5.3二叉树的遍历5.4线索二叉树5.5树、森林和二叉树的关系5.6哈夫曼树及其应用5.7实训例题,5.1树5.1.1树的基本概念,树型结构是一种非线性结构，它的数据元素之间呈现分支、分层的特点。1树的定义树(Tree)是由n(n0)个结点构成的有限集合T，当n=0时T称为空树；否则，在任一非空树T中：(1)有且仅有一个特定的结点，它没有前驱结点，称其为根(Root)结点；(2)剩下的结点可分为m(m0)个互不相交的子集T1，T2，Tm，其中每个子集本身又是一棵树，并称其为根的子树(Subtree)。注意：树的定义具有递归性，即“树中还有树”。树的递归定义揭示出了树的固有特性,注意：由于子树的互不相交性，树中每个结点只属于一棵树（子树），且树中的每一个结点都是该树中某一棵子树的根。,2树的表示方法（1）直观（树形、倒置树）表示法。（2）嵌套集合（文氏图）表示法。（3）凹入表（缩进）表示法（类似于书的目录）。（4）广义表（嵌套括号）表示法。,3树的常用术语结点包含一个数据元素和若干指向其子树的分支度结点拥有的子树个数树的度该树中结点的最大度数叶子度为零的结点分支结点（非终端结点）度不为零的结点孩子和双亲结点的子树的根称为该结点的孩子，相应地，该结点称为孩子的双亲兄弟同一个双亲的孩子祖先和子孙从根到该结点所经分支上的所有结点。相应地，以某一结点为根的子树中的任一结点称为该结点的子孙。结点的层次结点的层次从根开始定义，根结点的层次为1，其孩子结点的层次为2，堂兄弟双亲在同一层的结点树的深度树中结点的最大层次有序树和无序树如果将树中每个结点的各子树看成是从左到右有次序的(即位置不能互换)，则称该树为有序树；否则称为无序树。森林m(m0)棵互不相交的树的有限集合,5.1.2树的基本操作,(1)初始化InitTree(T)(2)判断树空TreeEmpty(T)(3)求根结点Root(T)(4)求双亲结点Parent(T,x)(5)求孩子结点Child(T,x,i)(6)插入子树InsertChild(T,x,i,y)(7)删除子树DeleteChild(T,x,i)(8)遍历树Traverse(T),5.1.3树的存储结构,1.双亲（数组）表示法树的一种顺序存储结构，将树中的结点按照从上到下，从左到右的顺序存放在一个一维数组中，每个数组元素中存放一个结点的信息，包括该结点本身的信息和该结点的双亲的位置信息即双亲的下标值。类型描述：#defineMaxSize50typedefstruct/*结点的类型*/ElementTypedata;intparent;/*结点双亲的下标*/SeqTrNode;typedefstruct/*树的类型*/SeqTrNodetreeMaxSize;/*存放结点的数组*/intnodenum;/*树中实际所含结点的个数*/SeqTree;SeqTreeT;特点：找双亲容易，找孩子难,2.孩子表示法孩子表示法是树的一种链式存储结构。(1)指针方式的孩子表示法（多重链表）：每个结点有多个指针域，分别指向其子树的根结点同构：结点的指针个数相等，为树的度D结点不同构：结点指针个数不等，为该结点的度d(2)孩子链表：每个结点的孩子结点用单链表存储，再用含n个元素的结构数组指向每个孩子链表。,类型描述：#defineMaxSize50typedefstructChNode/*孩子链表结点的类型*/intchild;structChNode*next;ChildNode,*ChPoint;typedefstruct/*顺序表中每个结点的类型*/ElementTypedata;ChPointFirstChild;/*指向第一个孩子结点的指针*/Node;typedefstruct/*树的类型*/NodeTreeListMaxSize;intnodenumber；/*树中实际所含结点的个数*/ChList;,特点：找孩子容易，找双亲及兄弟难,3.孩子兄弟表示法（二叉树表示法）用二叉链表作树的存储结构，链表中每个结点除了包含该结点本身的值域外，还要设置两个指针域分别指向其第一个孩子结点和下一个兄弟结点类型描述：typedefstructTrNode/*树中每个结点的类型*/ElementTypedata;structTrNode*FirstChild,*RightSibling;TreeNode,*ChSiTree;ChSiTreeroot;/*指向树根结点的指针*特点：操作容易破坏了树的层次,5.2二叉树5.2.1二叉树的定义及基本操作,1二叉树的定义定义：二叉树(BinaryTree)是n(n0)个结点的有限集合BT，它或者是空集，或者由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树组成。特点：每个结点至多有二棵子树(即不存在度大于2的结点)；二叉树的子树有左、右之分，且其次序不能任意颠倒。基本形态：,注意：二叉树不是树的特例,2二叉树的基本操作(1)初始化InitTree(BT)(2)判断二叉树是否为空TreeEmpty(BT)(3)求根结点Root(BT)(4)求双亲结点Parent(BT,x)(5)求二叉树的高度Depth(BT)(6)求结点的左孩子LChild(BT,x)(7)求结点的右孩子RChild(BT,x)(8)遍历二叉树Traverse(BT),5.2.2二叉树的性质,性质1在二叉树的第i层上至多有2i-1个结点(i1)。用归纳法即可证明此性质。当i=1时，是二叉树的第一层，只有一个根结点，而2i-1=20=1，故命题成立。假设对所有的j(1j1，则其双亲是i/2(2)如果2in，则结点i无左孩子；如果2in，则其左孩子是2i(3)如果2i+1n，则结点i无右孩子；如果2i+1n，则其右孩子是2i+1,5.2.3二叉树的存储结构,1.顺序存储实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素,类型描述#defineMaxSize30typedefstructSeqBTcharbtreeMaxSize;intlength;/*二叉树中所含结点的实际个数*/SeqBT;特点：结点间关系蕴含在其存储位置中浪费空间，适于存满二叉树和完全二叉树,2.链式存储二叉链表：一个结点应至少含三个域：一个数据域（data），两个指针域（指向左孩子的指针域lchild和指向右孩子的指针域rchild），类型描述：typedefstructBNodeElemTypedata;structBNode*lchild;structBNode*rchild;BTNode;typedefBTNode*BinTree;,root为头指针。二叉链表由头指针root惟一确定，若二叉树为空，则root=NULL。其类型说明为BinTreeroot;在n个结点的二叉链表中，有n+1个空指针域在二叉链表中，要访问一个结点的孩子结点很容易，但要访问一个结点的双亲结点不容易,3.三叉链表三叉链表就是在二叉链表的基础上再增加一个指向结点双亲结点的指针。类型描述：typedefstructBPNodeeleptypedata;structBPNode*lchild;structBPNode*rchild;structBPNode*parent;BTPNode,*BTPTree;,5.3二叉树的遍历5.3.1二叉树的遍历,1.定义：二叉树的遍历就是按一定的规律访问二叉树的结点，使得每个结点被访问一次，且仅被访问一次。遍历问题对于线性结构来说很容易实现，但对于二叉树这种非线性结构来说，就不那么容易了，因为从二叉树的任意结点出发，既可以向左走，也可以向右走，所以，必须找到一种规律，按同样的方法处理每个结点及其子树来实现遍历。二叉树的遍历的常用方法有三种：DLR、LDR和LRD，分别称作先根次序(前序，先序)遍历、中根次序(中序)遍历和后根次序(后序)遍历。,（1）先序遍历若二叉树为空，则空操作；否则依次执行以下操作；访问根结点；先序遍历根结点的左子树；先序遍历根结点的右子树；(2)中序遍历若二叉树为空，则空操作；否则依次执行以下操作：中序遍历根结点的左子树；访问根结点；中序遍历根结点的右子树；(3)后序遍历若二叉树为空，则空操作；否则依次执行以下操作：后序遍历根结点的左子树；后序遍历根结点右子树；访问根结点；,先序遍历：,中序遍历：,后序遍历：,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,2二叉树遍历算法的实现（1）先序遍历算法描述如下：voidPreOrder(BinTreeroot)if(root!=NULL)printf(%c，root-data);/*访问根结点*/PreOrder(root-lchild);/*先序遍历左子树*PreOrder(root-rchild);/*先序遍历右子树*/*PreOrder*/,（2）中序遍历算法描述如下：voidInOrder(BinTreeroot)if(root!=NULL)InOrder(root-lchild);/*中序遍历左子树*printf(%c，root-data);/*访问根结点*/InOrder(root-rchild);/*中序遍历右子树*/*InOrder*/,(3)后序遍历算法描述如下：voidPostOrder(BinTreeroot)if(root!=NULL)PostOrder(root-lchild);/*后序遍历左子树*PostOrder(root-rchild);/*后序遍历右子树*printf(%c，root-data);/*访问根结点/*PostOrder*/,三种遍历算法的不同之处仅在于访问根结点和遍历左右子树的先后次序，若在算法中暂时抹去和递归无关的printf语句，则三种遍历算法基本上相同，这说明这三种遍历算法的搜索路线相同，从递归执行过程的角度来看三种遍历算法也是完全相同的，图5.18显示了图5.15(a)所示的二叉树的三种遍历的搜索路线,3二叉树遍历算法的非递归实现二叉树遍历的递归实现思路自然、简单，易于理解，但执行效率较低。为了提高程序的执行效率，可以显式的设置栈，写出相应的非递归遍历算法。非递归的遍历算法可以根据递归算法的执行过程写出。以中序遍历为例进行说明。为便于叙述，给中序遍历算法中的语句加上行号，如下所示：voidInOrder(BinTreeroot)1if(root!=NULL)2InOrder(root-lchild);/*中序遍历左子树*3printf(%c，root-data);/*访问根结点*/4InOrder(root-rchild);/*中次序遍历右子树*5主调函数为：M:InOrder(bt);M+1:,对于图5.19(a)所示的二叉树，中序遍历递归算法的执行过程如图5.19(b)所示。P113,图中，指针值用指针指向的结点的值代替，栈中的数据，如A,3表示是两个数据，A先进栈，3再进栈，即在栈中占两个空间。退栈时亦然。,根据上述执行过程，可以写出一个初步的非递归算法。voidInOrder(BinTreeroot)inttop=-1;L1:if(root!=NULL)/*遍历左子树*/top=top+2;if(topmax)return;/*栈满溢出*/stop-1=root;/*本层参数进栈*/stop=L2;/*返回地址进栈，L2对应上述执行过程中的行号3*/root=root-lchild;/*给下层参数赋植*/gotoL1;/*进入下一层*/L2:printf(“%c”,root-data);/*访问根结点*/,top=top+2;/*遍历右子树*/if(topmax)return;/*栈满溢出*/stop-1=root;stop=L3;/*L3对应上述执行过程中的行号5*/root=root-rchild;gotoL1;L3:if(top!=-1)x=stop;/*取出返回地址*/root=stop-1;/*取出本层参数*/top=top-2;gotox;/*转向相应语句，或者L2或者L3*/,简化的非递归算法如下：voidInOrder(BinTreeroot)inttop=-1;L1:if(root!=NULL)/*遍历左子树*/top=top+1;if(topmax)return;/*栈满溢出*/stop=root;/*本层参数进栈*/root=root-lchild;/*给下层参数赋植*/gotoL1;/*进入下一层*/L2:printf(“%c”,root-data);/*访问根结点*/root=root-rchild;gotoL1;,if(top!=-1)root=stop取出本层参数*/top=top-1;gotoL2;/*转向输出*/,整理后的算法的流程图如图5.20所示。,算法中用到的栈为顺序栈，其类型描述为：#defineMaxSize栈可能达到的最大元素个数/*可根据实际情况设定*/typedefstructBinTreeelemMaxSize;inttop;/*栈顶位置*/SeqStack;二叉树中序遍历的非递归算法描述如下：voidInOrderZ(BinTreeroot)/*中序遍历非递归算法*/SeqStacks;/*s为顺序栈*/s.top=-1;,dowhile(root!=NULL)/*当二叉树非空时*/s.top+;if(s.top=MaxSize-1)printf(“stackfull”);return;elses.elems.top=root;/*根结点root进栈*/root=root-lchild;/*沿左孩子链依次扫描*/*if*/*while*/,if(s.top!=-1)/*栈非空时则退栈*/root=s.elems.top;s.top-;printf(“%c”,root-data);/*访问根结点T*/root=root-rchild;/*指针指向其右子树*/*if*/while(s.top!=-1)|(root!=NULL);/*栈为空且搜索指针为空时，遍历结束*/*InOrderZ*/,算法分析：二叉树遍历算法中的基本操作是访问根结点，不论按哪种次序遍历，都要访问所有的结点，对含n个结点的二叉树，其时间复杂度均为O（n）。所需辅助空间为遍历过程中所需的栈空间，最多等于二叉树的深度k乘以每个结点所需空间数，最坏情况下树的深度为结点的个数n，因此，其空间复杂度也为O(n)。,4.遍历序列与二叉树的结构对一棵二叉树进行遍历得到的遍历序列（先序或中序或后序）是惟一的。但仅由一个二叉树的遍历序列（先序或中序或后序）不能决定一棵二叉树,例如图5.21(a)和5.21(b)所示的两棵不同的二叉树，它们的先序遍历序列是相同的。,可以证明，如果同时知道一棵二叉树的先序序列和中序序列，或者同时知道一棵二叉树的中序序列和后序序列，就能惟一地确定这棵二叉树。例如知道一棵二叉树的先序序列和中序序列，如何构造二叉树呢？由定义，二叉树的先序遍历是先访问根结点D，然后遍历根的左子树L，最后遍历根的右子树R。因此在先序序列中的第一个结点必是根结点D；另一方面，中序遍历是先遍历根的左子树L，然后访问根结点D，最后遍历根的右子树R，于是根结点D把中序序列分成两部分：在D之前的是由左子树中的结点构成的中序序列，在D之后的是由右子树中的结点构成的中序序列。反过来，根据左子树的中序序列的结点个数，又可将先序序列除根以外的结点分成左子树的先序序列和右子树的先序序列。依次类推，即可递归得到整棵二叉树。,例如已知一棵二叉树的先序序列为ABDGCEF，中序序列为DGBAECF，构造其对应的二叉树。首先由先序序列得知二叉树的根为A，则其左子树的中序序列必为DGB，右子树的中序序列为ECF。反过来得知其左子树的先序序列必为BDG，右子树的先序序列为CEF。类似地分解下去，过程如图5.22所示，最终就可得到整棵二叉树，如图5.23所示。,5.3.2典型题例,【例1】建立二叉树的二叉链表存储结构构造二叉链表的方法很多，这里介绍一个基于先序遍历的构造算法。假设二叉树中结点的元素均为单个字符。算法的输入是二叉树的先序序列，但必须在其中加入虚结点（以“#”表示）以示空指针的位置，这样的先序序列称为扩展的先序序列。如图5.24所示的二叉树，输入的扩展先序遍历的字符序列为：ABD#E#C#F#。首先输入一个根结点，若输入的是“#”字符，表示该二叉树为空树，即root=NULL；否则向系统申请结点空间，由root指向该结点，把输入的字符赋给root-data，之后，依次递归地建立它的左子树root-lchild和右子树root-rchild。,算法描述如下：voidCreateBinTree(BinTree*root)/*建立二叉链表。root是指向根结点的指针。输入序列是扩展的先序序列*/charch;if(ch=getchar()=#)*root=NULL;/*建立空二叉树*/else*root=(BTNode*)malloc(sizeof(BTNode);/*生成结点*/(*root)-data=ch;CreateBinTree(/*递归构造右子树*/*else*/*CreatBinTree*/,【例2】求二叉树的叶子结点的个数。可以用两种方法求解这个问题。方法一：设置一个初值为0的变量leaf进行计数，在遍历的过程中每访问一个结点就对该结点进行判断，若是叶子，将leaf加1。当遍历完整个二叉树后，leaf的值就是叶子结点的个数。可以采用任何遍历算法，在此采用先序遍历算法实现。具体算法描述如下：intCountLeaf(BinTreeroot)/*求二叉树中的叶子结点个数*/intstaticleaf=0;/*静态变量保留每次递归调用后的值*/if(root!=NULL)CountLeaf(root-lchild);/*中序遍历左子树*if(root-lchild=NULL)/*CountLeaf*/,方法二：当二叉树为空时，叶子结点的个数为0；当二叉树只有一个结点时，叶子结点的个数为1；否则，叶子结点的个数等于左、右子树叶子结点个数之和。因此，可用下面的递归公式计算二叉树root的叶子结点个数BtLeaf(root)：据此，算法描述如下：intBtLeaf(BinTreeroot)if(root=NULL)return(0);if(root-lchild=NULL/*BtLeaf*/,【例3】求二叉树的深度。和例2类似，也可以用两种方法求解这个问题。方法一：以先序遍历二叉树的算法为基础，二叉树的深度为二叉树中结点层次的最大值。根结点的层次为1，其余结点的层数等于其双亲结点的层数加1。因此，可以通过遍历计算二叉树中的每个结点的层次，其中最大值即为二叉树的深度。tdeep为全局变量，调用前置初值零，在调用函数TreeDeep之后，tdeep的值就是二叉树的深度。算法描述如下：inttdeep=0;voidTreeDeep(BinTreeroot,intnodeep)/*nodeep为root所指结点所在的层次，初值为1*/if(root!=NULL)if(tdeeplchild,nodeep+1);/*先序遍历左子树*TreeDeep(root-rchild,nodeep+1);/*先序遍历右子树*/*TreeDeep*/,方法二：当二叉树为空时，其深度为0；否则，其深度为其左右子树深度的最大值加1。因此，可用下面的递归公式计算二叉树root的深度：算法描述如下：intBtDepth(BinTreeroot)intdep,ldep,rdep;if(root=NULL)dep=0;/*二叉树为空，深度为0*/elseldep=BtDepth(root-lchild);/*求左子树的深度*/rdep=BtDepth(root-rchild);/*求右子树的深度*/if(ldeprdep)dep=ldep+1;/*求二叉树的深度*/elsedep=rdep+1;return(dep);/*BtDepth*/,【例4】在二叉树中查找值为x的结点，找到，返回指向该结点的指针，否则返回空指针。首先将根结点的值与x比较，若相等，则返回指向根结点的指针；否则，在根的左子树中继续同样的查找，若未找到，则在右子树中继续查找，找到，返回指向该结点的指针，否则说明在二叉树中不存在值为x的结点，返回空指针。算法描述如下：BinTreeLocateTree(BinTreeroot,elemtypex)BinTreep;if(root=NULL)return(NULL);elseif(root-data=x)return(root);/*值为x的结点是根结点*/elsep=LocateTree(root-lchild,x);/*在左子树中查找x*/if(p)return(p);/*在左子树中查找成功*/elsereturn(LocateTree(root-rchild,x);/*在右子树中查找x*/*LocateTree*/,5.4线索二叉树,1定义在二叉链表中，很容易找到结点的孩子，但要得到某一结点在某种遍历次序下的前驱和后继信息就必须进行遍历，在遍历的动态过程中得到这些信息。如果在操作中要频繁访问结点的前驱和后继，可以把在某种遍历过程中得到的前驱和后继的信息存储在结点中，即在二叉链表的结点结构中再增加两个域：前驱域、后继域。这样二叉树的存储效率就降低了。可以利用二叉链表中的n+1个空链域来存放前驱和后继的信息。规定空的lchild域存放结点的前驱信息即指向结点的前驱的指针，空的rchild域存放结点的后继信息即指向结点的后继的指针，这种指向结点的前驱或后继的指针就称为线索。为了区分指针域中的指针是指向孩子结点还是指向前驱或后继结点，在每个结点中增加两个标志域：左标志域ltag和右标志域rtag，它们的含义是：0lchild域指示结点的左孩子ltag=1lchild域指示结点的前驱0rchild域指示结点的右孩子rtag=1rchild域指示结点的后驱此时的结点结构如图5.25所示，共有5个域。,0lchild域指示结点的左孩子ltag=1lchild域指示结点的前驱0rchild域指示结点的右孩子rtag=1rchild域指示结点的后驱此时的结点结构如图所示，共有5个域。类型描述：typedefstructThNodeElementTypedata;structThNode*lchild,*rchild;intltag,rtag;ThBinNode;typedefThBinNode*ThBinTree;,加上线索的二叉树称为线索二叉树（ThreadedBinaryTree）。把一棵二叉树变为线索二叉树的过程称为线索化。如果线索是在先序遍历过程中得到的，就称为先序线索二叉树。如果线索是在中序遍历过程中得到的，就称为中序线索二叉树。如果线索是在后序遍历过程中得到的，就称为后序线索二叉树。先序（中序、后序）线索二叉树相应的链表就称为先序（中序、后序）线索二叉链表。,2建立线索二叉树由于线索化的实质是将二叉链表中的空指针改为指向结点前驱或后继的线索，而一个结点的前驱或后继结点的信息只有在遍历时才能得到，因此线索化的过程即为在遍历过程中修改空指针的过程。为此附设一个指针pre始终指向刚刚访问过的结点，而指针p指向当前正在访问的结点。显然结点*pre是结点*p的前趋，而*p是*pre的后继。下面给出将二叉树按中序进行线索化的算法。该算法与中序遍历算法相似，区别仅在于访问根结点时所做的处理不同。,在线索化算法中，访问当前根结点*p所做的处理是：（1）若结点*p的左孩子域为空，则将其左标志置为1，且令p-lchild为指向其中序前驱结点*pre的左线索即其左孩子域指向*pre；（2）若结点*p有中序前趋结点*pre（即pre！=NULL）且其右孩子域为空，则将其右标志置为1，且令pre-rchild为指向其后继结点*p的右线索即其右孩子域指向*p；（3）将pre指向刚刚访问过的结点*p（即pre=p）。这样，在下次访问一个新结点*p时，*pre为其前驱结点。显然，pre的初值应为NULL。,二叉树中序线索化的算法描述如下：voidInThread(ThBinTreep)/*将二叉树p中序线索化，线索标志初值为0*/if(p!=NULL)InThread(p-lchild);/*左子树线索化*/if(p-lchild=NULL)p-ltag=1;/*建立左线索标志*/p-lchild=pre;/*置前驱线索*/elsep-ltag=0;if(pre!=NULL/*当前访问结点为下一个访问结点的前驱*/InThread(p-rchild)/*右子树线索化*/*InThread*/,3查找某一所结点在指定遍历次序下的前驱和后继结点在中序线索二叉树中，查找结点*p的中序后继结点分两种情况：（1）若p-rtag=1(此时*p的右子树为空)，则p-rchild为右线索，直接指向*p的中序后继结点；（2）若p-rtag=0，说明*p的右子树非空，则*p的中序后继必是其右子树中第一个中序遍历到的结点，也就是从*p的右孩子开始，沿左指针链往下查找，直到找到一个没有左孩子的结点为止。该结点是*p的右子树中“最左下的”结点，它就是*p的中序后继结点。,如图5.27所示，*p的中序后继结点是Rk（k1）。RK一定没有左孩子，RK可能有右孩子也可能没有右孩子，若Rk无右孩子，则它必定是叶子结点。若k=1，则表示*p的右孩子R1是*p的中序后继,算法描述如下：ThBinTreeInorderNext(ThBinTreep)/*在中序线索树中找结点*p的中序后继，函数返回指向中序后继的指针*/ThBinTreeq;if(p-rtag=1)/*p的右子树为空*/return(p-rchild);/*p-rchild是右线索*/else/*p的右子树不空，在右子树中查找“最左下”结点*/q=p-rchild;/*从*p的右孩子开始查找*/while(q-ltag=0)q=q-lchild;return(q);/*InorderNext*/,可以应用类似的方法，在中序线索二叉树中查找结点*p的中序前趋结点。若p-ltag=1，即*p的左子树为空，则p-lchild为左线索，直接指向*p的中序前趋结点；若p-ltag=0说明*p的左子树非空，则*p的中序前驱必是其左子树中最后一个中序遍历到的结点，则从*p的左孩子出发，沿右指针链往下查找，直到找到一个没有右孩子的结点为止。该结点是*p的左子树中“最右下的”结点，该结点是*p的中序前趋结点（如图5.28所示）。,算法描述如下：ThBinTreeInorderPre(ThBinTreep)/*在中序线索树中查找*p结点的中序前驱,函数返回指向中序前驱的指针*/ThBinTreeq;if(p-ltag=1)/*p的左子树为空/return(p-lchild);/*p-lchild为左线索直接指向*p的中序前驱结点*/else/*p的左子树非空,在左子树中查找“最右下”结点*/q=p-lchild;/*从*p的左孩子开始查找*/while(q-rtag=0)/*当*q不是右下结点，继续查找*/q=q-rchild;return(q);/*InorderPre*/,4遍历线索二叉树遍历某种次序的线索二叉树比遍历一般的二叉树容易，只要从该次序下的开始结点出发，反复查找结点在该次序下的后继，直至终端结点。我们仍以中序线索二叉树为例，给出按中序遍历线索二叉树的算法，在中序遍历时访问的第一个结点是从根结点出发，沿左指针链往下查找，直到找到一个没有左孩子的结点为止，该结点是根的左子树中“最左下的”结点。,遍历中序线索二叉树算法描述如下：voidInorderThread（ThBinTreep）/*遍历中序线索二叉树*/if(p!=NULL)/*非空二叉树*/while(p-ltag=0)/*找中序序列的开始结点*/p=p-lchild;while(p)printf(“t%cn”,p-data);/*访问结点*p*/p=InorderNext(p);/*找*p的中序后继结点*/*InorderThread*/显然，该算法的时间复杂度为O(n)，但它是非递归算法，所以在常数因子上小于递归的遍历算法。,5.5树、森林和二叉树的关系5.5.1树、森林转换为二叉树,1树转换为二叉树将一棵树转换为二叉树，要经过以下四个步骤：（1）在树中所有相邻兄弟之间加一条连线。（2）对树中的每个结点，只保留它与第一个孩子结点之间的连线，抹去它与其它孩子结点之间的连线。（3）把所有的连线拉成横平竖直。（4）以树的根结点为轴心，将整棵树顺时针转动45的角度，使之结构层次分明。,2森林转换为二叉树（1）先确定森林中各树的一个排列顺序；（2）把每一棵树转换为相应的二叉树；（3）从第二棵二叉树开始，依次将第i+1棵二叉树当作第i棵二叉树的根结点的右子树，i=1，2，直到所有的二叉树连成一棵二叉树为止，这棵二叉树就是这个森林转换成的二叉树。如图5.31（a)中的森林，经上述转换，变成为图5.31(c)中的二叉树。,5.5.2树、森林的遍历,1树的遍历（1）树的先序遍历若树非空，则：访问根结点；从左至右依次先序遍历根的各子树。（2）树的后序遍历若树非空，则：从左至右依次后序遍历根的各子树；访问根结点。,2.森林的遍历（1）先序遍历森林若森林非空，则：访问森林中第一棵树的根结点；先序遍历第一棵树中根结点的各子树所构成的森林；先序遍历除第一棵树外其它树构成的森林。（2）后序遍历森林后序遍历森林中第一棵树的根结点的各子树所构成的森林；访问第一棵树的根结点；后序遍历除第一棵树外其它树构成的森林。,5.6哈夫曼树及其应用5.6.1哈夫曼树的定义及构造,1哈夫曼树的基本概念路径：树中一个结点到另一个结点之间的分支路径长度：路径上的分支数目树的路径长度：从树根到树中每一结点的路径长度之和结点的权：给树中结点赋予一个有某种意义的数结点的带权路径长度：从该结点到树根之间的路径长度与结点上权的乘积树的带权路径长度：树中所有叶子结点的带权路径长度之和，通常记为：WPL其中，n表示叶子结点的数目，wi和li分别表示叶子结点ki的权植和根到叶子结点ki之间的路径长度。哈夫曼树(最优二叉树)：在权为w1，w2，wn的n个叶子结点的所有二叉树中，带权路径长度WPL最小的二叉树,例如：给定4个叶子结点a，b，c和d，分别带权7，5，2和3。可以构造出不同的二叉树，图5.32所示的是其中的三棵，它们的带权路径长度分别为：（a）WPL=7*2+5*2+2*2+3*2=34（b）WPL=7*3+5*3+2*1+3*2=44（c）WPL=7*1+5*2+2*3+3*3=32其中（c）所示的二叉树的WPL最小，其实它就是哈夫曼树。,2、哈夫曼算法基本思想:（1）根据给定的n个权值w1，w2，wn构造n棵二叉树的森林F=BT1，BT2，BTn，其中每棵二叉树BTi中都只有一个权值为wi的根结点，其左右子树均为空。（2）在森林F中选出两棵根结点的权值最小的二叉树（当这样的二叉树不止两棵时，可以从中任选两棵），将这两棵二叉树合并成一棵新的二叉树，此时，需要增加一个新结点作为新二叉树的根，并将所选的两棵二叉树的根分别作为新二叉树的左右孩子（谁左，谁右无关紧要），将左右孩子的权值之和作为新二叉树根的权值。（3）在集合F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集合F中；（4）对新的森林F重复（2）、（3），直到森林F中只剩下一棵二叉树为止。这棵二叉树便是所求的哈夫曼树。,图5.33给出了前面提到的叶子结点权值集合为W7，5，2，3的哈夫曼树的构造过程。注意：对于同一组给定的叶子结点的权值所构造的哈夫曼树，树的形状可能不同，但带权路径长度值是相同的，一定是最小的。,3哈夫曼算法的实现有n个叶子结点的哈夫曼树中共有2n-1个结点，用一个大小为2n-1的数组来存储哈夫曼树中的结点，在哈夫曼树算法中，对每个结点，既需要知道其双亲结点的信息，又需要知道其孩子结点的信息，因此，其存储结构为：#definen7/*叶子数目，根据实际情况定义值*/#definem2*n-1/*结点总数*/typedefstructintweight;/*结点的权值*/intlchild,rchild,parent;/*左、右孩子及双亲的下标*/HTNode;、typedefHTNodeHuffmanTreem+1;/*HuffmanTree是结构数组类型，其0号单元不用*/HuffmanTreeht;,算法思想：（1）初始化。将ht1.m中每个结点的lchild,rchild,parent域全置为零（2）输入。读入n个叶子结点的权值存放于ht数组的前n个位置的weight域中，它们是初始森林中n个孤立的根结点的权值。（3）合并。对初始森林中的n棵二叉树进行n-1次合并，每合并一次产生一个新结点，所产生的新结点依次存放到数组ht的第i(nim)个位置。每次合并分两步：在当前森林ht1.i-1的所有结点中，选择权值最小的两个根结点htp1和htp2进行合并，1p1,p2i-1；将根为htp1和htp2的两棵二叉树作为左右子树合并为一棵新的二叉树，新二叉树的根存放在hti中，因此，将htp1和htp2的双亲域置为i,并且新二叉树根结点的权值应为其左右子树权值的和，即hti.weight=htp1.weight+htp2.weight，新二叉树根结点的左、右孩子分别为p1、p2，即hti.lchild=p1,hti.rchild=p2。,Huffman算法描述如下：voidCreateHuffmanTree(HuffmanTreeht)/*构造Huffman树，htm为其根结点*/inti,p1,p2;InitHuffmanTree(ht);/*将ht初始化*/InputWeight(ht);/*输入叶子权值至ht1.n的weight域*/for(i=n+1;i=m;i+)/*共进行n-1次合并，新结点依次存于HTi中*/SelectMin(ht,i-1,/*for*/*CreateHuffmanTree*/,对于图5.33所示的构造哈夫曼树的过程的结果如表5.1与5.2所示。表5.1哈夫曼树初态表5.2哈夫曼树终态,562哈夫曼树的应用Huffman编码：数据通信用的二进制编码思想：根据字符出现频率编码，使电文总长最短编码：根据字符出现频率构造Huffman树，然后将树中结点引向其左孩子的分支标“0”，引向其右孩子的分支标“1”；每个字符的编码即为从根到每个叶子的路径上得到的0、1序列,例要传输的字符集D=C,A,S,T,;字符出现频率w=2,4,2,3,3,T:00;:01A:10C:110S:111,例如，假设有一个电文字符集D=a,b,c,d,e，f，g，h，每个字符的使用频率分别为：0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11。设计其哈夫曼编码。为方便计算，可以将所有字符的频率乘以100，使其转换成整型数值集合，得到5,29,7,8,14,23,3,11，以此集合中的数值作为叶子结点的权值构造一棵哈夫曼树，如图5.34所示。字符集D中字符的哈夫曼编码为：a:0001；b:10；c:1110；d:1111；e:110；f:01；g:0000；h:001,57实训例题,实训例题1设计哈夫曼编码【问题描述】根据给定字符的使用频率，为其设计哈夫曼编码。【基本要求】功能：求出n个字符的哈夫曼编码。输入：输入n个字符和字符在电文中的使用频率。输出：n个字符的哈夫曼编码。【数据结构】#definen8/*叶子数目*/#definem2*n-1/*结点总数*/,typedefstructintweight;/*结点的权值*/intlchild,rchild,parent;/*左、右孩子及双亲的下标*/HTNode;typedefHTNodeHumffmanTreem+1;/*HuffmanTree是结构数组类型，其0号单元不用*/HumffmanTreeht;,把编码存储在一个数组code中，哈夫曼树中每个叶子结点的哈夫曼编码长度不同，因字符集的大小为n，因此编码的长度不会超过n，数组code的大小可设为n+1（下标为0的单元不用）。编码的存储结构为：typedefstructcharch;/*存储字符*/charcoden+1;/*存放编码位串*/CodeNode;typedefCodeNodeHuffmanCoden+1;/*HuffmanCode是结构数组类型，其0号单元不用，存储哈夫曼编码*/,【算法思想】首先由以下三步求哈夫曼树。（1）初始化。将ht1.m中每个结点的lchild,rchild,parent域全置为零。（2）输入。读入n个叶子结点的权值存放于ht数组的前n个位置中，它们是初始森林中n个孤立的根结点的权值。（3）合并。对初始森林中的n棵二叉树进行n-1次合并，每合并一次产生一个新结点，所产生的新结点依次存放到数组ht的第i(nim)个位置。每次合并分两步：在当前森林ht1.i-1的所有结点中，选择权值最小的两个根结点htp1和htp2（p1为权值最小的根结点的序号，p2为权值次小的根结点的序号）进行合并，1p1,p2i-1；将根为htp1和htp2的两棵二叉树作为左右子树合并为一棵新的二叉树，新二叉树的根存放在hti中，因此，将htp1和htp2的双亲域置为i,并且新二叉树根结点的权值应为其左右子树权值的和，即hti.weight=htp1.weight+htp2.weight，新二叉树根结点的左、右孩子分别为p1、p2，即hti.lchild=p1,hti.rchild=p2（权值小的作为左孩子）。,求得哈夫曼树后，再按下述方法求哈夫曼编码。依次以叶子hti（1in）为出发点，向上回溯至根为止。用临时数组cd存放求得的哈夫曼编码，用变量start指示每个叶子结点的编码在数组cd中的起始位置，实际的编码从cdstart到cdn。对于当前叶子结点hti，将start置初值n，找其双亲结点htf，若当前结点是双亲结点的左孩子结点，则cd数组的相应位置置0；若当前结点是双亲结点的右孩子结点，则cd数组的相应位置置1。然后start减1。再对双亲结点进行同样的操作，直到根结点为止，燃后，让start的值加1，指向编码的开始位置。实际的编码从cdstart到cdn。最后把编码复制到数组hcdi的code域中。,【模块划分】一共设计5个模块：初始化哈夫曼树函数InitHuffmanTree（）；输入权值函数InputWeight()；选择两个权值最小的根结点函数SelectMin()；构造哈夫曼树函数CreateHuffmanTree()；求哈夫曼编码函数Huffmancode()。,【源程序】#inclu