数据结构-树和二叉树教案.docx

《数据结构-树和二叉树教案.docx》由会员分享，可在线阅读，更多相关《数据结构-树和二叉树教案.docx（26页珍藏版）》请在课桌文档上搜索。

1、/第六章树和二叉树/下面呢，我们就讨论第六章、树和二叉树。那么我们回忆一下数据结构四大类。第一类，线性结构，除了广义表以外，我们都讨论完了。现在我们开始讨论第二大类，树形结构，在树形结构里面呢，我们主要讨论两种结构。一类树，一类二叉树（线性结构里头我们讨论了什么？）。首先，我们先看树的数据类型定义。那先看数据对象D：具有相同特性的数据元素的集合，这就是它的数据对象。数据元素之间是一个什么样的关系呢，我们用下面这段话来描述。如果数据对象是一个空集，我们称之为空树。从这里看得出来，所有的数据结构都这样一个空的这样一个结构。空串、空表等等。空树的意思是一个数据元素都没有。否那么的话，如果这个集合不是

2、一个空集的话，那么在这个数据结构里面一定存在一个成为根的数据元素root，而且这个数据元素一定是唯的。就是说，一定存在，而且唯一。那么就是说除了空树以外，如果数据集合里面只有一个数据元素的话，那么这个数据元素，就是这个树的根。如果说这个数据集合里面的元素个数大于1的话，其余个结点呢，我们一定可以给它分成m个子集。这些子集互不相交。并且每个子集本身呢，又是一棵符合上面定义的树。这些子集是树，而且称之为根的子树。我们看一个例子，（画图）Abcdefgij这是一个树，当然它不是空树，这个树呢是9个数据元素的集合。一定存在这一个叫做根的结点。这个A呢，我们称之为树根，除了这个根以外，我们可以分成这样三

3、个集合。以B开始的一个子集，以C开始的一个子集，和D开始的一个子集。这三个子集互不相交，每个子集呢又是一棵树，并且它和根呢，有一个关系存在，这棵树叫做根的子树。这棵树呢，又存在一个根结点，这root根和我们子树根之间，存在这一个这样一个前驱后继的关系，一般画树，我们不画箭头，但是我们讨论的是有向树，是有箭头的。就是说BCD是A的后继。那对于B的这样一个子树，又是符合我们定义的子树，那就是说它有一个根结点，它有两颗子树。在根结点和子树根之间呢，又存在一个前驱和后继的关系，那对E、F来说，它们本身又是一颗树。对于E这棵树来说，它的数据元素只有一个，所以它是仅含有根结点的一颗子树。在定义的时候我们说

4、还有空树的，但是在实际使用的时候，是没有意义的。由于我们数据结构和离散数学还是有一定的关系的，在离散数学中，为了一些数学上的完整性的定义，才有空树这样的定义，在我们数据结构中也有定义，单实际上用处不大。这就是树的类型的一个结构特性。下面我们本来就该讨论根本操作了，但是对于树来讲呢，还有一些根本术语介绍一下，以便我们对根本操作的理解。下面就看有关树的根本术语。现在先来看一下有关树的术语。树当中，它的根本单位是一个结点：什么叫结点呢：数据元素+假设干指向子树的分支比方刚刚我们举的那个例子，一个数据元素A+指向BCD的子树的分支，那就称一个结点。结点的度：结点上指向分支的个数（在树上面每个结点的度可

5、能是不一样的，比方我们分解到只含有一个根结点的子树时，它没有子树也没有分支，那它的度就是零。对于刚刚的根结点，它的度就是3.）整个树的度；我们定义为：整个树当中所有结点的度的最大值。对于我们刚刚的那棵树呢，这棵树的度呢，就是3,因为，结点最大的度是3.叶子结点：对树来说，分解到最后，对于子树来说就一个根节点，度为零的结点。（也就是只有一个根结点的子树。对于这样的一个结点，是没有子树的，它对于整个树来说，是很特殊的，叫做叶子结点。除了叶子结点，其他的结点的度都是大与零的。）反过来我们把它叫做分支结点：就是那些度大于零的结点。对于一棵树来说呢，我们经常要谈到的是，根结点，叶子结点、分支结点。当然了

