大家好。
数据结构与算法这一讲开始第六章树的学习。
我们首先定下树的一些基本术语，特别介绍一下
森林跟二叉树之间的转换。
那树，它是这么一个结点的有限集合，
那其中有一个特定的结点称为根。
那么在根底下，其它的结点被划分为
若干个不相交的有限集合，而每一个集合，
又都是这个树的子树。
那这就是一个递归的定义。在数据结构与算法里面，
我们定义的树一般都是有向有序的，也就是说，
子树的相对顺序是非常重要的。那可以说，
我们这个度为2的有序树，它并不是二叉数。
因为我们在度为2的有序树里面， 第一棵子树它被删掉以后，
它的第二个结点，它自然就成为第一。
那在二叉树里面，我们删掉了左结点以后，
那右结点它还是右结点，它一定在右边，所以不能够
去替代左结点。那我们来看一下树的逻辑结构。
树它是n个结点的有穷集合。
那这个集合之上，我们还有一个关系。
那这个关系里面，它有这么一个特点就是，
有一个结点是根结点，它没有任何的前驱，
那除了这个根结点以外，其它的结点都是只有一个唯一的前驱。
那我们表达这个结点集合是这样的，那在这上头的
关系集合，实际上是我们用来表达，这个
尖括号就表示它是有方向的。那在我们的
数据结构里面，这个树我们一般都是看着从根往叶的方向。
因此，因为它这个方向是都从根往叶，
我们就不去画那个箭头了。
树有一些相关的术语，首先是结点。那结点里面，子节点，父节点
跟二叉树里面是类似的。那也就是说，如果两个结点它们是有序对，
那其中靠近根的那个就是父，然后靠近叶的方向就是
子结点。还有，我们有兄弟结点里面的前兄弟和后兄弟这样的概念。
所谓前兄弟后兄弟，也就是说在这个
树里面它们的排行，第一第二第三，那紧邻着的那就是互相是 前后兄弟的关系。
还有分支和叶。那如果是说 没有任何的子结点了，那就是叶；
那如果说它有结点，那就是分支。
树的根也是一个独特的一个分支结点。
关于边的一些定义，我们
首先就是边，它其实就是这个有序对，那
如果是从根往这个树叶的方向，
这里面有那么一个结点的序列， 那我们就称为这是一个路径，
那这个结点序列里面当然它都是这个树里面的
合理的这种有序对。那在这个
路径里面我们任何结中间的一段，它也是路径了。
那在这个路径里面靠近根的方向，就是称为祖先结点，
反过来就是，靠近叶的这个方向，就是后代结点。
结点的度数，在树里面是非常重要的，
因为在二叉数里面我们反正只有两个结点。
那在树里面，这个每一个结点的子树个数
可能有多大，那我们预计着这个树它大概会有多宽。
还有层数，我们定义根为第0层，
其它的结点所在的层次，就是它的父结点的层数加1。
那深度其实就是层数最大的那样一个叶结点的层数。
高度是层数加1，我们也可以这么说，
深度实际上可以看作是这个
边的这样的层数；那高度，我们可以看作是 结点有多少层。
树有以下各种形式，那我们来看一下它的表达形式。
最传统的就是一个倒挂的树，那根在上面，叶在下面，这是非常形象的一种表达。
那我们还有形式化的这种表达，实际上就是用集合论来
表达的这集点集，然后关系集，注意这个关系，是有向的
边的关系。我们还可以用文氏图来表达，
因为树，它是一个 层次化的一个有向无环图。因此，
如果用文氏图来表达，我们就可以看到
它这些圈圈代表的这些集合，它们是互相嵌套的，
不会相交。那如果我们在这个文氏图中，
我们把它们的这个圈圈都排在同一个水平线上，
然后中间划一刀，我们把这些圈圈，都把它展成括号的形式，
就变成了嵌套括号的表达。
那这个嵌套括号的表达，它其实就是
对树这么一个复杂的非线性结构的一个
线性化，也就是序列化的工作。那序列化了以后，我们就可以把整棵树，存在文件里面，
保存起来。我们也可以从文件里面把这么一个序列读出来，
恢复成为内存里面表达的一个树的结构。
凹入法的表示方法，就是在我们有的时候
要用控制台来打印这个树的树形，
那我们就可以根据这个树的层次来排，
也就是，第0层这个A，和第一层B和C。
一层层这样的嵌套表达出来。这也是非常形象的可以表达出这个树。
那我们在图书的杜威表示法里面，
我们可以看到，它其实就是这么一个凹入法的表示方法。它也是个树结构。
森林跟二叉树，它有一些等价的
关系。森林它实际上是0棵或者是多棵不相交的树的集合。
那也可以说，一棵树，如果我们删掉树根，它就变成了森林。
那如果是 在森林上面，就例如这个两棵树的森林，
上面加一个结点，它就成了一个独树的一个森林。
那其实它也是森林的一个特殊情况。因为我们看，
森林的定义就是0棵或多棵不相交的树的集合，
所以它一颗其实也是森林。
森林跟二叉数之间可以进行一个相互的转换， 而且这种转换，是一一对应的。
那我们把森林转化为二叉数的时候，我们首先是
把这个第一棵树它的根结点作为二叉数的一个
根，然后它根底下的这些子结点， 这个T11，T12
就作为这个二叉数的左子树。
那剩下的这几个子树，就分别是在这个二叉树的这个右链里面
的这些结点所代表的这个子树。那这是一个递归定义的过程。
那我们来看一个例子，我们怎么转换它。
首先，我们就是把这个
兄弟结点，注意，一定是亲兄弟不能去找堂兄弟，
那同一层的这个亲兄弟，也就是拥有同一个父结点。
那如果是说，森林的最上一层，那因为我们上面可以看作有个虚的这么一个
父结点，那它们也是亲兄弟。那亲兄弟之间连上线。
然后，我们把这个结点，去除，
除了跟它的第一个孩子之间的这个连线，就是
如果是跟它的其它的第二第三个等等其它的子孩子的连线，我们都给它去掉。
那第三步就是稍微整理一下，把它整成
我们比较习惯看的这么一个二叉树的形式，
那我们就把森林转化为了二叉数。
反过来，我们也可以用
二叉数来转换为森林。那这个转换的过程，就是，
把这个二叉数的根作为我们森林的第一棵子树的根，
然后这个二叉数底下的这个左子树，作为这个森林的
整个其它的这个子树，我们进行相应的转换。那
二叉数的这个根以下的这些右链， 我们就是进行
这个相应的转换，又把它看作是一个剩余的这个森林，再做刚才的递归的转换。
那我们来看一个例子。
也就是说从这个二叉数我们转成森林的话，我们首先
从一个结点出发，我们加到它的这个第一个左子结点，
然后，我们，除了这个第一个左子结点，它本来跟刚才这个结点，就已经有连线。
那么这个结点底下的右链， 都跟这个刚才的这个父，
建立于一条边，这样把它关联起来，像这边的蓝色的连线。
然后，我们把这个原来的这个右链，
我们就是给它都去掉，就是原来这个右链，都给它去掉。
然后我们再调整一下， 变成我们一个比较习惯看的一个森林的形式，那这个转换就完成了。
今天的课就到这儿，谢谢大家。