树和二叉树第六章

.,第六章树和二叉树,6.1树的定义和基本术语6.2二叉树6.3遍历二叉树和线索二叉树6.4树和森林6.6赫夫曼树及其应用,.,6.1树的定义和基本术语,树(Tree)：是n(n=0)个结点的有限集。在任意一个非空树中：有且仅有一个特定的称为根(Root)的结点；当n=1时，其余结点可分为m(m0)个互不相交的有限集T1,T2,Tm,其中Ti是一棵树，称为根结点子树例:(a)是只有一个根结点的树.(b)是有13个结点的树，A是根，其余结点分成三个互不相交的子集：T1=(B,E,F,K,L);T2=(C,G);T3=(D,H,I,J,M).T1,T2,T都是根A的子树，本身也是一棵树,.,A,(a)只有根结点的树,T1,T2,T3,(b)一般的树A是根，T1,T2,T3是三棵子树,.,ADTTree数据对象D:D是具有相同特性的数据元素的集合.数据关系R:若D为空集，则称为空树；若D仅含一个数据元素，则R为空集，否则R=H,H是如下二元关系：(1)在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；,抽象类型树的定义,.,(2)若D-root=，则存在D-root的一个划分D1D2,Dn(m0),对任意j=k(1H;对应于D-root的划分，H-,有唯一的一个划分H1,H2,Hn(m0),对任意的j=k(1=j,k=m)有HjHk=，且对任意i(1=i=m),Hi是Di上的二元关系，(Di,Hi)是一棵符合本定义的树，称为根root的子树。,.,基本操作P:InitTree(初始条件：树T存在操作结果：销毁树T,树的基本操作,.,CreatTree(初始条件：树T存在操作结果：若T为空树，则返回TRUE，否则FALSE,.,TreeDepth(T);初始条件：树T存在操作结果：返回T的深度Root(T);初始条件：树T存在操作结果：返回T的根Value(T,cur_e);初始条件：树T存在，cur_e是T中某个结点操作结果：返回cur_e的值,.,Assign(T,cur_e,value);初始条件：树T存在，cur_e是T中某个结点操作结果：结点cur_e赋值为valueParent(T,cur_e);初始条件：树T存在，cur_e是T中某个结点操作结果：若cur_e是T的非根结点，则返回它的双亲，否则函数值为“空”LeftChild(T,cur_e);初始条件：树T存在，cur_e是T中某个结点操作结果：若cur_e是T的非叶子结点，则返回它的最左孩子，否则返回“空”,.,RightSibling(T,cur_e);初始条件：树T存在，cur_e是T中某个结点操作结果：若cur_e有右兄弟，则返回它的右兄弟，否则函数值为“空”InsertChild(初始条件：树T存在，P指向T中某个结点，1=i=0)棵互不相交的树的集合,.,6.2二叉树,定义：是一棵或为空树，或树中每个结点的度数=2有序树特点：每个结点至多有两棵子树二叉树的子树有左右之分,其次序不能任意互换,.,(a),(b),(c),(d),(e),(a)空二叉树(b)仅有根结点的二叉树(c)右子树为空的二叉树(d)左，右子树均非空的二叉树(e)左子树为空的二叉树,二叉树的五中基本形态：,.,InitBiTree(初始条件：二叉树T存在操作结果：销毁二叉树T,二叉树的基本操作,.,CreatBiTree(初始条件：二叉树T存在操作结果：若T为空二叉树，则返回TRUE，否则FALSE,.,BiTreeDepth(T);初始条件：二叉树T存在操作结果：返回T的深度Root(T);初始条件：二叉树T存在操作结果：返回T的根Value(T,e);初始条件：二叉树T存在，e是T中某个结点操作结果：返回e的值,.,Assign(T,cur_e,value);初始条件：树T存在，cur_e是T中某个结点操作结果：结点cur_e赋值为valueParent(T,e);初始条件：二叉树T存在，e是T中某个结点操作结果：若e是T的非根结点，则返回它的双亲，否则返回“空”LeftChild(T,e);初始条件：二叉树T存在，e是T中某个结点操作结果：返回e的左孩子，若无左孩子.返回“空”,.,RightChild(T,e);初始条件：二叉树T存在，e是T中某个结点操作结果：返回e的右孩子若无右孩子.返回“空”LeftSibling(T,cur_e);初始条件：二叉树T存在，e是T中某个结点操作结果：返回e的左兄弟，否则函数值为“空”,.,RightSibling(T,e);初始条件：二叉树T存在，e是T中某个结点操作结果：返回e的右兄弟，否则函数值为“空”InsertChild(T,P,LR,c);初始条件：二叉树T存在，P指向T中某个结点，LR为0或者1,非空二叉树c与T不相交并且右子树为空.操作结果：根据LR为0或1,插入c为T中p指结点左或右子树.P所指结点的原有左或者右子树则成为c的右子树,.,DeleteChild(T,P,LR);初始条件：二叉树T存在,p指向T中某个结点，LR为0或1.操作结果：根据LR为0或1,删除T中P所指结点的左或者右子树PreorderTraverse(T,Visit();初始条件：二叉树T存在,Visit是对结点操作的应用函数操作结果：按先序遍历二叉树T,对T的每个结点调用函数visit()一次且至多一次，一旦visit()失败，则操作失败,.,InorderTraverse(T,Visit();初始条件：二叉树T存在,Visit是对结点操作的应用函数操作结果：中序遍历树T,对T的每个结点调用函数visit()一次且至多一次，一旦visit()失败，则操作失败.PostTraverse(T,Visit();初始条件：二叉树T存在,Visit是对结点操作的应用函数操作结果：后序遍历树T,对T的每个结点调用函数visit()一次且至多一次，一旦visit()失败，则操作失败,.,LevelTraverseT(T,Visit();初始条件：二叉树T存在,Visit是对结点操作的应用函数操作结果：层次遍历树T,对T的每个结点调用函数visit()一次且至多一次，一旦visit()失败，则操作失败.ADTBinarytree,.,性质1在二叉树的第i层上至多有2i-1各结点证明：用归纳法证明i=1时，只有一个根结点.显然，2i-1=20=1是对的设当n=k-1时，第k-1层上至多有2k-2个结点则当n=k时，每个结点至多有两棵子树所以：k层结点数最多为k-1层的2倍所以：S=1)由性质1可知，深度为k的二叉树的最大结点数为i=1k(第i层上的最大结点数)=i=1k2i-1=2k-1,.,性质3对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1证明：设n1为二叉树T中度为1的结点数。因为二叉树中所有结点的度均小于或等于2，所以结点总数为n=n0+n1+n2(1)对二叉树的分支数，除了根结点外，其余结点都有一个分支进入，设B为分支总数，则n=B+1。由于这些分支是由度为1或2的结点射出的，所以又有B=n1+2n2得出：n=n1+2n2+1(2)由式(1)和式(2)得:n0=n2+1,.,特殊形态的二叉树,满二叉树：深度为k,具有2k-1个结点得二叉树完全二叉树：对深度为k，n个结点的二叉树，当且仅当其每个结点都与深度为k的完整二叉树结点为编号从1到n结点一一对应,.,特殊形态的二叉树图示,满二叉树,完全二叉树,.,性质4具有n个结点的完全二叉树的深度为log2n+1证明：假设深度为k，则根据性质2和完全二叉树的定义有2k-1-1n=2k-1于是k-1n,则结点i无左孩子（结点i为叶子结点);否则其左孩子LCHILD(i)是结点2i.如果2i+1n,则结点i无右孩子;否则其右孩子RCHILD(i)是结点2i+1,.,顺序存储结构：,1,5,6,4,3,2,7,对应顺序存储结构,完全二叉树,二叉树的存储结构,.,1,3,5,6,4,2,7,一般二叉树,顺序存储结构,.,二叉树的顺序存储表示,#defineMAX_TREE_SIZE100/二叉树的最大结点数TypedefTElemTypeSqBiTreeMAX_TREE_SIZE;/0号单元存储根结点SqBiTreebt;,.,链式存储结构二叉链表结点结构,左指针域数据域右指针域,.,二叉树的二叉链表存储表示,TypedefstructBitnodeTElemTypedata;structBiTNode*lchild,*rchild;/左,右孩子指针BiTNode,*BiTree;,.,三叉链表结点结构,双亲结点域,A,D,C,B,单支树的二叉链表,.,A,D,F,E,B,C,G,二叉链表,.,A,C,B,D,F,E,G,三叉链表,.,6.3遍历二叉树和线索二叉树,遍历二叉树：访问每个结点，一次仅且一次先序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则访问根结点先序遍历左子树先序遍历右子树中序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则中序遍历左子树访问根结点；中序遍历右子树,.,后序遍历二叉树的操作定义若二叉树为空，则空操作；否则后序遍历左子树后序遍历右子树访问根结点层次遍历二叉树的操作定义若二叉树为空，则空操作；否则从上到下,从左到右依次访问各个结点,.,例：如图所示的二叉树，表示下述表达式a+b*(cd)e/f若先序遍历此树，得到前缀表达式（波兰式）+a*bcd/ef若中序遍历二叉树，得到中缀表达式a+b*cde/f若后序遍历二叉树，的到后缀表达式（逆波兰式）abcd*+ef/,f,e,/,+,a,*,b,d,c,.,算法6.1StatusPreOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)If(T)if(Visit(T-data)if(PreorderTraverse(T-lchild,Visit)if(PreorderTraverse(T-rchild,Visit)returnOK;returnERROR;elsereturnOK;/PreorderTraverse,先序遍历二叉树的递归算法,.,层次遍历二叉树的算法,用队列辅助实现StatusleverOrderTraverse(BiTreeT,Statut(*Visit)(TElemTypee)InitQueue(Q);EnQueue(Q,T);while(!QueueEmpty(Q)DelQueue(Q,p);if(p!=NULL)visit(p-data);EnQueue(Q,p-lchild);EnQueue(Q,p-rchild);/whileReturnOK;,.,二叉树遍历的非递归算法,一.先序遍历非递归算法先序遍历的特点是:首先访问根结点,访问完根后访问左子树,所以对每一个结点,访问完该结点后,沿其左孩子链访问下去,直到左链为空.这时,所有访问过的结点进栈.然后结点出栈,对于每一个出栈结点,即表示该结点和其左子树已经被访问结束,按先序遍历定义,应该访问该结点的右子树,.,算法思想:1.当前指针指向根结点.2.访问当前结点,并且进栈,当前指针指向当前结点的左孩子,重复2,直到左孩子为空3.依次退栈,将当前指针指向出栈结点的右孩子.4.若栈非空,或者当前指针非空,执行2,否则结束.,.,Statuspreorder(BiTreeT,status(*visit()initstack(s);push(s,T);while(!stackempty(s)while(gettop(s,p),.,pop(s,p);if(!stackempty(s)pop(s,p);push(s,p-rchild);/if/whileReturnOK;,.,二.中序遍历非递归算法,二.中序遍历非递归算法中序的特点是:首先访问左子树,所以对每一个结点,沿左链走下去,直到左链为空,所有经过的结点进栈.然后结点出栈,对于每一个出栈结点,表示该结点的左子树访问结束.按中序遍历的定义,应该访问该结点(根),访问完该结点后,访问该结点的右子树.,.,1.当前指针指向根结点.2.当前结点进栈,当前指针指向其左孩子,重复2,直到左孩子为空.3.依次退栈,退栈指针成为当前指针,访问当前结点.4.将当前指针指向右孩子.5.若栈非空或者当前指针非空,执行2;否则结束.,.,Statusinorder(BitreeT,status(*visit()initstack(s);push(s,t);while(!stackEmpt(s)while(gettop(s,p),.,if(!stackEmpty(s)pop(s,p);if(!visit(p-data)returnERROR;push(s,p-rchild);/if/whileReturnOK;,.,三.后序遍历非递归算法,三.后序遍历非递归算法在后序遍历中,当当前指针指向某个结点时,不能马上进行访问,而先要遍历左子树,所以要求该结点进栈保存.当访问完它的左子树后,再次搜索该结点时,还不能进行访问,还要遍历其右子树.所以需要再次将此结点入栈保存.为了区别同一结点的两次入栈,需要引进一个入栈次数的标志.我们约定:标志0为该结点首先入栈,标志1为该结点第二次入栈.为此需要设两个栈:一个栈用来存放结点地址,即为结点栈s1m,另一个栈用来存放结点进栈标志,即标志栈s2m,栈指针为同一个.,.,1.当前指针指向根结点2.当前结点进栈,所对应的标志为0,当前指针其左孩子,重复2,直到左孩子为空.3.当栈顶标志为1时,依次退栈,并且访问退栈指针所指结点,直到标志为04.将栈顶标志变成为1,将当前指针指向栈顶元素的右孩子,准备遍历右子树.5.若栈顶非空或者当前指针非空,执行2,否则结束.,.,Voidpostorder(BiTreeT,status(*visit()ints2m,top=0;BiTreep,s1m;p=T;dowhile(p!=NULL)s1top=p;s2top+=0;/p结点首先入栈p=p-lchild;/遍历左子树,.,while(top,.,表达式(a*b-c)的二叉树,1,2,-,*,a,b,c,-,-,*,*,a,a,b,b,c,c,遍历的递归执行过程，其中红色，蓝色，绿色分别表示先序，中序，后序遍历过程中访问结点输出信息,.,方法一：,指向前驱结点,指向某一种遍历下后继结点,在二叉链表中增加指向某一种遍历下前驱和后继指针(线索）目的：提高查找某一种遍历下前驱和后继结点效率,线索二叉树,.,方法二：利用二叉链表中（n+1个）空指针域来作为指向某一种遍历下前趋和后继结点的指针域，为了区别指针的用途，同时在每个结点增加两个标志域Ltag,Rtag,.,其中：,Ltag=0lchild域指示结点的左孩子1lchild域指示结点的前驱,Rtag=0rchild域指示结点的右孩子1rchild域指示结点的后继,.,NIL,NIL,中序线索二叉树,.,thrt,bt,中序线索链表,.,二叉树的二叉线索存储表示,二叉树的二叉线索存储表示：TypedefenumLink,ThreadPointerTag;/Link=0:指针，Thread=1;线索TypedefstructBiThrNodeTElemTypedata;structBiThrNode*lchild,*rchild;/左右孩子指针PointerTagLtag,Rtag;/左右标志BiThrNode,*BiThrTree;,.,a.只要找到序列中第一个结点，然后依次找结点后继直至其后继为空为止。如何在中序线索树中找结点的后继的方法：（1）若Rtag=1，则rchild指的是后继结点（2）若Rtag=0，则右子树的最左孩子为其后继结点,在线索树上进行遍历的方法,.,b.或只要找到序列中最后一个结点，然后依次找结点前趋直至其前趋为空为止。如何在中序线索树中找结点前趋的方法：（1）若Ltag=1，则lchild指的是前趋结点（2）若Ltag=0，则左子树的最右孩子为其前趋结点,在线索树上进行遍历的方法,.,算法6。5：StatusInOrderTraverse_Thr(BiThrTreeT,Status(*Visit)(TElemTypee)/T指向头结点，头结点的左链Lchhild指向根结点/中序遍历二叉线索树T的非递归算法，/对每个数据元素调用函数VisitP=T-lchild;/P指向根结点While(P!=T)/空树或遍历结束时，p=Twhile(p-Ltag=Link)p=p-lchild;,中序遍历二叉线索树T的非递归算法,.,if(!Visit(p-data)returnERROR;/访问其左子树为空的结点while(p-Rtag=Thread/InOrderTraverse_Thr,.,在后序线索树中找结点后继，分三种情况：若结点x是二叉树的根，则后继为空；若结点x是其双亲的右孩子或是其双亲的左孩子且其双亲没有右子树，则其后继即为双亲结点若结点x是其双亲的左孩子，且其双亲有右子树，则其后继为双亲的右子树上按后序遍历列出的第一个结点,.,线索化的实质：是将二叉链表中的空指针改为指向前驱或后继的线索，而前驱或后继的信息只有在遍历时才能得到，所以线索化的过程为遍历过程中修改空指针的过程。设:pre指针,始终指向刚刚访问过的结点，若p指向当前访问的结点，则pre指向其前驱,二叉树的线索化算法,.,算法6.6：StatusInorderThreading(BiThrTree/若二叉树为空，则左指针回指,.,elseThrt-lchild=T;pre=Thrt;InThreading(T);/中序遍历进行中序线索化pre-rchild=Thrt;pre-RTag=Thread;/最后一个结点线索化Thrt-rchild=pre;returnOK;/InOrderThreading,.,算法6.7VoidInThreading(BiThrTreep)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);/右子树线索化/InThreading,.,6.4树和森林,树的存储结构双亲表示法以一组连续空间存储树的结点，同时在每个结点中附设一个指示器指示其双亲结点在链表中的位置.树的双亲表存储表示：#defineMAX_TREE_SIZE100TypedefstructPTNodeTElemTypedata;intparent;/双亲位置域PTNode;,.,TypedefstructPTNodenodesMAX_TREE_SIZE;intn;/结点数Ptree;如图：树的双亲表示法示例,0,1,2,3,4,5,6,7,8,9,6-13,.,孩子表示法方法一：多重链表法每个结点结构,d树的度,方法二：孩子链表法,为每个孩子建立一个孩子链表,.,孩子链表存储结构：TypedefstructCTNode/孩子结点intchild;structCTNode*next;*ChildPtr;TypedefstructTElemTypedata;ChildPtrfirstchild;/孩子链表头指针CTBox;TypedefstructCTBoxnodesMAX_TREE_SIZE;intn,r;/结点数和根的位置Ctree;,.,如图:是图6-13的孩子链表表示法,0,1,2,3,4,5,6,7,8,9,.,双亲表示法和孩子表示法结合如图：是下图6-14对应的带双亲的孩子链表,0,1,2,3,4,5,6,7,8,9,.,6-14,.,三.孩子兄弟表示法以二叉链表作为树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个孩子结点，分别命名为firstchild域和nextsibling域。又称为二叉链表表示法存储表示：TypedefstructCSNodeElemTypedata;structCSNode*firstchild,*nextsibling;CSNode,*CSNree;,.,树转化为二叉树方法：左手拉第一个孩子，右手拉下一个兄弟,A,E,C,B,D,E,D,C,B,A,树,二叉树,森林与二叉树的转换,.,森林转化为二叉树方法：将森林中每棵树转化为二叉树,第一棵树的根为二叉树的根，森林中各棵树的根是兄弟关系.如图：,A,J,I,H,G,F,E,D,C,B,森林,二叉树,.,树遍历方法：先根(次序)遍历树方法：先访问树的根结点，然后依次先根遍历根的每棵子树后根(次序)遍历方法：先依次后根遍历每棵子树，然后访问根结点,树和森林的遍历,.,例：对下图进行先根遍历，得到先根序列为ABCDE对此树进行后根遍历，得到树的后根序列为BDCEA,A,D,E,C,B,.,先序遍历森林若森林非空，按下述规律遍历：访问森林中第一棵树的根结点；先序遍历第一棵树中根结点的子树森林；先序遍历除去第一棵树之后剩余的树构成的森林。中序遍历森林若森林非空：中序遍历森林中第一棵树的根接点的子树森林；访问第一棵树的根结点；中序遍历除去第一棵树之后剩余的树构成森林。,森林遍历方法,.,对下图中森林进行先序遍历和中序遍历，先序序列为：ABCDEFGHIJ中序序列为：BCDAFEHJIG如图：,A,J,I,H,G,F,E,D,C,B,森林,二叉树,.,6.6赫夫曼树及其应用,路径长度：路径上的分枝数目称为树的路径长度树的路径长度：从树根到每一结点的路径长度之和树的带权路径长度：树中所有叶子结点的带权路径长度之和，通常记作：WPL=k=1nwkLk最优二叉树(haffman树)：带权路径长度WPL最小的二叉树,.,如图中的三棵二叉树，都有4个叶子结点a,b,c,d,分别带权7,5,2,4,a,b,c,d,c,b,a,d,d,c,b,a,7,5,2,4,7,5,2,4,7,5,2,4,(a),(b),(c),.,它们的带权路径长度分别为(a)WPL=72+52+22+42=36(b)WPL=73+53+21+42=46(c)WPL=71+52+2V3+43=35,.,根据给定的n个权值w1,w2,wn构成n棵二叉树的集合F=T1,T2,Tn,其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树均空在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左，右子树上根结点的权值之和。在F中删除这两棵树，同时将新得到的二叉树加入F中重复(2)和(3)，直到F只含一棵树为止。,赫夫曼树构造算法,.,a,d,c,b,7,5,2,4,如图：展示了构造赫夫曼树的构造过程。其中，根结点上标注的数字是所赋的权。,.,赫夫曼编码,利用Haffman树进行编码，各叶子结点表示待进行编码的字符,约定二叉树左分枝为0，右分枝为1，从根到叶的编码串就是这个叶子结点字符的Haffman编码,.,例6-2已知某系统在通信联络中只可能出现八种字符，其概率分别为0