6、，根结点也是分支结点的一种。树呢，我们看是一个层次的结构，那从根结点，沿着分支呢，能走到任何一个结点。从根到这个结点所经过的分支和结点，构成了一条路径。这条路径叫从根到这个结点的路径。在树里面还有一些术语，根我们族谱里面的术语差不多。因为，树这样的个结构，最早就是从族谱中的来的。有孩子结点、双亲结点、前面我们讲到了根和子树根的关系，是父子关系，或者是双亲和孩子的关系。对于树根来说，是树根的孩子，那么反过来，这个跟对子树根来说，它是双亲。兄弟结点呢，是有相同的根的子树，这些子树根之间的关系呢，就是兄弟关系了。它们有相同的双亲。有了兄弟结点，呢我们还可以得到堂兄弟结点。祖先结点的定义呢，我们说从根

7、到结点有条路径，这条路径有假设干个结点，这些结点都是它的祖先。包括它的祖父、太祖父、等这些都是它的祖先。那子孙结点就是，在这棵根以下的结点，都是它的子孙结点。树是一个层次的关系：所以在树上的结点呢，它有它的层次，我们假设根结点的层次为1以下的结点呢，就依次类推了。那也就是说第1层的结点的子树根结点的层次为1+1层。从刚刚这棵树看，A是第一层的，BCD是第二层的。EFG是第三层，的IJ是第四层。叶子结点最大的层次数，我们称之为树的深度。树的深度：树中叶子结点所在的最大层次，就是树的深度。这里面我们要强调一下，数据结构在这个树的层次上来讲呢，有时候约定是不一样的，有的书上把根结点的层数设为0,有的

8、设为L我们在这设定为1.这个时候呢。树的深度是不变的，还是最大层次数，叶子结点的层数变了，变成原来的层数减L(在看别的书的时候，要看一下说明，如果根节点层为0的话，深度和最大的叶子节点层次数差1)那么在数据结构中呢，树和森林是不一样的，但又是两个密切相依赖的两个概念，森林呢，是M棵互不相交树的集合。反过来，从另外一个角度，树的定义可以由森林来定义。就是说任何一棵非空树是一个二元组T=(root,F)都是有一个根和子树森林构成的。(画图)比方(这样的一个树，我去掉了根结点，就可以看作是由3棵树构成的一个森林，这是一二三棵树。这个森林加上一个根，就是一颗树。反过来，森林又是树的集合。这个概念我们以

9、后也会经常用到)下面我们看，树的根本操作。树的根本操作比拟多，我们可以分为三类进行讨论，一类是查找，一类是插入，一类是删除。我们先看查找。查找呢一种是特定的查找种是按关系查找，比方我们查树的根root(T).或者找树上的某个结点返回它的值、或者是给一个值返回树上的这个结点。VaIUe(T,cuje)一种是按关系的查找，有找双亲结点Parent(TCUje)。取这个结点的双亲。反过来，我们按照孩子的关系来找。树呢，有多个孩子，以后，我们会知道，我们是根据第一个孩子，和兄弟关系来找的。一个是每一个结点最左边的孩子，一个是每个结点的右兄弟。那我们看，通过找这个结点的左孩子LeftChild(T,cu

10、r_e),在找这个孩子结点的右兄弟RightSibling(T,cuje),当把有兄弟找完之后，这个结点的孩子结点就完全找到了。还有就是对树的特性进行的操作，一个是看树是不是为空TreeEmPty(T)。一个是树的深度TreeDePth(T),还有一个树的重要操作呢，是树的遍历TraverseTree(T5VisitO)=l）.怎么证明呢，我们用归纳法：（画图）。I=I的时候，显然成立，只有一个根结点。2的零次方等于1.我们现在假设i在第k层满足这样的条件就是i=k时，它的结点数呢，满足最多也就是2k“个。那当i=k+l时，由于这一层的结点是上一层结点的子树根。每一个结点最多有两个子树根。那在

