大家好，数据结构与算法这一讲的内容是第六章：树。
我们今天介绍树的抽象数据类型，以及树的遍历。
那在介绍了树的逻辑结构之后，
我们来表达它的抽象数据类型，
主要是通过一个这样的模版的形式来表达的。
那我们树跟二叉树类似，我们要定义它的结点类还有整个树的类，
那在这个结点类里面特别重要的就是LeftMostChild的这样一个函数，还有 RightSibling 这个函数。
这个LeftMostChild，它的意思就是说这个结点是我当前结点的第一个孩子。
在二叉链表示的这个树的结构里面，它是左边那一个，所以我们 叫left most child.
而 RightSibling ， 就是我自己当前这个结点。
我的右兄弟，实际上在二叉链形式表达的这个右结点，
就是我的下一个兄弟结点， 我们拥有共同的一个父结点。
那其他的，就是我们常规的一些表达。
树的抽象数据类型里面，我们特别要注意的就是parent这个函数。
这个parent 的这个函数， 它在树抽象数据类型里面，
我们其实一般情况下是不能够直接得到一个结点的父的， 因为我们其实只存从一个结点，
它的left most child, 以及它的 right sibling，这两个线索。 那我要是找到父，我们就需要一些算法，我们后面会介绍。
那其他的，就是像遍历等等一些运算。那我们来看遍历的运算。
那类似于二叉树，我们有先根序列，那这个先根序列，它其实就等价于二叉树里面的前序的遍历。
那我就是先遍历这么一个第一棵子树。在第一个子树里面，我从这个根出发
然后，先遍历它的第一个子树， 以及剩下的其它的这个子树。
在遍历完第一棵树以后，我们再遍历剩下的其他的树。
那后根序列它跟先根， 有类似的这样一个深搜的过程，但是它就是
在访问当前的这个根的时候，它要是它自己的所有的子树都访问完了，才访问这个根。
那我们来看一下，遍历森林和遍历二叉树的对应。
先根我们刚才说了，它是类似于二叉树的前序。
后根，它其实是类似于 二叉树里面的中序。
那我们有没有中根的方法？那我们其实是没有的。
因为对于一棵树，它有好几个这个结点的情况，我们不知道因该从什么地方来截止，访问完这个左边的这几个子树，再访问根，
再访问右边剩下的子树。在一些特殊的应用里面，如果你有这个需要，也可以定义你自己的类似于中根的遍历。
那我们看一下先根遍历的算法。我们的这个算法就是，我们首先，访问这个根节点。
然后，我们递归的访问，以它的这个第一个子树，也就是left most child，
所代表的整个这一个子树森林，因为我们在二叉链的这个结构里面left most child 的它的right
sibling就是直接给串起来了，因此我们下降到leftmost child 以后， 那它的整个这个
子树的这些几个子树的信息都已经被表达出来。
然后我们 访问完第一棵树的自己的根结点和它所对应的这些子树以后
我们降到这棵树， 它的right sibling。也就是下一棵子树，然后，
再进入下一层循环，又是重复刚才的过程。接着再进入下一棵子树。
我们以这样的顺序，就访问完整个森林。
那我们来看一下后根的深搜算法。
那后根，我们首先就是， 要降到这个根节点它的left most child 所代表的这样的一个子树的森林。
然后，能递归的访问。访问完了以后，我们再访问根。然后我们降到这个根的 right sibling，就是第二棵子树
又是重复刚才的过程，然后我们再降到第三棵子树，又重复刚才的过程，一直到处理完毕为止。
那我们看一下这个宽搜。
宽搜，也称宽度优先搜索或者是层次遍历。
那我们是一次先访问第零层再访问第一层，再一次访问其他层，直到最后一层访问为止。
那我们看宽搜的这个遍历，在我们这个树形表达的这种图示里面我们是这样从上到下，一层层的。
在对应的二叉链的形式里面，其实我们可以看到是一个个的形线，这样子，来表达的。
就是要注意这样的一个顺序。
那我们看，广度优先搜索，它的算法。
那我们从这个森林的第一棵树的根开始，
我们把它的这个所有的这些子树的树根都给它放到一个队列里面。
因为我们是广度优先，是一种先进先出的形式，所以用队列来作为中间的数据结构。
当这个队列不空的时候，我们从队列的首部弹出一个元素， 然后，我们访问这个元素。
接着，我们进入这个元素所指向的这个左子结点。
进入它的这个左子结点以后， 这里就是沿着这个左子结点的它的这个右兄弟链，我们来访问。
我们访问了以后都是把 这个左子结点以及它的右兄弟链本身， 都给它入到队列里面。
这里，大家特别注意一下在二叉链形式表达- 的这样的森林里面，我们有这么一个结构，
就是同一个结点出发，然后下降到它的这个左子结点。
然后左子结点，顺着这个右链，这个都是它的 这个第结点的子孩子，所以我们要在找这个子结点的时候，也是这么一个结构。
我们在讲到存储实现的时候，会给大家介绍找父结点的这么一个算法就用到了这样一个类似于 L 型的这么一个转折的结构。
那最后留给大家一些思考。也就是我们能否- 用二叉树的前序遍历框架来编写森林的先根遍历？
那我们能不能够用二叉树的中序遍历框架来编写它的后根遍历？
那我们另外就是森林的非递归的深度优先遍历的框架我们怎么写。
还有我们来看一下， 宽搜的这一些观点。
那我们刚才说到， 宽搜，我们对应于这样的一个森林，我们是一层层来的。
对应于它的二叉链表现的形式，是这个斜线过来的。
那我们不能够还用 二叉树的这样一个宽搜的这个形式，
这样从上到下，从左到右，一个个的来，那它的寓意就 完全不是我们森林的含义了。
这一讲到这儿， 谢谢大家。