斗罗世界中的C语言与数据结构：第三章
斗罗世界中的C语言与数据结构：第三章
接下来是第四关，考验学员的学习能力。这一关会开放史莱克学院的主网给他们查询资料，只是他们的所有行为都会经过反作弊系统的审查。
第一题：
看清了有点麻烦，而且夕羽颜并不知道二叉排序树是什么？于是他打开浏览器，使用唐门研发的搜索引擎检索二叉排序树的内容。
内容来源：二叉排序树(Binary Sort Tree) - 程序员姜戈 - 博客园 (cnblogs.com)
这是他检索到的有关二叉排序树的内容。哦！原来他就是二叉查找树，也叫做二叉搜索树，这么多名字，搞得夕羽颜有点晕头转向了。
他提炼了一下，如下内容出现在他的脑海中：
- 左子树的所有结点都比根节点小，而所有右子树的结点都比根节点大。
- 二叉排序树中各结点的值是唯一的。
这时候会不会有疑问了，如果给出的序列有重复的值怎么办呢?
夕羽颜又开始查找资料，终于在一本书籍中找到了如下内容：
“二叉树是一种动态查找表。特点是，树的结构不是一次生成的，而是在查找过程中，当树中不存在关键字等于给定值的结点时再进行插入。新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。”
简而言之，就是如果存在重复的值，只添加一次，后面重复出现的不再添加到树上!
所以我们开始来画树。
夕羽颜使用它的计算机武魂根据他的意识很快就画好了A选项的图：
B选项是这样的：
这两个选项是一样的，那么只要找到一个和他们两个不一样的即可。
很快我们就可以看到C选项和A、B选项不一样。
而D选项和A、B选项都是一样的。
其实，只要我们熟练了，还是可以不用画图的。可以很快判断哪一个与其他不一样。
在这一题，夕羽颜落后了其他竞争对手不少，所以第二题他得加快速度了！
一看到这道题目，夕羽颜就慌了，夕羽颜之前并没接触过B-树，这可如何是好。于是他赶快查找B-树的有关资料…
图片内容来源：https://www.cnblogs.com/lianzhilei/p/11250589.html
我们可以看到其中说明的”每个节点最多最有m个子节点。“所以m阶B-树是一棵m叉树。而B树又叫做平衡多路查找树，所以m阶B-树是一棵m叉平衡排序树。至于为什么平衡？
这里有两点可以参考：
- 左子树和右子树的分布是比较均匀的。
- 从根节点至任何一个叶子节点的链路长度是一致的。
第二题答完夕羽颜发现他居然已经到了较为领先的位置，原来大家都是第一次接触B树。接下来是第三题，这一题夕羽颜的父亲之前给他提到过，所以他很快就答对了。
题目解析：
首先我们得了解什么是稳定性：
通俗地讲就是能让任何2个相等的数排序之前在序列的先后位置同进行排序之后在序列的先后位置相同。再简单一点就是，如果a1 = a2，a1本来在a2的前面，然后进行排序之后，a1仍然还在a2之前。
所以回答这个问题，要求我们掌握上面所有的排序算法。
堆排序、快速排序、希尔排序、直接选择排序是不稳定的。
而基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的。
所以答案是D。
腾讯云开发者