11、i=k+l层,结点数最多也就是上一层结点数X2.就是2皿*2=2k=2,性质2：它是说，深度为h的二叉树。它的结点数最多为2工1。深度为h的二叉树呢共有h层，我们让每一层取得结点数最多。看一看h曾最多有多少。从第一层20+2+22+0+2h,=2工1（等比数列的求和公式）。所以深度为k的二叉树上至多还有2J1。这个性质是由性质1得到的。性质3：对于任何一颗二叉树，如果它含有no个叶子节点。n2个度为2的结点。那么它必然存在一个关系式：n=n2+l.（二叉树上的节点只有三种，有多少个度为1的结点，度为0的结点和度为2的结点一定满足这样的关系。（画图，假定二叉树上度为零的结点是no.）度为1的结点

12、的个数是nl.度为2的结点个数为n2。那么总的和肯定是二叉树上总的结点数目n=n+nl+n2,如果二叉树上分支的数目等于b的话，我们分支的数目和节点的数目的关系是什么呢？（画图说明）对于二叉树的结点来说，除了根结点，其他的结点都能找到它的双亲，有一个双亲说明有一个分支，那意味着结点数比分支数多了一个，也就是n=b+l.那么我们看这些分支是谁产生的呢，我们反过来看，度为1的结点产生一个分支，度为2的结点产生两个分支。度为零的结点不产生分支。因此b=2n2+nl那n=2n2+nl+l）。这样我们就得到了两个式子，一个是n=n+nl+n2这是从结点的度的类型这个方面来看。而第二式子那么说明了这些所有

13、节点n和分支数目的关系，而这个分支数目是度为1和度为2的结点产生的。因此，把上面两个式子联立一下，相减：得到n（l-n2=0这就是n=n2+l.那这个式子的意思就是，不管二叉树上有多少个度为1的结点，度为零的结点和度为2的结点存在着这样一个关系。后面两种重要特性呢，涉及到两种特殊的树。一种叫满二叉树：它指的是深度为k且含有2仁1个结点的二叉树。那也就是说什么是满二叉树，那就是说这个二叉树上面不存在度为1的结点。而且除了叶子结点以外，每个结点都有两棵子树。而且只有最后一层是叶子结点。其他都是分支结点。就是每一层都取它最大的结点数。那么就是一个满二叉树。对于满二叉树，我们可以从上到下，从左到右这样

14、进行编号，进行编号以后呢，我们就引出了完全二叉树的概念：树中所含有的n个结点和满二叉树中编号为1至n的结点一一对应。下面我们画一个图来表示。这是一棵满二叉树、我对它进行编号，从1到15.o什么是完全二叉树呢，就是说如果完全二叉树有5个结点。那么这五个结点应该和满二叉树的1到5个结点对应。如果有6个结点、7个结点。那也就是说完全二叉树有这样一个特性，上面每一层都是满二叉树。只有最后一层不满。而且不满也是按照顺序从左到右的依次出现。完全二叉树，在以后的应用中呢，是经常会用到的，所以对于完全二叉树有两个重要的特性。(如一个节点和编号10对应而是和编号11对应了)性质4：具有n个结点的完全二叉树的深度

