第6章-树及二叉树.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第六章 树和二叉树,6.1,树的类型定义,6.2,二叉树的类型定义和实现,6.3,遍历二叉树和线索二叉树,6.4,树和森林,6.5,Huffman,树与,Huffman,编码,6.1,树的类型定义,树,是,n,个结点的有限集,D,，当,n,1,时：,1,）有一个特定的结点,root,被称为,根,(,结点,),;,2,）除根以外的结点被分成,m,(,m,0),个不相交的有限集,T,1,T,2,T,m,，其中每个集合又是一棵树，称为根的,子树,。,该定义是一个递归的定义，树可以用广义表的形式描述：,Tree=(,root,T,1,T,2,T,m,),其中,root,是结点类型，其余为树类型,(,广义表类型,),。,树是一种数据结构：,Tree,=(D,R),其中,:,对比树型结构和线性结构的结构特点,线性结构,树型结构,第一个数据元素,(,无前驱,),根结点,(,无前驱,),最后一个数据元素,(,无后继,),多个叶子结点,(,无后继,),其它数据元素,(,一个前驱、一个后继,),其它数据元素,(,一个前驱、多个后继,),基 本 术 语,结 点,:,结点的度,:,树的度,:,叶子结点,:,分支结点,:,数据元素,+,若干指向子树的分支,分支的个数,树中所有结点的度的最大值,度为零的结点,度大于零的结点,(,从根到结点的,),路径：,从根到该结点所经分支和结点构成,孩子结点、双亲结点、兄弟结点、堂兄弟、祖先结点、子孙结点,结点的,层次,:,树的,深度,：,假设根结点的层次为,1,，第,l,层的结点的子树的根结点的层次为,l,+1,。,树中叶子结点所在的最大层次。,森 林：,是,m,(,m,0),棵互不相交的树的集合。,(,),有确定的根；,(,),树根和子树根之间为有向关系。,有向树：,有序树：,子树之间存在确定的次序关系。,无序树：,子树之间不存在确定的次序关系。,树的表示方法：层次结构；,1,）,嵌套集合；,2,）,广义表；,3,）,凹入表示法,就逻辑结构而言，树是二元组：,Tree,=(root,F),F,是,m,(,m,0),棵子树的森林，,F=(T,1,T,2,T,m,),，其中,T,i,=(,r,i,F,i,),；当,m0,时，存在二维关系：,RF=|,i,=1,2,m,m,0,A,B,C,D,E,F,G,H,I,J,M,K,L,A(,B(E,F(K,L),C(G),D(H,I,J(M),),T,1,T,3,T,2,树根,例如,:,树的抽象数据类型定义如下：,ADT Tree,数据对象：,D,是具有相同特性的数据元素的集合。,数据关系：,若,D,为空集，则称为空树。,否则:,(1),在,D,中存在唯一的称为根的数据元素,root,；,(2),当,n,1,时，其余结点可分为,m,(,m,0,)个互不相交的有限,集,T,1,T,2,T,m,，其中每一棵子集本身又是一棵符合本定 义的树，称为根,root,的子树。,基本操作：,初始化操作,InitTree,(,&T,),操作结果：,初始化置空树。,DestroyTree,(&T),初始条件：,树,T,存在。,操作结果：,销毁树,T,。,结构销毁操作,CreateTree,(,&T,definition,),操作结果：,按定义构造树。,引用型操作,Root(T),初始条件：,树,T,存在。,操作结果：,求树的,根,结点。,Parent(T,cur,_,e,),初始条件：,树,T,存在。,操作结果：,用,cur_e,返回当前结点,双亲,的元素值。,Value(T,cur,_,e,),初始条件：,树,T,存在。,操作结果：,用,cur_e,返回当前结点的,元素值,。,引用型操作（续）,RightSibling,(T,cur,_,e,),初始条件：,树,T,存在。,操作结果：,用,cur,_,e,返回当前结点,右兄弟,的元素值。,LeftSibling,(T,cur,_,e,),初始条件：,树,T,存在。,操作结果：,用,cur,_,e,返回当前结点,左兄弟,的元素值。,引用型操作（续）,TreeEmpty,(T),初始条件：,树,T,存在。,操作结果：,判定树是否为空树,。,TraverseTree,(T,Visit,(),初始条件：,树,T,存在。,操作结果：,按照某种顺序用,Visit,访问所有的结点。,TreeDepth,(T),初始条件：,树,T,存在。,操作结果：,求树的,深度,。,加工型操作,Assign(T,&,cur,_,e,value,),初始条件：,树,T,存在。,操作结果：,用,value,给当前结点,cur,_,e,赋值,。,DeleteChild,(&T,&,p,i,),初始条件：,树,T,存在，,1,i,degree,(,p,),。,操作结果：,删除结点,p,的第,i,棵子树,。,InsertChild,(&T,&,p,i,c,),初始条件：,树,T,存在，且,i,1,。,操作结果：,将以,c,为根的树插入为结点,p,的第,i,棵子树,。,加工型操作,（续）,ClearTree,(&T),初始条件：,树,T,存在。,操作结果：,清空树中的所有结点,。,ADT Tree,6.2,二叉树的类型定义和实现,二叉树中每个结点至多只有,2,棵子树，二叉树的子树有左右之分。,二叉树的五种基本形态：,空树,只含根结点,右子树为空树,左子树为空树,左右子树均不为空树,二叉树的抽象数据类型定义如下：,ADT,BinaryTree,数据对象：,D,是具有相同特性的数据元素的集合。,数据关系：,若,D,为空集，则称为空树。,否则:,(1),在,D,中存在唯一的称为根的数据元素,root,；,(2),当,n,1,时，其余结点可分为,2,个互不相交的有限集,T,1,、,T,2,，其中每一棵子集本身又是一棵符合本定义的,二叉树，,T,1,称为根,root,的,左子树,，,T,2,称为根,root,的,右子树,，,基本操作：,初始化操作,InitBiTree,(&T),操作结果：,初始化置空二叉树。,DestroyBiTree,(,初始条件：,二叉树,T,存在。,操作结果：,销毁二叉树,T,。,结构销毁操作,CreateBiTree,(&T,definition,),操作结果：,按定义构造二叉树。,引用型操作,Root(T),初始条件：,二叉树,T,存在。,操作结果：,求二叉树的根结点。,Parent(T,e,),初始条件：,二叉树,T,存在。,操作结果：,用,e,返回当前结点双亲的元素值。,Value(T,e,),初始条件：,二叉树,T,存在。,操作结果：,用,e,返回当前结点的元素值。,引用型操作（续）,LeftChild,(T,e,),初始条件：,二叉树,T,存在。,操作结果：,用,e,返回当前结点左子女的元素值。,RightChild,(T,e,),初始条件：,二叉树,T,存在。,操作结果：,用,e,返回当前结点右子女的元素值。,引用型操作（续）,RightSibling,(T,e,),初始条件：,二叉树,T,存在。,操作结果：,用,e,返回当前结点右兄弟的元素值。,LedtS,ibling,(T,e,),初始条件：,二叉树,T,存在。,操作结果：,用,e,返回当前结点左兄弟的元素值。,引用型操作（续）,BiTreeEmpty,(T);,初始条件：,二叉树,T,存在。,操作结果：,判定,二叉,树是否为空树,。,BiTreeDepth,(T),初始条件：,二叉树,T,存在。,操作结果：,求,二叉,树的深度,。,引用型操作（续）,PreOrderTraverse,(T,Visit,(),初始条件：,二叉树,T,存在。,操作结果：,按照先序用,Visit,遍历二叉树中的所有结点。,InOrderTraverse,(T,Visit,(),初始条件：,二叉树,T,存在。,操作结果：,按照中序用,Visit,遍历二叉树中的所有结点。,引用型操作（续）,PostOrderTraverse,(T,Visit,(),初始条件：,二叉树,T,存在。,操作结果：,按照后序用,Visit,遍历二叉树中的所有结点。,LevelOrderTraverse,(T,Visit,(),初始条件：,二叉树,T,存在。,操作结果：,按照层次用遍历,Visit,二叉树中的所有结点。,加工型操作,InsertChild,(&T,&,p,LR,c,),初始条件：,二叉树,T,存在。,操作结果：,根据,LR,的值，,将以,c,为根的树插入为结点,p,的子树,。,DeleteChild,(T,p,LR);,初始条件：,二叉树,T,存在。,操作结果：,根据,LR,的值，,删除结点,p,的子树,。,加工型操作,（续）,ClearBiTree,(&T),初始条件：,二叉树,T,存在。,操作结果：,清空,二叉,树中的所有结点,。,ADT,BinaryTree,Assign(T,&,e,value,),初始条件：,二叉树,T,存在。,操作结果：,用,value,给当前结点,e,赋值,。,二叉树的重要特性,在二叉树的第,i,层上至多有,2,i,-1,个结点。,(,i,1),性质,1,证明：用归纳法证明，,i=,1,层时，只有一个根结点：,2,i-1,=,2,0,=,1,；,假设对所有的,j,，,1,j,i,，命题成立，二叉树上每个结点至多有两棵子树，则第,i,层的结点数,=2,i,-2,2=2,i,-1,。,深度为,k,的二叉树上至多含 2,k,-1 个结点,(,k,1,),。,性质,2,证明：,基于上一条性质，深度为,k,的二叉树上的结点数至多为,2,0,+2,1,+2,k,-1,=2,k,-1,。,对任何一棵二叉树，若它含有,n,0,个叶子结点、,n,2,个度为 2 的结点，则必存在关系式：,n,0,=,n,2,+1。,性质,3,证明：,设,n,1,为,二叉树中度为的结点数，其结点总数,n,=,n,0,+,n,1,+,n,2,，,二叉树上分支总数,b,=,n,1,+2,n,2,，,而,b,=,n,-1=,n,0,+,n,1,+,n,2,1,，,由此,，,n,0,=,n,2,+1。,两类特殊的二叉树：,满二叉树：,指的是深度为,k,且含有,2,k,-1,个结点的二叉树。,完全二叉树：,树中所含的,n,个结点和满二叉树中编号为,1,至,n,的结点一一对应。,具有,n,个结点的完全二叉树的深度为,log,2,n,+1,性质,4,证明：,设完全二叉树的深度为,k,，则根据第二条性质得,2,k-1,n,2,k,，,即,k,-1,log,2,n,n,，,则该结点无左孩子，否则，编号为,2,i,的结点为其左孩子结点；,(3),若,2,i,+1,n,，,则该结点无右孩子结点，否则，编号为,2,i,+1,的结点为其右孩子结点。,课堂讨论：,Q1,：,满二叉树和完全二叉树有什么区别？,A1,：,满二叉树是叶子一个也不少的树，而完全二叉树虽然前,n-1,层是满的，但最底层却允许在右边缺少连续若干个结点。,满二叉树是完全二叉树的一个特例。,Q2,：,为什么要研究满二叉树和完全二叉树这两种特殊形式？,A1,：,因为只有这两种形式可以实现顺序存储！,Q3:,设一棵完全二叉树具有,1000,个结点，则它有,个叶子结点，有,个度为,2,的结点，有,个结点只有非空左子树，有,个结点只有非空右子树。,499,1,0,由于最后一层叶子数为,489,个，是,奇数,，说明有,1,个结点只有非空左子树；而完全二叉树中不可能出现非空右子树,(0,个,),。,A3,：,易求出总层数和末层叶子数。总层数,k=,log,2,n,1,=,10,;,且前,9,层总结点数为,2,9,-1=,511,(,完全二叉树的前,k-1,层肯定是满的,),所以末层叶子数为,1000-511=,489,个。,500,请注意叶子结点总数,末层叶子数！,还应当加上第,k-1,层（靠右边）的,0,度结点个数。,分析：末层的,489,个叶子只占据了上层的,245,个结点（,489/2,),上层（,k=9),右边的,0,度结点数还有,2,9-1,-245=11,个！,第,i,层上的满结点数为,2,i-1,所以，,全部叶子数,489(,末层,),11(k-1,层,)=500,个。,度为,2,的结点叶子总数,1=499,个。,另一法：可先求,2,度结点数,再由此得到叶子总数。,首先，,k-2,层的,2,8,-1,（,255,）个结点肯定都是,2,度的（完全二叉）,另外，末层叶子（刚才已求出为,489,）所对应的双亲也是度,2,，（共有,489/2,244,个）。,所以，全部,2,度结点数为,255(,k-2,层,),244(,k-1,层,)=499,个；,总叶子数,2,度结点数,1=500,个。,二叉树的存储结构,#,define,MAX_TREE_SIZE,100,/,二叉树的最大结点数,typedef,TElemType,SqBiTree,MAX,_,TREE,_,SIZE,;,/0,号单元存储根结点,SqBiTree,bt,;,二叉树的顺序存储表示,按照依次自上而下、自左至右的顺序，存储,完全,二叉树结点的元素值。,例如,:,A,B,D,C,E,F,0,1,2,3,4,5,6,7,8,9,10,11,12,13,二叉树的链式存储表示,1.,二叉链表,结点结构,:,lchild,data,rchild,typedef,struct,BiTNode,/,结点结构,TElemType,data,;,struct,BiTNode,*,lchild,*,rchild,;,/,左右孩子指针,BiTNode,*,BiTree,;,typedef,struct,TriTNode,/,结点结构,TElemType,data,;,struct,TriTNode,*,lchild,*,rchild,;,/,左右孩子指针,struct,TriTNode,*,parent,;,/,双亲指针,TriTNode,*,TriTree,;,结点结构,:,2,三叉链表,lchild,data,parent,rchild,root,A,B,C,D,E,F,6.3,遍历二叉树和线索二叉树,顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且,仅,被访问一次。,二叉树由根、左子树和右子树组成。对二叉树而言，可以有三条搜索路径：,1,）,先,(,根,),序遍历,：根,左子树,右子树,2,）,中,(,根,),序遍历,：左子树,根,右子树,3,）,后,(,根,),序遍历,：,左子树,右子树,根,一、遍历二叉树,若二叉树为空树，则空操作；否则，,（,1,）访问根结点；,（,2,）先序遍历左子树；,（,3,）先序遍历右子树。,先,(,根,),序的遍历算法,:,该算法定义根据二叉树的递归定义进行递归实现。,访问路径描述：从根结点开始，沿着左子树方向依次访问，当左子树遍历完成，从左子树退回时访问每个结点的右子树。,void Preorder,(,BiTree,T,void,(*,visit,)(,TElemType,&,e,),/,先序遍历二叉树,if,(,T,),(*,visit,)(,T,-,data,);,/,访问结点,Preorder,(,T,-,lchild,visit,);,/,遍历左子树,Preorder,(,T,-,rchild,visit,);,/,遍历右子树,/,Preorder,算法的递归描述：,二叉树算法实现基于二叉链表存储结构,void Preorder,(,BiTree,T,void,(*,visit,)(,TElemType,&,e,),/,先序遍历二叉树,InitStack,(,S,);,p,=,T,;,while,(,p,|,!,StackEmpty,(,S,),if,(,p,),/,往左子树方向前进,(*,visit,)(,p,-,data,);,Push,(,S,p,);,p,=,p,-,lchild,;,else,/,从左子树退回,Pop,(,S,p,);,p,=,p,-,rchild,;,/,while,/,Preorder,算法的非递归描述：,二叉树算法实现基于二叉链表存储结构,若二叉树为空树，则空操作；否则，,（,1,）中序遍历左子树；,（,2,）访问根结点；,（,3,）中序遍历右子树。,中,(,根,),序的遍历算法：,访问路径描述：沿着左子树方向找到最“左边”的结点作为起点，从左子树退回时依次访问每个结点及其右子树。,void,Inorder,(,BiTree,T,void,(*,visit,)(,TElemType,&,e,),/,中序遍历二叉树,if,(,T,),Inorder,(,T,-,lchild,visit,);,/,遍历左子树,(*,visit,)(,T,-,data,);,/,访问结点,Inorder,(,T,-,rchild,visit,);,/,遍历右子树,/,Inorder,算法的递归描述：,二叉树算法实现基于二叉链表存储结构,void,Inorder,(,BiTree,T,void,(*,visit,)(,TElemType,&,e,),/,中序遍历二叉树,InitStack,(,S,);,p,=,T,;,while,(,p,|,!,StackEmpty,(,S,),if,(,p,),/,往左子树方向前进,Push,(,S,p,);,p,=,p,-,lchild,;,else,/,从左子树退回,Pop,(,S,p,);,(*,visit,)(,p,-,data,);,p,=,p,-,rchild,;,/,while,/,Inorder,算法的非递归描述：,二叉树算法实现基于二叉链表存储结构,若二叉树为空树，则空操作；否则，,（,1,）后序遍历左子树；,（,2,）后序遍历右子树；,（,3,）访问根结点。,后,(,根,),序的遍历算法：,访问路径描述：找到最“左边”的叶子结点作为起点，每次经过一个结点时需要判断：如果是从左子树返回，则进入右子树；如果从右子树返回，则访问该结点并后退。判断的方法是看该结点的右子树的根是否为刚刚访问的那个结点。,void,Postorder,(,BiTree,T,void,(*,visit,)(,TElemType,&,e,),/,后序遍历二叉树,if,(,T,),Postorder,(,T,-,lchild,visit,);,/,遍历左子树,Postorder,(,T,-,rchild,visit,);,/,遍历右子树,(*,visit,)(,T,-,data,);,/,访问结点,/,Postorder,算法的递归描述：,二叉树算法实现基于二叉链表存储结构,void,Postorder,(,BiTree,T,void,(*,visit,)(,TElemType,&,e,),/,后序遍历二叉树,InitStack,(,S,);,p,=,T,;,q,=,NULL,;,while,(,p,|,!,StackEmpty,(,S,),/,访问某棵子树,if,(,p,),Push,(,S,p,);,p,=,p,-,lchild,;,/“,前进”,else,GetTop,(,S,p,);,/,判断栈顶结点,if,(,p,-,rchild,&,p,-,rchild,!=q,),p,=,p,-,rchild,;,else,Pop,(,S,p,);(*,visit,)(,p,-,data,);,q,=p,;,p,=,NULL,;,/,用,q,保存刚访问的结点并回退,/,else,/,while,/,Postorder,算法的非递归描述：,二叉树算法实现基于二叉链表存储结构,二、遍历算法的应用举例,.,统计二叉树中叶子结点的个数,算法基本思想,:,遍历二叉树，“访问结点”,(,visit,),的操作为：计数。,void,CountLeaf,(,BiTree,T,int,&,count,),if,(,T,),if,(,!T,-,lchild,)&(,!T,-,rchild,),count,+;,/,计数,CountLeaf,(,T,-,lchild,count,);,CountLeaf,(,T,-,rchild,count,);,/,if,/,CountLeaf,.,求二叉树的深度,算法基本思想,:,从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加,1,。,“访问结点”,(,visit,),的操作为：求得左、右子树深度的最大值，然后加,1,。,遍历顺序为后根序。,首先分析二叉树的深度和它子树深度之间的关系：,int,Depth,(,BiTree,T,),if,(,!T,),depthval,=0;,else,depthL,=,Depth,(,T,-,lchild,);,depthR,=,Depth,(,T,-,rchild,);,depthval,=1+(,depthL,depthR,?,depthL,:,depthR,);,return,depthval,;,/,Depth,.,建立二叉链表存储结构,以字符串的形式输入二叉树：按照二叉树先序遍历的顺序输入二叉树中每个结点的元素。空结点也必须输入。,例如，,空树：,以空格字符“,”表示；,只含一个根结点的二叉树,：,以字符串“A,”表示,；,二叉树,T,：,以字符串“,AB,C,D,”,表示,A(B(C()D(),Status,CreateBiTree,(,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,-,rchild,);,/,构造右子树,return OK,;,/,CreateBiTree,三、线索二叉树,.,何谓线索二叉树？,遍历二叉树的结果是结点的一个,线性,序列。,先序序列,:A B C D E F G H K,中序序列,:,B D C A H G K F E,后序序列,:,D C B H K G F E A,ABCDEFGHK,遍历序列中的线性关系指针称为“,线索,”。,在二叉链表的结点中增加两个标志域，并作如下规定：,1,）若该结点的,左子树,不空，则,lchild,域的指针指向其左子树，且左标志域的值为“,指针,Link,”,；否则，,lchild,域的指针指向其前驱，且左标志的值为“,线索,Thread,”,。,2,）若该结点的,右子树,不空，则,rchild,域的指针指向其右子树，且右标志域的值为“,指针,Link,”,；否则，,rchild,域的指针指向其后继，且右标志的值为“,线索,Thread,”,。,以这种结点定义的二叉树的存储结构称作“,线索链表,”。,其二叉树称为“,线索二叉树,”。,对二叉树进行遍历，使其变为线索二叉树的过程叫做“,线索化,”。,在线索链表中定义,头结点,，其,lchild,指向二叉树的根结点，,rchild,指向中序遍历序列中的最后一个结点。,线索链表的,C,语言描述：,typedef,enum,Link,Thread,PointerThr,;,/,Link,=0:,指针，,Thread,=1:,线索,typedef,struct,BiThrNod,TElemType,data,;,struct,BiThrNode,*,lchild,*,rchild,;,/,左右指针,PointerThr,LTag,RTag,;,/,左右标志,BiThrNode,*,BiThrTree,;,data,A,G,E,I,D,J,H,C,F,B,ltag,0,0,1,1,1,1,0,1,0,1,rtag,0,0,0,1,0,1,0,1,1,1,A,G,E,I,D,J,H,C,F,B,例,1,：,带了两个标志的某先序遍历结果如表所示，请画出对应二叉树。,A,B,C,G,E,I,D,H,F,root,悬空,？,悬空？,解：该二叉树中序遍历结果为,:,H,D,I,B,E,A,F,C,G,所以添加线索应当按如下路径进行：,例,2,：,画出以下二叉树对应的中序线索二叉树。,为,避免悬空态，应增设一个头结点,对应的中序线索二叉树存储结构如图所示：,0,0,A,0,0,C,0,0,B,1,1,E,1,1,F,1,1,G,0,0,D,1,1,I,1,1,H,注：此图中序遍历结果为,:,H,D,I,B,E,A,F,C,G,0,-,root,0,3.,给定如图所示二叉树,T,，,请画出与其对应的中序线索二叉树。,28,25,40,55,60,33,08,54,解,:,因为中序遍历序列是：,55,40 25 60,28,08 33,54,对应线索树应当按此规律连线，即在原二叉树中添加虚线。,NIL,NIL,.,线索链表的遍历算法,:,例如,:,对中序线索链表的遍历算法,中序遍历的第一个结点？,左子树上最“左边的”没有左子树的结点。,在中序线索链表中结点的后继？,若无右子树，则为后继线索所指结点；,否则为其右子树进行中序遍历访问的第一个结点。,void,InOrder,_,Thr,(,BiThrTree,T,void,(*,Visit,)(,TElemType,e,),/,遍历头结点为,T,的中序线索链表,p,=,T,-,lchild,;,/,p,指向根结点,while,(,p,!,=,T,),/,最后一个结点的,rchild,指向,T,while,(,p,-,LTag,=,Link,),p,=,p,-,lchild,;,/,第,一个结点,(*,Visit,)(,p,-,data,);,while,(,p,-,RTag,=,Thread,&,p,-,rchild,!,=,T,),p,=,p,-,rchild,;(*,Visit,)(,p,-,data,);,/,访问后继结点,p,=,p,-,rchild,;,/,进入右子树,/,InOrderTraverse,_,Thr,.,建立线索链表,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,;,/,保持,pre,指向,p,的前驱,InThreading,(,p,-,rchild,);,/,右子树线索化,/,if,/,InThreading,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,;,InThreading,(,T,);,pre,-,rchild,=,Thrt,;,/,处理最后一个结点,pre,-,RTag,=,Thread,;,Thrt,-,rchild,=,pre,;,return OK,;,/,InOrderThreading,在算法中，,pre,作为公用变量，在函数,InThreading,中的修改必须反应在算法中。这样，当,InThreading,(,T,),执行完毕时，,pre,是其中序遍历序列中的最后一个结点，,T,不变。,6.4,树和森林,一、树的存储结构,.,双亲表示法,顺序存储结构，每个结点指示双亲结点的位置,A,-1,B,0,C,0,D,0,E,2,F,2,G,5,0,1,2,3,4,5,6,data,parent,r=0,n=7,typedef,struct,PTNode,Elem data,;,int,parent,;,/,双亲位置域,PTNode,;,#,define,MAX,_,TREE,_,SIZE,100,C,语言描述:,typedef,struct,PTNode,nodes,MAX,_,TREE,_,SIZE,;,int,r,n,;,/,根结点的位置和结点个数,PTree,;,.,孩子链表表示法,顺序,+,链式存储结构，顺序存放结点，每个结点指向其孩子结点的单链表。,A,B,C,D,E,F,G,0,1,2,3,4,5,6,data,firstchild,r=0,n=7,1,2,3,4,5,6,typedef,struct,CTNode,int,child,;,struct,CTNode,*,next,;,*,ChildPtr,;,/,孩子结点结构,typedef,struct,ElemType,data,;,ChildPtr,firstchild,;,/,孩子链表的头指针,CTBox,;,/,双亲结点结构,typedef,struct,CTBox,nodes,MAX,_,TREE,_,SIZE,;,int,n,r,;,/,结点数和根结点的位置,CTree,;,C,语言描述:,.,孩子,-,兄弟表示法,(,二叉树表示法,),链式存储结构，用二叉链表作为存储结构。左指针指向第一个孩子结点，右指针指向右兄弟结点。,typedef,struct,CSNode,ElemType,data,;,struct,CSNode,*,firstchild,*,nextsibling,;,CSNode,*,CSTree,;,C,语言描述:,二、森林和二叉树的对应关系,根据二叉链表表示法，任何一棵树和二叉树之间存在对应关系：树对应的二叉树的右子树为空，如果森林中的树的根结点之间看作是兄弟关系，则可以构建森林对应的二叉树。,设森林为：,F=T,1,T,2,T,m,，,二叉树为：,B=(,root,LB,RB),由森林转换成二叉树的转换规则为,:,若,F=,，即,m,=0,，则,B=;,若,F,，即,m,0,，则,root,=ROOT(T,1,),，,LB,为,T,1,的子树森林,T,11,T,12,T,1,n,对应的二叉树，,RB,为森林,T,2,T,m,对应的二叉树。,由二叉树转换为森林的转换规则为：,若,B=,，则,F=,；,ROOT(T1)=,root,；由,LB,对应得到,(T,11,T,12,，,T,1,n,),；由,RB,对应得到,(T,2,T,3,T,m,),。,三、树和森林的遍历,树的遍历可有三条搜索路径,:,按层次遍历,:,先根,(,次序,),遍历,:,后根,(,次序,),遍历,:,若树不空，先访问根结点，然后依次先根遍历各棵子树。,若树不空，先依次后根遍历各棵子树，然后访问根结点。,若树不空，则自上而下自左至右访问树中每个结点。,先根遍历时顶点的访问次序：,A B E F C D G H I J K,后根遍历时顶点的访问次序：,E F B C I J K H G D A,层次遍历时顶点的访问次序：,A B C D E F G H I J K,1,第一棵树的根结点；,2,第一棵树的子树森林；,3,其它树构成的森林。,根据森林和二叉树的对应关系，森林由三部分构成：,森林的遍历,1.,先序遍历,若森林不空，则访问森林中第一棵树的根结点；,先序遍历森林中第一棵树的子树森林；,先序遍历森林中其余树构成的森林。,即：依次从左至右对森林中的每一棵树进行先根遍历。,.,中序遍历,若森林不空，则中序遍历第一棵树的子树森林；,访问森林中第一棵树的根结点；,中序遍历森林中其余树构成的森林。,即：依次从左至右对森林中的每一棵树进行中根遍历。,树的遍历和二叉树遍历的对应关系？,树,森林,二叉树,先根遍历,先序遍历,先序遍历,后根遍历,中序遍历,中序遍历,6.5 Huffman,树与,Huffman,编码,一、最优二叉树,(,Huffman,树,),结点路径长度：,从根到该结点的路径上,分支,的数目。,树的路径长度：,树中,每个结点,的路径长度之,和,。,树的带权路径长度：,树中所有,叶子结点,的带权路径长度之和。,结点的带权路径长度：,从根到该结点之间的路径长度与结点权的,乘积,。,在所有含,n,个叶子结点、并带相同权值的,m,叉树中，必存在一棵其带权路径长度取最小值的树，称为“,最优树,”。,如果,m,=2,，称为“,最优二叉树,”。,例如：,WPL=,60,WPL=,89,根据给定的,n,个权值,w,1,w,2,w,n,，构造,n,棵二叉树的集合,F=T,1,T,2,T,n,，,T,i,为一个权值为,w,i,的结点构成的二叉树；,二、构造,Huffman,树,Huffman,算法：,在,F,中选取根的权值最小的两棵二叉树，分别作为左右子树构造一棵新的二叉树，并置这棵新二叉树根的权值为其左右孩子结点的权值之和；,将新二叉树加入,F,，并在,F,中删除其左右子树；,重复,(2),和,(3),两步，直至,F,中只含一棵树为止。,例如,:,已知权值,W=5,6,2,9,7,二叉树集合,F,变化如下：,1,）,2,）,3,）,4,）,5,）,前缀编码：,不等长编码中，任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。,三、,Huffman,编码,利用,Huffman,树可以,构造一种不等长的二进制编码,，并且构造所得的哈夫曼编码是一种最优前缀编码，即使所传电文的总长度最短。,不等长编码中，出现频率大的字符的编码长度短。,【,例,】,假设用于通信的电文由8个字母（AH）组成，字母在电文出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。试为这8个字母设计,哈,夫曼编码。,算法提示：,将频率,(100),看作是,AH,的权值，根据权值的集合构造最优二叉树。每个权值结点最后得到的编码就是相对应的字符的,Huffman,编码。,3.,掌握各种二叉树遍历策略的递归算法，灵活运用遍历算法实现二叉树的其它操作。,本章学习要点,1.,熟练掌握二叉树的性质，了解相关性质证明。,2.,熟悉二叉链表的存储结构的特点及适用范围。,4.,理解各种二叉树遍历策略的非递归算法。,5.,理解线索二叉树以及二叉树的线索化过程。,8.,了解最优二叉树的特性，掌握建立最优二叉树和,Huffman,编码的方法。,6.,熟悉树的存储结构及其基本操作。,7.,掌握树和森林与二叉树的转换方法。,