树和二叉树学习

树和二叉树学习第1页/共222页2树的类型定义二叉树的类型定义二叉树的存储结构遍历二叉树和线索二叉树树和森林赫夫曼树主要内容第2页/共222页3社会的组织结构家族的族谱计算机中的目录组织描述层次结构，是一种一对多的逻辑关系树型结构实例第3页/共222页41.树的类型定义树的定义(Tree)树是由n(n>0)个结点组成的有限集合如果n=0，称为空树如果n>0，则有一个特定的称之为根(root)的结点，它只有直接后继，但没有直接前驱除根以外的其它结点划分为m(m>=0)个互不相交的有限集合T0,T1,…,Tm-1，每个集合又是一棵树，并且称之为根的子树递归定义第4页/共222页5ABCDEFGHIJKLM根子树树(逻辑上)的特点每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继第5页/共222页6ABCDEFGHIJKLM树的基本概念

结点分支结点叶子结点根结点内部结点结点度不为0的结点度为0的结点第6页/共222页7树的基本概念

结点的度和树的度结点的度即结点拥有的子树个数。树的度是树内各结点的度的最大值。ABCDEFGHIJKLM3213200100000第7页/共222页8树的基本概念

结点的层次和树的深度(高度)结点的层次从根开始定义。根位于第1层，根的孩子位于第2层，余则类推。树的深度即树中结点的最大层次。第1层第2层第3层第4层树的高度为4ABCDEFGHIJKLM第8页/共222页9树的基本概念

孩子、双亲、兄弟结点的子树的根称为结点的孩子。该结点称为其孩子的双亲。同一双亲的孩子间互称兄弟。ABCDEFGHIJKLM孩子双亲第9页/共222页10树的基本概念

祖先、子孙结点的祖先是从根到该结点所经分支上的所有结点；以某结点为根的子树中的任一结点都称该结点的子孙。ABCDEFGHIJKLMABCDEFGHIJKLM第10页/共222页11树的基本概念森林：m(m>=0)棵互不相交的树的集合BEFKLDHMIJCGACGBDEFKLHMIJ第11页/共222页12树的有序性：若树中结点的子树的相对位置不能随意改变，则称该树为有序树，否则称该树为无序树。树的基本概念==有序树无序树ABDCACBD第12页/共222页13有序树中最左边的子树的根称其第一个孩子，最右边的子树的根称其最后一个孩子。老大老二老三

有序树的第一个孩子和最后一个孩子树的基本概念ABDC第13页/共222页14树的常用表示法AEFBIJGHCDFGIJABCEDH凹入表示嵌套集合广义表A(B(E,F),C,D(G(J),H,I))ABEFCDGJHI第14页/共222页15为何要重点研究每结点最多只有两个“叉”的树？树太一般，子树的个数无限制，表示困难二叉树的结构最简单，规律性最强可以证明，所有树都能转为唯一对应的二叉树，不失一般性。2.二叉树第15页/共222页16二叉树的基本定义二叉树的定义是n≥0个结点的有穷集合该集合或者为空、或者由一个根结点和两个分别称为左子树和右子树的互不相交的二叉树组成。当集合为空时，称该二叉树为空二叉树。逻辑结构：一对二(1:2)基本特征:树的一种每个结点最多有2棵子树(即度<=2)BCADE第16页/共222页17二叉树与树的区别

树至少应有一个结点，而二叉树可以为空；树的孩子结点没有限制，而二叉树中的每个结点最多有2个孩子结点；树的子树没有顺序，但如果二叉树的根结点只有一棵子树，必须明确区分它是左子树还是右子树，因为两者将构成不同形态的二叉树。第17页/共222页18二叉树的五种基本形态2.只有树根A1.空树ΦBADE3.只有左子树4.只有右子树BADEBCADE5.左右子树都有第18页/共222页19问：具有3个结点的二叉树可能有几种不同形态？有5种Φ二叉树的基本形态第19页/共222页201.度为2的树是二叉树。2.度为2的有序树是二叉树。3.具有三个结点的树可以有以下五种形态：1种第20页/共222页21二叉树的性质性质1：在二叉树的第i层最多有2i-1个结点(i>=1)证明：当i=1时，显然成立假设当i=k时，也成立，即第k层最多2k-1个结点当i=k+1时，由于二叉树的每个结点最多有2个孩子，所以第k+1层最多有2*2k-1=2(k+1)-1个结点故对于任意i(i>=1)，二叉树的第i层最多有2i-1个结点提问：第i层上至少有

个结点？1第21页/共222页22二叉树的性质性质2：深度为k的二叉树最多有2k-1个结点(k>=1)证明：由性质1可知：第i层最多有2i-1个结点所以总的结点数最多为k=41234第22页/共222页23二叉树的性质性质3：对任何一棵二叉树T，若叶子结点数(即度为0的结点数)为n0，度为2的结点数为n2，则n0=n2+1证明：总结点数n=n0+n1+n2设分支数为B，则n=B+1又B=n1+2n2结点无外乎度为0、1、2三种情况”五个手指四个叉”除了树根，其余每个结点”上方”都有一个分支度为2的结点“下方”有2个分支度为1的结点“下方”有1个分支度为0的结点“下方”有0个分支解方程组： 得：n0=n2+1第23页/共222页24树的叶子数与其它结点数的关系设度为m的树中度为0,1,2,…,m的结点数分别为n0,n1,n2,…,nm，结点总数为n，分支数为B，则下面二式成立n=n0+n1+n2+…+nm(1)n=B+1=n1+2n2+…+mnm+1(2)由(1)和(2)得叶子结点数