15、为IOgnJ+Io我们看这个的证明。(画图)假定这个完全二叉树的深度是ko那么它的节点数最大不会超过2k-l,最小呢一定大于深度为k-1的满二叉树，因为你至少的在深度为k的这一层有一个结点。即2kLln=2kJ那也可以这样写：就是2k-,=n2k这样，我们给这个不等式两边取对数。k-l=log2nn,那么该结点无左孩子，否那么，编号为2i的结点为其左孩子结点；(3)假设2i+ln,那么该结点无右孩子结点，否那么，编号为2i+l的结点为其右孩子结点。下面我们就来证明这三个特性，我们先看对于编号为i的结点如果左孩子存在的话，一定是编号为2i,如果右孩子存在的话一定是2i+L我们看对于i=l的时候，

16、我们可以看到如果有左右孩子的话，(画图)一定是2i和2i+l现在我们看一般的情况，对某一层，假设为第k层某一个结点的编号。对于完全二叉树来说，也就是说前面k-1层是满的。这个k-1层结点的个数呢，是2的kl次方减L因此这个节点的编号一定是2的kl次方。下面，我们看它的下一层，这意味着前面k层的个数是满的，一定是2的k次方减1.也就是说这个结点的编号是2的k次方。那么它的兄弟结点呢，一定是2的k次方加1.那么就是说，如果这两个结点存在的话，也就是说2的k次方加1小于n的话，那么这个就成立的。我们用归纳法，对于第i个结点满足这个关系，就是I左孩子是2i,右孩子是2i+l那么我们看它的兄弟，它的兄弟

17、呢，编号一定是i+L它的兄弟的左孩子的编号,显然是这个2i+l结点紧挨着的下一个编号。也就是2i+l的堂兄弟应该是2i+2,它的右孩子呢，应该是2i+32i+2=2(i+l),2i+3=2(i+l)+l所以呢我们这个假设就是成立的，由归纳证明就可以得到。那反过来由这个关系我们很容易得到，如果这个结点的编号是i的话，那它的双亲就是i2o那如果这个结点是i的话，那么他的双亲就是i/2取下整。这个关系呢，是我们以后经常会用到的。关于二叉树的概念呢，我们就讲到这里。下面我们看一下，二叉树的存储结构。二叉树有各种存储表示法，第一种呢，叫二叉树的顺序存储表示。我们用C语言来描述它，就是把二叉树的这个结点呢

18、，存储在一维数组中间。这个一维数组的最大值呢，我们设定为100.二叉树结点的个数呢，由具体的二叉树的结点个数来定。那么如何把这个层次的关系、左右子树的关系用一个一维数组来表示它呢。我们知道一维数组就存储ABCDEF这样的结点。我们知道顺序存储结构仅仅存储的这些ABCDEF结点，而不存储他们之间的关系，他们的关系用固定的的一个位置上的相邻来表示。如果我们把这棵树看成是满二叉树或完全二叉树的一局部。那也就是说把根结点放在一维数组的第一个分量里面，编号为1.的话，那么BD就应该是23。这样的话，我们用含有六个元素的二叉树呢，我们用一个14个分量的一维数组就可以完全表示了。如下列图所示：0123456

19、78910111213ABD（!：1-那么也就是说为了表示这样一个具体的二叉树的结点呢，每个结点不是挨着存储。而是按照它的编号是多少而存在相应的数组分量里面。显然，这种存储方式呢，仅适合与完全二叉树。因为对于完全二叉树来说，前面的元素都是满的。而这个二叉树呢，为了把这个树的左右关系表示出来，我们必须空出很多的空间，所以就很浪费空间了。因此，对于任意的一个二叉树呢，我们不用这样的存储方式。但是对于完全二叉树呢，用这一种方式是相当方便的。这是第一种顺序存储表示。由于二叉树有两个后继，我们经常的用两个指针指向它的后继，下面呢，我们就看看二叉树的链式存储表示。二叉树的链式存储表示，由于结点的不同，可以

