1 00:00:03,627 --> 00:00:06,165 大家好,数据结构与算法,这一章,我们介绍第六章 2 00:00:06,513 --> 00:00:12,471 最后的内容,就是,树的顺序存储结构以及K叉树, 3 00:00:12,921 --> 00:00:18,605 那有很多种顺序的树存储方 4 00:00:18,923 --> 00:00:21,889 法,那顺序的方法它有什么 5 00:00:21,889 --> 00:00:26,225 意义,主要就是说,我们一个树,它是在 6 00:00:26,590 --> 00:00:31,288 内存里面一个动态的而且是复杂的数据结构 7 00:00:31,645 --> 00:00:36,168 我们如果需要把它导到外存里面存储起来 8 00:00:36,807 --> 00:00:43,812 而且,以后要恢复,在内存里面,而且进行运算 那我们,就必须把这些节点, 9 00:00:44,537 --> 00:00:49,972 进行序列化,那序列化的操作,我们首先 10 00:00:49,972 --> 00:00:57,103 就会考虑说,/i,我们有哪一些遍历的方法,遍历它就是一种序列化 11 00:00:57,103 --> 00:01:02,920 但是,简单的遍历,它不足以 恢复树,那我们来看一下 12 00:01:02,920 --> 00:01:09,075 在先根顺序下的遍历方法,因为是先根遍历 13 00:01:09,796 --> 00:01:12,925 因此,如果一个节点,它有 14 00:01:13,337 --> 00:01:17,147 左孩子,那个左孩子就直接是跟在 15 00:01:17,148 --> 00:01:22,879 这个节点后面,因此,我们只需要用ltag信息来表达 16 00:01:23,308 --> 00:01:28,249 而,它的rlink,是比较复杂的 17 00:01:29,109 --> 00:01:32,829 因为有可能会在比较远的地方出现 18 00:01:33,365 --> 00:01:38,522 我们有,ltag和rlink的信息 19 00:01:38,887 --> 00:01:43,563 就能够完整的表达,这个树的结构, 20 00:01:44,423 --> 00:01:48,588 当然,我们也还需要保存它的info 21 00:01:48,588 --> 00:01:55,173 域的信息,我们来看,有了rlink和ltag信息,我们怎么恢复树 22 00:01:56,308 --> 00:02:00,267 那假设,这些信息我已经存在一个数组 23 00:02:00,266 --> 00:02:04,409 里面,这个是,对应的数组,每一个下标的 24 00:02:04,745 --> 00:02:10,374 这个相应的节点信息,我们首先,可以 25 00:02:11,129 --> 00:02:16,306 把这几个节点,我都new出 26 00:02:16,306 --> 00:02:22,411 它的相应的一个内存里面的指针,new出来以后 27 00:02:23,013 --> 00:02:29,803 ,我还对应的放到一个指针数组里面,当然,我可以不放到这个数组,另开一个 28 00:02:30,133 --> 00:02:35,698 跟它平行的数组,然后,我再去读这里 29 00:02:36,323 --> 00:02:41,459 面的rlink和ltag的信息,根据这个信息 30 00:02:42,127 --> 00:02:47,900 ,我很方便的恢复它的结构,例如,对于C节点,那 31 00:02:47,901 --> 00:02:49,980 它的,/i,rlink 32 00:02:49,979 --> 00:02:56,433 是D,然后,它的这个ltag说明,说,它有左子节点 33 00:02:56,433 --> 00:03:01,549 ,其后的这个E,就是它的左孩子,我们就这样建立 34 00:03:01,549 --> 00:03:08,112 那我根据这个方法,依次的建立这些信息,最后,就给它 35 00:03:08,111 --> 00:03:13,503 形成了一个二叉链的结构,对应到这样的一个等价 36 00:03:13,503 --> 00:03:15,430 的声明的表 37 00:03:15,429 --> 00:03:20,876 达,看,刚才的这个信息,其实它是有 38 00:03:20,877 --> 00:03:26,124 些冗余的,这个冗余,就在rlink里面, 39 00:03:26,819 --> 00:03:34,450 那我们看一下,能不能够,也让它成为一个指示tag位的 也就是说,/i, 40 00:03:34,450 --> 00:03:42,118 0,1,表示就行 了,因为,我们刚才的这个rlink,ltag的这种信息 41 00:03:42,728 --> 00:03:50,682 其中,我如果是,内存里面有那么一个,/i,二叉链表达的一个树 42 00:03:50,682 --> 00:03:54,082 结构,我要让你导到外存里面,你要 43 00:03:54,082 --> 00:03:58,358 去获取这个rlink的信息,是要编写一段比较的复杂的 44 00:03:59,040 --> 00:04:03,326 代码的,如果我只需要表达rtag信息 45 00:04:03,327 --> 00:04:08,071 也就是说,有孩子,我就是0,没有孩子,就是1 46 00:04:08,071 --> 00:04:12,485 那这样的话,就只需要一个简单的先根遍历 47 00:04:12,897 --> 00:04:19,210 就把这个整个信息,就导到外存里面了,我们来看这个结构 48 00:04:20,529 --> 00:04:21,529 ,iii,这是一个声明,它 49 00:04:24,510 --> 00:04:28,644 对应的一个二叉链的形式,那我们导它的 50 00:04:29,034 --> 00:04:35,113 啊,ltag和rtag就非常方便,我就直接在这一个先根 51 00:04:35,113 --> 00:04:42,375 遍历里面,相应的都得到了这些信息,我们现在,从rtag,ltag 52 00:04:42,375 --> 00:04:48,189 里面来恢复树,我们这个恢复树的操作,首先,我们 53 00:04:50,548 --> 00:04:56,506 /i,对一个节点,那,如果它说,它是,rtag是等于0,那表示它有 54 00:04:56,506 --> 00:05:03,718 右孩子,那右孩子在哪,现在我看不到,那我就是先把它放到栈里头,把这个节点本身 55 00:05:03,718 --> 00:05:09,498 放到栈里头,我们继续处理,碰到,/i,这个 56 00:05:09,498 --> 00:05:13,281 节点界的时候,没有左子节点,也就是说,它没有 57 00:05:13,280 --> 00:05:18,410 左孩子,那它的后续的这个Key,因为它不是别人的左孩子 58 00:05:19,004 --> 00:05:23,497 它要挂到这个二叉链结构里面,它必须是某一个节 59 00:05:23,497 --> 00:05:28,105 点的右兄弟,因此,它是谁的右兄弟,我们就从栈 60 00:05:28,105 --> 00:05:33,152 顶弹出一个元素,那它就是j的右兄弟,我们把它挂上 61 00:05:33,715 --> 00:05:37,874 那,接着,我们再继续往下处理,啊, 62 00:05:38,291 --> 00:05:43,438 类似,这几个,iii,元素,它们都是别人的右兄弟 63 00:05:43,938 --> 00:05:59,147 所以,我们依次从栈顶,iii,弹出相应的元素,然后,把这个节点就挂成它的右兄弟,我们在记这个位置,它也是 64 00:05:59,570 --> 00:06:05,200 它没有右兄弟,它也没有左孩子,那D, 65 00:06:05,200 --> 00:06:11,841 就必然是别人的 一个右兄弟,那,我们从栈顶找到C, 66 00:06:12,273 --> 00:06:16,279 这个节点,那它就是C的右兄弟,我们把D给挂 67 00:06:16,279 --> 00:06:22,323 接上,然后,依次这样处理,我们就处理完了,然后我们就获得 68 00:06:22,323 --> 00:06:27,368 了这么一个等价的一个,iii,森林的结构, 69 00:06:27,935 --> 00:06:33,325 那我们看,这个,iii,带双标记的先根次序的恢复, 70 00:06:33,324 --> 00:06:37,204 算法,首先,我们这些 71 00:06:37,204 --> 00:06:50,046 ,双标记的节点信息,是存在一个数组里头,这个数组,每一个元素它有一个info域,还有ltag,rtag,最开始,我们先 72 00:06:50,470 --> 00:06:55,084 new出一个指针,这个指针,就是准备成为根 73 00:06:55,085 --> 00:07:02,182 节点,然后,对这个数组的信息,就是依次扫描 74 00:07:03,216 --> 00:07:07,992 ,因为我前头已经得到了 75 00:07:07,992 --> 00:07:14,353 这个节点的一个地址,那我就把这个point域,它的info给挂接上, 76 00:07:14,749 --> 00:07:18,005 然后,我判断,它的rtag是不是0, 77 00:07:18,317 --> 00:07:22,508 如果是0,表示它有右兄弟,那我给它放到栈里面, 78 00:07:22,508 --> 00:07:29,448 否则,我们把这个右兄弟赋为空,接着,我们就准备下一个 79 00:07:29,448 --> 00:07:34,996 节点,我们,如果是节点本身它的ltag等于0, 80 00:07:35,305 --> 00:07:40,456 也就是说,表示它有左孩子,那么,这个下一个节点 81 00:07:40,838 --> 00:07:49,543 就是,它刚才我们当前这个节点的左孩子 ,我们把预先准备的这个节点信息,给它 82 00:07:50,370 --> 00:07:54,945 挂接上,否则,就是,这个,iii,节点,就是 83 00:07:56,052 --> 00:08:01,291 ,它的左孩子是空,它后面这个节点,就是某一个 84 00:08:01,807 --> 00:08:04,672 ,节点它的右兄弟, 85 00:08:05,104 --> 00:08:11,675 是谁的右兄弟,这个信息是保留在栈里面的,我们从栈顶弹出一个元素 86 00:08:12,221 --> 00:08:17,095 然后,挂接,挂接好以后,我们继续进行循环,我们要注意 87 00:08:17,631 --> 00:08:22,422 ,因为我们其实是在最开始,已经预先申请一个节点的, 88 00:08:22,422 --> 00:08:28,168 位置,而且,我们是在循环里面,每一次,是对这个预先申请的 89 00:08:28,652 --> 00:08:32,329 去赋值,那因此,在这个算法里面, 90 00:08:32,811 --> 00:08:36,490 有最后那个节点,它其实是没有被处理 91 00:08:36,490 --> 00:08:42,047 的,一定要注意,对它单独的进行一个处理,而且,对它来说, 92 00:08:42,378 --> 00:08:48,980 它的左孩子,右孩子都是空,它的这个值,就是我们整个数组里面最后 93 00:08:49,529 --> 00:08:53,446 那一个位置的值,那相应 94 00:08:53,816 --> 00:08:57,521 的,我们来看一下,带双标记位的层次表示 95 00:08:57,521 --> 00:09:05,471 方法,我们也是只需要用 ltag和rtag就能够完整的表示它的 96 00:09:05,471 --> 00:09:10,482 信息,我们来看,这么一个带双标记的层次, 97 00:09:10,482 --> 00:09:16,568 序列,给你这样的,/i,rtag,/i,ltag 98 00:09:17,030 --> 00:09:22,457 的层次序列,你看起来,很犯晕,一下子不知道,这个结构是个什么样的, 99 00:09:22,958 --> 00:09:29,118 那既然是层次序列,那我们就需要用到这样的一个队列,来作为辅助的 100 00:09:29,118 --> 00:09:36,658 数据结构,那么,同样,我们是从左到右,顺序的来扫描这个序列 101 00:09:37,305 --> 00:09:45,028 那如果,这个节点,/i,它说它有ltag 也就是说,/i,它的 102 00:09:45,028 --> 00:09:52,012 这个,/i,左孩子是存在的,那我们把它存在 103 00:09:52,368 --> 00:09:56,362 队列里面,/i,我们等着后面 104 00:09:56,362 --> 00:10:02,013 它的这个左子节点出现的时候再挂接,而它说它 105 00:10:03,186 --> 00:10:05,963 ,/i,rtag等于0,也就是说,它有 106 00:10:06,268 --> 00:10:14,334 右兄弟,那在这个层次序列里面,下一位,就是它的直接的右兄弟,我们可以直接挂上 107 00:10:14,798 --> 00:10:18,629 那,当某一个节点 108 00:10:19,050 --> 00:10:27,272 ,它说它的这个, 右兄弟为1的时候,那就表示 109 00:10:27,769 --> 00:10:33,477 说,它后面的这个节点,不是它的右兄弟 那,它该是 110 00:10:33,477 --> 00:10:40,281 谁,那它显然是前面某一个节点它的左孩子,/i, 111 00:10:41,244 --> 00:10:47,612 因为,我们为了要把这些节点都挂接到那个二叉链表示的这么一个 112 00:10:47,612 --> 00:10:56,494 内部数据 结构,那某一节点,他必须要么是别人的左子孩子,或者是别人的右兄弟 113 00:10:57,059 --> 00:11:01,298 那如果是说,它不是别人的右兄弟,它显然是某一个节点的左 114 00:11:01,299 --> 00:11:06,174 子孩子,所以,我们就可以用这个原则,/i,一直进行, 115 00:11:07,086 --> 00:11:10,303 内部处理,那就得到了,相应的这么一个 116 00:11:10,303 --> 00:11:15,634 内部的二叉链表示的这么一个树的结构 117 00:11:16,038 --> 00:11:19,850 那它对应于我们右边这边的,/i, 118 00:11:20,374 --> 00:11:26,024 声明,带双标记位的层次序列, 119 00:11:26,621 --> 00:11:31,255 我们也类似刚才带双标记的先根序列的构 120 00:11:31,254 --> 00:11:36,197 造过程,我们的不同,首先就是,/i,要 121 00:11:36,197 --> 00:11:41,694 用到队列,然后,从这开始,真的是非常的类似 122 00:11:42,162 --> 00:11:47,456 /i,首先,我们准备一个根节点,然后,我们,/i,对这个 123 00:11:47,457 --> 00:11:54,582 双标记的层次序列,我们,/i,进行一个扫描,当然,我们只扫描 124 00:11:54,947 --> 00:12:02,226 N-1次, /i一进来,我们就可以知道,这个第一个,就是根的 125 00:12:02,226 --> 00:12:08,228 信息,那我们把,/i,这个节点的,这个信息域,就 126 00:12:08,624 --> 00:12:13,487 设为最开始的那一个,/i,然后我们看,/i,某一 127 00:12:13,488 --> 00:12:18,011 个节点,/i,它如果是说,它的左tag 128 00:12:18,375 --> 00:12:23,342 啊,是等于0,那么就是说,它有左子节点,我们把它 129 00:12:23,343 --> 00:12:28,243 入到队列里面,否则,我们把它的左子孩子设为 130 00:12:28,242 --> 00:12:33,215 空,接着,我们准备下一个节点,我们 131 00:12:34,880 --> 00:12:39,452 /i,再看这个节点,/i,它的这个rtag是不是等于0, 132 00:12:39,983 --> 00:12:43,104 如果是,等于0,这个刚才 133 00:12:43,104 --> 00:12:48,295 准备的这个节点,就可以设为它的右兄弟 134 00:12:49,167 --> 00:12:53,395 否则,就是说,它没有右兄弟, 135 00:12:53,872 --> 00:12:59,381 我们把它的右兄弟设为空,同时,我们要为后面这个刚准备的节点 136 00:12:59,381 --> 00:13:05,225 负责,也就是说,刚准备的这个节点,它不是别人的右兄弟, 137 00:13:05,225 --> 00:13:11,073 那它一定是别人的左孩子,我们就从刚才前面保留过的队列 138 00:13:11,073 --> 00:13:17,854 里面,去找出第一个 元素,然后,我们把这个新准备的这个节点, 139 00:13:17,854 --> 00:13:22,611 设为刚才退出队列的这个元素,它的左孩子, 140 00:13:23,020 --> 00:13:27,714 然后,我们这个指针,也是,/i,接着,/i,降 141 00:13:27,715 --> 00:13:33,456 到这个,我们刚才新准备的节点,而且,继续刚才的循环操作, 142 00:13:33,832 --> 00:13:40,262 那,最后,我们也要是对,/i,最后那个节点,进行一个单独的 143 00:13:40,261 --> 00:13:45,316 处理,/i,它的左孩子,/i,右兄弟,都是设为 144 00:13:46,254 --> 00:13:51,188 空,而且它的值,就是我们这个序列里面的,最后那个元素的值 145 00:13:54,372 --> 00:13:58,239 /i,我们还有带度数的后根次序的表示方法 146 00:13:59,053 --> 00:14:02,492 那,在后根次序表示方法里面,我们 147 00:14:02,492 --> 00:14:07,611 这个节点,/i,按照后根的这个次序来遍历, 148 00:14:08,783 --> 00:14:12,120 然后,我们存储这个节点,它们的 149 00:14:12,632 --> 00:14:19,158 度数,那这个表达是非常完整的,那我们来看,我们怎么样 150 00:14:19,751 --> 00:14:22,845 把这个带度数的后根次序,变成树 151 00:14:23,861 --> 00:14:30,384 那我们在考察每一个节点的时候,我们看一下, 152 00:14:30,383 --> 00:14:36,075 它的度,/i,如果是说,度为0,我可以直接的入到 153 00:14:36,658 --> 00:14:42,212 栈里面,因为,这个后根遍历,它是一个,/i, 154 00:14:42,841 --> 00:14:50,737 后进先出的这么一个结构,也就是深搜结构,它都是要 用到栈,来做为中间的数据结构, 155 00:14:51,919 --> 00:14:55,739 那,当我们遇到E,这个 156 00:14:55,740 --> 00:15:03,051 元素,/i,它说它有三个子节点,那它的 度为3,那我们就从栈里面, 157 00:15:03,650 --> 00:15:07,784 退出三个元素,大家要注意,退元素的时候, 158 00:15:08,305 --> 00:15:14,234 要注意它们的,/i,次序,也就是说,最先进的那一个,是最左的 159 00:15:14,235 --> 00:15:20,761 子节点,然后,/i,最后进的那个,是,/i,最右边的这个子节点 160 00:15:22,695 --> 00:15:25,329 /i,我们组合成一个子树以后, 161 00:15:25,989 --> 00:15:33,138 把这个E节点, 又要入到这个栈里面,我们继续处理,那当我们遇到这个 162 00:15:33,677 --> 00:15:40,351 C的时候,也是,要从栈里面,退出3个元素,然后,把C本身,/i,要存进去 163 00:15:41,642 --> 00:15:45,469 那,X和I,它们都是度为0, 164 00:15:45,469 --> 00:15:50,370 所以,/i,我们遇到D的时候,它度为2,从这个 165 00:15:51,560 --> 00:15:57,352 /i,栈里面取出2个元素,那构成了一个 新子树,那么注意一下,这个栈 166 00:15:58,574 --> 00:16:02,390 在处理完了以后,栈里面可能有若干个 167 00:16:02,391 --> 00:16:06,263 节点,那就表示,整个这个森林的 168 00:16:06,480 --> 00:16:12,029 它们的根的 节点,那在不同的存储表示里面, 169 00:16:12,482 --> 00:16:16,399 有的存储表示,你可能需要,把这些根,要 170 00:16:16,399 --> 00:16:22,358 穿一下,那还有一些其他的表示方法,/i,比如说, 171 00:16:22,358 --> 00:16:28,979 这个,带标记的满二叉树表示方法,也就是说,我们需要标记 172 00:16:29,409 --> 00:16:33,312 一下,哪些节点是内部节点,哪些节点是 173 00:16:33,311 --> 00:16:40,769 叶节点,/i,我们同学可以回去想一下,这个信息也是非常完整的,有这个信息我们可以很好的 174 00:16:41,124 --> 00:16:46,428 恢复这样的对应的一个树结构或着森林结构 175 00:16:47,525 --> 00:16:54,895 啊,如果这个 ,/i,相应的这么一个二叉链的结构,它不是一个 176 00:16:57,063 --> 00:17:01,277 ,/i,满二叉树的,也就是说,某些节点可能只有一个 177 00:17:01,718 --> 00:17:07,108 子节点,这种情况下,我们可以把这个空的地方,给补 178 00:17:07,108 --> 00:17:12,034 充上,也就是说,伪满二叉树的形式,那就是,像 179 00:17:12,811 --> 00:17:19,183 B节点,它的,/i,左右子孩子,那这个左边是空的,那么就补一个 180 00:17:19,183 --> 00:17:23,343 空的标记,最后给大家留一下 181 00:17:23,655 --> 00:17:29,238 思考题,也就是,在这些顺序表达里面? 182 00:17:29,238 --> 00:17:33,179 信息冗余的问题,另外,还有很多顺序 183 00:17:33,178 --> 00:17:39,475 表达的方法,大家都可以考虑一下,比如说,带度数的先根,还有带度数的 184 00:17:39,475 --> 00:17:42,183 层次,还有一个重要的问题, 185 00:17:42,182 --> 00:17:48,802 也就是,二叉树,它也是一种动态的结构,如果,我们要把它存到 186 00:17:49,088 --> 00:17:55,245 外存里面,我也要把这个复杂的动态结构给它序列化,当然我们 187 00:17:55,244 --> 00:18:03,402 也对应到各种遍历的方法,那跟森林的,/i,顺序化的存储类似,你其 188 00:18:03,402 --> 00:18:08,325 实也可以,设计一套,二叉树的这些,/i,顺序的存储 189 00:18:08,325 --> 00:18:13,010 方法,但是,要注意,语义上是稍微有不同 190 00:18:16,628 --> 00:18:19,741 的,然后,我们再介绍一下 K叉 191 00:18:20,786 --> 00:18:24,992 树,那K叉,它其实非常类似于二叉树,也就是说 192 00:18:25,396 --> 00:18:31,533 二叉树,需要严格的区分左右,如果你把左看做是第一孩子,右看做是第二 193 00:18:31,533 --> 00:18:36,534 孩子,那在K叉树里面,它也是非常严格 194 00:18:36,534 --> 00:18:42,858 的区分第几个孩子,当然,我们这里编号是 iii,0到K-1 195 00:18:43,211 --> 00:18:49,427 那,这几个孩子,哪一个空,别的都不能够替代前面的这个空的位置 196 00:18:49,880 --> 00:18:55,207 你其实,也可以看做,这个K叉树,每一个节点,它都有完整的 197 00:18:55,493 --> 00:19:00,091 K个指针域,哪一个域空了,别人都不能够替代 198 00:19:00,090 --> 00:19:03,209 挤上去,那你必须,就让它空在 199 00:19:03,210 --> 00:19:09,466 那,我们类似的,也有,iii,满K叉树 200 00:19:09,848 --> 00:19:14,228 还有,完全K叉树的,/i,相关的定义,当然, 201 00:19:14,228 --> 00:19:21,122 K叉树也有些应用,我们同学可以去考虑一下 谢谢大家