n0=1+n2+2n3+…+(m-1)nm

第24页/共222页25满二叉树(FullBinaryTree)深度为k，结点数为2k-1即结点数达到最大值特殊形态的二叉树完全二叉树(CompleteBinaryTree)树中每个结点的编号（从上到下，从左到右）都与一个同深度的满二叉树的结点一一对应叶子结点只可能在层次最大的两层上出现完全二叉树和和满二叉树相比，就是最底层最右边连续缺少一些结点第25页/共222页26特殊形态的二叉树2h-1结论：

深度为h且具有2h-1个结点的二叉树为满二叉树。思考：深度为h的完全二叉树至少有多少个结点？第26页/共222页27二叉树的性质性质4：具有n个结点的非空完全二叉树的深度为证明：设深度为k，则：2k-1-1<n<=2k-1由此推出：2k-1<=n<2k两边求对数：k-1<=log2n<k所以：24-123-1第27页/共222页28二叉树的性质性质5：若将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号：(1)若i=1，则结点i是树根，无双亲 若i>1，则其双亲是结点i/2(2)若2i>n，则结点i无左孩子(即i为叶结点)，否则其左孩子为2i(3)若2i+1>n，则结点i无右孩子，否则其右孩子为2i+1由(2)(3)可以推导出(1)理解：结点i如果有左孩子的话，其编号应该为2i如果2i>n，则左孩子不存在第28页/共222页29二叉树的性质性质6：具有n个结点的非空二叉树共有n-1个分支。证明：除了根结点以外，每个结点有且仅有一个双亲结点，即每个结点与其双亲结点之间仅有一个分支存在，因此，具有n个结点的非空二叉树的分支总数为n-1。第29页/共222页301.n(n>0)个结点的树的高度最低是多少？最高是多少？2.n(n>0)个结点的二叉树的高度最低是多少？最高是多少？推论n个结点的树：高最多为n，最低为2。n个结点的二叉树：高最多为n(单支树)，最低为log2n+1(完全二叉树)。自测题第30页/共222页31自测题

3.有关二叉树下列说法正确的是()A.二叉树的度为2B.一棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任何一个结点的度都为24.已知一棵完全二叉树的第6层(设根是第1层)有8个叶结点，则该完全二叉树的结点个数最多是()

A.39B.52C.111D.119第31页/共222页32完全二叉树性质的推论n个结点的完全二叉树中：度为1的结点数为(n+1)%2度为0的结点数为(n+1)/2度为2的结点数为(n+1)/2-1编号最大的分支结点是n/2编号最小的叶子结点是n/2+1具有n0个叶子结点的完全二叉树中共有2n0个结点或2n0-1个结点。第32页/共222页33一棵完全二叉树有1000个结点，则它必有

个叶子结点；有

个度为2的结点；有

个结点只有非空左子树；有

个结点只有非空右子树。(1000+1)/2

=500叶子总数-1=49910因为最后一个结点坐标是偶数，所以必为左子树。有1个结点只有非空左子树，有0个结点只有非空右子树。自测题第33页/共222页34自测题5.一棵124个叶结点的完全二叉树，最多有()个结点。A.247B.248C.249D.250E.2516.已知一棵完全二叉树中共有626个结点，叶子结点的个数应为()。A.311B.312C.313D.314E.其他第34页/共222页35自测题7.一个具有1025个结点的二叉树的高h为()。A.11B.10C.11至1025之间D.10至1024之间8.已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有______个叶子结点。12第35页/共222页36二叉树本节小结二叉树的概念和类型定义注意和树的类型定义的对比二叉树的性质要求自己能推导、应用、推广第36页/共222页373.二叉树的存储结构二叉树的顺序存储结构用一维数组来表示#defineMAX_TREE_SIZE100typedefdatatypeSqBiTree[MAX_TREE_SIZE];SqBiTreeBt;按照满二叉树的顺序存放第37页/共222页38完全二叉树的顺序存储结构

根据完全二叉树的性质5，对于深度为h的完全二叉树，将树中所有结点的数据信息按编号顺序一次存储到数组BT[1…2h-1]中，由于编号与数组下标一一对应，该数组就是该完全二叉树的顺序存储结构。1234567891012345678910下标：

BT[3]的双亲为3/2=1，即在BT[1]中；其左孩子在BT[2i]=BT[6]中；其右孩子在BT[2i+1]=BT[7]中。第38页/共222页39一般二叉树的顺序存储结构123456789101234567891012345678910BT[5]的双亲为5/2=2，即在BT[2]中，与实际矛盾！其左孩子在BT[2i]=BT[10]中，实际应在BT[9]中。

对于一般二叉树，需要在二叉树中“增添”一些实际上并不存在的“虚结点”(可以认为这些结点的数据信息为空)，使其在形式上成为一棵“完全二叉树”；然后按照完全二叉树的顺序存储结构的构造方法将所有结点的信息依次存放到数组BT[1..2h-1]中。第39页/共222页4012340678900120015123456789101112131415BT[6]的双亲为6/2=3，即在BT[3]中！其左孩子在BT[2i]=BT[12]中；其右孩子在BT[2i+1]=BT[13]中，而BT[13]＝0，表示无右孩子。第40页/共222页41一般二叉树的顺序存储结构极端情形：单支树深度为k的二叉树，最少只有k个结点却需要2k-1个存储单元137深度增加一层10增加1倍之多1030007000000015第41页/共222页42二叉树的链式存储结构二叉链表data为数据域；lchild与rchild分别为指向左、右子树的指针域。3.二叉树的存储结构lchilddatarchilddatalchildrchild第42页/共222页43二叉链表示例说明：一个二叉链表由根指针T唯一确定。若二叉树为空，则T=NULL；若结点的某个孩子不存在，则相应的指针为空。具有n个结点的二叉链表中，共有2n个指针域。其中只有n-1个用来指示结点的左、右孩子，其余的n+1个指针域为空。