20、有各种的存储表示方法。其中最简单的是二叉链表，所谓二叉链表，就是二叉树的结点里面含有两个指针域，一个数据域。整个树呢，我们就用指向根结点的指针就可以表示了。我们简单的画一棵二叉树。（画图）每个结点呢，有两个指针域，左边的指示它左子树的根，右边的指示它右子树的根，对A来说，它的左子树根是B,B的左子树根为空，右子树根是C。而C是叶子结点。叶子结点的指针为空，整个二叉树用指向根结点的一个指针就可以表示了。每个结点呢，都有指向左子树和指向右子树的根，那它的双亲关系呢，是当我找到这个结点是某一个结点的左子树或右子树的话，那反过来这个结点就是这个结点的双亲，所以双亲的信息，我们也包含着，只是是一个隐含的

21、信息，而不是显著的。那么如果某些情况下你想把双亲结点的信息表示出来的话，那么很简单，我们就在指针域里面加一个指针，加一个指针域指向它的双亲，那么根结点的双亲域显然是空的，B的双亲是A,这个结点双亲也是A,这个结点双亲是B。这样的话结点里面有三个指针了，我们把这就叫做三叉链表。三叉链表和刚刚二叉链表的差异呢，仅仅是多设了一个指针域。整个二叉树呢，还是由指向根结点的一个指针来表示了。那么我们可以只指示左右子树，隐含着双亲信息，反过来我们也可以仅仅表示双亲信息，让左右子树的信息隐含在内，来表示这个二叉树。但是对于二叉树来说，它的子树根呢，一定是有左右之分的。因此如果只含有双亲信息的话，表示是不完备的

22、。那么这个结点呢我们就用一个数据域，指向双亲的指针，和左右孩子标志域来表示。整个二叉树呢，我们是把这些所有的结点放在一个一维数组里面来表示的。加上结点的数目，和根结点的位置，就形成了这样二叉树的一个表示方法。这个表示方法，我们称之为双亲链表。例如我们对刚刚这棵二叉树，我们有四个结点ABCD,每个结点呢，在数组里面有一个下标，结点本身的有一个数据域，还有一个双亲域，这个双亲域我们不是给出双亲结点的数据，而是给出他的双亲结点在这个一维数组里面所在的位置，它是在零的分量里面，所以它的双亲结点就是零。同时B呢是A的左孩子，D是A的右孩子。C呢，是B的右孩子，C的双亲就是U用J来表示没有双亲。那么整个二

23、叉树呢，是用这样一个结点类型的一个一-维数组来表示的。同时，我们还要用，根结点的位置0.和整个结点的数目4来表示。那也就是说，我们从0到3的这个数组里面的分量呢，存储着这个结点里面的信息。这就是双亲链表。因为我们树呢，是从根往下的一个有向树，因此我们只用一个指示根的指针和一个二叉链表呢，就可以完全确定这二叉树了。双亲链表呢，如果我们只用一个指向双亲的指针的话，那每个结点就是孤立的。分散的。所以我们要把它和起来，和在一个一维数组里面。才能够整个来表示它.二叉树的链式存储表示呢，还有一种线索链表，我们等以后讲到线索树的时候再讲。前面，我们讨论了三个问题，一个是树的类型定义，二叉树的类型定义，以及二

24、叉树的特性，还有二叉树的存储结构。下面我们要讨论这章的个主要的问题，叫做二叉树的遍历。那么在这一节里面,我们准备讨论这样五个问题。这五个问题从问题的提出，到遍历算法的描述，一直到遍历算法的应用。我们首先看，问题的提出。也就是什么是遍历：顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅仅被访问一次。这个访问的含义呢，可以是各种个样的。比方说，输出结点信息，或对结点进行赋值。那么这样一个结点遍历的问题呢，对于任何一个结构都是存在的。遍历是任何一个结构的根本操作，但为什么我们前面没有强调呢，因为对线性结构来说，每个结点只有一个后继，因此从第一个结点出发，它只有唯一的一个搜索路径

