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