第43页/共222页44二叉树的链式存储结构三叉链表比二叉链表的链结点多增加了一个指向双亲结点的指针域parent。3.二叉树的存储结构lchilddataparentrchildparentdataleftchildrightchild第44页/共222页45三叉链表示例第45页/共222页46二叉链表结点结构的定义

typedefintdatatype;typedefstructnode { datatypedata;

structnode*lchild,*rchild; }bitree;二叉树的链表表示lchilddatarchild第46页/共222页47二叉树的存储结构本节小结各种存储结构注意各自的优缺点比如顺序存储空间浪费大二叉链表不能直接找到父结点第47页/共222页48练习1

已知非空二叉树采用广义表形式作为输入，请写一算法，建立该二叉树的二叉链表存储结构。第48页/共222页49关于广义表形式表示二叉树的说明1.约定表中的一个字母代表一个结点的数据信息。2.每个根结点作为由子树构成的表的名字放在表的前面。3.每个结点的左子树和右子树之间用逗号分开，若只有右子树而无左子树，则逗号不能省略。4.在整个广义表的末尾加一个特殊符号（如@）作为结束标志。ABCDFGE第49页/共222页50二叉树的广义表表示方法二叉树@defi=“@”空树Φ第50页/共222页51大写字母二叉树@defi=“A”只有树根A二叉树的广义表表示方法第51页/共222页52大写字母(二叉树,)二叉树#二叉树defi=“A(B,C(D,E))”ACDEB二叉树的广义表表示方法第52页/共222页531.若取到的元素为字母，则如下建立一个新结点，若该结点为根结点，则将该结点的地址送T。若该结点不是二叉树的根结点，则将该结点作为左孩子（若标志为1）或者右孩子（若标志为2）链接到其双亲结点上（双亲结点的地址在栈顶）。2.若取到的元素为左括号（，则表明一个子表开始，将标志置为1，同时将前面那个结点的地址进栈。3.若取到的元素为右括号），则表明一个子表结束，作退栈操作。4.若取到的元素为逗号，则表明以左孩子为根的子树处理完毕，接着应该处理以右孩子为根的子树，将标志置为2。如此处理广义表中每一个元素，直到取到结束符号@为止。第53页/共222页54练习2

已知具有n个结点的非空完全二叉树采用顺序存储结构，结点的数据信息依次存放于数组BT[1..n]中。请写出由此产生该二叉树二叉链表结构的算法。第54页/共222页55建立根结点以BT的第2个元素开始取一个元素建立一个新结点保存新结点的地址找到新结点的双亲结点的地址确定新结点是双亲结点的左（或右）孩子将新结点插入二叉链表中保存在一个数组中利用二叉树的性质5第55页/共222页56设置一个一维数组PTR存放结点所在链结点的地址建立根结点，并将根结点的地址保存在数组PTR中从数组BT的第2个元素开始依次取结点的信息BT[i]，每取得一个结点做如下操作：1.建立一个新结点，并将结点地址保存在PTR[i]中；2.建立新结点的双亲结点的位置(地址)；3.确定新结点是其双亲结点的左孩子或右孩子；4.将新结点作为双亲结点的左孩子或右孩子插入二叉链表中。位置j=i/2地址PTR[j]若i%2==0，则新结点是其双亲结点的左孩子；当i%2!=0，则新结点是其双亲结点的右孩子；第56页/共222页57ijj=i/2当i%2==0时，i是j的左孩子当i%2!=0时，i是j的右孩子第57页/共222页58#defineMaxNode100/*MaxNode>=n*/bitree*BUILDBTREE(datatypeBT[],intn){bitree*T,*PTR[MaxNode];inti,j;PTR[1]=(bitree*)malloc(sizeof(bitree));PTR[1]->data=BT[1];PTR[1]->lchild=NULL;PTR[1]->rchild=NULL;T=PTR[1];/*建立根结点*/第58页/共222页59for(i=2;i<=n;i++){PTR[i]=(bitree*)malloc(sizeof(bitree));PTR[i]->data=BT[i];PTR[i]->lchild=NULL;PTR[i]->rchild=NULL;j=i/2;/*计算双亲结点的位置j*/if(i%2==0)PTR[j]->lchild=PTR[i];/*BT[i]是双亲的左孩子*/elsePTR[j]->rchild=PTR[i];/*BT[i]是双亲的右孩子*/

}returnT;}第59页/共222页60

已知非空二叉树采用顺序存储结构，结点的数据信息依次存放于数组BT[1..n]中。请写出由此产生该二叉树二叉链表结构的算法。练习3第60页/共222页61一、二叉树的遍历

按照一定的顺序(原则)对二叉树中每一个结点都访问一次(仅访问一次)，得到一个由该二叉树的所有结点组成的序列，这一过程称为二叉树的遍历。访问的含义包括查询、打印、计算、修改等对结点的操作。4.二叉树的遍历第61页/共222页62常用的遍历方法：