25、，这是很自然的，所以我们就不需要重点的讨论，自然就会实现这样一个遍历的操作了。但是二叉树不一样，二叉树是一个非线性结构。每个结点有两个后继，那么就存在着按什么样的搜索路径来进行遍历的问题了。对于二叉树来说，它有两个后继,它可以有这样三条搜索路径。第一条是先上后下的按层次的遍历。先访问根结点，然后访问根节点的子树根。对于每一层来说呢,先左后右。那么先访问它的根结点，如果有左子树，访问它的左子树，如果没有左子树，访问它的右子树。然后在访问它子树的子树。一层一层的往下遍历，这是一种搜索路径。第二种：先左后右的遍历，二叉树不是有两棵子树吗？整个二叉树的遍历就可以看作是，对左子树的遍历和对右子树的遍历的

26、和。那么对于根结点的遍历，就是根结点就有一个结点，直接访问呢就好了。那么左右子树呢，有一个先一个后的问题。-种搜索路径呢，是我先左后右，我先去遍历左子树,然后在遍历右子树上所有的结点。反过来，还有就是先访问右子树上的结点，然后再访问左子树上的结点。这两条路径呢是相反，单是完全对称的。我们讨论其中一条就可以了。下面我们就重点讨论先左后右的遍历。先左后右的遍历算法有先根、中根、后根三种遍历算法。那我们首先来看一看什么是先序的遍历算法，什么是中序的遍历算法，什么是后序的遍历算法。我们现在有这样一颗二叉树。（邮递员模拟的问题）下面看先根序遍历算法的描述，很简单：如果二叉树为空树，那么空操作，什么就不用

27、做了，否那么，的话，访问根结点先序遍历左子树先序遍历右子树中根序遍历算法的描述，很简单：如果二叉树为空树，那么空操作，否那么：中序遍历左子树访问根结点中序遍历右子树后根序遍历算法的描述，很简单：如果二叉树为空树，那么空操作，否那么：后序遍历左子树后序遍历右子树访问根结点这里需要注意的是如果你整个二叉树是后序遍历，那么你遍历子树的时候也是什么样的遍历。(中序、先序是一样的。)上面呢，我们给出了遍历的定义。下面也就是第三个问题，我们看一下算法的递归描述。我们用C语言呢，来把刚刚的算法描述一下。整个算法的描述呢，主要有递归和非递归的算法，我们主要看一下递归的算法。如果二叉树是空树，什么也不做了，所以

