大家好，数据结构与算法，这一章，我们介绍第六章
最后的内容，就是，树的顺序存储结构以及K叉树，
那有很多种顺序的树存储方
法，那顺序的方法它有什么
意义，主要就是说，我们一个树，它是在
内存里面一个动态的而且是复杂的数据结构
我们如果需要把它导到外存里面存储起来
而且，以后要恢复，在内存里面，而且进行运算 那我们，就必须把这些节点，
进行序列化，那序列化的操作，我们首先
就会考虑说，/i，我们有哪一些遍历的方法，遍历它就是一种序列化
但是，简单的遍历，它不足以 恢复树，那我们来看一下
在先根顺序下的遍历方法，因为是先根遍历
因此，如果一个节点，它有
左孩子，那个左孩子就直接是跟在
这个节点后面，因此，我们只需要用ltag信息来表达
而，它的rlink，是比较复杂的
因为有可能会在比较远的地方出现
我们有，ltag和rlink的信息
就能够完整的表达，这个树的结构，
当然，我们也还需要保存它的info
域的信息，我们来看，有了rlink和ltag信息，我们怎么恢复树
那假设，这些信息我已经存在一个数组
里面，这个是，对应的数组，每一个下标的
这个相应的节点信息，我们首先，可以
把这几个节点，我都new出
它的相应的一个内存里面的指针，new出来以后
，我还对应的放到一个指针数组里面，当然，我可以不放到这个数组，另开一个
跟它平行的数组，然后，我再去读这里
面的rlink和ltag的信息，根据这个信息
，我很方便的恢复它的结构，例如，对于C节点，那
它的，/i,rlink
是D，然后，它的这个ltag说明，说，它有左子节点
，其后的这个E,就是它的左孩子，我们就这样建立
那我根据这个方法，依次的建立这些信息，最后，就给它
形成了一个二叉链的结构，对应到这样的一个等价
的声明的表
达，看，刚才的这个信息，其实它是有
些冗余的，这个冗余，就在rlink里面，
那我们看一下，能不能够，也让它成为一个指示tag位的 也就是说，/i,
0，1，表示就行 了，因为，我们刚才的这个rlink，ltag的这种信息
其中，我如果是，内存里面有那么一个，/i，二叉链表达的一个树
结构，我要让你导到外存里面，你要
去获取这个rlink的信息，是要编写一段比较的复杂的
代码的，如果我只需要表达rtag信息
也就是说，有孩子，我就是0，没有孩子，就是1
那这样的话，就只需要一个简单的先根遍历
就把这个整个信息，就导到外存里面了，我们来看这个结构
，iii，这是一个声明，它
对应的一个二叉链的形式，那我们导它的
啊，ltag和rtag就非常方便，我就直接在这一个先根
遍历里面，相应的都得到了这些信息，我们现在，从rtag，ltag
里面来恢复树，我们这个恢复树的操作，首先，我们
/i，对一个节点，那，如果它说，它是，rtag是等于0，那表示它有
右孩子，那右孩子在哪，现在我看不到，那我就是先把它放到栈里头，把这个节点本身
放到栈里头，我们继续处理，碰到，/i,这个
节点界的时候，没有左子节点，也就是说，它没有
左孩子，那它的后续的这个Key，因为它不是别人的左孩子
它要挂到这个二叉链结构里面，它必须是某一个节
点的右兄弟，因此，它是谁的右兄弟，我们就从栈
顶弹出一个元素，那它就是j的右兄弟，我们把它挂上
那，接着，我们再继续往下处理，啊，
类似，这几个，iii，元素，它们都是别人的右兄弟
所以，我们依次从栈顶，iii，弹出相应的元素，然后，把这个节点就挂成它的右兄弟，我们在记这个位置，它也是
它没有右兄弟，它也没有左孩子，那D，
就必然是别人的 一个右兄弟，那，我们从栈顶找到C，
这个节点，那它就是C的右兄弟，我们把D给挂
接上，然后，依次这样处理，我们就处理完了，然后我们就获得
了这么一个等价的一个，iii，森林的结构，
那我们看，这个，iii，带双标记的先根次序的恢复，
算法，首先，我们这些
，双标记的节点信息，是存在一个数组里头，这个数组，每一个元素它有一个info域，还有ltag，rtag，最开始，我们先
new出一个指针，这个指针，就是准备成为根
节点，然后，对这个数组的信息，就是依次扫描
，因为我前头已经得到了
这个节点的一个地址，那我就把这个point域，它的info给挂接上，
然后，我判断，它的rtag是不是0，
如果是0，表示它有右兄弟，那我给它放到栈里面，
否则，我们把这个右兄弟赋为空，接着，我们就准备下一个
节点，我们，如果是节点本身它的ltag等于0，
也就是说，表示它有左孩子，那么，这个下一个节点
就是，它刚才我们当前这个节点的左孩子 ，我们把预先准备的这个节点信息，给它
挂接上，否则，就是，这个，iii，节点，就是
，它的左孩子是空，它后面这个节点，就是某一个
，节点它的右兄弟，
是谁的右兄弟，这个信息是保留在栈里面的，我们从栈顶弹出一个元素
然后，挂接，挂接好以后，我们继续进行循环，我们要注意
，因为我们其实是在最开始，已经预先申请一个节点的，
位置，而且，我们是在循环里面，每一次，是对这个预先申请的
去赋值，那因此，在这个算法里面，
有最后那个节点，它其实是没有被处理
的，一定要注意，对它单独的进行一个处理，而且，对它来说，
它的左孩子，右孩子都是空，它的这个值，就是我们整个数组里面最后
那一个位置的值，那相应
的，我们来看一下，带双标记位的层次表示
方法，我们也是只需要用 ltag和rtag就能够完整的表示它的
信息，我们来看，这么一个带双标记的层次，
序列，给你这样的,/i,rtag，/i,ltag
的层次序列，你看起来，很犯晕，一下子不知道，这个结构是个什么样的，
那既然是层次序列，那我们就需要用到这样的一个队列，来作为辅助的
数据结构，那么，同样，我们是从左到右，顺序的来扫描这个序列
那如果，这个节点，/i，它说它有ltag 也就是说，/i，它的
这个，/i，左孩子是存在的，那我们把它存在
队列里面，/i，我们等着后面
它的这个左子节点出现的时候再挂接，而它说它
，/i，rtag等于0，也就是说，它有
右兄弟，那在这个层次序列里面，下一位，就是它的直接的右兄弟，我们可以直接挂上
那，当某一个节点
，它说它的这个， 右兄弟为1的时候，那就表示
说，它后面的这个节点，不是它的右兄弟 那，它该是
谁，那它显然是前面某一个节点它的左孩子，/i，
因为，我们为了要把这些节点都挂接到那个二叉链表示的这么一个
内部数据 结构，那某一节点，他必须要么是别人的左子孩子，或者是别人的右兄弟
那如果是说，它不是别人的右兄弟，它显然是某一个节点的左
子孩子，所以，我们就可以用这个原则，/i,一直进行，
内部处理，那就得到了，相应的这么一个
内部的二叉链表示的这么一个树的结构
那它对应于我们右边这边的，/i,
声明,带双标记位的层次序列，
我们也类似刚才带双标记的先根序列的构
造过程，我们的不同，首先就是，/i,要
用到队列，然后，从这开始，真的是非常的类似
/i,首先，我们准备一个根节点，然后，我们，/i，对这个
双标记的层次序列，我们，/i，进行一个扫描，当然，我们只扫描
N-1次， /i一进来，我们就可以知道，这个第一个，就是根的
信息，那我们把，/i，这个节点的，这个信息域，就
设为最开始的那一个，/i，然后我们看，/i，某一
个节点，/i，它如果是说，它的左tag
啊，是等于0，那么就是说，它有左子节点，我们把它
入到队列里面，否则，我们把它的左子孩子设为
空，接着，我们准备下一个节点，我们
/i，再看这个节点，/i，它的这个rtag是不是等于0，
如果是，等于0，这个刚才
准备的这个节点，就可以设为它的右兄弟
否则，就是说，它没有右兄弟，
我们把它的右兄弟设为空，同时，我们要为后面这个刚准备的节点
负责，也就是说，刚准备的这个节点，它不是别人的右兄弟，
那它一定是别人的左孩子，我们就从刚才前面保留过的队列
里面，去找出第一个 元素，然后，我们把这个新准备的这个节点，
设为刚才退出队列的这个元素，它的左孩子，
然后，我们这个指针，也是，/i，接着，/i，降
到这个，我们刚才新准备的节点，而且，继续刚才的循环操作，
那，最后，我们也要是对，/i，最后那个节点，进行一个单独的
处理，/i，它的左孩子，/i，右兄弟，都是设为
空，而且它的值，就是我们这个序列里面的，最后那个元素的值
/i，我们还有带度数的后根次序的表示方法
那，在后根次序表示方法里面，我们
这个节点，/i，按照后根的这个次序来遍历，
然后，我们存储这个节点，它们的
度数，那这个表达是非常完整的，那我们来看，我们怎么样
把这个带度数的后根次序，变成树
那我们在考察每一个节点的时候，我们看一下，
它的度，/i，如果是说，度为0，我可以直接的入到
栈里面，因为，这个后根遍历，它是一个，/i，
后进先出的这么一个结构，也就是深搜结构，它都是要 用到栈，来做为中间的数据结构，
那，当我们遇到E，这个
元素，/i，它说它有三个子节点，那它的 度为3，那我们就从栈里面，
退出三个元素，大家要注意，退元素的时候，
要注意它们的，/i，次序，也就是说，最先进的那一个，是最左的
子节点，然后，/i，最后进的那个，是，/i，最右边的这个子节点
/i，我们组合成一个子树以后，
把这个E节点， 又要入到这个栈里面，我们继续处理，那当我们遇到这个
C的时候，也是，要从栈里面，退出3个元素，然后，把C本身，/i，要存进去
那，X和I，它们都是度为0，
所以，/i，我们遇到D的时候，它度为2，从这个
/i，栈里面取出2个元素，那构成了一个 新子树，那么注意一下，这个栈
在处理完了以后，栈里面可能有若干个
节点，那就表示，整个这个森林的
它们的根的 节点，那在不同的存储表示里面，
有的存储表示，你可能需要，把这些根，要
穿一下，那还有一些其他的表示方法，/i，比如说，
这个，带标记的满二叉树表示方法，也就是说，我们需要标记
一下，哪些节点是内部节点，哪些节点是
叶节点，/i，我们同学可以回去想一下，这个信息也是非常完整的，有这个信息我们可以很好的
恢复这样的对应的一个树结构或着森林结构
啊，如果这个 ，/i，相应的这么一个二叉链的结构，它不是一个
，/i，满二叉树的，也就是说，某些节点可能只有一个
子节点，这种情况下，我们可以把这个空的地方，给补
充上，也就是说，伪满二叉树的形式，那就是，像
B节点，它的，/i，左右子孩子，那这个左边是空的，那么就补一个
空的标记，最后给大家留一下
思考题，也就是，在这些顺序表达里面？
信息冗余的问题，另外，还有很多顺序
表达的方法，大家都可以考虑一下，比如说，带度数的先根，还有带度数的
层次，还有一个重要的问题，
也就是，二叉树，它也是一种动态的结构，如果，我们要把它存到
外存里面，我也要把这个复杂的动态结构给它序列化，当然我们
也对应到各种遍历的方法，那跟森林的，/i，顺序化的存储类似，你其
实也可以，设计一套，二叉树的这些，/i，顺序的存储
方法，但是，要注意，语义上是稍微有不同
的，然后，我们再介绍一下 K叉
树，那K叉，它其实非常类似于二叉树，也就是说
二叉树，需要严格的区分左右，如果你把左看做是第一孩子，右看做是第二
孩子，那在K叉树里面，它也是非常严格
的区分第几个孩子，当然，我们这里编号是 iii，0到K-1
那，这几个孩子，哪一个空，别的都不能够替代前面的这个空的位置
你其实，也可以看做，这个K叉树，每一个节点，它都有完整的
K个指针域，哪一个域空了，别人都不能够替代
挤上去，那你必须，就让它空在
那，我们类似的，也有，iii，满K叉树
还有，完全K叉树的，/i,相关的定义，当然，
K叉树也有些应用，我们同学可以去考虑一下 谢谢大家