1.前(先)序遍历

DLR2.中序遍历

LDR3.后序遍历

LRD4.按层次遍历遍历规则注：指访问的结点D是先于子树出现还是后于子树出现。以根结点为参照系根左子树右子树第62页/共222页63原则若被遍历的二叉树为空，则空操作否则1.访问根结点2.以前序遍历原则遍历根结点的左子树3.以前序遍历原则遍历根结点的右子树二、前序遍历(PreorderTraversal)递归第63页/共222页64BACFDEGHA遍历序列：BCFDEGH(1)访问根结点；(2)前序遍历左子树；(3)前序遍历右子树。二、前序遍历(PreorderTraversal)第64页/共222页65三、中序遍历(InorderTraversal)原则若被遍历的二叉树为空，则空操作否则1.以中序遍历原则遍历根结点的左子树2.访问根结点3.以中序遍历原则遍历根结点的右子树递归第65页/共222页66遍历序列：(1)中序遍历左子树；(2)访问根结点；(3)中序遍历右子树。BACFDEGHABCFDEGH三、中序遍历(InorderTraversal)第66页/共222页67四、后序遍历(PostorderTraversal)原则若被遍历的二叉树为空，则空操作否则1.以后序遍历原则遍历根结点的左子树2.以后序遍历原则遍历根结点的右子树3.访问根结点递归第67页/共222页68遍历序列：(1)后序遍历左子树；(2)后序遍历右子树；(3)访问根结点。BACFDEGHABCFDEGH四、后序遍历(PostorderTraversal)第68页/共222页69二叉树的其它操作：广度优先遍历BACFDEGHA遍历序列：BCFDEGH广度优先遍历(也叫层次遍历)(1)按结点所在层次，由低层向高层依次遍历；(2)同层按自左向右次序遍历。第69页/共222页70二叉树的其它操作：广度优先遍历

二叉树的层序遍历算法：

(1)初始化设置一个队列；

(2)把根结点指针入队列；

(3)当队列非空时，循环执行步骤(a)到步骤(c):(a)出队列取得一个结点指针，访问该结点；

(b)若该结点的左子树非空，则将该结点的左子树指针入队列；

(c)若该结点的右子树非空，则将该结点的右子树指针入队列；

(4)结束。第70页/共222页71(1)从根开始：若二叉树非空，则根入队；(2)队头出队，并访问；BA^C^D^E^G^^F^^H^T排队处遍历序列思路：ApBC(3)若当前结点有左子树，则其左子树的根入队；(4)若当前结点有右子树，则其右子树的根入队；(5)重复(2)~(4)，DEpFpGHppp直至队空。第71页/共222页72算法：StatusLevelOrderTraverse(biTree*T){InitQueue(Q);AddQueue(Q,T);//树根入队

while(!QueueEmpty(Q))//只要队列非空

{DeleteQueue(Q,p);//出队一个结点

if(!Visit(p->data))returnERROR;//访问之

if(p->lchild)AddQueue(Q,p->lchild);

//左孩子入队

if(p->rchild)AddQueue(Q,p->rchild);

//右孩子入队

}

returnOK;}第72页/共222页73二叉树的遍历:算法回忆一下递归算法的适用情况(1)问题本身直接用递归定义的(2)问题的规律有递归的特点二叉树及其遍历是用递归定义的用递归算法肯定可以解决如果不用递归呢？第73页/共222页74二叉树的前序遍历递归算法若二叉树为空，则算法结束；否则：(1)访问根结点；(2)前序遍历根结点的左子树；(3)前序遍历根结点的右子树。voidPreOrderTraverse(bitree*T){if(T)二叉树非空

{printf("\t%c\n",T->data);访问根结点

PreOrderTraverse(T->lchild);前序遍历左子树

PreOrderTraverse(T->rchild);前序遍历右子树

}}第74页/共222页75二叉树的中序遍历递归算法若二叉树为空，则算法结束；否则：(1)中序遍历根结点的左子树；(2)访问根结点；(3)中序遍历根结点的右子树。voidInOrderTraverse(bitree*T){if(T){

InOrderTraverse(T->lchild);printf("\t%c\n",T->data);InOrderTraverse(T->rchild);}}第75页/共222页76二叉树的后序遍历递归算法若二叉树为空，则算法结束；否则：(1)后序遍历根结点的左子树；(2)后序遍历根结点的右子树；(3)访问根结点。voidPostOrderTraverse(bitree*T){if(T){PostOrderTraverse(T->lchild);PostOrderTraverse(T->rchild);

printf("\t%c\n",T->data);

}}第76页/共222页771.递归算法的优点(1)问题的数学模型或算法设计方法本身就是递归的，采用递归算法来描述它们非常自然；(2)描述直观，结构清晰、简洁；正确性证明比非递归算法容易。2.递归算法的不足(1)算法的执行时间与空间开销往往比非递归算法要大，当问题规模较大时尤为明显；(2)对算法进行优化比较困难；(3)分析跟踪算法的执行过程比较麻烦；(4)描述算法的语言不具有递归功能时，算法无法描述。谨慎使用递归，因为它的简洁可能会掩盖它的低效率。五、递归问题的非递归算法的设计第77页/共222页78五、递归问题的非递归算法的设计回顾遍历的过程(以中序为例)1先走到最左2往回访问父结点3往右访问右子树3.1走到最左3.2回访父结点3.3访问右子树

