学了C/C++ 语言，我们已经会编程解题了，那怎么用来处理实际的问题呢？ 怎么设计数据结构来有效地管理企业人员？如何编写程序没让人才和岗位达到最佳匹配？如何安排旅行计划，找到最佳行程路径？这些学习、工作、生活中常常困扰我们的问题，你将在《数据结构基础》课程中找到答案。 数据结构是计算机程序设计的基础，告诉我们数据在计算机里是如何组织与存储的，能帮助我们刻画实际问题中的信息及其相互关系。当我们对一个实际问题本身有了一个结构化的认识之后，就可以选择合适的解决方法了。 完成这门课之时，你将掌握线性表、栈与队列、字符串、二叉树、树、图等经典的数据结构，并运用这些基础数据结构和相关算法解决实际应用问题。扎实的数据结构知识是项目开发与结构层次设计的关键，学好这门课会让你在高年级的计算机专业课程以及毕业项目设计中事半功倍，同时也将为你成为一名优秀的程序设计人员打下坚实的基础。 附：本课程的内容来自教材：《数据结构与算法》（张铭、王腾蛟、赵海燕 编著），高等教育出版社，2008年。
树的顺序存储和K叉树
Loading...
来自 Peking University 的课程
数据结构基础
218 个评分
从本节课中
树
生活中，树形结构是很多客观事物与关系的抽象模型，例如亲属关系可以形成一个族谱，公司的上下级关系可以形成一个人事表。不过这些树形结构中，父结点往往都不止一个子结点，说明二叉树的表达能力不足以表示这些常见的客观问题。
本章将引入树和森林的概念，介绍树的存储结构和多种表示方法。在实际应用中，你可以根据不同的情境，使用不同存储方式的树，从而解决相关的问题。
重点：树的深搜、宽搜遍历，树的左子/右兄表示，父结点表示法与并查集运算，树的顺序存储（输入/输出都要考虑）。
难点：树的各种应用基本上都基于遍历框架，需要注意左子/右兄表述方法中的对右兄弟链的访问；树的顺序存储通常也适应于二叉树的情况，可以用于完成建树的操作。
与讲师见面
Prof. Ming Zhang 张铭教授
School of Electronics Engineering and Computer Science北京大学计算机系
大家好，数据结构与算法，这一章，我们介绍第六章
最后的内容，就是，树的顺序存储结构已经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，对这个
双标记的层次序列，我们，/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叉树也有些应用，那我们同学可以去考虑一下 谢谢大家
