首页 > 试题广场 >

下面关于二叉搜索树正确的说法包括________。

[单选题]

待删除节点有左子树和右子树时，只能使用左子树的最大值节点替换待删除节点。

给定一棵二叉搜索树的前序和后序遍率历结果，无法确定这棵二叉搜索树。

给定一棵二叉搜索树，根据节点值大小排序所需时间复杂度是线性的。

给定一棵二叉搜索树，可以在线性时间复杂度内转化为平衡二叉搜索树。

推荐

snowpacer

A可以用右子树最小结点来替代错误

B 对于搜索树来说，只要知道前序遍历就能还原了，第一个是根结点，之后的连续K个小于根节点的为左子树，后面的都是右子树，然后递归；错误

C 正确，中序遍历就可以了

D 如果允许额外的存储空间，可以先按照C生成一个排好序的数组，然后不断的找mid节点作为根来构造平衡树就是线性的，如果不允许额外空间只能靠旋转的话无法用线性时间。因为题目是单选，只能理解为不允许额外的存储空间了，

所以只能选C

编辑于 2015-07-27 19:43:34 回复(4)

啥

B是错的，因为二叉搜索树的中序遍率历结果是顺序的，只要把其前序或者后序排个序就可以得到。

所以可以得到二叉树结构

编辑于 2015-12-30 13:37:05 回复(8)

Monk

答案：C

A：除了可以使用左子树的最大节点替换之外，还可以使用右子树最小节点替换

B：只有前中，后中的组合才能确定一个二叉树

C：中序遍历一个二叉搜索树的结果就是从小到大的排序结果，前中后序遍历每个节点都只访问一遍，时间复杂度为O（N）

D：每个节点旋转的时间复杂度为O（logN），总共N个节点，总时间复杂度为O（NlogN）

发表于 2015-07-25 14:58:26 回复(2)

上官封痕

A选项：如果对这棵搜索二叉树做中序遍历，待删除结点的前驱是它左子树最右边的结点，它的后继是它右子树最左边的结点

发表于 2016-08-19 15:31:38 回复(0)

philian

来讲讲B吧
无法保证用先序和后序唯一确定一棵二叉树，是因为无法保证区分左右孩子。比如根节点缺失左子树或右子树这样两种不同的拓扑结构，其先序和后序遍历很可能是完全一样的。
但某些情况下，比如，如果二叉树是真二叉树，那么树中各节点有0个或2个孩子，这时就可以确定左右孩子次序，这时先序和后序可以唯一确定一棵二叉树。

发表于 2016-12-18 09:20:55 回复(1)