...ABCDEFG第78页/共222页79二叉树的遍历：非递归算法ABCDEFG当向左/右走到底时怎么办？需要返回到祖先哪个祖先？路过的却未访问的最近的祖先这就需要一种机制能记录访问的“历史信息”:路过却未访问的结点，以便能够回溯回去这就需要一个栈存放来这些祖先第79页/共222页80EH二叉树的遍历：非递归算法(1)非空树从根开始；(2)若当前结点存在，则暂存，p下到左子树；否则回退→访问当前结点→p下到右子树中序遍历非递归思路：BA^C^D^E^G^^F^^H^TpA栈SBDp^p遍历序列：Dp^pBGp^Gpp^pEp^pHp^pACp^pCFp^pFp^(3)重复(2)直到p空且栈空第80页/共222页81Stack[0..M-1]--保存遍历过程中结点的地址；top--栈顶指针，初始为-1；p--遍历过程中使用的指针变量，初始时指向根结点。用自然语言表达的算法1.若p指向的结点非空，则将p指的结点的地址进栈，然后，将p指向左子树的根；2.若p指向的结点为空，则从栈中退出栈顶元素送p，访问该结点，然后，将p指向右子树的根；重复上述过程，直到p为空，并且栈也为空。第81页/共222页82二叉树的中序遍历：非递归算法intInOrderT(bitree*T){bitree*p=T;SqStack*S;

InitStack(S);

//建栈

while(p||!StackEmpty(s))//还有未访问的

{if(p)//一直向左走到底，路过的所有的根入栈

{Push(S,p);p=p->lchild;

//遍历左子树

}else//p为NULL，说明走到了底

{Pop(S,p);Visit(p->data);

//弹出一个还没访问的结点，访问之

p=p->rchild;//遍历右子树

}}returnOK;}p指向树根p走到了底，再依次弹出刚才路过却没有访问的结点，访问之，然后p向右走第82页/共222页83时间复杂度n个结点，每一个都要访问一次显然时间复杂度为O(n)(这里n为结点数)空间复杂度不论是递归还是非递归算法都要用到栈栈的最大深度=树的深度所有空间复杂度为O(n)(这里n为树的深度)二叉树的遍历：算法效率第83页/共222页84二叉树的初始化算法的基本思想:创建二叉树的头结点。程序实现：voidInitiate(bitree**root){*root=(bitree*)malloc(sizeof(bitree));(*root)->lchild=NULL;(*root)->rchild=NULL;}root是指向根指针的指针第84页/共222页85按前序构造二叉链表例1：按下列次序输入字符(φ表示空格):ABCφφDEφGφφFφφφ

A^B^C^D^E^F^^G^二叉链表为:例2：HGφFφφMφφrootH^G^M^^F^第85页/共222页86按前序构造二叉链表的算法voidCreateBT(bitree**P){charch;ch=getchar();/*从键盘上输入一个字符*/

if(ch=='')*P=NULL;else{*P=(bitree*)malloc(sizeof(bitree));(*P)->data=ch;CreateBT(&((*P)->lchild));CreateBT(&((*P)->rchild));}}P是指向根指针的指针，*P的值发生变化后可以返回第86页/共222页87前序遍历序列：A,B,D,K,J,G,C,F,I,E,H中序遍历序列：D,B,G,J,K,A,F,I,E,C,H后序遍历序列：D,G,J,K,B,E,I,F,H,C,A按层次遍历序列：A,B,C,D,K,F,H,J,I,G,E第87页/共222页88第88页/共222页89前序序列：中序序列：后序序列：ABIFCGDEHFIBCGADEHFIGCBHEDA第89页/共222页90利用前序序列和中序序列恢复二叉树利用中序序列和后序序列恢复二叉树利用前序序列和后序序列恢复二叉树前序序列：A,B,D,C后序序列：D,B,C,A第90页/共222页91六、由遍历序列恢复二叉树前序序列：

A,B,D,E,J,C,F,I,G中序序列：

D,B,J,E,A,F,I,C,G第91页/共222页92已知前序序列和中序序列，恢复二叉树

在前序序列中寻找根；到中序序列中分左右。规律已知中序序列和后序序列，恢复二叉树

在后序序列中寻找根；到中序序列中分左右。第92页/共222页93例:已知结点的前序序列和中序序列分别为：前序序列：ABDEGHCF

中序序列：DBGEHACF求此二叉树六、由遍历序列恢复二叉树第93页/共222页94由已知的前序序列和中序序列构造二叉树的方法ABD前序EGHCFDBG中序EHACFA012345左子树右子树左子树右子树六、由遍历序列恢复二叉树第94页/共222页95ABD前序EGHCFDBG中序EHACFAB01左右左右D由已知的前序序列和中序序列构造二叉树的方法六、由遍历序列恢复二叉树第95页/共222页96ABD前序EGHCFDBG中序EHACFBADE01左左右右GH由已知的前序序列和中序序列构造二叉树的方法六、由遍历序列恢复二叉树第96页/共222页97ABD前序EGHCFDBG中序EHACFBACFDEGH0右右由已知的前序序列和中序序列构造二叉树的方法六、由遍历序列恢复二叉树第97页/共222页98(1)由前序序列得根；(2)在中序序列中查找根，并确定左子树中结点个数；(3)分别确定左、右子树的前序序列和中序序列；(4)分别构造左、右子树六、由遍历序列恢复二叉树由已知的前序序列和中序序列构造二叉树的方法第98页/共222页99已知二叉树的1.前序序列ABDFCEHG

