大家好,数据结构与算法,这一章,我们介绍第六章
最后的内容,就是,树的顺序存储结构已经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叉树也有些应用,那我们同学可以去考虑一下 谢谢大家