数据结构(第6章-树和二叉树)-PPT.ppt

数据结构数据结构(第第6章章 树和二叉树树和二叉树)6.1 树的定义和基本术语树的定义和基本术语v 什么是树？树是由什么是树？树是由 n(n 0)个结点的有限集合。如果个结点的有限集合。如果 n=0，称为空树；如果，称为空树；如果 n 0，则，则 有且仅有一个特定的称之为根有且仅有一个特定的称之为根(Root)的结点，它只有直的结点，它只有直接后继，但没有直接前驱；接后继，但没有直接前驱；当当n 1，除根以外的其它结点划分为，除根以外的其它结点划分为 m(m 0)个互不个互不相交的有限集相交的有限集 T1,T2,Tm，其中每个集合本身又是一，其中每个集合本身又是一棵树，并且称为根的子树棵树，并且称为根的子树(SubTree)。T=A，B，C，D，E，F，G，H，I，J，K，L，MA是根，其余结点可以划分为是根，其余结点可以划分为3个互不相交的集合：个互不相交的集合：T1=B，E，F，K，L T2=C，G T3=D，H，I，J，M 这些集合中的每一集合都本身又是一棵树，它们是这些集合中的每一集合都本身又是一棵树，它们是A的子树。的子树。对于对于T1，B是根，其余结点可以划分为是根，其余结点可以划分为2个互不相交的集合：个互不相交的集合：T11=E，K，L T12=F T11，T12是是B的子树。的子树。HBAJFEDKLCMIGq 树的示例树的示例1.树中只有根结点没有前趋；树中只有根结点没有前趋；2.除根外，其余结点都有且仅一个前趋；除根外，其余结点都有且仅一个前趋；3.树的结点，可以有零个或多个后继；树的结点，可以有零个或多个后继；4.除根外的其它结点，都存在唯一条从除根外的其它结点，都存在唯一条从根到该结点的路径；根到该结点的路径；5.树是一种分支结构。树是一种分支结构。HBAJFEDKLCMIGq 树的逻辑结构特点树的逻辑结构特点 树可表示具有分支结构关系的对象树可表示具有分支结构关系的对象例例1.家族族谱家族族谱 设某家庭有设某家庭有13个成员个成员A、B、C、D、E、F、G、H、I、J、K、L、M，他们之间的关系可如图所示的树表示。，他们之间的关系可如图所示的树表示。例例2.单位行政机构的组织关系单位行政机构的组织关系HBAJFEDKLCMIGq 树的应用树的应用 树是常用的数据组织形式树是常用的数据组织形式 有些应用中数据元素之间并不存在分支结构关系，但是为有些应用中数据元素之间并不存在分支结构关系，但是为了便于管理和使用数据，将它们用树的形式来组织。了便于管理和使用数据，将它们用树的形式来组织。例例3.计算机的文件系统计算机的文件系统 不论是不论是DOS文件系统还是文件系统还是window文件系统，所有的文件文件系统，所有的文件是用树的形式来组织的。是用树的形式来组织的。文件夹文件夹1文件夹文件夹2文件文件1文件文件2文件夹文件夹11 文件夹文件夹11 文件文件11文件文件12Cq 树的应用树的应用树的结点：包含一个数据元素的树的结点：包含一个数据元素的内容及若干指向子树的分支。内容及若干指向子树的分支。孩子结点：结点的子树的根称为孩子结点：结点的子树的根称为该结点的孩子；如该结点的孩子；如E是是B的孩子。的孩子。双亲结点：双亲结点：B结点是结点是A结点的孩子，结点的孩子，则则A结点是结点是B结点的双亲；如结点的双亲；如B是是E的双亲。的双亲。兄弟结点：同一双亲的孩子结点；如兄弟结点：同一双亲的孩子结点；如H、I、J互为兄弟。互为兄弟。堂兄结点：同一层上结点；如堂兄结点：同一层上结点；如G与与E、F、H、I、J互为堂兄。互为堂兄。祖先结点：结点的祖先是从根到该结点所经分支上的所有结点；祖先结点：结点的祖先是从根到该结点所经分支上的所有结点；如如H的祖先为的祖先为A、D。子孙结点：以某结点为根的子树中的任一结点称为该结点的子孙；子孙结点：以某结点为根的子树中的任一结点称为该结点的子孙；如如A的子孙为的子孙为B、C、D、E、F、G、H、I、J、K、L、M。HBAJFEDKLCMIGq 基本术语基本术语大家应该也有点累了，稍作休息大家应该也有点累了，稍作休息大家有疑问的，可以询问和交流大家有疑问的，可以询问和交流大家有疑问的，可以询问和交流大家有疑问的，可以询问和交流结点的度：结点子树的个数；结点的度：结点子树的个数；如如D的度为的度为3。叶子结点：也叫终端结点，是叶子结点：也叫终端结点，是度为度为0的结点；如的结点；如K、L、F、G、M、I、J。分支结点：度不为分支结点：度不为0的结点；如的结点；如A、B、C、D结点层次：根结点的层定义为结点层次：根结点的层定义为1，根的孩子为第二层结点，依此，根的孩子为第二层结点，依此类推。类推。树的高度：树中结点的最大层次；如图所示树的高度为树的高度：树中结点的最大层次；如图所示树的高度为4。树的度：树的度：树中各结点的度的最大值；如图所示树的度为树中各结点的度的最大值；如图所示树的度为3。森林：森林：m(m=0)棵互不相交的树的集合；棵互不相交的树的集合；HBAJFEDKLCMIGq 基本术语基本术语v 线性结构线性结构 第一个数据元素第一个数据元素（无前驱）；（无前驱）；最后一个数据元素（无后继）；最后一个数据元素（无后继）；其它数据元素（一个前驱、一个后继）。其它数据元素（一个前驱、一个后继）。v 树型结构树型结构 根结点（无前驱）；根结点（无前驱）；多个叶子结点多个叶子结点（无后继）；（无后继）；其它数据元素（一个前驱、多个后继）。其它数据元素（一个前驱、多个后继）。q 树型结构和线性结构的结构特点对比树型结构和线性结构的结构特点对比6.2.1 二叉树的定义二叉树的定义 l 或为空树，或由根及至多两棵互不相交的左子树、右子或为空树，或由根及至多两棵互不相交的左子树、右子树构成树构成(即不存在度大于即不存在度大于2的结点的结点)，并且左、右子树本身也，并且左、右子树本身也是二叉树。是二叉树。说明：说明：1.二叉树中每个结点最多有两棵子二叉树中每个结点最多有两棵子树，二叉树每个结点度小于等于树，二叉树每个结点度小于等于2；2.左、右子树不能颠倒左、右子树不能颠倒有序树；有序树；3.二叉树是递归结构，在二叉树的定二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念。义中又用到了二叉树的概念。BADCFEG6.2 二叉树二叉树 (a)(b)(c)(d)(e)(a)空树空树 (b)只含根结点只含根结点 (c)右子右子树为空树树为空树 (d)左右子树均不为空树左右子树均不为空树 (e)左子树左子树为空树为空树LLRRq 二叉树的形态二叉树的形态性质性质1 在二叉树的第在二叉树的第 i 层上至多有层上至多有 2i-1个结点。个结点。(i 1)证明用归纳法证明用归纳法证明：当证明：当i=1时，只有根结点，时，只有根结点，2 i-1=2 0=1。假设对所有假设对所有j，1ji，命题成立，即第，命题成立，即第j层上至多有层上至多有2 j-1 个个结点。结点。由归纳假设第由归纳假设第i-1 层上至多有层上至多有 2i-2个结点。个结点。由于二叉树的每个结点的度至多为由于二叉树的每个结点的度至多为2，故在第，故在第i层上的最大结层上的最大结点数为第点数为第i-1层上的最大结点数的层上的最大结点数的2倍，即倍，即22i-2=2 i-1。6.2.2 二叉树的性质二叉树的性质性质性质2 深度为深度为 k 的二叉树至多有的二叉树至多有 2 k-1个结点个结点(k 1)。证明：由性质证明：由性质1可见，深度为可见，深度为k的二叉树的最大结点数为的二叉树的最大结点数为 20+21+2 k-1=2 k-16.2.2 二叉树的性质二叉树的性质性质性质3 对任何一棵二叉树对任何一棵二叉树T，如果其叶结点数为，如果其叶结点数为 n0，度为，度为2的结点数为的结点数为 n2，则，则n0n21。证明：设二叉树中度为证明：设二叉树中度为1的结点数为的结点数为n1，二叉树中总结点数，二叉树中总结点数为：为：nn0n1n2 二叉树中的分支数，除根结点外，其余结点都有一个二叉树中的分支数，除根结点外，其余结点都有一个进入分支，设进入分支，设B为二叉树中的分支总数，为二叉树中的分支总数，则有：则有：nB1。由于这些分支都是由度为由于这些分支都是由度为1和和2的结点射出的，所以有：的结点射出的，所以有：Bn1+2 n2 ;nB1n12n21得到：得到：n0n216.2.2 二叉树的性质二叉树的性质满二叉树：深度为满二叉树：深度为k的二叉树，有的二叉树，有2k-1个结点则称为满二叉个结点则称为满二叉树；树；完全二叉树：如果深度为完全二叉树：如果深度为k、由、由n个结点的二叉树中个结点个结点的二叉树中个结点能够与深度为能够与深度为k的顺序编号的满二叉树从的顺序编号的满二叉树从1到到n标号的结点相标号的结点相对应，则称为完全二叉树。对应，则称为完全二叉树。完全二叉树的特点是：完全二叉树的特点是：1.所有的叶结点都出现在第所有的叶结点都出现在第k层或层或k1层。层。2.对任一结点，如果其右子树的最大层次为对任一结点，如果其右子树的最大层次为l，则其左子，则其左子树的最大层次为树的最大层次为 l 或或 l 1。q 两种特殊的二叉树两种特殊的二叉树62175438910 1113 14 1512621754389 1011 122154367216543非完全二叉树非完全二叉树完全二叉树完全二叉树满满二二叉叉树树q 两种特殊的二叉树两种特殊的二叉树性质性质 4：具有：具有 n 个结点的完全二叉树的深度为个结点的完全二叉树的深度为 log2n +1。证明：设完全二叉树的深度为证明：设完全二叉树的深度为 k，则根据性质，则根据性质2和完全二叉和完全二叉树的定义有树的定义有2k-1-1 n 2k-1或或 2k-1 n 2k取对数取对数 k-1 1，则其双亲是结点则其双亲是结点 i/2 。2.如果如果2in，则结点，则结点i为叶子结点，无左孩子；否则，其为叶子结点，无左孩子；否则，其左孩子是结点左孩子是结点2i。3.如果如果2i1n，则结点，则结点i无右孩子；否则，其右孩子是结无右孩子；否则，其右孩子是结点点2i1。6.2.2 二叉树的性质二叉树的性质证明：此性质可采用数学归纳法证明。因为证明：此性质可采用数学归纳法证明。因为1与与2、3是相对应的，是相对应的，所以只需证明所以只需证明2和和3。当当 i=1时时，根据结点编号方法可知，根的左、右孩子编号分，根据结点编号方法可知，根的左、右孩子编号分别是别是2和和3，结论成立。，结论成立。假定假定i-1时结论成立，即结点时结论成立，即结点i-1的左右孩的左右孩子编号满足：子编号满足：LCHILD(i-1)=2(i-1)；RCHILD(i-1)=2(i-1)+1 通过完全二叉树可知，结点通过完全二叉树可知，结点 i 或者与结点或者与结点i-1同层且紧靠其右，同层且紧靠其右，或者结点或者结点i-1在某层最右端，而结点在某层最右端，而结点i在其下一层最左端。但是，无在其下一层最左端。但是，无论如何，结点论如何，结点i的左孩子的编号都是紧接着结点的左孩子的编号都是紧接着结点i-1的右孩子的编号，的右孩子的编号，故：故：LCHILD(i)=RCHILD(i-1)+1=2i；RCHILD(i)=LCHILD(i)+1=2i+1命题成立。命题成立。6.2.2 二叉树的性质二叉树的性质分析：根据完全二叉树的结构和编号规则，在分析：根据完全二叉树的结构和编号规则，在i的左孩子前面的的左孩子前面的两个结点是结点两个结点是结点i-1的左、右孩子，由归纳假设有：结点的左、右孩子，由归纳假设有：结点i-1的左的左孩子为孩子为2(i-1)，右孩子为，右孩子为2(i-1)+1。.i与与i+1同层同层.i-12(i-1)2(i-1)+1i2i2i+1.i与与i+1不同层不同层6.2.2 二叉树的性质二叉树的性质i2i2i+1i-12i-22i-1最后证明结论最后证明结论1。当当i=1时，显然根结点无双亲；当时，显然根结点无双亲；当i1时，结点时，结点i可能是可能是其双亲其双亲x的左孩子，也可能是右孩子，若是左孩子，由结论的左孩子，也可能是右孩子，若是左孩子，由结论2知，知，x的左孩子应为的左孩子应为2x，即，即2x=i，x=i/2；若是右孩子，由；若是右孩子，由结论结论3知，知，x的右孩子应为的右孩子应为2x+1，即，即2x+1=i，x=(i-1)/2。故故 i的双亲为的双亲为i/2 证毕。证毕。6.2.2 二叉树的性质二叉树的性质v 顺序存储结构顺序存储结构l 所谓顺序存储结构，就是用一组连续的存储单元存储二所谓顺序存储结构，就是用一组连续的存储单元存储二叉树的数据元素，结点在这个序列中的相互位置能反映出叉树的数据元素，结点在这个序列中的相互位置能反映出结点之间的逻辑关系。结点之间的逻辑关系。二叉树中结点之间的关系就是双亲二叉树中结点之间的关系就是双亲结点与左右孩子结点间的关系。因此，必须把二叉树的所结点与左右孩子结点间的关系。因此，必须把二叉树的所有结点安排成为一个恰当的序列。具体定义如下：有结点安排成为一个恰当的序列。具体定义如下：#define MAX-TREE-SIZE 100 TElemType SqBiTreeMAX-TREE-SIZE;6.2.3 二叉树的存储结构二叉树的存储结构l 通常是按照二叉树结点从上至下、从左到右的顺序存储，通常是按照二叉树结点从上至下、从左到右的顺序存储，但这样结点在存储位置上的前驱后继关系并不一定就是它们但这样结点在存储位置上的前驱后继关系并不一定就是它们在逻辑上的邻接关系。依据二叉树的性质，完全二叉树和满在逻辑上的邻接关系。依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可以唯一地二叉树采用顺序存储比较合适，树中结点的序号可以唯一地反映出结点之间的逻辑关系，这样既能够最大可能地节省存反映出结点之间的逻辑关系，这样既能够最大可能地节省存储空间，又可以利用数组元素的下标值确定结点在二叉树中储空间，又可以利用数组元素的下标值确定结点在二叉树中的位置，以及结点之间的关系。的位置，以及结点之间的关系。q 二叉树的顺序存储结构二叉树的顺序存储结构FBAGEDCHIJKL例如：例如：bt3的双亲为的双亲为3/2=1，即在，即在bt1中；中；其左孩子在其左孩子在bt2i=bt6中；中；其右孩子在其右孩子在bt2i+1=bt7中。中。如何反映结点之如何反映结点之间的逻辑关系？间的逻辑关系？A1B2C3D4E5F6G7H8I9J10K11L12q 完全二叉树的顺序表示完全二叉树的顺序表示l 一般二叉树也按完全二叉树形式存储，只有增添一些并不存在一般二叉树也按完全二叉树形式存储，只有增添一些并不存在的空结点的空结点(用用表示，表示，表示该处没有元素存在，仅仅为了好理解表示该处没有元素存在，仅仅为了好理解)，使之成为一棵完全二叉树的形式，然后再用一维数组顺序存，使之成为一棵完全二叉树的形式，然后再用一维数组顺序存储。储。A1B2C3D45E6F7G8H910111213I14J15EBAFDCGHIJ例如对于例如对于B结点而言：结点而言：bt2的双亲为的双亲为1/2=1，即在，即在bt1中中(为为A)；其左孩子在其左孩子在bt2i=bt4中中(为为D)；其右孩子在其右孩子在bt2i+1=bt5中中(为为)。q 一般二叉树的顺序表示一般二叉树的顺序表示l 这种存储结构适合于完全二叉树，既不浪费存储空间，这种存储结构适合于完全二叉树，既不浪费存储空间，又能很快确定结点的存放位置、以及结点的双亲和左右孩又能很快确定结点的存放位置、以及结点的双亲和左右孩子的存放位置，但对一般二叉树，可能造成存储空间的浪子的存放位置，但对一般二叉树，可能造成存储空间的浪费。费。例如，深度为例如，深度为k，且只有，且只有k个结个结点的右单支树点的右单支树(每个非叶结点只每个非叶结点只有右孩子有右孩子)，也需，也需2k-1个单元，个单元，即有即有(2k-1)-k个单元被浪费。个单元被浪费。12kq 顺序存储的优缺点顺序存储的优缺点v 所谓链式存储是指，用链表来表示一棵二叉树，即用链所谓链式存储是指，用链表来表示一棵二叉树，即用链来指示着元素的逻辑关系。通常采用二叉链表来存储。来指示着元素的逻辑关系。通常采用二叉链表来存储。链表中每个结点由三个域组成，除了数据域外，还有链表中每个结点由三个域组成，除了数据域外，还有两个指针域，分别用来给出该结点左右孩子所在的结点的两个指针域，分别用来给出该结点左右孩子所在的结点的存储地址。其定义如下：存储地址。其定义如下：typedef struct BiTNode TElemType data;struct BiTNode*lchild,*rchild;BiTNode,*BiTree;q 链式存储结构链式存储结构 D A B C E F Tlchilddatarchild结点结构结点结构BADCEFq 二叉链表二叉链表 A B C D E F G三叉链表图示三叉链表图示BACDEFGq 三叉链表三叉链表lchild data结点结构结点结构parent rchild6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树6.3.1 遍历二叉树遍历二叉树v定义：所谓遍历二叉树，就是遵从某种次序，访问二叉树定义：所谓遍历二叉树，就是遵从某种次序，访问二叉树中的所有结点，使得每个结点仅被访问一次。中的所有结点，使得每个结点仅被访问一次。这里所提的这里所提的“访问访问”的含义很广，可以是查询、修改、的含义很广，可以是查询、修改、输出某元素的值，以及对元素作某种运算等等。但要求这输出某元素的值，以及对元素作某种运算等等。但要求这种访问不破坏它原来的数据结构。遍历一个线性结构很简种访问不破坏它原来的数据结构。遍历一个线性结构很简单，只须从开始结点出发，顺序扫描每个结点即可。但对单，只须从开始结点出发，顺序扫描每个结点即可。但对二叉树这样的非线性结构，每个结点可能有两个后继结点，二叉树这样的非线性结构，每个结点可能有两个后继结点，因此需要寻找一种规律来系统访问树中的各结点。因此需要寻找一种规律来系统访问树中的各结点。如何访问二叉树的每个结点且如何访问二叉树的每个结点且每个结点仅被访问一次？每个结点仅被访问一次？由于二叉树的定义是递归的，它是由三个基本单元组成，由于二叉树的定义是递归的，它是由三个基本单元组成，即根结点、左子树和右子树。因此，遍历一棵非空二叉树的即根结点、左子树和右子树。因此，遍历一棵非空二叉树的问题可以分解为三个子问题：访问根结点、遍历左子树、遍问题可以分解为三个子问题：访问根结点、遍历左子树、遍历右子树，只要依次遍历这三部分，就可以遍历整个二叉树。历右子树，只要依次遍历这三部分，就可以遍历整个二叉树。由于实际问题一般都是要求左子树较右子树先遍历，分由于实际问题一般都是要求左子树较右子树先遍历，分别称为先序遍历、中序遍历和后序遍历。别称为先序遍历、中序遍历和后序遍历。令令L，R，D分别代表二叉树的左子树、右子树、根结点，分别代表二叉树的左子树、右子树、根结点，则有则有DLR、LDR、LRD三种遍历规则。三种遍历规则。q 递归实现方法递归实现方法若二叉树非空，则：若二叉树非空，则：1.访问根结点访问根结点 2.先序遍历左子树先序遍历左子树 3.先序遍历右子树先序遍历右子树BADCD L RAD L RD L RBDCD L R得到的序列为：得到的序列为：A B D Cq 先序遍历二叉树先序遍历二叉树Status PreOrderTraverse(BiTree T)/采用二叉链表存贮二叉树采用二叉链表存贮二叉树 if(T)/若二叉树不为空若二叉树不为空 Visit(T-data)；/访问根结点访问根结点 PreOrderTraverse(T-lchild);/先序遍历先序遍历T的左子树的左子树 PreOrderTraverse(T-rchild);/先序遍历先序遍历T的右子树的右子树 /PreOrderTraverseq 先序遍历二叉树算法实现先序遍历二叉树算法实现viod pre(bint T)if (T)visite(T-data);pre(T-lchild);pre(T-rchild);q 先序遍历二叉树算法实先序遍历二叉树算法实现现BADC主程序主程序Pre(T)TAvisite(A);pre(T L);TBvisite(B);pre(T L);T返回返回pre(T R);TDvisite(D);pre(T L);T返回返回pre(T R);T返回返回pre(T R);TCvisite(C);pre(T L);T返回返回pre(T R);T返回返回先序序列：先序序列：A B D C若二叉树非空，则：若二叉树非空，则：1.中序遍历左子树中序遍历左子树 2.访问根结点访问根结点 3.中序遍历右子树中序遍历右子树BADCL D RBL D RL D RADCL D R得到的序列为：得到的序列为：B D A Cq 中序遍历二叉树中序遍历二叉树若二叉树非空，则：若二叉树非空，则：1.后序遍历左子树后序遍历左子树 2.访问根结点访问根结点 3.后序遍历右子树后序遍历右子树BADC L R DL R DL R DADCL R DB得到的序列为：得到的序列为：D B C Aq 后序遍历二叉树后序遍历二叉树*-bcav 这这一一路路线线正正是是从从根根结结点点开开始始沿沿左左子子树树深深入入下下去去，当当深深入入到到最最左左端端，无无法法再再深深入入下下去去时时，则则返返回回，再再逐逐一一进进入入刚刚才才深深入入时时遇遇到到结结点点的的右右子子树树，再再进进行行如如此此的的深深入入和和返返回回，直直到到最最后后从从根根结结点点的的右右子子树树返返回回到到根根结结点点为为止止。先先序序遍遍历历是是在在深深入入时时遇遇到到结结点点就就访访问问，中中序序遍遍历历是是在在从从左左子子树树返返回回时时遇遇到到结结点点访访问问，后后序序遍遍历历是在从右子树返回时遇到结点访问。是在从右子树返回时遇到结点访问。v 在这一过程中，返回结点的顺序与深入结点的顺序相反，即后深入先返回，在这一过程中，返回结点的顺序与深入结点的顺序相反，即后深入先返回，正好符合栈结构后进先出的特点。因此，可以用栈来帮助实现这一遍历路线。正好符合栈结构后进先出的特点。因此，可以用栈来帮助实现这一遍历路线。q 三种遍历过程示意图例三种遍历过程示意图例-*abc 先序遍历：从二叉树根结点开始，沿左子树一直走到末端先序遍历：从二叉树根结点开始，沿左子树一直走到末端(左子树为空左子树为空)为止，在走的过程中，访问所遇结点，并依次为止，在走的过程中，访问所遇结点，并依次把所遇结点进栈，当左子树为空时，从栈顶退出某结点，把所遇结点进栈，当左子树为空时，从栈顶退出某结点，并将指针指向该结点的右子树。如此重复，直到栈为空或并将指针指向该结点的右子树。如此重复，直到栈为空或指针为空止。指针为空止。中序遍历：从二叉树根结点开始，沿左子树一直走到末端中序遍历：从二叉树根结点开始，沿左子树一直走到末端(左子树为空左子树为空)为止，在走的过程中，把依次遇到的结点进栈，为止，在走的过程中，把依次遇到的结点进栈，待左子树为空时，从栈中退出结点并访问，然后再转向它待左子树为空时，从栈中退出结点并访问，然后再转向它的右子树。如此重复，直到栈空或指针为空止。的右子树。如此重复，直到栈空或指针为空止。q 非递归实现方法非递归实现方法status InOrderTraverse(BiTree T)InitStack(S);Push(S,T);/根结点进栈根结点进栈 while(!StackEmpty(S)while(GetTop(S,p)&p)Push(S,p-lchild);Pop(S,p);/空指针退栈空指针退栈 if(!StackEmpty(S)Pop(S,p);Visit(p-data);Push(S,p-rchild);return OK;q 中序遍历的非递归算法中序遍历的非递归算法q 中序遍历的非递归算法演示中序遍历的非递归算法演示A AB BC CD DE EF FGGp pi iP-AP-A(1)(1)A AB BC CD DE EF FGGp pi iP-AP-AP-BP-B(2)(2)q 中序遍历的非递归算法演示中序遍历的非递归算法演示A AB BC CD DE EF FGGp pi iP-AP-AP-BP-BP-CP-C(3)(3)p=NULLp=NULLA AB BC CD DE EF FGGi iP-AP-AP-BP-B访问：访问：访问：访问：C C(4)(4)q 中序遍历的非递归算法演示中序遍历的非递归算法演示p pA AB BC CD DE EF FGGi iP-AP-A访问：访问：访问：访问：C BC B(5)(5)A AB BC CD DE EF FGGi iP-AP-AP-DP-D访问：访问：访问：访问：C BC Bp p(6)(6)q 中序遍历的非递归算法演示中序遍历的非递归算法演示A AB BC CD DE EF FGGi iP-AP-AP-DP-DP-EP-E访问：访问：访问：访问：C BC Bp p(7)(7)A AB BC CD DE EF FGGi iP-AP-AP-DP-D访问：访问：访问：访问：C B EC B Ep p(8)(8)q 中序遍历的非递归算法演示中序遍历的非递归算法演示A AB BC CD DE EF FGGi iP-AP-AP-DP-DP-GP-G访问：访问：访问：访问：C B EC B EP=NULLP=NULL(9)(9)A AB BC CD DE EF FGGi iP-AP-AP-DP-D访问：访问：访问：访问：C B E GC B E Gp p(10)(10)q 中序遍历的非递归算法演示中序遍历的非递归算法演示A AB BC CD DE EF FGGi iP-AP-A访问：访问：访问：访问：C B E G DC B E G Dp p(11)(11)A AB BC CD DE EF FGGi iP-AP-AP-FP-F访问：访问：访问：访问：C B E G DC B E G Dp p(12)(12)q 中序遍历的非递归算法演示中序遍历的非递归算法演示A AB BC CD DE EF FGGi iP-AP-A访问：访问：访问：访问：C B E G D FC B E G D Fp=NULLp=NULL(13)(13)A AB BC CD DE EF FGGi i访问：访问：访问：访问：C B E G D F AC B E G D F Ap p(14)(14)q 中序遍历的非递归算法演示中序遍历的非递归算法演示A AB BC CD DE EF FGGi i访问：访问：访问：访问：C B E G D F AC B E G D F Ap=NULLp=NULL(15)(15)后序遍历：利用栈来实现二叉树的后序遍历要比先序和中后序遍历：利用栈来实现二叉树的后序遍历要比先序和中序遍历复杂得多，在后序遍历中，当搜索指针指向某一个序遍历复杂得多，在后序遍历中，当搜索指针指向某一个结点时，不能马上进行访问，而先要遍历左子树，所以此结点时，不能马上进行访问，而先要遍历左子树，所以此结点应先进栈保存，当遍历完它的左子树后，再次回到该结点应先进栈保存，当遍历完它的左子树后，再次回到该结点，还不能访问它，还需先遍历其右子树，所以该结点结点，还不能访问它，还需先遍历其右子树，所以该结点还必须再次进栈，只有等它的右子树遍历完后，再次退栈还必须再次进栈，只有等它的右子树遍历完后，再次退栈时，才能访问该结点。为了区分同一结点的两次进栈，引时，才能访问该结点。为了区分同一结点的两次进栈，引入一个栈次数的标志，元素第一次进栈标志为入一个栈次数的标志，元素第一次进栈标志为1，第二次进，第二次进标志为标志为2，当退出的元素标志为，当退出的元素标志为2时，访问结点。时，访问结点。q 非递归实现方法非递归实现方法void leaf(BiTree T)/采用二叉链表存贮二叉树，采用二叉链表存贮二叉树，n为全局变量，用于累加二叉树的叶为全局变量，用于累加二叉树的叶子结点个数，本算法在先序遍历二叉树的过程中，统计叶子结点子结点个数，本算法在先序遍历二叉树的过程中，统计叶子结点的个数，初始化的个数，初始化n=0if(T)if(T-lchild=NULL&T-rchild=NULL)n+=1;/若若T所指结点为叶子结点则计数所指结点为叶子结点则计数 leaf(T-lchild);leaf(T-rchild);/if /leaf例例1 编写求二叉树的叶子结点个数的算法编写求二叉树的叶子结点个数的算法void leaf(BiTree T)If(T)if(T-lchild=NULL&T-rchild=NULL)n+=1;leaf(T-lchild);leaf(T-rchild);/if /leafStatus PreOrderTraverse(BiTree T)if(T)Visit(T-data)；PreOrderTraverse(T-lchild);PreOrderTraverse(T-rchild);/PreOrderTraverse访问结点时统计访问结点时统计叶子结点的个数叶子结点的个数访问结点时访问结点时调用调用visit()比较先序遍历和计算叶子结点算法相同点和不同点比较先序遍历和计算叶子结点算法相同点和不同点 分析：本算法要借用队列来完成，其基本思想是，若二分析：本算法要借用队列来完成，其基本思想是，若二叉树非空，先将根结点进队列。然后进入循环：只要队列叉树非空，先将根结点进队列。然后进入循环：只要队列不空，就出队列，遍历该结点，然后判断出队列的结点是不空，就出队列，遍历该结点，然后判断出队列的结点是否有左孩子和右孩子，如有就让左、右孩子进队列。否有左孩子和右孩子，如有就让左、右孩子进队列。例例2 按层次遍历二叉树的算法按层次遍历二叉树的算法void layorder(BiTree T)InitQueue(Q)/队列初始化队列初始化 if(T!=NULL)EnQueue(Q,T);/入队列入队列 while(not QueueEmpty(Q)/若队列非空若队列非空 DeQueue(Q,p);/出队出队 visite(p-data);if(p-lchild!=NULL)EnQueue(Q,p-lchild);/入队列入队列 if(p-rchild!=NULL)EnQueue(Q,p-rchild);/入队列入队列 例例2 按层次遍历二叉树的算法按层次遍历二叉树的算法输入：二叉树的先序序列输入：二叉树的先序序列结果：二叉树的二叉链表结果：二叉树的二叉链表问题：遍历操作访问二叉树的每个结问题：遍历操作访问二叉树的每个结点，而且每个结点仅被访问一次。是点，而且每个结点仅被访问一次。是否可利用遍历，建立二叉链表的所有否可利用遍历，建立二叉链表的所有结点并完成相应结点的链接？结点并完成相应结点的链接？基本思想：输入在空子树处添加字符基本思想：输入在空子树处添加字符的二叉树的按先序遍历的顺序，建的二叉树的按先序遍历的顺序，建立二叉链表的所有结点并完成相应结立二叉链表的所有结点并完成相应结点链接。点链接。BADCEF在空子树处添加的二在空子树处添加的二叉树的先序序列：叉树的先序序列：A B D F E C 例例3 建立二叉链表建立二叉链表Status CreateBiTree(BiTree&T)/输入输入(在空子树处添加字符的二叉树的在空子树处添加字符的二叉树的)先序序列先序序列(设元素均为设元素均为字符字符)scanf(&ch);if(ch=)T=NULL;/若若ch=则表示空则表示空子树子树 else if(!(T=(BiTNode*)malloc(sizeof(BiTNode)exit(OVERFLOW);T-data=ch;/建立建立(根根)结点结点 CreateBiTree(T-lchild);/递归构造左子树链表递归构造左子树链表 CreateBiTree(T-rchild);/递归构造右子树链表递归构造右子树链表 return OK;/CreateBiTreeq 建立二叉链表算法建立二叉链表算法q 建立二叉链表算法建立二叉链表算法BACDA B C D A BCDATBCD分分析析：由由先先序序序序列列和和中中序序序序列列的的定定义义可可知知，先先序序序序列列中中第第一一个个结结点点必必为为根根结结点点，而而在在中中序序序序列列中中，根根结结点点刚刚好好是是左左、右右子子树树的的分分界点，因此，界点，因此，可按如下方法建立二叉树：可按如下方法建立二叉树：1.用先序序列的第一个结点作为根结点用先序序列的第一个结点作为根结点;2.在中序序列中查找根结点的位置，并以此为界将中序序列划在中序序列中查找根结点的位置，并以此为界将中序序列划分为左、右两个序列分为左、右两个序列(左、右子树左、右子树);3.根根据据左左、右右子子树树的的中中序序序序列列中中的的结结点点个个数数，将将先先序序序序列列去去掉掉根根结结点点后后的的序序列列划划分分为为左左、右右两两个个序序列列，它它们们分分别别是是左左、右右子子树树的先序序列的先序序列;4.对左、右子树的先序序列和中序序列递归地实施同样方法，对左、右子树的先序序列和中序序列递归地实施同样方法，直到所得左、右子树为空。直到所得左、右子树为空。例例4 由二叉树先序和中序序列建立一个唯一二叉树由二叉树先序和中序序列建立一个唯一二叉树 如一棵二叉树的先序序列为如一棵二叉树的先序序列为ABDGHCEFI，中序序列为，中序序列为GDHBAECIF，试建立该二叉树。，试建立该二叉树。构造过程：由先序可知构造过程：由先序可知A为根结点，再根据中序序列知：为根结点，再根据中序序列知：由由GDHB是左子树，是左子树，ECIF是右子树。是右子树。v A为根结点为根结点A BDGH CEFIGDHB A ECIFv B为左子树的根结点为左子树的根结点B DGHGDH Bv 一直进行下去一直进行下去AG,D,H,B组成左子树组成左子树E,C,I,F组成右子树组成右子树 示例分析示例分析a b c d e f gc b d a e g faab bccddeeffggabcdefg先序序列先序序列先序序列先序序列中序序列中序序列中序序列中序序列遍历是二叉树最基本最常用的操作。遍历是二叉树最基本最常用的操作。1.对二叉树所有结点做某种处理可在遍历过程中实现；对二叉树所有结点做某种处理可在遍历过程中实现；2.查找二叉树某个结点，可通过遍历实现；查找二叉树某个结点，可通过遍历实现；与线性表相比，对二叉树的遍历存在如下问题：与线性表相比，对二叉树的遍历存在如下问题：1.遍历算法要复杂的多，费时的多；遍历算法要复杂的多，费时的多；2.为查找二叉树中某结点在某种遍历下的后继，必须从根为查找二叉树中某结点在某种遍历下的后继，必须从根开始遍历，直到找到该结点及后继；开始遍历，直到找到该结点及后继；如果能将二叉树线性化，就可以减化遍历算法，提高如果能将二叉树线性化，就可以减化遍历算法，提高遍历速度。遍历速度。6.3.2 线索二叉树线索二叉树定义：当以二叉链表作为存储结构时，只能找到结点的左右孩子定义：当以二叉链表作为存储结构时，只能找到结点的左右孩子的信息，而不能直接得到结点的任一序列的前驱与后继信息，这的信息，而不能直接得到结点的任一序列的前驱与后继信息，这种信息只有在遍历的动态过程中才能得到，为了能保存所需的信种信息只有在遍历的动态过程中才能得到，为了能保存所需的信息，可增加标志域。息，可增加标志域。0 lchild 域指示结点的左孩子域指示结点的左孩子 1 lchild 域指示结点的前驱域指示结点的前驱 0 rchild 域指示结点的右孩子域指示结点的右孩子 1 rchild 域指示结点的后继域指示结点的后继 以这种结构构成的二叉链表作为二叉树的存储结构，叫做线