数据结构 第6章 树和二叉树.ppt

第6章 树和二叉树,6.1 树的定义和基本概念6.2 二叉树 6.2.1 二叉树的定义和基本术语 6.2.2 二叉树的性质 6.2.3 二叉树的存储结构6.3 遍历二叉树 6.3.1 遍历二叉树 6.3.2 线索二叉树 6.4 树和森林 6.4.1 树的存储结构 6.4.2 森林与二叉树的转换 6.5 哈夫曼树及其应用,树型结构是一类重要的非线性结构。树型结构是结点之间有分支，并且具有层次关系的结构，它非常类似于自然界中的树。树结构在客观世界是大量存在的，例如家谱、行政组织机构都可用树形象地表示。树在计算机领域中也有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，可用树来组织信息；在分析算法的行为时，可用树来描述其执行过程。等等。,6.1 树的定义和基本操作 一树的定义 定义：树(Tree)是n(n=0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：（1）有且仅有一个特定的称为根(Root)的结点；（2）其余的结点可分为m(m=0)个互不相交的子集T1,T2,T3Tm，其中每个子集又是一棵树，并称其为子树(Subtree)。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。由此可知，树的定义是一个递归的定义，即树的定义中又用到了树的概念。,在图6-1(c)中，树的根结点为A，该树还可以分为三个互不相交子集T0，T1，T2，具体请参见图6-2，其中T0=B，E，F，J，K，L，T1=C，G，T2=D，H，I，M，其中的T0，T1，T2都是树，称为图6-1（C）中树的子树，而T0，T1，T2又可以分解成若干棵不相交子树。如T0可以分解成T00，T01两个不相交子集，T00=E，J，K，L，T01=F，而T00又可以分为三个不相交子集T000，T001，T002，其中，T000=J，T001=K，T002=L。,二树的逻辑结构描述 一棵树的逻辑结构可以用二元组描述为：tree=(k,R)k=ki1in;n0,kielemtype R=r其中，k是具有相同特性的数据元素的集合;n为树中结点个数，若 n=0，则为一棵空树，n 0时称为一棵非空树，而关系 r 应满足下列条件：（1）有且仅有一个结点没有前驱,称该结点为树根;（2）除根结点以外,其余每个结点有且仅有一个直接前驱;（3）树中每个结点可以有多个直接后继(孩子结点)。例如，对图6-1(c)的树结构,可以二元组表示为：K=A，B，C，D，E，F，G，H，I，J，K，L，M R=r r=(A,B)，(A,C)，(A,D)，(B,E)，(B,F)，(C,G)，(D,H)，(D,I)，(E,J)，(E,K)，(E,L)，(H,M),四、基本术语1.结点：指树中的一个数据元素，一般用一个字母表示。度：一个结点包含子树的数目，称为该结点的度。树中结点度的最大值称为树的度。3.树叶（叶子）：度为0的结点，称为叶子结点或树叶，也叫终端结点。4.孩子结点：若结点X有子树，则子树的根结点为X的孩子结点，也称为孩子，儿子，子女等。如图6-1（c）中A的孩子为B，C，D。5.双亲结点：若结点X有子女Y，则X为Y的双亲结点。6.祖先结点：从根结点到该结点所经过分枝上的所有结点为该结点的祖先，如图6-1（c）中M的祖先有A，D，H。7.子孙结点：某一结点的子女及子女的子女都为该结点子孙。8.兄弟结点：具有同一个双亲的结点，称为兄弟结点。,9.分枝结点：除叶子结点外的所有结点，为分枝结点，也叫非终端结点。10层数：根结点的层数为1，其它结点的层数为从根结点到该结点所经过的分支数目再加1。11.树的高度（深度）：树中结点所处的最大层数称为树的高度，如空树的高度为0，只有一个根结点的树高度为1。12.有序树：若一棵树中所有子树从左到右的排序是有顺序的，不能颠倒次序。称该树为有序树。13.无序树：若一棵树中所有子树的次序无关紧要，则称为无序树。14森林（树林）：若干棵互不相交的树组成的集合为森林。一棵树可以看成是一个特殊的森林。,五树的基本运算(1)inittree(T)初始化树T。(2)root(T)求树T的根结点。(3)parent(T,x)求树T中，值为x的结点的双亲。(4)child(T,x,i)求树T中，值为x的结点的第i个孩子。(5)addchild(y,i,x)把值为x的结点作为值为y的结点的第i个孩子插入到树中。(6)delchild(x,i)删除值为x的结点的第i个孩子。(7)traverse(T)遍历或访问树T。,树的存储结构,在计算机中，树的存储通常采用顺序存储结构和链式存储结构，但无论采用何种存储方式，都要求存储结构不但能存储各结点本身的数据信息，还要能唯一地反映树中各结点之间的逻辑关系,1.双亲结点数组表示法,#define Maxnode 100/*树中结点的最大个数*/typedef struct elemtype data；int parent；NodeType；NodeType TMaxnode；,孩子表示法,一、多重链表法,由于树中每个结点都有零个或多个孩子结点，因此，可以令每个结点包括一个结点信息域和多个指针域，每个指针域指向该结点的一个孩子结点，通过各个指针域值反映出树中各结点之间的逻辑关系。在这种表示法中，树中每个结点有多个指针域，形成了多条链表，所以这种方法又常称为多重链表法。在一棵树中，各结点的度数各异，因此结点的指针域个数的设置有两种方法：每个结点指针域的个数等于该结点的度数；每个结点指针域的个数等于树的度数。,二、孩子链表表示法 为树的每个节点建立一个孩子链表。孩子链表表示法是将树按图5.3所示的形式存储。其主体是一个与结点个数一样大小的一维数组，数组的每一个元素有两个域组成，一个域用来存放结点信息，另一个用来存放指针，该指针指向由该结点孩子组成的单链表的首位置。单链表的结构也由两个域组成，一个存放孩子结点在一维数组中的序号，另一个是指针域，指向下一个孩子。,这种存储表示可描述为：#define Maxnode 100/*树中结点的最大个数*/typedef struct int childcode；struct ChildNode*nextchild；ChildNode typedef struct elemtype data；ChildNode*firstchild；NodeType；NodeType tMaxnode；,双亲孩子表示法,双亲表示法仍将各结点的孩子结点分别组成单链表，同时用一维数组顺序存储树中的各结点，数组元素除了包括结点本身的信息和该结点的孩子结点链表的头指针之外，还增设一个域，存储该结点双亲结点在数组中的序号的树,孩子兄弟表示法,在树中，每个结点除其信息域外，再增加两个分别指向该结点的第一个孩子结点和下一个兄弟结点的指针。在这种存储结构下，树中结点的存储表示可描述为：typedef struct TreeNode elemtype data；struct TreeNode*fch，*nsib；NodeType；,6.2 二叉树 二叉树在树结构的应用中起着非常重要的作用，因为对二叉树的许多操作算法简单，而任何树都可以与二叉树相互转换，这样就解决了树的存储结构及其运算中存在的复杂性。6.2.1 定义与基本操作定义：二叉树是由n(n=0)个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。这也是一个递归定义。二叉树可以是空集合，二叉树的特点是每个结点最多有两个孩子，或者说，在二叉树中，不存在度大于2的结点，并且二叉树是有序树。,二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。这是二叉树与树的最主要的差别。图6.5列出二叉树的5种基本形态，图6.5(C)和图6.5（d）是不同的两棵二叉树。,(a)空二叉树,A,A,B,A,B,A,C,B,(b)根和空的左右子树,(c)根和左子树,(d)根和右子树,(e)根和左右子树,图6.5 二叉树的5种形式,6.2.2 二叉树的性质二叉树具有下列重要性质：性质1：在二叉树的第i层上至多有2i-1个结点(i1)。证明:用归纳法当i=1,即第一层只有一个根结点,显然 2i-1=20=1成立假设i-1时命题成立，即第i-1层至多有2 i-2个结点，则取i 时，由于二叉树中每个结点至多有两个孩子，故第i层上的结点数最多是第i-1层上最多结点数的2倍，即取i时，该层上至多有22 i-2=2 i-1个结点。命题成立。,性质2.深度为k的二叉树至多有2k-1个结点(k1)。（深度一定，二叉树的最大结点数也确定）证明：深度为k的二叉树，若要求结点数最多，则必须每一层的结点数都为最多，由性质1可知，最大结点数应为每一层最大结点数之和。既为 20+21+2k-1=2k-1,性质3.对任意一棵二叉树，如果叶子结点个数为n0，度为2的结点个数为n2，则有n0=n2+1。证明：设二叉树中度为1的结点数为n1，二叉树中总结点数为N，因为二叉树中所有结点均小于或等于2，所以有：Nn0n1n2(6-1)再看二叉树中的分支数，除根结点外，其余结点都有一个进入分支，设B为二叉树中的分支总数，则有：NB1。由于这些分支都是由度为1和2的结点射出的，所以有：Bn1+2*n2 NB1n12n21(6-2)由式（61）和（62）得到：n0+n1+n2=n1+2*n2+1 n0n21,下面介绍两种特殊形态的二叉树：满二叉树和完全二叉树。一棵深度为k且由2k-1个结点的二叉树称为满二叉树。下图就是一棵满二叉树。对结点进行了顺序编号，如果深度为k、由n个结点的二叉树中的结点能够与深度为k的顺序编号的满二叉树从1到n标号的结点相对应，则称这样的二叉树为完全二叉树。满二叉树是完全二叉树的特例。完全二叉树的特点是：（1)所有的叶结点都出现在第k层或k1层。（2）对任一结点，如果其右子树的最大层次为L，则其左子树的最大层次为L或L1。,性质4：具有n个结点的完全二叉树高度为log2(n)+1(注意 x 表示取不大于x的最大整数，读作对x下取整，x表示取不小于x的最小整数，读作对x上取整。)证明：设该完全二叉树高度为k，则该二叉树的前面k-1层为满二叉树，共有2k-1-1个结点，而该二叉树具有k层，第k层至少至少有1个结点，最多有2k-1个结点。因此有下面的不等式成立：（2k-1 1）+1 n（2k-1-1）+2k-1，即有 2k-1n2k。于是 k-1 log2nk，由于k是整数，则k=log2 n+1证毕。,性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号（从第1层到第log2n+1层，每层从左到右按顺序编号）,则对任一结点i（11，则其双亲是结点i/2。（2）如果2in，则结点i为叶子结点，无左孩子；否则，其左孩子是结点2i。（3）如果2i1n，则结点i无右孩子；否则，其右孩子是结点2i1。,证此性质可采用数学归纳法证明。因为1与2、3是相对应的，所以只需证明2和3，而且在此只需讨论有左孩子（2in）和有右孩子（2i+1n）的情况。当 i1时（i是根），根据结点编号方法可知，根的左、右孩子编号分别是2和3，结论成立。假定i-1时结论成立，即结点i-1的左右孩子编号满足：lchild（i-1）=2（i-1）rchild（i-1）=2（i-1）+1观察图5.8知，结点i或者与结点i-1同层且紧靠其右，或者结点i-1在某层最右端，而结点i在其下一层最左端。但是，无论如何，结点i的左、右孩子的编号都是紧接着结点i-1的右孩子的编号，故：lchild（i）=rchild（i-1）+1=2i rchild（i）=lchild（i）+1=2i+1 故命题成立。,根据完全二叉树的结构和编号规则，在i的左孩子前面的两个结点是结点i-1的左、右孩子，假设有：结点i-1的左孩子为2(i-1)，右孩子为2(i-1)+1。,.,.,i与 i+1同层,.,.,.,.,i与 i+1不同层,i-1,i-1,i的左孩子应为2i如果 2in,则编号为2i的结点不存在,即i无左孩子 而i的右孩子应为2i+1如果 2i+1n,则编号为2i+1的结点不存在,即i无右孩子（2）和（3）得证.最后证明:(1)i=1时，结点i是树的根；否则(i1)，结点i的双亲为结点i/2 当i=1时,显然根结点无双亲；当i1时，结点i可能是其双亲x的左孩子，也可能是右孩子，若是左孩子，由（3）知，x的左孩子应为2x，即2x=i，x=i/2若是右孩子，由（3）知，x的右孩子应为2x+1，即2x+1=i，x=(i-1)/2故 i的双亲为i/2 证毕,性质6.含有n个结点的二叉链表中，有n+1个空链域。证明：空链域数=2n0+n1 因为 n=n0+n1+n2(1)又有 n0=n2+1 即-1=n2-n0(2)（1）-（2）得 n+1=2n0+n1 故空链域数=n+1,6.2.3 二叉树的存储结构一.顺序存储结构 它是用一组连续的存储单元存储二叉树的数据元素。因此，必须把二叉树的所有结点安排成为一个恰当的序列，结点在这个序列中的相互位置能反映出结点之间的逻辑关系。通常是按照二叉树结点从上至下、从左到右的顺序存储，但这样结点在存储位置上的前驱后继关系并不一定就是它们在逻辑上的邻接关系，只有通过一些方法确定某结点在逻辑上的前驱结点和后继结点，这种存储才有意义。因此，依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可以唯一地反映出结点之间的逻辑关系，这样既能够最大可能地节省存储空间，又可以利用数组元素的下标值确定结点在二叉树中的位置，以及结点之间的关系。,1 2 3 4 5 6 7 8 9 10 11 12,完全二叉树,a,b,c,d,e,f,g,h,i,j,k,l,bt3的双亲为3/2=1，即在b t1中；其左孩子在bt2i=bt6中；其右孩子在bt2i+1=bt7中。,D,二叉树,C,G,F,E,B,A,1 2 3 4 5 6 7 8 9 10 11 A B C D E 0 0 0 0 F G,一般二叉树也按完全二叉树形式存储,只有增添一些并不存在的空结点（用0表示），使之成为一棵完全二叉树的形式，然后再用一维数组顺序存储。,这种存储结构适合于完全二叉树，既不浪费存储空间，又能很快确定结点的存放位置、以及结点的双亲和左右孩子的存放位置，但对一般二叉树，可能造成存储空间的浪费。例如，深度为k，且只有k个结点的右单枝树(每个非叶结点只有右孩子)，需2k-1个单元，即有2k-1-k个单元被浪费。,1,k,二、链式存储结构 所谓二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示着元素的逻辑关系。通常有下面两种形式。（1）二叉链表存储 链表中每个结点由三个域组成，除了数据域外，还有两个指针域，分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。,在n个结点的二叉链表中，有n+1个空指针域,（2）三叉链表存储 每个结点由四个域组成，其中，data、lchild以及rchild三个域的意义同二叉链表结构；parent域为指向该结点双亲结点的指针。这种存储结构既便于查找孩子结点，又便于查找双亲结点；但是相对于二叉链表存储结构而言，它增加了空间开销。,三、二叉链表存储的描述typedef struct BiTNode elemtype data；struct BiTNode*lchild，*rchild；Bitnode，*Bitree；即将Bitree定义为指向二叉链表结点结构的指针类型。尽管在二叉链表中无法由结点直接找到其双亲，但由于二叉链表结构灵活，操作方便，对于一般情况的二叉树，甚至比顺序存储结构还节省空间。因此，二叉链表是最常用的二叉树存储方式。后面所涉及到的二叉树的存储结构不加特别说明的都是指二叉链表结构。,Initiate（bt）建立一棵空二叉树。Create（x，lbt，rbt）生成一棵以x为根结点的数据域信息，以二叉树lbt和rbt为左子树和右子树的二叉树。Insertlchild（bt，x，parent）将数据域信息为x的结点插入到二叉树bt中作为结点parent的左孩子结点。如果结点parent原来有左孩子结点，则将结点parent原来的左孩子结点作为结点x的左孩子结点。Insertrchild（bt，x，parent）将数据域信息为x的结点插入到二叉树bt中作为结点parent的右孩子结点。如果结点parent原来有右孩子结点，则将结点parent原来的右孩子结点作为结点x的右孩子结点。Deletelchild（bt，parent）在二叉树bt中删除结点parent的左子树。Deleterchild（bt，parent）在二叉树bt中删除结点parent的右子树。Search（bt，x）在二叉树bt中查找数据元素x。Traverse（bt）按某种方式遍历二叉树bt的全部结点。,四、二叉树的基本操作,五 算法的实现,下面讨论基于二叉链表存储结构的上述操作的实现算法。,1Initiate（bt）初始建立二叉树bt，并使bt指向头结点。在二叉树根结点前建立头结点，就如同在单链表前建立的头结点，可以方便后边的一些操作实现。Bitree Initiate（）/*初始化建立二叉树bt的头结点*/Bitree bt;if（bt=（Bitnode*）malloc（sizeof（Bitnode）=NULL）return 0；bt-lchild=NULL；bt-rchild=NULL；return bt；,2Create（x，lbt，rbt）建立一棵以x为根结点的数据域信息，以二叉树lbt和rbt为左右子树的二叉树。建立成功时返回所建二叉树结点的指针；建立失败时返回空指针。BiTree Create（elemtype x，Bitree lbt，Bitree rbt）/*生成一棵以x为根结点的数据域值以lbt和rbt为左右子树 的二叉树*/Bitree p；if（p=（Bitnode*）malloc（sizeof（Bitnode）=NULL）return NULL；p-data=x；p-lchild=lbt；p-rchild=rbt；return p；算法 5.2,3Insertlchild（bt，x，parent）将数据域信息为x的结点插入到二叉树bt中作为结点parent的左孩子结点。如果结点parent原来有左孩子结点，则将结点parent原来的左孩子结点作为结点x的左孩子结点。BiTree Insertlchild（Bitree bt，elemtype x，Bitree parent）/*在二叉树bt的结点parent的左子树插入结点数据元素x*/Bitree p；if（parent=NULL）printf（“n插入出错”）；return NULL；if（p=（BiTNode*）malloc（sizeof（BiTNode）=NULL）return NULL；p-data=x；p-lchild=NULL；p-rchild=NULL；if（parent-lchild=NULL）parent-lchild=p；else p-lchild=parent-lchild；parent-lchild=p；return bt；,5Deletelchild（bt，parent）在二叉树bt中删除结点parent的左子树。当parent或parent的左孩子结点为空时删除失败。删除成功时返回根结点指针；删除失败时返回空指针。Bitree Deletelchild（Bitree bt，Bitree parent）/*在二叉树bt中删除结点parent的左子树*/Bitree p；if（parent=NULL|parent-lchild=NULL）printf（“n删除出错”）；return NULL p=parent-lchild；parent-lchild=NULL；free（p）；/*当p为非叶子结点时，这样删除仅释放了所删子树根结点的空间，*/*若要删除子树分支中的结点，需用后面介绍的遍历操作来实现。*/return br；,作业1.一棵深度为k的满二叉树的结点总数为2k-1，一棵深度为k的完全二叉树的结点总数的最小值为2k-1 最大值为2k-1 2.由a,b,c三个结点构成的二叉树，共有5种不同的结构。3.对于一个具有n个结点的二叉树，当它为一棵满二叉树时具有最小高度，即为log2(n)+1，当它为一棵单支树具有最大高度，即为n4.对于具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为2n个，其中n-1个用于链接孩子结点，n+1个空闲着,6.3 遍历二叉树和线索二叉树6.3.1遍历二叉树 一、定义：所谓遍历二叉树，就是遵从某种次序，访问二叉树中的所有结点，使得每个结点仅被访问一次。这里所提的“访问”的含义很广，可以是查询、修改、输出某元素的值，以及对元素作某种运算等等。但要求这种访问不破坏它原来的数据结构。遍历一个线性结构很简单，只须从开始结点出发，顺序扫描每个结点即可。但对二叉树这样的非线性结构，每个结点可能有两个结点，因此需要寻找一种规律来系统访问树中的各结点。,二、方法：1、递归遍历：由二叉树的定义是递归的，它是由三个基本单元组成，即根结点、左子树和右子树。因此，遍历一棵非空二叉树的问题可以分解为三个子问题：访问根结点、遍历左子树、遍历右子树，只要依次遍历这三部分，就可以遍历整个二叉树。在任一给定结点上，可以按某种次序执行三个操作：访问结点本身，遍历该结点左子树，遍历该结点右子树。由于实际问题一般都是要求左子树较右子树先遍历，分别称为先序遍历（先访问根结点，再遍历左子树，再遍历右子树）、中序遍历（先遍历左子树，再访问根结点，再遍历右子树）和后序遍历（先遍历左子树，再遍历右子树，最后访问根结点）。令L,R,D分别代表二叉树的左子树、右子树、根结点，则有DLR、LDR、LRD三种遍历规则。,先序遍历二叉树若二叉树非空，则：1）访问根结点 2)先序遍历左子树 3）先序遍历右子树,A,D,B,C,D L R,先序遍历序列：A B D C,返回,返回,返回,返回,A,C,B,D,返回,先序序列：A B D C,void Preorder（Bint bt）if（bt=NULL）return；/*递归调用的结束条件*/Visite（bt-data）;/访问结点的数据域 Preorder（bt-lchild）；/*先序 递归遍历bt的左子树*/Preorder（bt-rchild）；,中序遍历二叉树若二叉树非空，则：1）中序遍历左子树2）访问根结点 3）中序遍历右子树,L D R,中序遍历序列：B D A C,后序遍历二叉树若二叉树非空，则：1）后序遍历左子树 2）后序遍历右子树 3）访问根结点,L R D,后序遍历序列：D B C A,例如如图所示的二叉树表达式(a+b*(c-d)-e/f)若先序遍历此二叉树,按访问结点的先后次序将结点排列起来,其先序序列为：-+a*b-cd/ef 按中序遍历,其中序序列为：a+b*c-d-e/f按后序遍历,其后序序列为：abcd-*+ef/-,*,a,/,b,-,d,c,f,e,三种遍历过程示意图例,*,a,b,c,虚线表示执行过程:向下表示更深层的递归调用;向上表示递归调用返回;沿虚线记下各类符号,便得到遍历的结果.,2、非递归遍历：利用一个一维数组作为栈，来存储二叉链表中结点中序遍历算法思想为：从二叉树根结点开始，沿左子树一直走到末端(左孩子为空)为止，在走的过程中，把依次遇到的结点进栈,待左子树为空时,从栈中退出结点并访问,然后再转向它的右子树。如此重复，直到栈空且指针为空止。从二叉树的根结点开始，令变量P为根节点，若P不为空，则令P沿左子树根结点前进，在前进过程中，把所经历的结点逐个压入栈中，当P为空时，弹出栈顶元素给P,并访问该结点，再令P为当前结点的右子树根节点。重复上述步骤，当P为空且栈也为空时，遍历结束。,i,(1),i,P-A,P-B,(2),i,P-A,P-B,P-C,(3),p=NULL,i,P-A,P-B,访问：C,(4),i,P-A,访问：C B,(5),i,P-A,P-D,访问：C B,(6),i,P-A,P-D,P-E,访问：C B,(7),i,P-A,P-D,访问：C B E,(8),i,P-A,P-D,P-G,访问：C B E,P=NULL,(9),i,P-A,访问：C B E G D,(11),i,P-A,P-F,访问：C B E G D,(12),i,P-A,P-D,访问：C B E G,p,(10),i,P-A,访问：C B E G D F,p=NULL,(13),i,访问：C B E G D F A,(14),i,访问：C B E G D F A,p=NULL,(15),先序遍历算法思想为：从二叉树的根结点开始，令变量P为根节点，访问当前结点P，并将P压入栈中，然后令P为当前结点的左孩子根节点。若P不为空结点，继续访问当前结点P，并将P压入栈中。如此重复，直到P为空时，从栈中弹出栈顶元素赋给变量P,并令P为它当前指向结点的右孩子根结点，如此重复，当P为空且栈也为空时，遍历结束。,void NRPreOrder(BiTree:bt)BiTree stackMAXNODE,p;int top;if(bt=NULL)return 0;top=0;p=bt;while(!(p=NULL,后序遍历算法思想为：利用栈来实现二叉树的后序遍历要比前序和中序遍历复杂得多，在后序遍历中，当搜索指针指向某一个结点时，不能马上进行访问，而先要遍历左子树，所以此结点应先进栈保存，当遍历完它的左子树后，再次回到该结点，还不能访问它，还需先遍历其右子树,所以该结点还必须再次进栈，只有等它的右子树遍历完后，再次退栈时，才能访问该结点。为了区分同一结点的两次进栈，引入一个栈次数的标志，一个元素第一次进栈标志为0，第二次进标志为1，并将标志存入另一个栈中，当从标志栈中退出的元素为1时，访问结点。,三、遍历算法应用举例 例：由二叉树的前序序列和中序序列建立一个唯一的二叉树。分析：若二叉树的任意两个结点的值都不相同，则二叉树的前序序列和中序序列能唯一确定一棵二叉树。另外，由前序序列和中序序列的定义可知，前序序列中第一个结点必为根结点，而在中序序列中，根结点刚好是左、右子树的分界点，因此，可按如下方法建立二叉树：1.用前序序列的第一个结点作为根结点;2.在中序序列中查找根结点的位置，并以此为界将中序序列划分为左、右两个序列(左、右子树);3.根据左、右子树的中序序列中的结点个数，将前序序列去掉根结点后的序列划分为左、右两个序列，它们分别是左、右子树的前序序列;4.对左、右子树的前序序列和中序序列递归地实施同样方法，直到所得左、右子树为空。,1.A为根结点,A BDGH CEFI,GDHB A ECIF,2.B为左子树的根结点,B DGH,GDH B,3.D为左子树的左子树的根结点,4.C为右子树的根结点,5.F为右子树的右子树的根结点,C E FI,E C IF,6.3.2 线索二叉树一、定义：当以二叉链表作为存储结构时,只能找到结点的左右孩子的信息,而不能在结点的任一序列的前驱与后继信息,这种信息只有在遍历的动态过程中才能得到,为了能保存所需的信息,可增加标志域;0 lchild 域指示结点的左孩子 ltag=1 lchild 域指示结点的前驱 0 rchild 域指示结点的右孩子 rtag=1 rchild 域指示结点的后继 以这种结构构成的二叉链表作为二叉树的存储结构,叫做线索链表,其中指向结点前驱与后继的指针叫做线索.加上线索的二叉树称之为线索二叉树。,二、二叉树的二叉线索存储表示（经常遍历或查找的二叉树采用线索链表存储结构比较合适）typedef struct BiThrNode elemtype data;struct BiThNode*lchild,*rchild;unsigned ltag:1;unsigned rtag:1;Bithrnodetype,*Bithrtree;,若结点有左子树，则左链域lchild指示其左孩子（ltag=0）；否则，令左链域指示其前驱（ltag=1）；若结点有右子树，则右链域rchild指示其右孩子（rtag=0）；否则，令右链域指示其后继（rtag=1）；,按不同的方式遍历二叉树所得到的线索二叉树是不相同的。,T,中序序列：BCAED带头结点的中序线索二叉树,增设一个头结点，令其lchild指向二叉树的根结点，rchild指向中序遍历时访问的最后一个结点，ltag=0、rtag=1；并将该结点作为遍历访问的第一个结点的前驱和最后一个结点的后继；最后用头指针指示该头结点。,三、遍历线索二叉树 有了线索二叉树，就容易遍历二叉树了只要（）先找要遍历的第一个结点；（）然后依次找结点的后继；（）重复（）直到其后继为头结点 所有问题归为如何在线索二叉树中找结点的后继？,1、遍历先序线索二叉树 先序线索二叉树中，找结点的后继算法算法思想:对任意结点p:若p有左孩子，则后继为左孩子;若p无左孩子,有右孩子，则后继为右孩子；若p无左孩子,也无右孩子，则后继为右线索；2、遍历中序线索二叉树中序线索二叉树中，找结点的后继算法算法思想:对任意结点p，若rtag=1，则rchild指向该结点的后继；若rtag=0，则rchild指向该结点的右孩子，此时，应从右孩子开始，沿左指针前进，直到找到没有左孩子的结点s（ltag=1）,则s就是p的后继，即后继是中序遍历右子树时，访问的第一个结点；,3.遍历后序线索二叉树（1）后序线索二叉树中，找结点的后继算法算法思想:对任意结点p，若p为二叉树的根，则无后继;若p是双亲的右孩子、或是独生左孩子，则后继为双亲；若p是有兄弟的左孩子，则后继为双亲的右子树上按后序遍历时，访问的第一个结点(叶结点).,五、线索二叉树的建立 建立线索二叉树，或者说对二叉树线索化，实质上就是遍历一棵二叉树。在遍历过程中，访问结点的操作是检查当前结点的左、右指针域是否为空，如果为空，将它们改为指向前驱结点或后继结点的线索。为实现这一过程，设指针pre始终指向刚刚访问过的结点，即若指针p指向当前结点，则pre指向它的前驱，以便增设线索。另外，在对一棵二叉树加线索时，必须首先申请一个头结点，建立头结点与二叉树的根结点的指向关系，对二叉树线索化后，还需建立最后一个结点与头结点之间的线索。具体算法描述见课本P106,中序线索二叉树的递归算法，其中pre为全局变量。int InOrderThr(Bithrtree*head,Bithrtree T)if(!(*head=(Bithrnodetype*)malloc(sizeof(Bithrnodetype)return 0;(*head)-ltag=0;(*head)-rtag=1;(*head)-rchild=*head;if(!T)(*head)-lchild=*head;Else(*head)-lchild=T;pre=head;InThreading(T);pre-rchild=*head;pre-rtag=1;(*head)-rchild=pre;Return 1;,Void Inthreading(Bithrtree p)if(p)Inthreading(p-lchild);if(!p-lchild)p-ltag=1;p-lchild=pre;if(!pre-rchild)pre-rtag=1;pre-rchild=p;pre=p;Inthreading(p-rchild);,在中序线索二叉树上查找任意结点的中序前序结点（1）如果该结点的左标志为1，那么其左指针域所指向的结点便是它的前驱结点；（2）如果该结点的左标志为0，表明该结点有左孩子，它的前驱结点是以该结点的左孩子为根结点的子树的最右结点，即沿着其左子树的右指针链向下查找，当某结点的右标志为1时，它就是所要找的前驱结点。算法如下：Bithrtree Inprenode(Bithrtree p)Bithrtree pre;pre=p-lchild;If(p-ltag!=1)while(pre-rtag=0)pre=-rchild;return(pre);,在中序线索二叉树上查找值为x的结点先找到按某序遍历的第一个结点，然后再依次查询其后继；或先找到按某序遍历的最后一个结点，然后再依次查询其前驱。算法如下：Bithrtree Search(Bithrtree head,elemtype x)Bithrtree p;p=head-lchild;while(p-ltag=0,在中序线索二叉树上的更新:Viod Insertthrright(Bithrtree s,Bithrtree p)Bithrtree w;p-rchild=s-rchild;p-rtag=s-rtag;p-lchild=s;p-ltag=1;s-rchild=p;s-rtag=0;If(p-rtag=0)w=Inpostnode(p);w-lchild=p;,六线索二叉树上的插入运算 Addlchild（BT，y，x），以后序线索二叉树为例 功能：将以指针x为根的后序线索二叉树（仅有左子树）插入到后序线索二叉树BT中，并作为指针y所指结点的左子树。y原来的左子树在插入后，作为x的右子树。,yL,yR,插入前 y,xL,x,xL,yL,x,yR,插入后 y,后序遍历序列为：,可分以下四种情况：1.y无左、右子树 2.y有左、无右子树 3.y无左、有右子树 4.y有左、右子树,yR,xL,yL,x,y有左、右子树,pre,xLfirst,xLlast,yLfirst,yLlast,yRfirst,yRlast,6.4 树和森林6.4.1 树的存储结构 由于树的应用非常广泛，所以其表示方法也多种多样。不同的应用可采用不同的表示方法，以提高其运算效率。在计算机中，树的存储通常采用顺序存储结构和链式存储结构，但无论采用何种存储方式，都要求存储结构不但能存储各结点本身的数据信息，还要能唯一地反映树中各结点之间的逻辑关系。只有这样才能如实地表现一棵树。,一、双亲表示法实现：定义结构数组存放树的结点，每个结点含两个域：数据域：存放结点本身信息双亲域：指示本结点的双亲结点在数组中位置特点：找双亲容易，找孩子难,Type tnode=record Data:datatype;Parent:integer End;Tree=arrat1.maxnode of tnode;,0,1,2,2,3,5,5,5,1,6,1,2,3,4,5,7,8,9,data,parent,如何找孩子结点,二、孩子表示法多重链表：每个结点有多个指针域，分别指向其子树的根结点同构：结点的指针个数相等，为树的度d结点不同构：结点指针个数不等，为该结点的度d,data,fc,如何找双亲结点,孩子链表：其主体是一个与结点个数一样大小的一维数组，数组的每一个元素有两个域组成，一个域用来存放结点信息，另一个用来存放指针，该指针指向由该结点孩子组成的单链表的首位置。单链表的结构也由两个域组成，一个存放孩子结点在一维数组中的序号，另一个是指针域，指向下一个孩子。每个结点的孩子结点用单链表存储，再用含n个元素的结构数组指向每个孩子链表.,这种存储表示可描述为：type link=childnode;childnode=record Child:integer;Next:link End;Node=record data:elementtp;Next:link End;Tree=array1.n of node;,在孩子表示法中查找双亲比较困难，查找孩子却十分方便，故适用于对孩子操作多的应用。,三、孩子兄弟表示法实现：用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点.特点:操作容易,但破坏了树的层次,利用树的孩子兄弟链表这种存储结构便于实现各种树的操作。例如找某结点的第i个孩子，则只要先从fch域中找到第1个孩子结