中序序列DBFAHECG请构造该二叉树。2.后序序列DMFBHELGCA

中序序列DBMFAHECGL请构造该二叉树。自测题第99页/共222页100

一棵二叉树的前序、中序和后序序列如下，其中有部分未标出，试构造出该二叉树。前序序列为：__CDE_GHI_K中序序列为：CB__FA_JKIG后序序列为：_EFDB_JIH_A自测题第100页/共222页101试找出满足下列条件的二叉树1)前序序列与后序序列相同2)中序序列与后序序列相同3)前序序列与中序序列相同4)前序、中序、后序序列均相同5)中序序列与层次遍历序列相同自测题第101页/共222页102一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是()。A.CABDEFGB.ABCDEFGC.DACEFBGD.ADCFEGB自测题第102页/共222页103一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足()。A.其中任意一个结点均无左孩子B.其中任意一个结点均无右孩子C.其中只有一个叶子结点D.其中度为2的结点最多为一个E.空或只有一个结点F.高度等于其结点数自测题第103页/共222页104注意：

一个二叉树的遍历序列不能决定一棵二叉树，但前序（或后序）和中序遍历序列的组合可以唯一确定一棵二叉树。而前序和后序遍历则不能。口诀：DLR—前序遍历，即先根再左再右LDR—中序遍历，即先左再根再右LRD—后序遍历，即先左再右再根第104页/共222页105例6.1给二叉树中某个指定结点插入一个左结点

算法思想:

若当前结点(假设为curr)非空，在curr的左子树插入元素值为x的新结点，原curr所指结点的左子树成为新插入结点的左子树。若插入成功返回新插入结点的指针，否则返回空指针。二叉树操作举例第105页/共222页106bitree*InsertLeftNode(bitree*curr,datatypex){bitree*s,*t;if(curr==NULL)returnNULL;

t=curr->lchild;s=(bitree*)malloc(sizeof(bitree));s->data=x;s->lchild=t; s->rchild=NULL;

curr->lchild=s; returncurr->lchild;}第106页/共222页107算法思想:

若curr非空，删除curr所指结点的左子树。若删除成功，返回删除结点的双亲结点指针，否则返回空指针。例6.2删除二叉树中指定结点的左子树bitree*DeleteLeftTree(bitree*curr){if(curr==NULL||curr->lchild==NULL)returnNULL;free(curr->lchild);curr->lchild=NULL;returncurr;}第107页/共222页108例6.3求二叉树深度算法思想:

从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，并将所得的左、右子树深度的最大值加1。第108页/共222页109intBTreeDepth(bitree*BT){intleftdep,rightdep;if(BT==NULL)return(0);//空二叉树

else{leftdep=BTreeDepth(BT->lchild);rightdep=BTreeDepth(BT->rchild);if(leftdep>rightdep)return(leftdep+1);elsereturn(rightdep+1);}第109页/共222页110例6.4统计叶子结点数（1）算法思想:

中序(或前序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。由此，需在遍历算法中增添一个“计数”的参数，并将遍历算法中“访问结点”的操作改为：若是叶子，则计数器增1。第110页/共222页111intnum=0;//全局变量voidLeafCount(bitree*BT){if(BT){LeafCount(BT->lchild);//中序遍历左子树

if(!BT->lchild&&!BT->rchild)num++;

//叶子结点计数

LeafCount(BT->rchild);//中序遍历右子树

}}第111页/共222页112例6.4统计叶子结点数（2）intleafcount(bitree*BT){if(!BT)return(0);//空树没有叶子

else//只有根结点

if(!BT->lchild&&!BT->rchild)return(1);

elsereturn//左子树叶子数加上右子树叶子数

(leafcount(BT->lchild)+leafcount(BT->rchild));}第112页/共222页113例6.5交换所有结点的左右子树voidSubtree_Revolute(bitree*T){bitree*p;if(T){p=T->lchild;T->lchild=T->rchild;T->rchild=p;Subtree_Revolute(T->lchild);Subtree_Revolute(T->rchild);}}第113页/共222页114例6.6求二叉树的结点个数intnodecount(bitree*BT){if(BT==NULL)return(0);//空二叉树

elsereturn(nodecount(BT->lchild)+nodecount(BT->rchild)+1);}第114页/共222页115例6.7求二叉树的非叶子结点个数intnotleafcount(bitree*BT){if(!BT)return(0);//空二叉树

else//只有根结点

if(!BT->lchild&&!BT->rchild)return(0);elsereturn(notleafcount(BT->lchild)+notleafcount(BT->rchild)+1);}第115页/共222页116例6.8设一棵二叉树中各结点的值互不相同，其前序序列和中序序列分别存于两个一维数组pre[1..n]和mid[1..n]中，试遍写算法建立该二叉树的二叉链表。第116页/共222页117"ABDEGHCF"02134567pre"DBGEHACF"02134567mid1.由前序序列得根2.若序列中多于1个元素，则在中序序列中查找根（定位根在字符串中第一次出现的位置），并确定左子树中结点个数；makeT(pre,mid)第117页/共222页1184.分别构造左、右子树

r.lchild=makeT(lpre,lmid); r.rchild=makeT(rpre,rmid);3.分别确定左、右子树的前序序列和中序序列

lpre=pre(1,i-1); rpre=pre(i,n); lmid=mid(0,i-1); rmid=mid(i,m);第118页/共222页119

