大家好！数据结构与算法这一讲，
介绍第五章，二叉树里面的
抽象数据类型以及深搜的相关算法。
我们在讨论抽象数据类型的时候，
往往讨论的是逻辑结构加运算。
跟具体的存储无关。我们有针对整个树，以及围绕着结点的
两个抽象数据类型的定义。 整个树的，比如说初始化，合并。还有围绕着结点，就是对于它的
左子树，右子树，父结点，还有围绕着当前这个结点本身信息的访问。
首先我们来看一下对二叉树结点的ADT定义。
这个是头的一些信息，包括我们这个结点的
数据域，以及它的左子树，右子树的相关信息。有的时候
我们可能还要对这个数据域和左右子树等等进行修改。
对于整个树，最重要的就是
获取这个树的根结点，这样的一个信息。
然后我们根据需要，有的时候可能会设置、查找父结点以及左右兄弟结点
这样的信息。另外就是有对整个树的一些前序，中序，
后序的遍历，以及它的广搜遍历。
遍历二叉树，
实际上就是系统地访问整个数据结构里面的结点。 最好是每个结点
访问而且只访问一次。这实际上是对二叉树结点的一个
线性化的过程。这个线性化，我们会有一些应用。二叉树非线性结构的结点，
我们进行线性化以后，就可以存储在外存里面。
深搜相关的这些遍历算法，
主要是有三种。也就是前，中，后，
这3个序。那在这3种序里面，我们也都还规定，
是先系统地访问左子树，再系统访问右子树。它们的区别也就是，
根结点在什么时候访问。
例如对这样一个二叉树。它的前序的序列就会是：
A，B，D，E，G，C，F，
H，I。它的中序就会是：
D，B，G，E，A，C，H，
F，I。后序就会是：D，G，E，
B，H，I，F，C，A。
表达式二叉树，我们也可以得到前序，中序和后序
序列。其中前序序列和后序序列，相应的就是前缀和
后缀表达式。它保留了表达式里面所原有的计算顺序的信息。
而中序的序列，没有带括号的话就是改变了
它的计算顺序，已经跟原来这个表达式二叉树是不等价的。
所以我们不叫它中缀表达式。中缀表达式的话我们是需要加上括号的。
那深搜遍历的这个递归过程
非常简单。如果是说当前这个结点不空的情况下，
我们会递归地去遍历它的左子树，递归地遍历右子树。
差别就是，我们什么时候来访问这个结点本身。
如果我们把访问结点本身这个语句，写在这两个递归之前，这就是前序。
如果我们把它写在中间，这就是中序。如果是写在递归访问左子树，右子树
之后，这就是后序。这3个访问点，
在一些应用里面，都是有用的。例如我们刚才的这个表达式二叉树，
如果我们要得到正确的，带着括号的中缀表达式的形式，
我们就是在这3个访问点都会有些相应的操作。
需要，比如说，打左括号，打右括号。当然是要判断优先级，再打相应的括号。
那我们留一下思考。也就是这种前，中，后序，
这几种遍历形式呢，哪几种结合它可以恢复二叉树的这个结构？
这里我们给出具体的例子，大家可以看一下。深搜遍历二叉树，
它的递归算法是非常简洁的。 那我们下面来介绍非递归的算法。
那因为在前面我们说，用栈的模拟递归的时候也说到过。就是我们可以
理解这个编译栈的工作原理，以及更加深入地理解
这样的一个递归回溯的过程。另外还就是，在有些应用环境下，
比如说有空间的资源限制，我们不能够使用递归。
那在这里呢，我们也给出这3种深搜算法它的
非递归的算法。然后对这个二叉树，我们有更深入的理解。
我们首先看前序的这个算法。
那我们要前序遍历的话呢，就是看这个结点我就访问
然后，我马上就可以进入到它的左边。 因此我只要保存它的右结点信息。
我们看到这个结点，保存它的右结点，然后深入到左边。
我们一直重复这个过程。如果一直是左到不能再左，
没有可以继续深入的，那我们就是从这个栈里面弹出一个结点，
然后去继续刚才的这个过程。比如说这个C弹出来以后，
它要保持它的右结点F，然后它深入到它的左结点E。
继续这个过程，我们就得到了一个正确的，
前序的序列。这实际上是非常简单的。
那我们来看一下，它的算法的这个框架。
首先，我们是当前结点，就是赋为这个根。
然后呢，我们在栈底压一个监视哨，是一个空指针。
那压入这个监视哨以后，使得我们的这个算法写起来比较统一。
如果当前这个结点它非空，那首先我们就可以访问这个结点
信息。而且，如果它的右子结点
非空，那我们就把这个右结点，压到栈里面。
然后，如果它的左孩子，是非空的。
那我们就是当前结点就降到，
它的左孩子这个位置。否则，就是左孩子
是空了，那我们就是从栈里面找出一个结点继续访问。
那一直到最后，如果是说，当前这个结点它是空。那其实就是说，
碰到了这个栈底压的那个监视哨，整个这个算法就结束了。
中序访问的特点就是说，我们遇到当前这个结点，那我还不能访问。
那我呢要把它保留到这个栈里面。因为我要等到我的左
子树全都访问完了以后，才能访问自己，然后再进入到右子树。
因此，我们就是持续地沿着它这个左线入栈。
那一直到这个D它没有左孩子了。
因此，我们就可以访问它本身。然后，
本来是要进入它的右子树，但是它是空，所以直接退回到B， 然后再退回到A。
然后这个A，它找到了自己的这个右孩子是非空的。这个C呢，
就是入到栈里面。然后就是重复刚才的这样的一个过程。
直到我们所有的结点呢都是正确地给访问到。
那因此我们再总结一下这个中序遍历它的思想就是，
遇到这个结点我们把它推到栈里面，是遍历这个左子树。遍历完左子树以后，
我们从栈顶托出这个结点就访问它。
然后，按照刚才的这样的一套方法再
去继续访问这个结点的右子树。 那我们看一下它的算法啊。
我们也是从这个根开始。而且，最开始的时候这个栈是一个空栈。
如果是说，这个栈非空，
或者是说当前结点非空的情况下，
那首先我们就是，如果是当前结点非空，那我们是
把这个当前结点，压到栈里面，而且，进入到它的左子树。
否则，就是左子树访问完毕了。
那这个时候，我们从栈里面拿出一个元素。
然后这个元素就可以访问了。因为它的左子树都访问完了。
然后，我们把当前指针，就是要深入到刚才弹出的这个
栈顶它的右子树，然后再重复刚才的过程。这个访问点是个中访问点。那我们看，
前面的话是有一个访问点，实际上是可以处理前序
访问的相关的信息，也就是说如果你有一个应用，
只需要用到中序的访问点和前序访问点，是可以用这个非递归的中序周游框架的。
那么也就是当我见到这个元素的时候，我就访问它。
这是一个前访问点。那非递归的后序周游它复杂一些。
因为我们是要访问完左子树，而且访问完右子树以后，才能访问当前结点。
因此，我们需要有一个标志位，来判断是从左边返回的，还是从右边返回的。
这就相当于在我们前面介绍用栈来处理这个
递归的算法的时候，我们把它转成非递归的时候，我们要记录返回地址。
那我们来观察一下这个后序遍历，它的一个访问的这个过程。
那我们访问到当前结点我入栈的时候，我还要区别是，
从左边入还是从右边入。我们回忆一下刚才的中序遍历。因为它是马上就从左边进去了，
那右边呢它就是在留着下一次它从左边返回的时候，
要进到右边，它把自己弹出来，然后就扔掉，只存右边那个。但是这个
后访问是不一样的。就是说我要先告诉它我是从左边入。那我一直从左边入下去。
然后，D结点呢，我还要去看一下，哎，哦，是不是要再往右边入一下。
那左右都访问完了以后，才能访问D本身。
那同样左右都访问完以后呢，
就可以访问B结点本身。然后我们看，在A结点这个地方，那它是左子树处理完了，
那我们就是，可以从栈里面，拿出这个当前结点，
然后我把它标记一下，我要进入到它的右子树。
然后，我们就类似的，进入C的这个左子树。
然后就是进行相应的这个访问。 那我们这个C的左右子树
都访问完了以后，我们才能够访问C结点本身。
访问完C结点，可以看到A结点也可以
立即访问了。因为A结点，左右子树都已经被访问过了。
那在这个过程我们可以看到，其实是有一些冗余的进出栈的。
比如说像D的左子树和右子树它都是空结点。
那我们这里是冗余地进出栈了。这个是在算法优化的时候
可以做一些改进。但是，如果我们考虑它的一个比较机械的这个过程，实际上是这样的一个过程。
那我们来看一下非递归后序遍历的算法。
那在这个算法里面，我们要注意栈，
它的内容就是当前结点这个指针。
然后，还有就是一个返回地址的这个标志位。也就是从左边还是从右边的。
这个算法，我们也是先从根结点开始，
然后，我们判断一下栈是不是空，以及当前结点是不是空。
如果栈不空，或者是当前结点不空的情况下，
我们可以一直是沿着左路下降压栈。
然后做一个标记是我们当前是从左路进来的。
那一直到左到不能再左，左边就是空的这种情况，
那我们从栈顶弹出一个元素。然后看一下这个元素
它的返回标记。如果是从左边来的，那我们把它修改为到
右边去。然后再压到栈顶。就是将来等着从右边返回才能访问这个结点。
否则，如果它是从右边返回的，那就表示它的左右都已经处理完了，那我们可以访问当前这个结点。
而且这里我们注意，我们把这个指针呢赋为空。
这样的话就是进入到这个循环里面判断
这个栈是非空的情况下，因为这个指针是空，所以，
其实就是一个弹栈的操作。实际上我们在右线返回的时候，
可以连续地去弹栈。这几个深搜的遍历算法，
它都是为O(n)的时间代价。因为每个结点都是
被访问而且只被访问一次。实际上这个是可以通过这些结点的入栈、出栈，来看
它们的访问时间。那对于后序来说，每个结点分别是从
左、右各入/出一次，所以是O(n)的。
那前序、中序比它还简单一些。有些进出栈，
是被简略了。所以它的时间代价也是不会超过O(n)。
空间代价主要是跟栈的深度有关。那栈的深度就是跟树的这个高度有关。
那最坏情况下可能退化到一个线性的链，那就是O（n）的。那，
最好的情况，因为我们知道，二叉树它的深度我们最好的情况下，
也是log(n)级的。因此它的最好的空间代价也是O(log(n))。
那我们有几个思考。非递归的这个遍历里面，
我们栈里面主要是放了什么东西？特别是，对于这个后序的这种非递归的遍历，
你可以看一下这个栈里面的内容有一些什么特性？
另外就是，前、中、后序这个算法框架，
它们的通用性怎么样？我们这里主要是指的非递归的啊。
就是我们怎么样去修改，然后就是说体现出各个算法的
访问点？也就是前、中、后序到底访问点在什么地方？ 好，谢谢大家。