28、我们先序遍历是在二叉树不空的前提底下。、voidPreorder(BiTreeT,void(*visit)(TElemTypefee)/先序遍历二叉树if(T)visit(T-data);/访问结点Preorder(T-lchiId,visit);/遍历左子树Preorder(T-rchiId,visit);/遍历右子树其他的中序和后序遍历。与这个是非常类似的，只要你调整这三个语句的位置就可以了。要注意的是，还是采用递归的方式来进行遍历的。第四个问题，有的时候呢，我们还需要有非递归的算法的描述。我们现在就看一下，中序遍历算法的非递归算法是怎么样的。我们首先分析一下，中序遍历算法的规律。中序遍历

29、，对于每个结点来说，都是先遍历它的左子树，因此对于这个二叉树来说呢，对于A来说，先遍历左子树。同样对于B子树来说，也是先遍历左子树。什么时候访问它本身呢，就是在左子树空的时候，才接着访问B结点。所以我们从A开始中序访问遍历的第一个结点一定是B.也就是说我们从根节点出发，一直往左走，如果这个结点还有左子树还往左走，走到这个结点的左子树是空为止。那这个结点B就是我遍历访问的第一个结点。那么我一直往左走，我将来还是一定要回来的。也就是说我要能在访问完左子树的情况下，退回到这个根结点。也就是说我要能够退回到A.也就是说能够顺着原路退回，因此我们要把路过的结点给保存下来。那也就是什么啊，先走到的后访问，

30、后走到的先访问。显然保存这些结点的一个数据结构呢，就应该是一个栈了。假定我们现在有一个栈在这里。现在我们从A出发，往左走。A呢，就要入栈。入栈以后，我们就到了B。例如有一个指针指向B了。这时候，我们发现B呢，没有左子树。那么我们就直接对B进行访问。应该是遍历右子树。那现在有右子树，就进行遍历。所以我们就将P指过来，遍历以右子树为根的一个二叉树。对于C来说它也有左子树，它也要入栈。现在指针走到D。走到D以后，发现D没有左子树。所以就对他进行访问，D访问完了以后应该是去遍历右子树，但是现在右子树是空，说明以D为根的这个二叉树已经遍历完了。遍历完了以后，我们要往回退，退到哪里呢，退到C。退到C呢。我

31、们知道这个C退出来，肯定是从左子树回来的。所以对它进行访问。访问完了以后，我们要遍历右子树。现在右子树是空的。那么以C为根的子树也遍历完了。显然应该还是往回退。根据栈顶的指示，就退到a了。退到A后呢，就应该对它进行访问了。访问完了以后，我们还要遍历以它的右子树根为根的这样一个二叉树。从新往左走，它现在它的左子树是空的。所以我们就直接对他进行访问了。访问完了以后呢我们要遍历以F为根的一-颗二叉树。这时候F存在左子树。F入栈，往左走。G存在左子树。G入栈,往左走。H没有左子树，所以对他进行访问。然后往右走，但是右子树是空。然后根据栈顶的指针，我们退回到G,然后对G进行访问。K没有左子树，对K进行访

32、问。然后往右走，没有右子树，又退回去，退到哪里，根据栈顶指示退到F。对F进行访问，右子树为空，这时候，栈为空了，说明整个中序遍历就结束了。也就是我没有一个结点，它的右子树还没有遍历。那么从这个我们指针走的过程中，发现一个根本操作。就是往左走入栈。有一个这样一直往左走，入栈的根本操作。下面看到的就是这样一个一-直往左走的这样的操作，从指针T所指的这个根结点出发，一直向左走，走到哪里呢，走到一个左子树为空的结点，拿指向这个左子树为空的这样一个结点的指针返回。走的过程中呢，把那些含有左子树的结点都入栈。那也就是说，如果我们T是空的话，就是一棵空树，返回的NULLo如果这个T本身不空，那么我就看它左子

33、树是不是空。如果左子树空，那就返回它本身了。如果左子树不空的话，那么本身这个结点的指针入栈。然后顺着左指针呢，往左走。一直走到左子树根为空的那个结点返回。那么再有了这个向左走的根本操作以后，这样一个二叉树的非递归的算法。这个T是指向二叉树根结点的指针。首先就是一直往左走，如果二叉树是空，返回NULL这样整个遍历就结束了。否那么的话，一定返回一个指针是不空的。那么就对这个指针所指的结点进行访问。如果它右子树结点不空，再从他右子树的根结点出发，一直往左走。走到一个左子树为空的结点，进行访问。然后再从这个结点的右子树的根出发，往左走。那如果这个结点的右子树是空的话，那我们要看看栈是否为空。如果栈空整

34、个遍历就结束了。如果栈不空的话，就从栈里退出来，退出来以后，这个结点要进行访问。然后再往右走。当栈为空的时候呢，整个中序遍历就结束了。前面我们介绍了二叉树的遍历算法，包括问题的提出，算法的递归描述、以及中序算法的非递归描述。整个遍历呢是非常简单的，大家主要掌握它的递归形式的算法。整个二叉树的遍历算法是二叉树操作的一个核心。其实二叉树的应用呢，有很多的操作都是在二叉树遍历的根底上进行的。下面我们就看看如何利用二叉树的遍历操作完成其他的一些操作的例子。第一个例子呢，是统计二叉树中叶子结点的个数。我们用先序遍历来做。二叉树的叶子结点呢，是左右子树为空的度为。的结点。那么这个题呢，就是看二叉树上有多少

35、个叶子结点。我们首先分析一下这个问题，二叉树根本上有三种情况。1,假定二叉树是空树，那么叶子节点的数目肯定为零。2假定二叉树上只有一个根结点，那这个根结点本身就是叶子结点，所以它的叶子结点数目就是1.3第三种情况就是二叉树的结点数大于二的情况。那么这个二叉树的叶子结点的个数，就是左子树上叶子结点的个数和右子树上叶子结点数之和。那我们看一下这个程序。首先这个函数有两个参数，现在统计以这个T指针所指的二叉树上叶子结点的个数。个数的和呢，累加到这个CoUnt变量里面。这个变量的初值呢，等于零。如果这个二叉树是空的话，那么就什么都不做，count还是零。第二种情况，我们说本身这个树不空，但是左右子树都

36、为空，证明它是一个叶子结点，那么CoUnt数加1。如果左右不空，那么我们就递归调用这个函数，统计左子树上叶子结点的个数，在统计右子树上的叶子结点的个数，最终我们会得到整个树的叶子结点的个数。那这个过程呢，其实就是一个遍历操作，先遍历左子树，把叶子节点的个数累加上去，再遍历右子树，把结点的个数累加上去。我们看这样颗左子树的叶子结点的计算过程。如果二叉树不是叶子节点，那么它的叶子结点个数等于左子树叶子结点个数和右子树叶子结点的个数。这里我们要注意递归调用就是说对于每一个结点的操作都是相同的。第二个例子呢，我们求二叉树的深度。同样我们先分析一下二叉树深度的定义。二叉树的深度我们定义为：叶子结点的最大

37、的层次数。反过来，我们对二叉树的深度可以这么来看。如果二叉树是空树,那么它的深度就等于零。如果只有一个根结点的话，那么它的深度就是I.假定我们这样一棵树，假定左子树的深度为dl,右子树的深度为d2.那么对于整个二叉树来说。它的深度是不是应该是这两个深度的最大值加1.所以我们对于二叉树来说呢，分析问题呢，可以用二叉树本身递归的定义来分析，二叉树是一个根结点加上两颗子树，那么我们求树的深度，就可以先求子树的深度，然后加1,就可以了，但是对于子树呢，我们还是先求子树的子树深度然后加1.所以呢我们这个过程其实还是一个递归的过程。我们求二叉树的深度呢，我们用后序遍历来求，如果二叉树是空树，那么它的深度为

38、零，如果二叉树不空，我们就认为它一定有一个左子树、一定有一个右子树，分别求它左子树的深度和右子树的深度。整个树的深度呢，就是左右子树深度的最大值，再加上1.二叉树的很多操作呢，都是在二叉树递归定义的根底上，利用遍历来完成。你用什么样的遍历呢，那么根据问题的性质不同而不同。统计二叉树的叶子结点的个数，我们只要用先序遍历就可以，当然你也可以用后序遍历，一般我们能用先序遍历的话，就用先序遍历。而我们求树的深度呢，必须在左右子树的深度的根底上，才能求得树的深度。因此，必须用后序遍历，在求得左右子树深度的根底上，最大值加1,才是树的深度。第三个例子，就是复制二叉树。所谓复制二叉树，就是按照原来的二叉树的存储结构，我另外再生成一个二叉树，这个二叉树和原来的二叉树是一模一样的。那我们只要按照原来的二叉树的结点呢，再生成一个。假设这个树用二叉链表来表示。那么我们用指向根的一个指针就可以表示这个树。这个根结点里面有三个域，一个数据域，一个指向左子树，一个指向右子树。复制操作呢，就是要我们生成一个结点，数据域相同，把原来的拷贝过来就可以了。同样这个复制过来的树的左子树要跟我们原来的树的左子树相同。同样我们复制得到右子树。那么指向这个结点的指针，就是我得到的新的二叉树的根指针。那这个复制左子树和右子树的做法，和我们的