已知具有n个结点的完全二叉树采用顺序存储结构，结点的数据信息依次存放于一维数组BT[1..n]中，写出中序遍历二叉树的非递归算法。第119页/共222页120BT[1..6]ABCDEF123456中序序列：DBEAFC第120页/共222页121Stack[0..M-1]--保存遍历过程中结点的位置；top--栈顶指针，初始为-1；i--遍历过程中使用的位置变量，初始时指向根结点。i=1,BT[1]1.若i指向的结点非空，则将i进栈，然后，将i指向左子树的根；2.若i指向的结点为空，则从堆栈中退出栈顶元素送i，访问该结点，然后，将i指向右子树的根；重复上述过程，直到i为空，并且堆栈也为空。i=2*i;i=2*i+1;第121页/共222页122#defineMaxN100voidINORDER(datatypeBT[],intn){intStack[MaxN],i=1,top=-1;if(n>=0){do{while(i<=n){Stack[++top]=i;/*BT[i]的位置进栈*/i=i*2;}/*找到i的左孩子的位置*/i=Stack[top--];/*退栈*/VISIT(BT[i]);/*访问结点BT[i]*/i=i*2+1;/*找到i的右孩子的位置*/}while(i<n||top>=0);}}第122页/共222页123二叉树的其它操作建议思考以下问题：求二叉树中只有一个孩子的结点个数求二叉树中有两个孩子的结点个数复制一棵二叉树交换一棵二叉树的所有左右子树第123页/共222页124二叉树的操作本节小结深度优先遍历（包括前、中、后序）手工能写出前、中、后序遍历的结果要求能够写出递归和非递归的算法广度优先遍历了解其算法：为什么要用队列其它操作能把握大致方向：借助深度优先遍历、递归、广度优先遍历等第124页/共222页1255.线索二叉树一、线索二叉树的提出

二叉树的任何一种遍历，其实质均为对非线性结构的线性化。若将遍历序列中所体现的结点间的线性关系，保存在二叉树的存储结构中，则称线索二叉树。第125页/共222页1265.线索二叉树241356897【例】设二叉树Ｔ如图，则其中序遍历序列为：④⑦②⑧⑤⑨①③⑥【问题】

如何保存结点在遍历序列中的线性关系。第126页/共222页127

方案一在二叉链表中每个结点上增加两个指针域，分别用以指向该结点在遍历序列中的直接前驱和直接后继。5.线索二叉树二叉树Ｔ的中序遍历序列为：④⑦②⑧⑤⑨①③⑥21^3^4

5^8^^6^^9^T^7^^^21^3^4

5^8^^6^^9^T^7^第127页/共222页128

方案二5.线索二叉树利用二叉链表中的空链域保存结点间的线性关系：若结点的lchild域为空，则保存指向其直接前驱的指针；若结点的rchild域为空，则用于保存指向其直接后继的指针。为此，每个结点还需另设两个标志域，用以指明该结点的lchild域(rchild域)中所保存的指针是指向其左(右)孩子的，还是指向其直接前驱(直接后继)的。第128页/共222页129二叉树Ｔ的中序遍历序列为：④⑦②⑧⑤⑨①③⑥5.线索二叉树21^3^4

5^8^^6^^9^T^7^21345869T700000000^^^^^^^^^^1111111111第129页/共222页130二、什么是线索二叉树

利用二叉链表中空的指针域指出结点在某种遍历序列中的直接前驱和直接后继。指向前驱和后继的指针称为线索，加了线索的二叉树称为线索二叉树。三、线索二叉树的构造

