25版王道数据结构课后习题详细分析第七章 7.3树形查找

本文主要是介绍25版王道数据结构课后习题详细分析第七章 7.3树形查找，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、单项选择题

————————————————————

解析：二叉排序树插入新结点时不会引起树的分裂组合。对二叉排序树进行中序遍历可得到有序序列。当插入的关键字有序时，二叉排序树会形成一个长链，此时深度最大。在此种情况下进行查找，有可能需要比较每个结点的关键字，超过总结点数的1/2。

正确答案：

————————————————————

解析：由二叉排序树的定义不难得出中序遍历二叉树得到的序列是一个有序序列。

正确答案：

————————————————————

解析：二叉排序树的查找路径是自顶向下的，其平均查找长度主要取决于树的高度。

正确答案：

————————————————————

解析：在二叉排序树的存储结构中，每个结点由三部分构成，其中左(或右）指针指向比该结点的关键字值小(或大）的结点。关键字值最大的结点位于二叉排序树的最右位置，因此它的右指针一定为空（有可能不是叶结点)。还可用反证法，若右指针不为空，则右指针上的关键字肯定比:原关键字大，所以原关键字结点一定不是值最大的，与条件矛盾，所以右指针一定为空。

正确答案：

————————————————————

解析：在二叉排序树上查找时，先与根结点值进行比较，若相同，则查找结束，否则根据比较结果，沿着左子树或右子树向下继续查找。根据二叉排序树的定义，有左子树结点值≤根结点值≤右子树结点值。C序列中，比较911关键字后，应转向其左子树比较240，左子树中不应出现比911更大的数值，但240竟有一个右孩子结点值为912，所以不可能是正确的序列。

正确答案：

————————————————————

解析：按照二叉排序树的构造方法，不难得到A, B,D序列的构造结果相同。

正确答案：

————————————————————

解析：

正确答案：

————————————————————

解析：当输入序列是一个有序序列时，构造的二叉排序树是一个单支树，当查找一个不存在的关键字值或最后一个结点的关键字值时，需要n次比较。

正确答案：

————————————————————

解析：五个不同结点构造的二叉查找树，中序序列是确定的。先序序列的个数为n=5的卡特兰数，加上中序序列和先序序列能唯一确定一棵二叉树，因此二叉排序树的形态共有Catalan(5)=42种。

正确答案：

————————————————————

解析：当二叉排序树的叶结点全部都在相邻的两层内时，深度最小。理想情况是从第一层到倒数第二层为满二叉树。类比完全二叉树，可得深度为[log2(n + 1)]。

正确答案：

————————————————————

解析：

正确答案：

————————————————————

解析：

正确答案：

————————————————————

解析：

正确答案：

————————————————————

解析：插入和删除结点都有可能引起LR平衡旋转或者RL平衡旋转，发生两次旋转操作。

正确答案：

————————————————————

解析：当按关键字有序的顺序插入初始为空的平衡二叉树时，若关键字个数n=2*-1时，则该平衡二叉树一定是一棵满二叉树(可以用1~3、1~7手工验证)。当插入关键字1023时，平衡二叉树正好是一棵满二叉树，高度是9。因此，插入关键字1024后，平衡二叉树的高度是10。

正确答案：

————————————————————

解析：Ⅰ和Ⅱ都是红黑树的性质。AVL是高度平衡的二叉查找树，红黑树是适度平衡的二叉查找树，从这一点也可以看出AVL的查询效率往往更优，Ⅲ错误。AVL的某结点的左右孩子的平衡因子都是零，并不能说明左右子树的高度相等，因此该结点的平衡因子不一定为零，IⅣ错误。

正确答案：

————————————————————

解析：自平衡的二叉排序树是指在插入和删除时能自动调整以保持其所定义的平衡性，两者都属于自平衡二叉树，A正确。两者的查找、插入、删除操作的时间复杂度都为O(logr)，B正确。在红黑树中删除结点时，情况1可能变为情况2、3或4，情况⒉会变为情况3，可能会出现旋转次数超过2次的情况，C错误。从任一结点到每个叶结点的所有路径都包含相同数目的黑结点，没有两个连续的红结点，且叶结点是红色的，这意味着在任一结点到其左右子树中最远和最近的叶结点之间，红结点的数目小于或等于黑结点的数目，路径长度之比不超过2，D正确。

正确答案：

————————————————————

解析：红黑树的红结点数目最大可以是黑结点数目的2倍（如一棵有3个结点的红黑树，第1层为黑色，第2层为红色)，A错误。从根结点出发到所有叶结点的黑结点数是相同的，若所有结点都是黑色，则一定是满二叉树，B正确。考虑某个黑结点，它可以有一个空叶结点孩子和一个非空红结点孩子，C错误。红黑树中可能存在红结点，根结点为红色的子树不是红黑树，D错误。

正确答案：

————————————————————

解析：红黑树是一种特殊的二叉排序树，B项不满足二叉排序树的性质。C项中，结点2的左右黑结点数不同。D项中，结点3的左右黑结点数不同。只有A项满足红黑树的定义。

正确答案：

————————————————————

解析：

正确答案：

————————————————————

解析：

正确答案：

————————————————————

解析：

正确答案：

————————————————————

解析：根据平衡二叉树的定义，任意结点的左、右子树高度差的绝对值不超过1。而其余3个答案均可以找到不满足条件的结点。答题时可以把每个非叶结点的平衡因子都写出来。

正确答案：

————————————————————

解析：

正确答案：

————————————————————

解析：

正确答案：

————————————————————

解析：

正确答案：

————————————————————

解析：由于在二叉排序树中插入结点的位置是一个新的叶结点，若删除的是叶结点，则重新插入后得到的二叉排序树与原来的二叉排序树相同。若删除的是非叶结点，在删除过程中会找其他结点填补，重新插入后变成叶结点，则得到的二叉排序树与原来的二叉排序树不同。

正确答案：

————————————————————

解析：

正确答案：

————————————————————

解析：大多数教材将平衡二叉树定义为一种高度平衡的二叉排序树，二叉排序树的中序序列是一个升序序列，而题意正好相反。由此可知，命题老师认为平衡二叉树仅为一棵满足高度平衡的二叉树，不一定是二叉排序树。只有两个结点的平衡二叉树的根结点的度为1，A错误。中序遍历后得到一个降序序列(与二叉排序树正好相反)，树中最大元素一定无左子树(可能有右子树)，这与二叉排序树也正好相反，也因此不一定是叶结点，B错误，D正确。最后插入的结点可能会导致平衡调整，而不一定是叶结点，C错误。

正确答案：

————————————————————