5(选讲)树和二叉树解析.ppt

树和二叉树树和二叉树树和二叉树树和二叉树 预习检查预习检查v什么是二叉树v树的遍历有哪几种方式v树有那些应用2023/3/63 本章目标本章目标了解树的定义和基本术语了解树的定义和基本术语 了解二叉树的定义、性质、和存储结构了解二叉树的定义、性质、和存储结构掌握二叉树的遍历掌握二叉树的遍历本章结构本章结构树的逻辑结构和存储结构树的逻辑结构和存储结构树和二叉树树和二叉树二叉树遍历二叉树2023/3/65 5 5.1.1.1.1树型结构实例树型结构实例树型结构实例树型结构实例 1 1家族树家族树家族树家族树 5 5-1-1 树的逻辑结构和存储结构树的逻辑结构和存储结构树的逻辑结构和存储结构树的逻辑结构和存储结构 图图图图5-15-1家族树家族树家族树家族树 2023/3/662 2书的目录结构书的目录结构书的目录结构书的目录结构 图图图图5-25-2书的目录书的目录书的目录书的目录 5 5-1-1 书的目录结构书的目录结构书的目录结构书的目录结构2023/3/67 5 5.1.1.2 2 树的定义树的定义树的定义树的定义 1 1树的定义树的定义 树树(Tree)Tree)是是n n(n(n0)0)个个结结点点的的有有限限集集(记记为为T)T)，T T为为空空时时称称为为空空树树，否否则它满足以下两个条件：则它满足以下两个条件：(1)(1)有且仅有一个结点没有前驱，称该结点为根结点有且仅有一个结点没有前驱，称该结点为根结点(Root)Root)；(2)(2)除根结点以外，除根结点以外，其余其余结结点可分点可分为为m(mm(m0 0)个互不相交的有限集合个互不相交的有限集合T0T0，TlTl，Tm-1Tm-1。其中每个集合其中每个集合又构成一棵树，又构成一棵树，树树T0T0，Tl Tl，Tm-1Tm-1被被称称为为根根结结点的子点的子树树(Subree)Subree)。每棵子树的根结点有且仅有一个每棵子树的根结点有且仅有一个每棵子树的根结点有且仅有一个每棵子树的根结点有且仅有一个直接直接直接直接前驱，前驱，前驱，前驱，但可以有但可以有但可以有但可以有0 0个或多个后继。个或多个后继。个或多个后继。个或多个后继。树树的的逻辑结逻辑结构表示数据之构表示数据之间间的关系是一的关系是一对对多，或者多多，或者多对对一的关系。一的关系。它的它的结结构特点具有构特点具有明显的层次关系，是一种十分重要的非线性的数据结明显的层次关系，是一种十分重要的非线性的数据结构。构。5 5-1-1 树的逻辑结构和存储结构树的逻辑结构和存储结构树的逻辑结构和存储结构树的逻辑结构和存储结构 2023/3/68图图图图5-35-3树的示例树的示例树的示例树的示例 图图图图5-3(a)5-3(a)是一棵只有一个根结点的树；是一棵只有一个根结点的树；是一棵只有一个根结点的树；是一棵只有一个根结点的树；图图图图5-35-3(b)(b)是是是是一一一一棵棵棵棵有有有有1212个个个个结结结结点点点点的的的的树树树树，即即即即T=AT=A，B B，C C，KK，LL。A A是是是是棵棵棵棵根根根根，除除除除根根根根结结结结点点点点A A之之之之外外外外，其其其其余余余余的的的的1111个个个个结结结结点点点点分分分分为为为为三三三三个个个个互互互互不不不不相相相相交交交交的的的的集集集集合合合合。T1T1T1T1，T2T2T2T2和和和和T3T3T3T3是是是是根根根根A A A A的的的的三三三三棵棵棵棵子子子子树树树树，且且且且本本本本身身身身又又又又都都都都是是是是一一一一棵棵棵棵树树树树。所以树的所以树的所以树的所以树的定义定义是递归的是递归的是递归的是递归的 。2023/3/692 2 2 2树的基本术语树的基本术语树的基本术语树的基本术语 树的结点包含一个数据元素及若干指向其子树的分支。树的结点包含一个数据元素及若干指向其子树的分支。树的结点包含一个数据元素及若干指向其子树的分支。树的结点包含一个数据元素及若干指向其子树的分支。1.1.树的结点树的结点:包含一个包含一个DEDE和指向其子树的所有分支和指向其子树的所有分支;2.2.结点的度结点的度:一个结点拥有的子树个数一个结点拥有的子树个数,度为零的结点称为度为零的结点称为叶结点叶结点;3.3.树的度树的度:树中所有结点的度的最大值树中所有结点的度的最大值 Max(D(I)Max(D(I)含义含义:树中最大分支数为树的度树中最大分支数为树的度;4.4.结点的层次及树的深度结点的层次及树的深度:根为第一层根为第一层,根的孩子为第二层根的孩子为第二层,若某结若某结点为第点为第k k层层,则其孩子为则其孩子为k+1k+1层层.树中结点的最大层次称为树中结点的最大层次称为树的深度树的深度或高度或高度5.5.森林森林:是是m(m=0)m(m=0)棵互不相的树的集合棵互不相的树的集合 森林与树概念相近森林与树概念相近,相互很容易转换相互很容易转换.6.有序树、无序树有序树、无序树 如果树中每棵子树从左向右的排列拥有一定的如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树。顺序，不得互换，则称为有序树，否则称为无序树。2023/3/6107.7.森林森林:是是m m（m0m0）棵互不相交的树的集合。棵互不相交的树的集合。在树结构中，结点之间的关系又可以用家族关系描述，定义如下：在树结构中，结点之间的关系又可以用家族关系描述，定义如下：8.8.孩子、双亲孩子、双亲:结点子树的根称为这个结点的孩子，而这个结点又结点子树的根称为这个结点的孩子，而这个结点又被称为孩子的双亲。被称为孩子的双亲。9.9.子孙子孙:以某结点为根的子树中的所有结点都被称为是该结点的子以某结点为根的子树中的所有结点都被称为是该结点的子孙。孙。10.10.祖先祖先:从根结点到该结点路径上的所有结点。从根结点到该结点路径上的所有结点。11.11.兄弟兄弟:同一个双亲的孩子之间互为兄弟。同一个双亲的孩子之间互为兄弟。12.12.堂兄弟堂兄弟:双亲在同一层的结点互为堂兄弟。双亲在同一层的结点互为堂兄弟。2023/3/6113.3.树的基本运算树的基本运算树的基本运算树的基本运算树的基本运算主要有：树的基本运算主要有：初始化操作初始化操作INITIATE(T)INITIATE(T)：创建一棵空树。创建一棵空树。求根函数求根函数ROOT(T)ROOT(T)：求树求树T T的根；的根；ROOT(X)ROOT(X)：求结点求结点x x所在树的所在树的根。根。求双亲函数求双亲函数PARENT(T,x)PARENT(T,x)：在树在树T T中求中求x x的双亲。的双亲。求第求第i i个孩子函数个孩子函数CHILD(T,x,i)CHILD(T,x,i)：在树在树T T中求结点中求结点x x的第的第i i个孩个孩子。子。建树函数建树函数CRT-TREE(x,F)CRT-TREE(x,F)：建立以结点建立以结点x x为根，森林为根，森林F F为子树为子树的树。的树。6.6.遍历树操作遍历树操作TRAVERSE(T)TRAVERSE(T)：按顺序访问树按顺序访问树T T中各个结点。中各个结点。2023/3/6121 1树的遍历树的遍历树的遍历树的遍历 所所所所谓谓谓谓树树树树的的的的遍遍遍遍历历历历，就就就就是是是是按按按按照照照照某某某某种种种种顺顺顺顺序序序序依依依依次次次次访访访访问问问问树树树树中中中中各各各各个个个个结结结结点点点点，并并并并使使使使得得得得每每每每个个个个结结结结点点点点只只只只被被被被访访访访问问问问一一一一次次次次。也也也也就就就就是是是是把把把把非非非非线线线线性性性性结结结结构构构构的的的的树树树树结结结结点点点点变变变变成成成成线性序列的一种方式线性序列的一种方式线性序列的一种方式线性序列的一种方式 。树树树树的的的的遍遍遍遍历历历历可可可可以以以以按按按按深深深深度度度度优优优优先先先先遍遍遍遍历历历历，也也也也可可可可以以以以按按按按照照照照广广广广度度度度优优优优先先先先（按按按按层层层层次）遍历。深度优先遍历通常有两种方式：次）遍历。深度优先遍历通常有两种方式：次）遍历。深度优先遍历通常有两种方式：次）遍历。深度优先遍历通常有两种方式：前序前序前序前序遍历和遍历和遍历和遍历和后序后序后序后序遍历。遍历。遍历。遍历。(1)(1)前序遍前序遍前序遍前序遍历历历历的的的的递归递归递归递归定定定定义义义义：若树若树若树若树T T T T非空，则：非空，则：非空，则：非空，则：访问根结点访问根结点访问根结点访问根结点R R；按按按按照照照照从从从从左左左左到到到到右右右右的的的的顺顺顺顺序序序序依依依依次次次次前前前前序序序序遍遍遍遍历历历历根根根根结结结结点点点点R R的的的的各各各各子子子子树树树树T T1 1，T T2 2，T Tk k。5 5-1-5-1-5 树的遍历树的遍历树的遍历树的遍历2023/3/613(2)(2)(2)(2)后序遍历的递归定义：后序遍历的递归定义：后序遍历的递归定义：后序遍历的递归定义：若树若树若树若树T T T T非空，则：非空，则：非空，则：非空，则：按照从左到右的顺序依次后序遍历根按照从左到右的顺序依次后序遍历根按照从左到右的顺序依次后序遍历根按照从左到右的顺序依次后序遍历根T T T T的各子树的各子树的各子树的各子树T T T Tl l l l，T T T T2 2 2 2，T T T Tk k k k；访问根结点访问根结点访问根结点访问根结点R R。(3)(3)(3)(3)广度优先（按层）遍历广度优先（按层）遍历广度优先（按层）遍历广度优先（按层）遍历广广广广度度度度优优优优先先先先（按按按按层层层层次次次次）遍遍遍遍历历历历定定定定义义义义为为为为：先先先先访访访访问问问问第第第第一一一一层层层层结结结结点点点点（即即即即树树树树根根根根结结结结点点点点），再再再再从从从从左左左左至至至至右右右右访访访访问问问问第第第第二二二二层层层层结结结结点点点点，依依依依次次次次按按按按层层层层访访访访问问问问，直直直直到到到到树树树树中中中中结结结结点点点点全全全全部部部部被被被被访访访访问问问问为为为为止止止止。对对对对图图图图6-66-6(a)a)中中中中的的的的树树树树进进进进行行行行按按按按层层层层次次次次遍遍遍遍历历历历得得得得到到到到树树树树的的的的广广广广度度度度优优优优先先先先遍遍遍遍历历历历序序序序列为：列为：列为：列为：ABCDEFGABCDEFG。说明：说明：说明：说明：前前前前序序序序遍遍遍遍历历历历一一一一棵棵棵棵树树树树恰恰恰恰好好好好等等等等价价价价于于于于前前前前序序序序遍遍遍遍历历历历该该该该树树树树所所所所对对对对应应应应的的的的二二二二叉叉叉叉树树树树。（6.26.2节节节节将介绍二叉树）将介绍二叉树）将介绍二叉树）将介绍二叉树）后序遍历树恰好等价于中序遍历该树所对应的二叉树。后序遍历树恰好等价于中序遍历该树所对应的二叉树。后序遍历树恰好等价于中序遍历该树所对应的二叉树。后序遍历树恰好等价于中序遍历该树所对应的二叉树。2023/3/614树的先序遍历算法描述如下：树的先序遍历算法描述如下：树的先序遍历算法描述如下：树的先序遍历算法描述如下：voidPreorder(Btree*root)/先根遍历先根遍历k叉树叉树if(root!=NULL)printf(“%cn”,root-data);/访问访问根根结结点点for(i=0;iti);/递归递归前序遍前序遍历历每一个子每一个子结结点点2023/3/615 5 5.2.1.2.1.2.1.2.1二叉树的定义与性质二叉树的定义与性质二叉树的定义与性质二叉树的定义与性质 二叉树二叉树(Binary Tree)Binary Tree)是另一种重要的树型结构。是度为是另一种重要的树型结构。是度为2 2的的有序树，它的特点是每个结点至多有两棵子树。和树结构的定义有序树，它的特点是每个结点至多有两棵子树。和树结构的定义类似，二叉树的定义也可以用递归形式给出。类似，二叉树的定义也可以用递归形式给出。1 1 1 1二叉树的递归定义二叉树的递归定义二叉树的递归定义二叉树的递归定义 二二叉叉树树(BinaryTree)BinaryTree)是是n(nn(n0)0)个个结结点点的的有有限限集集。它它或或者者是是空空集集(n=0)n=0)，或者同时满足以下两个条件：或者同时满足以下两个条件：(1)(1)有且仅有一个根结点；有且仅有一个根结点；(2)(2)其余的结点分成两棵互不相交的左子树和右子树。其余的结点分成两棵互不相交的左子树和右子树。5 5-2 2 二叉树二叉树二叉树二叉树2023/3/616 二二叉叉树树与与树树有有区区别别：树树至至少少应应有有一一个个结结点点，而而二二叉叉树树可可以以为为空空；树树的的子子树树没没有有顺顺序序，但但如如果果二二叉叉树树的的根根结结点点只只有有一一棵棵子子树树，必必须须明明确确区区分分它它是是左左子子树树还还是是右右子子树树，因因为为两两者者将将构构成成不不同同形形态态的的二二叉叉树树。因因此此，二二叉树不是树的特例。它们是两种不同的数据结构。叉树不是树的特例。它们是两种不同的数据结构。二叉树有二叉树有5 5种基本形态：种基本形态：图图图图5-75-7二叉树的五种基本形态二叉树的五种基本形态二叉树的五种基本形态二叉树的五种基本形态(a)a)a)a)空二叉树空二叉树空二叉树空二叉树 (b)b)b)b)只有根结点的二叉树只有根结点的二叉树只有根结点的二叉树只有根结点的二叉树(c)c)c)c)右子树为空的二叉树右子树为空的二叉树右子树为空的二叉树右子树为空的二叉树 (d)d)左子树为空的二叉树左子树为空的二叉树左子树为空的二叉树左子树为空的二叉树(e)e)左右子树均不为空的二叉树左右子树均不为空的二叉树左右子树均不为空的二叉树左右子树均不为空的二叉树 2023/3/617两种特殊形两种特殊形态态的二叉的二叉树树：满满满满二叉二叉二叉二叉树树树树和完全二叉和完全二叉和完全二叉和完全二叉树树树树。(1)(1)满二叉树满二叉树(FullBinaryTree)FullBinaryTree)深度为深度为k k，且有且有2 2k k-1-1个结点的个结点的二叉树二叉树。特点：（特点：（1 1）每一层上结点数都达到最大）每一层上结点数都达到最大 （2 2）度为）度为1 1的结点的结点n n1 1=0=0，树树叶都在最下一叶都在最下一层层上。上。结点层序编号方法：从根结点起从上到下逐层（层内从左到右）对二叉树的结点层序编号方法：从根结点起从上到下逐层（层内从左到右）对二叉树的结点进行连续编号。结点进行连续编号。1237654K=3n=23-1=7 满二叉树2023/3/618 (2)(2)完全二叉树完全二叉树(Complete BinaryTree)Complete BinaryTree)深度为深度为k k，结点数为结点数为n n的二叉树，当且仅当每个结点的编号都与相同深的二叉树，当且仅当每个结点的编号都与相同深度的满二叉树中从度的满二叉树中从1 1到到n n的结点一一对应时，称为完全二叉树。的结点一一对应时，称为完全二叉树。图图5-8 5-8 完全二叉树完全二叉树完全二叉树的特点：完全二叉树的特点：（1 1）每个结点）每个结点i i的左子树的深度的左子树的深度LhLhi i-其结点其结点i i的右子树的深度的右子树的深度RhRhi i等等于于0 0或或1 1，即叶结点只可能出现在层次最大或次最大的两层上。，即叶结点只可能出现在层次最大或次最大的两层上。（2 2）完全二叉树结点数）完全二叉树结点数n n满足满足2 2k-1k-1-1-1n2n2k k-1-1（3 3）满二叉树一定是完全二叉树，反之不成立。满二叉树一定是完全二叉树，反之不成立。452132023/3/6191324653241LH1=3RH1=1LH1-RH1=2 非完全二叉树非完全二叉树非完全二叉树非完全二叉树LHLH2 2=0=0RHRH2 2=1=1LH2-RH2=0-1=-12023/3/6202 2 2 2二叉树的性质二叉树的性质二叉树的性质二叉树的性质 性质性质1 1 在二叉树的第在二叉树的第i i层上至多有层上至多有2 2i-1 i-1 个结点个结点(i1)i1)。性质性质2 2 深度为深度为k k的二叉树至多有的二叉树至多有2 2k k-1-1个结点个结点(k1)k1)。（深度一定，二叉树的最大结点数也确定）深度一定，二叉树的最大结点数也确定）性质性质3 3 二叉树中二叉树中,终端结点数终端结点数n n0 0与度为与度为2 2的结点数的结点数n n2 2有如下关系有如下关系:n n0=0=n n2 2+1+1 性质性质4 4 结点数为结点数为n n的完全二叉树，其深度为的完全二叉树，其深度为 loglog2 2n n +l+l 性质性质5 5 在按层序编号的在按层序编号的n n个结点的完全二叉树中，任意一结点个结点的完全二叉树中，任意一结点i(1in)i(1in)有：有：i=1i=1时，结点时，结点i i是树的根；否则是树的根；否则，结点结点i i的双亲为结点的双亲为结点 i/2i/2 (i1)i1)。2i 2in n时，结点时，结点i i无左孩子，为叶结点；否则，结点无左孩子，为叶结点；否则，结点i i的左孩子为结的左孩子为结点点2 2i i。2i+1 2i+1n n时，结点时，结点i i无右孩子；否则，结点无右孩子；否则，结点i i的右孩子为结点的右孩子为结点2 2i+1i+1。2023/3/621链式存储结构链式存储结构链式存储结构链式存储结构 （二叉链表）二叉链表）设计不同的结点结构，可以构成不同的链式存储结构。常用的有：设计不同的结点结构，可以构成不同的链式存储结构。常用的有：二叉链表二叉链表 三叉链表三叉链表 线索链表线索链表 用空链域存放指向前驱或后继的线索用空链域存放指向前驱或后继的线索2023/3/622 由由于于二二叉叉树树每每个个结结点点至至多多只只有有2个个孩孩子子，分分别别为为左左孩孩子子和和右右孩孩子子。因因此此可可以以把把每每个个结结点点分分成成三三个个域域：一一个个域域存存放放结结点点本本身身的的信信息息，另另外外两两个个是是指针域，分别存放左、右孩子的地址。每个结点的结构表示为：指针域，分别存放左、右孩子的地址。每个结点的结构表示为：其其中中左左链链域域lchildlchild为为指指向向左左孩孩子子的的指指针针，右右链链域域rchildrchild为为指指向向右右孩孩子子的的指指针针，数数据据域域datadata表表示示结结点点的的值值。若若某某结结点点没没有有左左孩孩子子或或右右孩孩子子，其其相应的链域为空指针。相应的链域为空指针。对应的结构类型定义如下：对应的结构类型定义如下：对应的结构类型定义如下：对应的结构类型定义如下：typedefstructnodetypedefstructnodeElemTypedata;ElemTypedata;structnode*lchild;structnode*lchild;structnode*rchild;structnode*rchild;BTree,*tree;BTree,*tree;其中，其中，其中，其中，treetree是指向根结点的指针。是指向根结点的指针。是指向根结点的指针。是指向根结点的指针。2023/3/623二叉链表的结点结构二叉链表的结点结构 lchild data rchildD 二叉树二叉树CEBAACBDE二叉链表二叉链表说明：说明：说明：说明：一一一一个个个个二二二二叉叉叉叉链链链链表表表表由由由由根根根根指指指指针针针针rootrootrootroot唯唯唯唯一一一一确确确确定定定定。若若若若二二二二叉叉叉叉树树树树为为为为空空空空，则则则则root=NULLroot=NULLroot=NULLroot=NULL；若若若若结点的某个孩子不存在，则相应的指针为空。结点的某个孩子不存在，则相应的指针为空。结点的某个孩子不存在，则相应的指针为空。结点的某个孩子不存在，则相应的指针为空。具具具具有有有有n n个个个个结结结结点点点点的的的的二二二二叉叉叉叉链链链链表表表表中中中中，共共共共有有有有2 2n n个个个个指指指指针针针针域域域域。其其其其中中中中只只只只有有有有n-1n-1个个个个用用用用来来来来指指指指示示示示结点的左、右孩子，其余的结点的左、右孩子，其余的结点的左、右孩子，其余的结点的左、右孩子，其余的n+1n+1个指针域为空。个指针域为空。个指针域为空。个指针域为空。2023/3/624 lchild data parent rchildD 二叉树二叉树CEBAACBDE三叉链表三叉链表3 3带双亲指针的二叉链表带双亲指针的二叉链表带双亲指针的二叉链表带双亲指针的二叉链表 由由于于经经常常要要在在二二叉叉树树中中寻寻找找某某结结点点的的双双亲亲时时，可可在在每每个个结结点点上上再再加加一一个个指指向向其双亲的指针其双亲的指针parent，形成一个带双亲指针的二叉链表。就是形成一个带双亲指针的二叉链表。就是三叉链表。三叉链表。三叉链表的结点结构三叉链表的结点结构性质性质性质性质6 6 6 6 含有含有含有含有n n n n个结点的二叉链表中，有个结点的二叉链表中，有个结点的二叉链表中，有个结点的二叉链表中，有n+1n+1n+1n+1个空链域个空链域个空链域个空链域。二叉树存储方法的选择，主要依赖于所要实施的各种运算的频度。二叉树存储方法的选择，主要依赖于所要实施的各种运算的频度。2023/3/6251 1 1 1二叉树的基本运算二叉树的基本运算二叉树的基本运算二叉树的基本运算（1 1 1 1）Inittree(&T)Inittree(&T)Inittree(&T)Inittree(&T)功能：初始化操作功能：初始化操作功能：初始化操作功能：初始化操作(建立一棵空的二叉树建立一棵空的二叉树建立一棵空的二叉树建立一棵空的二叉树)。（2 2 2 2）Root(T)Root(T)Root(T)Root(T)功能：求二叉树的根。功能：求二叉树的根。功能：求二叉树的根。功能：求二叉树的根。（3 3 3 3）Parent(T,x)Parent(T,x)Parent(T,x)Parent(T,x)功能：求二叉树功能：求二叉树功能：求二叉树功能：求二叉树T T T T中值为中值为中值为中值为x x x x的结点的双亲。的结点的双亲。的结点的双亲。的结点的双亲。（4 4 4 4）Lchild(T,x)Lchild(T,x)Lchild(T,x)Lchild(T,x)功能：求结点的左孩子。功能：求结点的左孩子。功能：求结点的左孩子。功能：求结点的左孩子。（5 5 5 5）Rchild(T,x)Rchild(T,x)Rchild(T,x)Rchild(T,x)功能：求结点的右孩子。功能：求结点的右孩子。功能：求结点的右孩子。功能：求结点的右孩子。（6 6 6 6）Traverse(T)Traverse(T)Traverse(T)Traverse(T)功能：遍历或访问二叉树功能：遍历或访问二叉树功能：遍历或访问二叉树功能：遍历或访问二叉树T T T T。（7 7 7 7）creatree(&T)creatree(&T)creatree(&T)creatree(&T)功能：创建二叉树功能：创建二叉树功能：创建二叉树功能：创建二叉树T T T T5 5-2-32-3 二叉树的基本运算节实现二叉树的基本运算节实现二叉树的基本运算节实现二叉树的基本运算节实现2023/3/626 2 2二叉树部分运算的算法描述二叉树部分运算的算法描述二叉树部分运算的算法描述二叉树部分运算的算法描述 (1)(1)创建二叉树创建二叉树创建二叉树创建二叉树creatree(&root,str)creatree(&root,str)：功能：创建二叉树功能：创建二叉树T T。算法描述如下：算法描述如下：voidcreatree(BTree*b,char*str)BTree*stackMAXSIZE,p=NULL;inttop=-1,k,j=0;charch;*b=NULL;ch=strj;while(ch!=0)switch(ch)case(：top+;stacktop=p;k=1,break;/为左结点为左结点case)：top-;break;case,：k=2;break;/为右结点为右结点default：p=(BTree*)malloc(sizeof(BTree);p-data=ch;p-lchild=p-rchild=NULL;2023/3/627p-data=ch;p-lchild=p-rchild=NULL;if(*b=NULL)/为根结点为根结点*b=p;elseswitch(k)case1：stacktop-lchild=p;break;case2：stacktop-rchild=p;break;j+;ch=strj;2023/3/628(2)(2)查找给定的结点查找给定的结点find(root(root，x)x)(3)(3)找左孩子结点找左孩子结点找左孩子结点找左孩子结点lchild(p)lchild(p)或右孩子结点或右孩子结点或右孩子结点或右孩子结点rchild(p)rchild(p)(4)(4)输出二叉树输出二叉树输出二叉树输出二叉树disptree(root)disptree(root)2023/3/6295.3.15.3.15.3.15.3.1遍历二叉树遍历二叉树遍历二叉树遍历二叉树 在二叉树的一些应用中，常常要求在树中查找具有某种特征在二叉树的一些应用中，常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理。这就引入了遍的结点，或者对树中全部结点逐一进行某种处理。这就引入了遍历二叉树的问题，即如何按某条搜索路径访问树中的每一个结点，历二叉树的问题，即如何按某条搜索路径访问树中的每一个结点，使得每一个结点仅切仅被访问一次。使得每一个结点仅切仅被访问一次。遍历二叉树：遍历二叉树：指按一定的规律对二叉树的每个结点，指按一定的规律对二叉树的每个结点，访问访问且且仅访问一次的处理过程。仅访问一次的处理过程。遍历对线性结构是容易解决的。而二叉树是非线性的，因而遍历对线性结构是容易解决的。而二叉树是非线性的，因而需要寻找一种规律，使二叉树上的结点能排列在一个线性队列上，需要寻找一种规律，使二叉树上的结点能排列在一个线性队列上，从而便于遍历。从而便于遍历。5-35-3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树遍历二叉树和线索二叉树遍历二叉树和线索二叉树 2023/3/630 访访问问是是一一种种抽抽象象操操作作，是是对对结结点点的的某某种种处处理理，例例如如可可以以是是求求结结点点的的度度、或层次、打印结点的信息，或做其他任何工作。或层次、打印结点的信息，或做其他任何工作。一次遍历后，使树中结点的一次遍历后，使树中结点的非线性非线性排列，按访问的先后顺序变为某种排列，按访问的先后顺序变为某种线性排列线性排列。遍历的次序：遍历的次序：假如以假如以L L、D D、R R分别表示遍历左子树、遍历根结点和遍分别表示遍历左子树、遍历根结点和遍历右子树，遍历整个二叉树则有历右子树，遍历整个二叉树则有DLRDLR、LDRLDR、LRDLRD、DRLDRL、RDLRDL、RLDRLD六种遍六种遍历方案。若规定历方案。若规定先左后右先左后右先左后右先左后右，则只有前三种情况，分别规定为：，则只有前三种情况，分别规定为：DLRDLR先（根）序遍历，先（根）序遍历，LDRLDR中（根）序遍历，中（根）序遍历，LRDLRD后（根）序遍历。后（根）序遍历。1 1 1 1遍历方案遍历方案遍历方案遍历方案 LDR LDR 中序遍历中序遍历中序遍历中序遍历；LRD LRD 后序遍历后序遍历后序遍历后序遍历；DLR DLR 先序遍历先序遍历先序遍历先序遍历2023/3/6311 1）中序遍历二叉树）中序遍历二叉树算法思想算法思想:若二叉树非空，则：若二叉树非空，则：1）中序遍历左子树）中序遍历左子树2）访问根结点）访问根结点3）中序遍历右子树）中序遍历右子树算法描述算法描述:voidInorder(BiTreebt)/bt为根结点指针为根结点指针if(bt)/根非空根非空Inorder(bt-lchild);visit(bt-data)visit(bt-data)；Inorder(bt-rchild);2 2）后序遍历二叉树）后序遍历二叉树算法思想算法思想:若二叉树非空，则：若二叉树非空，则：1）后序遍历左子树）后序遍历左子树2）后序遍历右子树）后序遍历右子树3）访问根结点）访问根结点算法描述算法描述:voidPostorder(BiTreebt)/bt为根结点指针为根结点指针if(bt)Postorder(bt-lchild);Postorder(bt-rchild);visit(bt-data)visit(bt-data)；2023/3/6323 3）先序遍历二叉树）先序遍历二叉树算法思想算法思想:若二叉树非空，则：若二叉树非空，则：1）访问根结点）访问根结点2）先序遍历左子树）先序遍历左子树3）先序遍历右子树）先序遍历右子树算法描述算法描述:voidPreorder(BiTreebt)/bt为根结点指针为根结点指针if(bt)/根非空根非空visit(bt-data)visit(bt-data)；Preorder(bt-lchild);Preorder(bt-rchild);例：表达式例：表达式a+b(c-d)-e/facdefb+遍历结果遍历结果:中序中序:a+bc-d-e/f后序后序:abcd-+ef/-先序先序:-+ab-cd/ef2023/3/633（1 1 1 1）先序遍历的递归算法如下（假定结点的元素值为字符型）：）先序遍历的递归算法如下（假定结点的元素值为字符型）：）先序遍历的递归算法如下（假定结点的元素值为字符型）：）先序遍历的递归算法如下（假定结点的元素值为字符型）：#includestdio.hincludestdio.htypedefcharElemType;typedefcharElemType;typedefstructnode/typedefstructnode/定定定定义链义链义链义链表表表表结结结结构构构构ElemTypedata;/ElemTypedata;/定定定定义结义结义结义结点点点点值值值值structnode*lchild;/structnode*lchild;/定定定定义义义义左子左子左子左子结结结结点指点指点指点指针针针针structnode*rchild;/structnode*rchild;/定定定定义义义义右子右子右子右子结结结结点指点指点指点指针针针针 BTree;BTree;preorder(BTree*root)/preorder(BTree*root)/前序遍前序遍前序遍前序遍历历历历if(root!=NULL)/if(root!=NULL)/如果不是空如果不是空如果不是空如果不是空结结结结点点点点printf(printf(“%cncn”,root-data);/,root-data);/输输输输出当前出当前出当前出当前结结结结点点点点值值值值preorder(root-lchild);/preorder(root-lchild);/递归递归递归递归前序遍前序遍前序遍前序遍历历历历左子左子左子左子结结结结点点点点preorder(root-rchild);/preorder(root-rchild);/递归递归递归递归前序遍前序遍前序遍前序遍历历历历右子右子右子右子结结结结点点点点 return;/return;/结结结结束束束束 2 2 2 2遍历算法遍历算法遍历算法遍历算法2023/3/634voidinorder(BTree*root)/voidinorder(BTree*root)/中序遍中序遍中序遍中序遍历历历历if(root!=NULL)/if(root!=NULL)/如果不是空如果不是空如果不是空如果不是空结结结结点点点点inorder(root-lchild);/inorder(root-lchild);/递归递归递归递归中序遍中序遍中序遍中序遍历历历历左子左子左子左子结结结结点点点点printf(printf(“%cncn”,root-data);/,root-data);/输输输输出当前出当前出当前出当前结结结结点点点点值值值值inorder(root-rchild);/inorder(root-rchild);/递归递归递归递归中序遍中序遍中序遍中序遍历历历历右子右子右子右子结结结结点点点点 (3)(3)(3)(3)后序遍历的算法实现后序遍历的算法实现后序遍历的算法实现后序遍历的算法实现 voidpostorder(BTree*root)/voidpostorder(BTree*root)/后序遍后序遍后序遍后序遍历历历历if(root!=NULL)/if(root!=NULL)/如果不是空如果不是空如果不是空如果不是空结结结结点点点点postorder(root-lchild);/postorder(root-lchild);/递归递归递归递归后序遍后序遍后序遍后序遍历历历历左子左子左子左子结结结结点点点点postorder(root-rchild);/postorder(root-rchild);/递归递归递归递归后序遍后序遍后序遍后序遍历历历历右子右子右子右子结结结结点点点点printf(“printf(“%cn”,root-data);/cn”,root-data);/输输输输出当前出当前出当前出当前结结结结点点点点值值值值（2 2 2 2）中序遍历的递归算法如下（假定结点的元素值为字符型）：）中序遍历的递归算法如下（假定结点的元素值为字符型）：）中序遍历的递归算法如下（假定结点的元素值为字符型）：）中序遍历的递归算法如下（假定结点的元素值为字符型）：2023/3/635void inorder(BiTree bt)void inorder(BiTree bt)InitStack(s)InitStack(s)；Push(s,bt)Push(s,bt)；while(!StackEmpty(s)while(!StackEmpty(s)while(GetTop(s)while(GetTop(s)Push(s,GetTop(s)-lchild)Push(s,GetTop(s)-lchild)；p=POP(s)p=POP(s)p=POP(s)p=POP(s)；if(!StackEmpty(s)if(!StackEmpty(s)visit(GetTop(s)-data)visit(GetTop(s)-data)；p=Pop(s)p=Pop(s)；Push(s,p-rchild);Push(s,p-rchild);中序遍历非递归算法中序遍历非递归算法,s s为存储二叉树结点指针栈：为存储二叉树结点指针栈：操作过程：操作过程：根根结结点点先先进进栈栈，左左结结点点紧紧跟跟根根后后面面进进栈栈,右右结结点在根出栈后入栈；点在根出栈后入栈；每每个个结结点点都都要要进进一一次次和和出出一一次次栈栈，并并且且总总是是访访问问栈栈顶顶元元素素，因因此此，算算法法正正确确，时时间间复复杂杂度度为为O(n)。2023/3/636 通通过过上上述述三三种种不不同同的的遍遍历历方方式式得得到到三三种种不不同同的的线线性性序序列列，它它们们的的共共同同的的特特点点是是有有且且仅仅有有一一个个开开始始结结点点和和一一个个终终端端结结点点，其其余余各各结点都有且仅有一个前驱结点和一个后继结点。结点都有且仅有一个前驱结点和一个后继结点。从二叉树的遍历定义可知，三种遍历算法的不同之处仅在于从二叉