利用链结点的空的左指针域存放该结点的直接前驱的地址，空的右指针域存放该结点的直接后继的地址；而非空的指针域仍然存放结点的左孩子或右孩子的地址。第130页/共222页131对下图按照中序遍历进行线索化中序遍历的结果为：a+b*c-d-e/f称作中序线索二叉树NULLNULL第131页/共222页132对下图按照前序遍历进行线索化前序遍历的结果为：-+a*b-cd/ef称作前序线索二叉树NULL第132页/共222页133对下图按照后序遍历进行线索化后序遍历的结果为：abcd-*+ef/-称作后序线索二叉树NULL第133页/共222页134线索二叉树：结点的结构现在lchild有2个功能(1)指向左孩子(2)指向前驱结点如何区别呢？增加一个标记ltag说明其当前的功能当ltag=0时：指向左孩子，是指针当ltag=1时：指向前驱结点，是线索rchild类似处理lchildltagdatartagrchild第134页/共222页135线索二叉树：结点类型定义lchildltagdatartagrchildtypedefintdatatype;typedefstructnode{

datatypedata;

structnode*lchild,*rchild;intltag,rtag;}bithptr;第135页/共222页136例：带了两个标志的某前序遍历结果如下表所示，请画出对应的二叉树。dataAGEIDJHCFBLtag0011110101Rtag0001010111AAGEIDJHCFBTag=1表示线索:Ltag=1表示前驱Rtag=1表示后继第136页/共222页1371a10*01e11f11b10-01c11d10+00/00-0??中序线索二叉树:a+b*c-d-e/f第137页/共222页1381a10*01e11f11b10-01c11d10+00/00-0头结点01第138页/共222页139线索二叉树：中序线索二叉树的遍历线索化二叉树的目的就在于方便遍历增加头结点lchild是指针：指向树根rchild是线索：指向中序遍历序列的尾结点同时中序遍历序列中的首结点的lchild和尾结点的rchild都是一个线索：都指向头结点这样就能方便的进行中序和逆向中序遍历了第139页/共222页140例：在中序线索二叉树中查找结点p的后继结点二叉树中序遍历序列:a+b*c-d当rtag=1时，后继就是p->rchild；当rtag=0时，说明p有右子树，必须沿着p的右子树的根的左子树方向查找，直到某结点的lchild域为线索(即，p右子树中最左下角的结点)，此结点就是p结点的后继。p四、线索二叉链表的应用+-*abdc第140页/共222页141中序线索二叉树查找结点p的后继结点算法bithptr*InOrderNext(bithptr*p){bithptr*q;if(p->rtag==1)return(p->rchild);else{q=p->rchild;

while(q->ltag==0)q=q->lchild;return(q);}}+-*abdc第141页/共222页回顾二叉树的中序遍历：非递归算法intInOrderT(bitree*T){bitree*p=T;SqStack*S;

InitStack(S);

∥建栈

while(p||!StackEmpty(s)){if(p){Push(S,p);∥二叉树非空，根结点进栈

p=p->lchild;

∥遍历左子树

}else{Pop(S,p);Visit(p->data);p=p->rchild;∥遍历右子树

}}returnOK;}第142页/共222页143中序线索二叉树的遍历(顺后继进行)基本思想第一个访问的结点应该是最左下角的结点(假设为p)然后p的后继是谁？若p->rchild是指针(0)，说明p有右子树，下一个结点应该是p右子树中最左下角的结点若p->rchild是线索(1)，直接访问p->rchild如此循环往复...第143页/共222页144中序线索二叉树的遍历算法intInOrderTraverse_Thr(bithptr*T){p=T->lchild;//p指向树根

while(p!=T)//p等于T则说明已经遍历完毕

{while(p->ltag==0)//p->lchild为指针

p=p->lchild;//则向左下走到底

Visit(p->data);//访问p

while(p->rtag==1&&p->rchild!=T)//p->rchild为线索

{p=p->rchild;

Visit(p->data);//访问p}p=p->rchild;//向右继续遍历

}

returnOK;}第144页/共222页145中序线索二叉树的遍历思考：如果反方向进行遍历呢(顺前驱进行)？第一个访问的结点应该是最右下角的结点(假设为p)然后p的前驱是谁？若p->lchild是指针，说明p有左子树，前驱应该是p左子树中最右下角的结点若p->lchild是线索，直接访问p->lchild如此循环往复...第145页/共222页146以后序线索二叉树为例第一个访问的应该是最左下角的结点(假设为p)，p的后继是谁？p线索二叉树：前/后序线索二叉树的遍历第146页/共222页147解答若p->rchild是线索则后继就是p->rchild否则若p是树根，则无后继若p是右孩子或者是唯一的左孩子，则后继是其父结点若p是左孩子，且有右兄弟，则后继是p的父结点的右子树中第一个访问的结点pppp线索二叉树：前/后序线索二叉树的遍历第147页/共222页148线索二叉树：前/后序线索二叉树的遍历困难对于后序线索二叉树，想要找结点p的后继结点，可能需要知道p的父结点是谁可是这是很难办到的两种方法从树根开始查找改用三叉链表来表示二叉树此困难对于后序线索二叉树找前驱结点、前序线索二叉树找后继/前驱结点同样存在p第148页/共222页149五、线索二叉树：二叉树的线索化普通的二叉树怎么变成线索二叉树？称作线索化基本思想线索其实就是按照遍历的顺序把闲置的指针链接到前驱/后继结点：遍历过程中维护两个指针：pre和p，分别指向遍历序列中一前一后的两个结点若pre->rchild闲置，pre->rchild=p若p->lchild闲置，p->lchild=pre第149页/共222页150StatusInOrderThreading(Bitree*Thrt,Bitree*T){Thrt=(Bitree*)malloc(sizeof(bithptr));//头结点

if(!Thrt)exit(OVERFLOW);Thrt->ltag=0;//头结点的lchild是指针

Thrt->rtag=1;//头结点的rchild是线索

if(!T)//若T为空树，头结点的左右指针回指

{Thrt->lchild=Thrt;Thrt->rchild=Thrt;}else{Thrt->lchild=T;

//头结点的lchild指向树根

pre=Thrt;

//pre是全局变量

InThreading(T);

//调用中序线索化函数处理二叉树Tpre->rchild=Thrt;//InThreading调用完以后

pre->rtag=1;//就差最后一个结点没有链接好

Thrt->rchild=pre;//此时，pre指向最后一个结点

}returnOK;}创建中序线索二叉树的头结点头结点与树根之间的连接修改中序遍历的最后一个结点与头结点之间的连接第150页/共222页151voidInThreading(Bitree*p){if(p){//p为空则返回

InThreading(p->lchild);//左子树线索化

if(!p->lchild){//若p->lchild闲置

p->lchild=pre;p->ltag=1;}if(!pre->rchild){//若pre->rchild闲置

pre->rchild=p;pre->rtag=1;}pre=p;//维持pre和p一前一后的关系

InThreading(p->rchild);//右子树线索化

}}第151页/共222页152voidInThreading(Bitree*p){if(p)

{InThreading(p->lchild);if(!p->lchild){p->lchild=pre;p->ltag=1;}

if(!pre->rchild){pre->rchild=p;pre->rtag=1;}

pre=p;InT