数据结构树和二叉树教案.doc

/第六章 树和二叉树/下面呢，我们就讨论第六章、树和二叉树。那么我们回忆一下数据结构四大类。第一类，线性结构，除了广义表以外，我们都讨论完了。现在我们开始讨论第二大类，树形结构，在树形结构里面呢，我们主要讨论两种结构。一类树，一类二叉树(线性结构里头我们讨论了什么？)。首先，我们先看树的数据类型定义。那先看数据对象D：具有相同特性的数据元素的集合，这就是它的数据对象。数据元素之间是一个什么样的关系呢，我们用下面这段话来描述。如果数据对象是一个空集，我们称之为空树。从这里看得出来，所有的数据结构都这样一个空的这样一个结构。空串、空表等等。空树的意思是一个数据元素都没有。否则的话，如果这个集合不是一个空集的话，那么在这个数据结构里面一定存在一个成为根的数据元素root，而且这个数据元素一定是唯一的。就是说，一定存在，而且唯一。那么就是说除了空树以外，如果数据集合里面只有一个数据元素的话，那么这个数据元素，就是这个树的根。如果说这个数据集合里面的元素个数大于1的话，其余个结点呢，我们一定可以给它分成m个子集。这些子集互不相交。并且每个子集本身呢，又是一棵符合上面定义的树。这些子集是树，而且称之为根的子树。我们看一个例子，（画图）ABCDEFGIJ 这是一个树，当然它不是空树，这个树呢是9个数据元素的集合。一定存在这一个叫做根的结点。这个A呢，我们称之为树根，除了这个根以外，我们可以分成这样三个集合。以B开始的一个子集，以C开始的一个子集，和D开始的一个子集。这三个子集互不相交，每个子集呢又是一棵树，并且它和根呢，有一个关系存在，这棵树叫做根的子树。这棵树呢，又存在一个根结点，这root根和我们子树根之间，存在这一个这样一个前驱后继的关系，一般画树，我们不画箭头，但是我们讨论的是有向树，是有箭头的。就是说BCD是A的后继。那对于B的这样一个子树，又是符合我们定义的子树，那就是说它有一个根结点，它有两颗子树。在根结点和子树根之间呢，又存在一个前驱和后继的关系，那对E、F来说，它们本身又是一颗树。对于E这棵树来说，它的数据元素只有一个，所以它是仅含有根结点的一颗子树。在定义的时候我们说还有空树的，但是在实际使用的时候，是没有意义的。由于我们数据结构和离散数学还是有一定的关系的，在离散数学中，为了一些数学上的完整性的定义，才有空树这样的定义，在我们数据结构中也有定义，单实际上用处不大。这就是树的类型的一个结构特性。下面我们本来就该讨论基本操作了，但是对于树来讲呢，还有一些基本术语介绍一下，以便我们对基本操作的理解。下面就看有关树的基本术语。现在先来看一下有关树的术语。树当中，它的基本单位是一个结点：什么叫结点呢：数据元素+若干指向子树的分支比如刚才我们举的那个例子，一个数据元素A+指向BCD的子树的分支，那就称一个结点。结点的度：结点上指向分支的个数（在树上面每个结点的度可能是不一样的，比如我们分解到只含有一个根结点的子树时，它没有子树也没有分支，那它的度就是零。对于刚才的根结点，它的度就是3.）整个树的度; 我们定义为：整个树当中所有结点的度的最大值。对于我们刚才的那棵树呢，这棵树的度呢，就是3，因为，结点最大的度是3.叶子结点：对树来说，分解到最后，对于子树来说就一个根节点，度为零的结点。（也就是只有一个根结点的子树。对于这样的一个结点，是没有子树的，它对于整个树来说，是很特殊的，叫做叶子结点。除了叶子结点，其他的结点的度都是大与零的。）反过来我们把它叫做分支结点：就是那些度大于零的结点。对于一棵树来说呢，我们经常要谈到的是，根结点，叶子结点、分支结点。当然了，根结点也是分支结点的一种。树呢，我们看是一个层次的结构，那从根结点，沿着分支呢，能走到任何一个结点。从根到这个结点所经过的分支和结点，构成了一条路径。这条路径叫从根到这个结点的路径。在树里面还有一些术语，根我们族谱里面的术语差不多。因为，树这样的一个结构，最早就是从族谱中的来的。有孩子结点、双亲结点、前面我们讲到了根和子树根的关系，是父子关系，或者是双亲和孩子的关系。对于树根来说，是树根的孩子，那么反过来，这个跟对子树根来说，它是双亲。兄弟结点呢，是有相同的根的子树，这些子树根之间的关系呢，就是兄弟关系了。它们有相同的双亲。有了兄弟结点，呢我们还可以得到堂兄弟结点。祖先结点的定义呢，我们说从根到结点有一条路径，这条路径有若干个结点，这些结点都是它的祖先。包括它的祖父、太祖父、等这些都是它的祖先。那子孙结点就是，在这棵根以下的结点，都是它的子孙结点。树是一个层次的关系：所以在树上的结点呢，它有它的层次，我们假设根结点的层次为1 以下的结点呢，就依次类推了。那也就是说第l层的结点的子树根结点的层次为l+1层。从刚才这棵树看，A是第一层的，BCD是第二层的。EFG是第三层，的 IJ是第四层。叶子结点最大的层次数，我们称之为树的深度。树的深度：树中叶子结点所在的最大层次，就是树的深度。这里面我们要强调一下，数据结构在这个树的层次上来讲呢，有时候约定是不一样的，有的书上把根结点的层数设为0，有的设为1.我们在这设定为1. 这个时候呢。树的深度是不变的，还是最大层次数，叶子结点的层数变了，变成原来的层数减1. （在看别的书的时候，要看一下说明，如果根节点层为0的话，深度和最大的叶子节点层次数差1）那么在数据结构中呢，树和森林是不一样的，但又是两个密切相依赖的两个概念，森林呢，是M棵互不相交树的集合。反过来，从另外一个角度，树的定义可以由森林来定义。就是说 任何一棵非空树是一个二元组 T=（root，F）都是有一个根和子树森林构成的。 （画图）比如（这样的一个树，我去掉了根结点，就可以看作是由3棵树构成的一个森林，这是一二三棵树。这个森林加上一个根，就是一颗树。反过来，森林又是树的集合。这个概念我们以后也会经常用到）下面我们看，树的基本操作。树的基本操作比较多，我们可以分为三类进行讨论，一类是查找，一类是插入，一类是删除。我们先看查找。查找呢一种是特定的查找一种是按关系查找，比如我们查树的根root(T)。或者找树上的某个结点返回它的值、或者是给一个值返回树上的这个结点。Value(T,cur_e)。一种是按关系的查找，有找双亲结点Parent(T,cur_e)。取这个结点的双亲。 反过来，我们按照孩子的关系来找。树呢，有多个孩子，以后，我们会知道，我们是根据第一个孩子，和兄弟关系来找的。一个是每一个结点最左边的孩子，一个是每一个结点的右兄弟。那我们看，通过找这个结点的左孩子LeftChild(T,cur_e)，在找这个孩子结点的右兄弟RightSibling(T,cur_e)，当把有兄弟找完之后，这个结点的孩子结点就完全找到了。还有就是对树的特性进行的操作，一个是看树是不是为空TreeEmpty(T)。一个是树的深度TreeDepth(T)，还有一个树的重要操作呢，是树的遍历TraverseTree(T,Visit()。以上是根查找相关的操作。第二呢，我们看插入的操作，一，我们看初始化一个空树InitTree(&T)。二、还有根据定义来建立一颗树CreateTree(&T,definition)，这个定义呢，可以有各种给法，比如给一个root和一个森林。或者呢，我给树上的每个结点，结点的每个孩子结点，一直到叶子结点为止，这样也可以定义一个树。所以呢，我可以根据一个定义，创建一棵树。三、给树的某个结点赋予一个值Assign(T,cur_e, value)。第四个呢，插入一个孩子结点InsertChild(&T,&p, i, c)。就是在T这棵书上，在p所指的这个结点上，插入一个c的一个子树，位置呢，由i来确定。第三个呢，是关于删除的操作，这些操作包括，清空树ClearTree(&T)、销毁树DestroyTree(&T)，把树T中p结点的第i个孩子删除, DeleteChild(&T, &p, i).这是树的基本操作的定义。我们讨论的树呢我们要说明一下，我们讨论的树呢，是一个有向树。虽然我们画图的时候不画箭头，但是我们根和子树之间呢，有一个前驱和后继的关系，所以每一棵树 1） 有确定的根，2）树根和子树根之间有为有向的关系。一般就叫树，但实际上，讨论的是有向树。但是我们讨论的树和子树之间呢可以有次序，也可以无次序，子树之间是否存在次序关系，决定了我们这棵树是有序树，还是无序树。子树之间存在次序则是有序树，子树之间不存在次序则是无序树。我们看最早的例子，这里我们再画一颗树。这两棵树的差别在于哪里呢，差别不在于结构，9个元素，三个棵子树。只不过子树的次序位置变化了。如果你讨论的是无序树，那么这两棵树是相同的，如果你讨论的是有序树，那么这两棵树就不等同，通常我们讨论的树呢，都是无序树（除了你特殊说明以外）。因为我们树这个结构在我们非数值型程序领域，主要描述我们日常生活中的这种层次关系，也就是上下级的关系，而对同级来说呢，是不讲次序的。因此，我们讨论的主要是无序树，那也就是说在无序树底下，这两棵树是等同的。这个呢，我们说是有关树的一些定义。现在，我们把树这样一个结构呢，和线性结构来比较一下，首先我们看，线性结构，它肯定存在一个没有前驱的第一个数据元素，那么在树形结构里面，也存在这一个没有前驱的元素，就是这个根结点。这一点呢，和顺序结构是类似的。都存在一个没有前驱的数据元素。在线性结构里面，只有一个没有后继的线性数据元素， 我们称之为最后一个元素，那么在树结构里面呢，就是度为零的结点，我们称之为叶子结点，在树里面，叶子结点就不是一个了。而可以有多个。其他的元素呢，在线性结构里面呢，都唯一有一个前驱，一个后继。树中的其他结点呢，分支节点，有一个前驱，可能有多个后继。所以我们说线性结构呢，是一种一对一的结构，而树形结构呢，是一种一对多的结构。从根开始，它可以有多个子树根，而每一个子树根上面只有一个双亲，底下呢，可以有多个孩子结点。一直到叶子结点呢，它没有后继。这就是从线性结构一对一的关系，扩展到树结构1对多的关系。以后我们会知道将树的结构再扩展到图的结构。那么这个就是关于树的类型定义。当然我们一般情况下，就该讨论树的实现和操作了，但是由于树的结构有它的不确定性，就是说它每个结点的度呢是可以不同的，它处理起来呢，相对来说比较麻烦一些。在这种情况下，我们就讨论一种结构相对固定的树，也就是下面我们要将的二叉树，在以后我们会知道对树的这样一种结构我们会转化为二叉树来讨论的。所以我们下面就要从新看一下二叉树的类型的定义。第二个问题，二叉树的类型定义。二叉树的定义呢，我们就不按照数据对象、和数据关系来说了，简单的看一下文字的描述就可以了，这样比较简洁。二叉树或为空树；或是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成的。（画一个二叉树的例子）二叉树也一定有一个根结点。除了根结点以外，其他结点分成两个互不相交的结点的集合。每一个集合是根的子树，同时它本身又是满足定义的一颗二叉树。二叉树的定义上有非常重要的一句话。就是这棵二叉树叫做根的左子树。这棵二叉树叫做根的右子树。那么我们再看二叉树的定义，虽然每个根结点只有两棵子树，这两棵子树都有特定的含义，一个叫左子树，一个叫右子树。当然这个左、右子树本身又可以是空树。比如B这个二叉树，它是由一个空的左子树和一个不空的右子树组成的。二C这个二叉树是由一个不空的左子树和空的右子树构成的。同样对于D这棵树，它是由左右都为空的二叉树构成的。所以从上面的定义来看呢，二叉树有五种基本形态，（画图）一种是空树，第二种是仅含有一个空节点的树、第三种是左子树不空，右子树为空的树第四种是右子树不空，左子树为空的树，第五种那就是左右子树都不空的树。左子树为空和右子树为空这两个概念是不同的,不能完全等同，这与我们树里面的有序无序树的情况是不同的。比如有序树，只有一颗子树（画图），对于二叉树来说没有这样的二叉树。对于二叉树来说，你必须明确到底是左子树空，还是右子树空。这一点是很重要的概念，在以后我们讲树的转化的时候呢，我们就会体会到左右的重要性了。二叉树的基本操作呢，跟树一样，我们也分查找、插入、删除三种来看。查找分特定的查找，比如说找根，差值为e的某个节点。也可以按关系来查找，找这个元素的双亲，找结点的左孩子（也就是左子树根），右子树根。如果本身是左子树根，那它就存在右兄弟。如果它本身就是右子树根，那它可能存在左兄弟。还有一些对树的状态的一些操作，比如判树是不是空树，求二叉树的深度。对于二叉树呢，还有四种遍历的操作。插入：初始化、改变二叉树上某个结点的值、根据一个定义生成一个二叉树，比如给出一个根，一个左子树，一棵右子树，我们可以构造一个二叉树。插入，在某个结点上插入一颗以C为根结点的二叉树。插入的位置可以是左子树也可以是右子树。删除：把二叉树清空，销毁二叉树、还有删除某个结点的一颗左或右子树。一般没有删除一个节点的操作，和树也一样，要删就删除一颗子树。二叉树是非常重要的，因为它的结构比较固定，因而有一些重要的特性；我们现在来看一下：性质1：在二叉树的第i层上至多有2i-1个结点（i=1）.怎么证明呢，我们用归纳法：（画图）。I=1的时候，显然成立，只有一个根结点。2的零次方等于1.我们现在假设i在第k层满足这样的条件就是i=k时，它的结点数呢，满足最多也就是2 k-1个。那当i=k+1时，由于这一层的结点是上一层结点的子树根。每一个结点最多有两个子树根。那在i=k+1层，结点数最多也就是上一层结点数2.就是2 k-1 *2=2 k =2 (k+1)-1 性质2：它是说，深度为h的二叉树。它的结点数最多为2 h -1。深度为h的二叉树呢共有h层，我们让每一层取得结点数最多。看一看h曾最多有多少。从第一层20+21+22+。+2h-1 = 2 h -1（等比数列的求和公式）。所以深度为k的二叉树上至多还有2 k -1。这个性质是由性质1得到的。性质3：对于任何一颗二叉树，如果它含有n0个叶子节点。n2个度为2的结点。那么它必然存在一个关系式：n0=n2+1. ( 二叉树上的节点只有三种， 有多少个度为1的结点，度为0的结点和度为2的结点一定满足这样的关系。（画图，假定二叉树上度为零的结点是n0.）度为1的结点的个数是n1. 度为2的结点个数为n2。那么总的和肯定是二叉树上总的结点数目n=n0+n1+n2, 如果二叉树上分支的数目等于b的话，我们分支的数目和节点的数目的关系是什么呢？（画图说明）对于二叉树的结点来说，除了根结点，其他的结点都能找到它的双亲，有一个双亲说明有一个分支，那意味着结点数比分支数多了一个，也就是n=b+1。那么我们看这些分支是谁产生的呢，我们反过来看， 度为1的结点产生一个分支，度为2的结点产生两个分支。度为零的结点不产生分支。因此b=2n2+n1那n=2n2+n1+1) 。这样我们就得到了两个式子，一个是n=n0+n1+n2这是从结点的度的类型这个方面来看。而第二式子则表明了这些所有节点n和分支数目的关系，而这个分支数目是度为1和度为2的结点产生的。因此，把上面两个式子联立一下，相减：得到n0-1-n2=0。这就是n0=n2+1。 那这个式子的意思就是，不管二叉树上有多少个度为1的结点，度为零的结点和度为2的结点存在着这样一个关系。后面两种重要特性呢，涉及到两种特殊的树。一种叫满二叉树：它指的是深度为k且含有2k-1个结点的二叉树。那也就是说什么是满二叉树，那就是说这个二叉树上面不存在度为1的结点。而且除了叶子结点以外，每个结点都有两棵子树。而且只有最后一层是叶子结点。其他都是分支结点。就是每一层都取它最大的结点数。那么就是一个满二叉树。对于满二叉树，我们可以从上到下，从左到右这样进行编号，进行编号以后呢，我们就引出了完全二叉树的概念：树中所含有的n个结点和满二叉树中编号为1至n的结点一一对应。下面我们画一个图来表示。这是一棵满二叉树、我对它进行编号，从1到15.。什么是完全二叉树呢，就是说如果完全二叉树有5个结点。那么这五个结点应该和满二叉树的1到5个结点对应。如果有6个结点、7个结点。那也就是说完全二叉树有这样一个特性，上面每一层都是满二叉树。只有最后一层不满。而且不满也是按照顺序从左到右的依次出现。完全二叉树，在以后的应用中呢，是经常会用到的，所以对于完全二叉树有两个重要的特性。（如一个节点和编号10对应而是和编号11对应了）性质4：具有n个结点的完全二叉树的深度为logn+1。我们看这个的证明。（画图）假定这个完全二叉树的深度是k。那么它的节点数最大不会超过2k-1，最小呢一定大于深度为k-1的满二叉树，因为你至少的在深度为k的这一层有一个结点。即 2k-1-1n=2k-1那也可以这样写：就是2k-1=n2k 这样，我们给这个不等式两边取对数。k-1=log2nn，则该结点无左孩子，否则，编号为2i的结点为其左孩子结点；(3) 若2i+1n，则该结点无右孩子结点，否则，编号为2i+1的结点为其右孩子结点。下面我们就来证明这三个特性，我们先看对于编号为i的结点如果左孩子存在的话，一定是编号为2i，如果右孩子存在的话一定是2i+1. 我们看对于i=1的时候，我们可以看到如果有左右孩子的话，（画图）一定是2i和2i+1。现在我们看一般的情况，对某一层，假设为第k层某一个结点的编号。对于完全二叉树来说，也就是说前面k-1层是满的。这个k-1层结点的个数呢，是2的k-1次方减1.因此这个节点的编号一定是2的k-1次方。下面，我们看它的下一层，这意味着前面k层的个数是满的，一定是2的k次方减1.也就是说这个结点的编号是2的k次方。那么它的兄弟结点呢，一定是2的k次方加1.那么就是说，如果这两个结点存在的话，也就是说2的k次方加1小于n的话，那么这个就成立的。我们用归纳法，对于第i个结点满足这个关系，就是I 左孩子是2i，右孩子是2i+1. 那么我们看它的兄弟，它的兄弟呢，编号一定是i+1. 它的兄弟的左孩子的编号，显然是这个2i+1结点紧挨着的下一个编号。也就是2i+1的堂兄弟应该是2i+2，它的右孩子呢，应该是2i+3. 2i+2=2(i+1)，2i+3=2(i+1)+1 所以呢我们这个假设就是成立的，由归纳证明就可以得到。那反过来由这个关系我们很容易得到，如果这个结点的编号是i的话，那它的双亲就是i/2。那如果这个结点是i的话，那么他的双亲就是i/2取下整。这个关系呢，是我们以后经常会用到的。 关于二叉树的概念呢，我们就讲到这里。 下面我们看一下，二叉树的存储结构。二叉树有各种存储表示法，第一种呢，叫二叉树的顺序存储表示。我们用C语言来描述它，就是把二叉树的这个结点呢，存储在一维数组中间。这个一维数组的最大值呢，我们设定为100. 二叉树结点的个数呢，由具体的二叉树的结点个数来定。那么如何把这个层次的关系、左右子树的关系用一个一维数组来表示它呢。我们知道一维数组就存储ABCDEF这样的结点。我们知道顺序存储结构仅仅存储的这些ABCDEF结点，而不存储他们之间的关系，他们的关系用固定的的一个位置上的相邻来表示。如果我们把这棵树看成是满二叉树或完全二叉树的一部分。那也就是说把根结点放在一维数组的第一个分量里面，编号为1.的话，那么BD就应该是2.3.。这样的话，我们用含有六个元素的二叉树呢，我们用一个14个分量的一维数组就可以完全表示了。如下图所示：那么也就是说为了表示这样一个具体的二叉树的结点呢，每个结点不是挨着存储。而是按照它的编号是多少而存在相应的数组分量里面。显然，这种存储方式呢，仅适合与完全二叉树。因为对于完全二叉树来说，前面的元素都是满的。而这个二叉树呢，为了把这个树的左右关系表示出来，我们必须空出很多的空间，所以就很浪费空间了。因此，对于任意的一个二叉树呢，我们不用这样的存储方式。但是对于完全二叉树呢，用这一种方式是相当方便的。这是第一种顺序存储表示。由于二叉树有两个后继，我们经常的用两个指针指向它的后继，下面呢，我们就看看二叉树的链式存储表示。二叉树的链式存储表示，由于结点的不同，可以有各种的存储表示方法。其中最简单的是二叉链表，所谓二叉链表，就是二叉树的结点里面含有两个指针域，一个数据域。整个树呢，我们就用指向根结点的指针就可以表示了。我们简单的画一棵二叉树。（画图） 每个结点呢，有两个指针域，左边的指示它左子树的根，右边的指示它右子树的根，对A来说，它的左子树根是B，B的左子树根为空，右子树根是C。而C是叶子结点。叶子结点的指针为空，整个二叉树用指向根结点的一个指针就可以表示了。每个结点呢，都有指向左子树和指向右子树的根，那它的双亲关系呢，是当我找到这个结点是某一个结点的左子树或右子树的话，那反过来这个结点就是这个结点的双亲，所以双亲的信息，我们也包含着，只是是一个隐含的信息，而不是显著的。那么如果某些情况下你想把双亲结点的信息表示出来的话，那么很简单，我们就在指针域里面加一个指针，加一个指针域指向它的双亲，那么根结点的双亲域显然是空的，B的双亲是A，这个结点双亲也是A，这个结点双亲是B。这样的话结点里面有三个指针了，我们把这就叫做三叉链表。三叉链表和刚才二叉链表的差别呢，仅仅是多设了一个指针域。整个二叉树呢，还是由指向根结点的一个指针来表示了。那么我们可以只指示左右子树，隐含着双亲信息，反过来我们也可以仅仅表示双亲信息，让左右子树的信息隐含在内，来表示这个二叉树。但是对于二叉树来说，它的子树根呢，一定是有左右之分的。因此如果只含有双亲信息的话，表示是不完备的。那么这个结点呢我们就用一个数据域，指向双亲的指针，和左右孩子标志域来表示。整个二叉树呢，我们是把这些所有的结点放在一个一维数组里面来表示的。加上结点的数目，和根结点的位置，就形成了这样二叉树的一个表示方法。这个表示方法，我们称之为双亲链表。例如我们对刚才这棵二叉树，我们有四个结点ABCD，每个结点呢，在数组里面有一个下标，结点本身的有一个数据域，还有一个双亲域，这个双亲域我们不是给出双亲结点的数据，而是给出他的双亲结点在这个一维数组里面所在的位置，它是在零的分量里面，所以它的双亲结点就是零。同时B呢是A的左孩子，D是A的右孩子。C呢，是B的右孩子，C的双亲就是1。用-1来表示没有双亲。那么整个二叉树呢，是用这样一个结点类型的一个一维数组来表示的。同时，我们还要用，根结点的位置0.和整个结点的数目4来表示。那也就是说，我们从0到3的这个数组里面的分量呢，存储着这个结点里面的信息。这就是双亲链表。因为我们树呢，是从根往下的一个有向树，因此我们只用一个指示根的指针和一个二叉链表呢，就可以完全确定这二叉树了。双亲链表呢，如果我们只用一个指向双亲的指针的话，那每个结点就是孤立的。分散的。所以我们要把它和起来，和在一个一维数组里面。才能够整个来表示它。二叉树的链式存储表示呢，还有一种线索链表，我们等以后讲到线索树的时候再讲。前面，我们讨论了三个问题，一个是树的类型定义，二叉树的类型定义，以及二叉树的特性，还有二叉树的存储结构。下面我们要讨论这一章的一个主要的问题，叫做二叉树的遍历。那么在这一节里面，我们准备讨论这样五个问题。这五个问题从问题的提出，到遍历算法的描述，一直到遍历算法的应用。我们首先看，问题的提出。也就是什么是遍历：顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅仅被访问一次。这个访问的含义呢，可以是各种个样的。 比如说，输出结点信息，或对结点进行赋值。那么这样一个结点遍历的问题呢，对于任何一个结构都是存在的。遍历是任何一个结构的基本操作，但为什么我们前面没有强调呢，因为对线性结构来说，每个结点只有一个后继，因此从第一个结点出发，它只有唯一的一个搜索路径，这是很自然的，所以我们就不需要重点的讨论，自然就会实现这样一个遍历的操作了。但是二叉树不一样，二叉树是一个非线性结构。每个结点有两个后继，那么就存在着按什么样的搜索路径来进行遍历的问题了。对于二叉树来说，它有两个后继，它可以有这样三条搜索路径。第一条是先上后下的按层次的遍历。先访问根结点，然后访问根节点的子树根。对于每一层来说呢，先左后右。那么先访问它的根结点，如果有左子树，访问它的左子树，如果没有左子树，访问它的右子树。然后在访问它子树的子树。一层一层的往下遍历，这是一种搜索路径。第二种：先左后右的遍历，二叉树不是有两棵子树吗？整个二叉树的遍历就可以看作是，对左子树的遍历和对右子树的遍历的和。 那么对于根结点的遍历，就是根结点就有一个结点，直接访问呢就好了。 那么左右子树呢，有一个先一个后的问题。一种搜索路径呢，是我先左后右，我先去遍历左子树，然后在遍历右子树上所有的结点。反过来，还有就是先访问右子树上的结点，然后再访问左子树上的结点。这两条路径呢是相反，单是完全对称的。我们讨论其中一条就可以了。下面我们就重点讨论先左后右的遍历。先左后右的遍历算法有先根、中根、后根三种遍历算法。那我们首先来看一看什么是先序的遍历算法，什么是中序的遍历算法，什么是后序的遍历算法。我们现在有这样一颗二叉树。（邮递员模拟的问题）下面看先根序遍历算法的描述，很简单：如果二叉树为空树，则空操作，什么就不用做了，否则，的话，访问根结点先序遍历左子树先序遍历右子树中根序遍历算法的描述，很简单：如果二叉树为空树，则空操作，否则：中序遍历左子树访问根结点中序遍历右子树后根序遍历算法的描述，很简单：如果二叉树为空树，则空操作，否则：后序遍历左子树后序遍历右子树访问根结点这里需要注意的是如果你整个二叉树是后序遍历，那么你遍历子树的时候也是什么样的遍历。（中序、先序是一样的。）上面呢，我们给出了遍历的定义。下面也就是第三个问题，我们看一下算法的递归描述。我们用C语言呢，来把刚才的算法描述一下。整个算法的描述呢，主要有递归和非递归的算法，我们主要看一下递归的算法。如果二叉树是空树，什么也不做了，所以我们先序遍历是在二叉树不空的前提底下。、void Preorder (BiTree T, void( *visit)(TElemType& e) / 先序遍历二叉树 if (T) visit(T-data); / 访问结点Preorder(T-lchild, visit); / 遍历左子树Preorder(T-rchild, visit); / 遍历右子树其他的中序和后序遍历。与这个是非常类似的，只要你调整这三个语句的位置就可以了。要注意的是，还是采用递归的方式来进行遍历的。第四个问题，有的时候呢，我们还需要有非递归的算法的描述。我们现在就看一下，中序遍历算法的非递归算法是怎么样的。我们首先分析一下，中序遍历算法的规律。中序遍历，对于每个结点来说，都是先遍历它的左子树，因此对于这个二叉树来说呢，对于A来说，先遍历左子树。同样对于B子树来说，也是先遍历左子树。什么时候访问它本身呢，就是在左子树空的时候，才接着访问B结点。所以我们从A开始中序访问遍历的第一个结点一定是B.也就是说我们从根节点出发，一直往左走，如果这个结点还有左子树还往左走，走到这个结点的左子树是空为止。那这个结点B就是我遍历访问的第一个结点。那么我一直往左走，我将来还是一定要回来的。也就是说我要能在访问完左子树的情况下，退回到这个根结点。也就是说我要能够退回到A.也就是说能够顺着原路退回，因此我们要把路过的结点给保留下来。那也就是什么啊，先走到的后访问，后走到的先访问。显然保留这些结点的一个数据结构呢，就应该是一个栈了。假定我们现在有一个栈在这里。现在我们从A出发，往左走。A呢，就要入栈。入栈以后，我们就到了B。例如有一个指针指向B了。这时候，我们发现B呢，没有左子树。那么我们就直接对B进行访问。应该是遍历右子树。那现在有右子树，就进行遍历。所以我们就将p指过来，遍历以右子树为根的一个二叉树。对于C来说它也有左子树，它也要入栈。现在指针走到D。走到D以后，发现D没有左子树。所以就对他进行访问，D访问完了以后应该是去遍历右子树，但是现在右子树是空，说明以D为根的这个二叉树已经遍历完了。遍历完了以后，我们要往回退，退到哪里呢，退到C。退到C呢。我们知道这个C退出来，肯定是从左子树回来的。所以对它进行访问。访问完了以后，我们要遍历右子树。现在右子树是空的。那么以C为根的子树也遍历完了。显然应该还是往回退。根据栈顶的指示，就退到a了。退到A后呢，就应该对它进行访问了。访问完了以后，我们还要遍历以它的右子树根为根的这样一个二叉树。从新往左走，它现在它的左子树是空的。所以我们就直接对他进行访问了。访问完了以后呢我们要遍历以F为根的一颗二叉树。这时候F存在左子树。F入栈，往左走。G存在左子树。G入栈，往左走。H没有左子树，所以对他进行访问。然后往右走，但是右子树是空。然后根据栈顶的指针，我们退回到G，然后对G进行访问。K没有左子树，对K进行访问。然后往右走，没有右子树，又退回去，退到哪里，根据栈顶指示退到F。对F进行访问，右子树为空，这时候，栈为空了，说明整个中序遍历就结束了。也就是我没有一个结点，它的右子树还没有遍历。那么从这个我们指针走的过程中，发现一个基本操作。就是往左走入栈。有一个这样一直往左走，入栈的基本操作。下面看到的就是这样一个一直往左走的这样的操作，从指针T所指的这个根结点出发，一直向左走，走到哪里呢，走到一个左子树为空的结点，拿指向这个左子树为空的这样一个结点的指针返回。走的过程中呢，把那些含有左子树的结点都入栈。那也就是说，如果我们T是空的话，就是一棵空树，返回的NULL。如果这个T本身不空，那么我就看它左子树是不是空。如果左子树空，那就返回它本身了。如果左子树不空的话，那么本身这个结点的指针入栈。然后顺着左指针呢，往左走。 一直走到左子树根为空的那个结点返回。那么再有了这个向左走的基本操作以后，这样一个二叉树的非递归的算法。这个T是指向二叉树根结点的指针。首先就是一直往左走，如果二叉树是空，返回NULL这样整个遍历就结束了。否则的话，一定返回一个指针是不空的。那么就对这个指针所指的结点进行访问。如果它右子树结点不空，再从他右子树的根结点出发，一直往左走。走到一个左子树为空的结点，进行访问。然后再从这个结点的右子树的根出发，往左走。那如果这个结点的右子树是空的话，那我们要看看栈是否为空。如果栈空整个遍历就结束了。如果栈不空的话，就从栈里退出来，退出来以后，这个结点要进行访问。然后再往右走。当栈为空的时候呢，整个中序遍历就结束了。前面我们介绍了二叉树的遍历算法，包括问题的提出，算法的递归描述、以及中序算法的非递归描述。整个遍历呢是非常简单的，大家主要掌握它的递归形式的算法。整个二叉树的遍历算法是二叉树操作的一个核心。其实二叉树的应用呢，有很多的操作都是在二叉树遍历的基础上进行的。下面我们就看看如何利用二叉树的遍历操作完成其他的一些操作的例子。第一个例子呢，是统计二叉树中叶子结点的个数。我们用先序遍历来做。二叉树的叶子结点呢，是左右子树为空的度为0的结点。那么这个题呢，就是看二叉树上有多少个叶子结点。我们首先分析一下这个问题，二叉树基本上有三种情况。1，假定二叉树是空树，那么叶子节点的数目肯定为零。2假定二叉树上只有一个根结点，那这个根结点本身就是叶子结点，所以它的叶子结点数目就是1.3第三种情况就是二叉树的结点数大于二的情况。那么这个二叉树的叶子结点的个数，就是左子树上叶子结点的个数和右子树上叶子结点数之和。那我们看一下这个程序。首先 这个函数有两个参数，现在统计以这个T指针所指的二叉树上叶子结点的个数。个数的和呢，累加到这个count变量里面。这个变量的初值呢，等于零。如果这个二叉树是空的话，那么就什么都不做，count还是零。第二种情况，我们说本身这个树不空，但是左右子树都为空，证明它是一个叶子结点，那么count数加1 。如果左右不空，那么我们就递归调用这个函数，统计左子树上叶子结点的个数，在统计右子树上的叶子结点的个数，最终我们会得到整个树的叶子结点的个数。那这个过程呢，其实就是一个遍历操作，先遍历左子树，把叶子节点的个数累加上去，再遍历右子树，把结点的个数累加上去。我们看这样一颗左子树的叶子结点的计算过程。简单的走上一边给出统计二叉树叶子结点的遍历如果二叉树不是叶子节点，那么它的叶子结点个数等于左子树叶子结点个数和右子树叶子结点的个数。这里我们要注意递归调用就是说对于每一个结点的操作都是相同的。第二个例子呢，我们求二叉树的深度。同样我们先分析一下二叉树深度的定义。 二叉树的深度我们定义为：叶子结点的最大的层次数。反过来，我们对二叉树的深度可以这么来看。如果二叉树是空树，那么它的深度就等于零。如果只有一个根结点的话，那么它的深度就是1. 假定我们这样一棵树，假定左子树的深度为d1，右子树的深度为d2.那么对于整个二叉树来说。它的深度是不是应该是这两个深度的最大值加1.所以我们对于二叉树来说呢，分析问题呢，可以用二叉树本身递归的定义来分析，二叉树是一个根结点加上两颗子树，那么我们求树的深度，就可以先求子树的深度，然后加1，就可以了，但是对于子树呢，我们还是先求子树的子树深度然后加1.所以呢我们这个过程其实还是一个递归的过程。我们求二叉树的深度呢，我们用后序遍历来求，如果二叉树是空树，那么它的深度为零，如果二叉树不空，我们就认为它一定有一个左子树、一定有一个右子树，分别求它左子树的深度和右子树的深度。整个树的深度呢，就是左右子树深度的最大值，再加上1. 二叉树的很多操作呢，都是在二叉树递归定义的基础上，利用遍历来完成。你用什么样的遍历呢，则根据问题的性质不同而不同。统计二叉树的叶子结点的个数，我们只要用先序遍历就可以，当然你也可以用后序遍历，一般我们能用先序遍历的话，就用先序遍历。而我们求树的深度呢，必须在左右子树的深度已知的基础上，才能求得树的深度。因此，必须用后序遍历，在求得左右子树深度的基础上，最大值加1，才是树的深度。第三个例子，就是复制二叉树。所谓复制二叉树，就是按照原来的二叉树的存储结构，我另外再生成一个二叉树，这个二叉树和原来的二叉树是一模一样的。那我们只要按照原来的二叉树的结点呢，再生成一个。假如这个树用二叉链表来表示。那么我们用指向根的一个指针就可以表示这个树。这个根结点里面有三个域，一个数据域，一个指向左子树，一个指向右子树。复制操作呢，就是要我们生成一个结点，数据域相同，把原来的拷贝过来就可以了。 同样这个复制过来的树的左子树要跟我们原来的树的左子树相同。同样我们复制得到右子树。那么指向这个结点的指针，就是我得到的新的二叉树的根指针。那这个复制左子树和右子树的做法，和我们的树的遍历一样。对于左子树本身呢有一个数据域和左子树右子树的指针域。复制的最基本的操作呢，是生成一个结点。这个结点的三个域由原来的结点的三个域相对而来的。对于数据域就复制值就可以了，对于指针域，我们首先得知道左右子树的情况后，完全建立这样一个结点。那这样哦复制二叉树与我们哪种遍历类似呢? (后序遍历)下面我们就看一下复制二叉树的算法,首先要生成一个结点.那么一个结点有三个值,根据这三个值才能构成一个结点.首先由系统生成一个空间,然后,给这个数据域赋值，将左右指针指向传递过来的两个指针。然后返回指向新生成的结点指针。下面才是复制的算法，这个算法呢，也是一个递归的算法，在左子树和右子树都复制完的基础上呢，我们才能生成一个这样的结点并返回指向根结点的指针。这个算法呢，我们知道是一个后序遍历。首先我先复制左子树，如果左子树是空，那么左子树指针就是空，如果我左子树不空，我根据左子树得到一颗二叉树，同样我也会得到一棵右子树复制过来的二叉树。最后我们得到一个根结点返回。第四个例子，建立二叉树的存储结构，一般来说，我们都是建立一个二叉树的二叉链表的存储结构。那么怎么建立二叉链表的存储结构呢。我们在将二叉树的基本操作里面呢，我们知道二叉树的创建时根据定义来创建的。那其实我们刚才的复制二叉树就是建立二叉树的一个方法。也就是说我从底下到上面，把二叉树的根结点建立完了以后呢，整个二叉树就算建立完了。这样的建立，就是根据一个已有的二叉树，建立一个二叉树的方法，那么我们还可以根据其他的定义来建立一个二叉树的二叉链表。那么我们就根据几种不同的定义来建立二叉树的二叉链表方法。但是你得注意，对于给出的定义，相对的信息也必须是完备的。就是说你给出的信息，建立的必须是唯一的一棵二叉树。而不能建立出不同的二叉树来。第一种方法是按给定的先序序列建立二叉链表。对于这种情况，我们其实还是建立一个根的结点。把左子树的根赋值给它，右子树的根给它。那么整个二叉树就建立完了。二叉树我们说是有三部分构成的，一个根结点，一个左子树、一个右子树。那这个二叉树呢，可以用根结点的一个字符、加上左子树的一个字符序列，右子树的一个字符序列。也就是整个二叉树呢，可以用一个字符序列来表示。第一个是根。那什么是空树呢，我们用一个空白字符来表示。那从二叉树的一个分析呢，我们始终不要忘了对于二叉树的空树的一个表示。那么如果你只给一个空字符的话，一定建立了一棵空树。那如果我给出一个A-，那么就是一个根结点，左子树是空树，右子树也是空树。也就是只含根结点的一颗二叉树。那么我们知道如果左字数不空，那么反过来它一定有一个左子树有一个右子树。对于这样一棵二叉树我们可以用这样一个序列来表示，一个根结点，一个左子树的字符序列，一个右子树的字符序列。画出该图，并给出字符序列的说明。特别是字符序列中，左右子树的说明这样的一颗二叉树可以由这样的字符序列来表示，反过来这样的一个字符序列唯一确定了这样一颗二叉树。（解释说明一下这个唯一性。）同样我们可以看到这个序列实际上是我们先序遍历二叉树的一个输出。这样的话，我们就可以输入这个字符序列，从给定的先序序列建立一个二叉树。下面我们看这个程序首先得到一个字符，如果字符不是空，那么这颗树就不是空树，这一个肯定是根结点的数据域的字符，然后依次建立它的左子树根和右子树根。建立的左子树根，返回的指针赋给这个T的左指针域。同样建立的右子树返回的一个指针赋给这个节点的右指针域。这样我们就可以得到一棵二叉树。这个先序序列与我们前面的先序序列不一样，这个序列加上了空格。下面我们看第五个例子，按给定的表达式建相应二叉树。 表达式我们在讲栈的时候，给大家介绍了表达式的先缀表示、中缀表示、和后缀表示法。那么一个表达式呢，它的基本的成分呢，是由两个操作数和一个运算符构成的。因此我们说一个表达式可以用二叉树来表示。（画图）表达式=第一操作数+运算符+第二操作数 那我们很自然的就能用一个二叉树来表示。以运算符为根结点，它的左子树就是第一操作数，右子树就是第二操作数。那当这个第一操作数本身又是一个表达式的时候，那它就又是一个二叉树。那么现在我们来看表达式所谓的先缀表示法，和它的后缀表示法，实际上就是对二叉树进行先序和后序遍历之后得到的结构。所谓先缀表示法，我们把运算符放在前面，然后是第一操作数第二操作数。后缀呢是第一操作数，第二操作数，运算符。所以这是先序遍历的规则，这是后续遍历的规则。那么如果一个二叉树够成了一个表达式，那么这颗二叉树呢，肯定是上面没有度为1的结点的。 比如我们这个例子（a+b）*c-d/e 我们可以用这样的一个二叉树来表示：每一个二元运算是一棵二叉树，而且这颗二叉树的节点呢，跟它的运算顺序是有关的。那这个表达式的先缀表达式呢是-+abc/de 顺序呢正好是我们先序遍历二叉树的输出的顺序-+abc/de。 那么刚才我们表示二叉树的时候，一定要加上控制符才能表示二叉树，而现在不加控制符，这样一个表达式的先缀式，能不能唯一的确定这颗二叉树。我们看这颗树上的分支节点和叶子结点有什么规律？所有的操作数都在叶子节点上，而且所有的运算符都在分支结点上。而且第一个操作符呢，肯定是根结点。那么我们看这个先序序列的话，这个肯定是根结点的字符。下面紧接着是它的左子树的根，在下面是它的左子树的根。碰到abcd的话肯定是叶子结点。那么我们看看通过这个序列能否建立一个二叉树。也就是说我们见到字符的话，就表示是一个叶子结点，见到运算符的话，就表示有一个左子树有一个右子树。那这个字符序列不是空的，那么就看第一个是运算符，一定是它的根结点。左右子树一定不空，下面我们就递归的建立它的左子树，那么X一定是左子树的根结点，表示还是一个运算符，在树中呢，它还是一颗子树，有左子树和右子树。下面是左子树根说明它还是一棵子树。有左子树有右子树，一次建立它的左子树，这时，它的左子树是一个操作数，表示是一个叶子结点。这个结点的左右指针是空的。对于+来说左子树建立完了，那么就改建立+的右子树，同样它是叶子结点，就是空。这时候整个以+为根的二叉树建立完了。这时候就是乘的右子树了，又是一个叶子结点。这时候的右子树完了，后面的一定是的右子树。因为是运算符，所以它有左子树右子树，左右子树分别为dc。由于表达式我们限定的是一个二元运算符，也就是说碰到一个运算符那么它一定存在着左右子树。碰到操作数的情况就是左右子树都空，所以在这这种情况下，我们可以根据表达式的先缀来建立这棵二叉树。那我们现在反过来，已经知道表达式的后缀，ab+cde/- 对于这个后缀式，我们求值是很方便的，从左到右扫描，当扫描到运算符的时候，那么就对它前面紧挨着的操作数做运算。那么所谓对它做运算，在我们二叉树里面呢，实际上就是建立一棵二叉树。现在我们又碰到了运算符了，这个乘要对前面两个做为操作数做运算，也就是构成了这样一棵树。后面我们碰到de/ 也就是相当于构造这棵树，最后面呢，我们又遇到了，那么对着两个操作数来说就又构成了一个表达式，对应于这样的一颗树。那么也就是说，由后缀式很容易求值，而且还很容易构造一棵树。那么如果我们给出的是一个原表达式，（a+b）*c-d/e ，希望从这个原表达式建树，当然你可以将原表达式转换成后缀式然后再建树，但是我们希望能有一个方法，直接从原表达式建树。 而不需要变成后缀式。我们知道从原表达式到后缀表达式的过程是需要一个栈，那么我们就看一看能不能利用一个栈直接将原表达式建立成一棵树。（演示程序说明一下就可以了）。至于算法的源程序实现呢，我们简单的看一下就可以了。刚才呢，我们讨论了几种二叉树的生成方法。一种呢，是由带空格的先序序列。第二种我们可以由先缀，后缀得到一棵二叉树。第三种呢，是根据表达式的原表达式建树。对于表达式而言，我们很容易到树，因为我们知道运算符就是一个度为二的结点。而操作数呢就是叶子结点。所以由它的先缀或是后缀呢，就很容易建立二叉树。对于任意的二叉树，我们必须用带空格的先序序列来建立。那么我想问，我们对于这样ABCD这样的先序序列，也就是说一棵二叉树的先序序列是ABCD，能否得到建造二叉树呢？ 当然可以，但是这样的二叉树有很多，不是唯一的。我们可以画出很多。为什么会有很多呢？我们来看一下，abcd这个序列。 首先a是根结点没什么问题，但是对于b是a的左子树根还是右子树根，是不是没有明确说明。因为如果a没有左子树，那么b就是它的右子树，a如果有左子树，那么b肯定是它的左子树根。那么我们用这种不带空格的先序序列是不能唯一的确定一个二叉树的。那么我们看这棵树的中序序列，例如左边的这棵树是abcd，中间的的序列是badc，右边这棵树的中序序列是acdb。 那么我们看这个中序遍历的序列的特点，特点就是根结点一定在左子树和右子树序列的中间，但是如果只给你一个中序序列，你还是不知道哪一个是树的根结点。而先序序列呢，第一个肯定是根结点，后面跟的是左子树序列，右子树序列。但是左右子树的分界线不清楚。也就是说你单独一个中序序列，或单独一个先序序列是不能唯一确定一棵二叉树的。但是如果你即知道了先序序列，又知道了中序序列，我们看能不能建立一棵树。先序：ABIDEFGCHJ后序：IBFEDGAJHC 所以呢，我们说由二叉树的先序序列和中序序列呢，一定能够得到一个唯一的二叉树。由于二叉树的根一定是先序序列的的第一个元素。那么这个元素在中序序列里面就是根的位置是a。这个a呢，将中序序列分成左子树bcd和右子树egf。然后再依次向下走，依次类推，就得到了一棵完整的二叉树。这样呢，我们就介绍了建立二叉链表存储结构的方法，那么建立其他形式的存储与这个是类似的，由于二叉链表是经常会用到的，所以我们就以二叉链表为例介绍。以上呢，也就是二叉链表的应用。以上我们讲了二叉树的遍历，在遍历里面我们提出了五个问题，首先是遍历问题的提出，遍历就是一条搜索路径，二叉树呢，我们有三条搜索路径，一条层次遍历，一个先左后右，一个先右后左。由于后两种是对称的，所以我们重点讨论了先左后右的遍历。然后写出了算法的描述，最后给出了遍历算法的应用。从刚才一些例子来看呢，这些算法的基础呢，就是二叉树的遍历，因此，我们说二叉树的遍历是非常重要的基本操作。所以希望大家能够熟练的掌握。下面我们讨论线索二叉树，在讨论二叉树的存储结构的时候，二叉树的链式存储结构里面有四种方式，二叉链表、三叉链表、双亲链表、和线索二叉树。那么现在我们再来讨论线索二叉树是什么样的存储结构，它是如果表示二叉树的。在线索二叉树里面，我们讨论这样三个问题，1是什么是线索二叉树、2是线索链表的遍历算法，最后是如何建立线索链表。下面我们讨论第一个问题，什么是线索二叉树。 简单的来说就是把遍历的时候得到的信息呢保存起来，作为一个线索的二叉树存储结构。我们看这是什么意思，对于任何一种遍历方法，最后的结构呢，都是得到一个结点的一个线性序列，也就是将我们这个树的非线性结构线性化。什么意思，就是对于我们得到的这样一个线性序列里面，每一个结点都有前驱和后继，那这个前驱和后继的信息是我们在遍历的过程中才能得到的。如果我们把这个在序列中前驱后继的信息，也就是在线性序列中前驱和后继的指针，称之为线索，如果你把这个线索放到存储结构中去的话，就称为线索链表。那与这样的线索链表对应的树的存储