首页 > 试题广场 >

给定数组 [ 20,9,45,28,73,92,38 ] ，

[填空题]

给定数组 [ 20,9,45,28,73,92,38 ] ，构造一棵左子节点 < 父节点 < 右子节点的二叉搜索树（Binary Search Tree）。把数字45删除，使用前序节点调整后，查询数字38需要1次。

查看答案及解析

weiyinfu

最后一次不比较了吗？

发表于 2018-08-16 17:56:45 回复(2)

夜破晓

二叉搜索树（二叉排序树/二叉查找树）：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉搜索树。

按照数组顺序逐个插入，数的形态是固定的。

被删除的结点左右子树都不为空时，用前驱结点（前序节点调整）或者后继结点（后序节点调整）代替被删除的结点位置，然后根据性质进行调整。

前驱结点：左子树最大值（小于被删除结点的所有结点中的最大值）

后继结点：右子树最小值（大于被删除结点的所有结点中的最小值）

编辑于 2019-04-01 17:15:14 回复(0)

三西后僧

为啥不是2次呢？20和38

发表于 2019-10-03 11:25:41 回复(1)

tritium_studio

这里没有要求平衡树，因此二叉搜索树就是顺序插入数组元素，每个元素都从根节点开始，比当前节点小就进入其左子树，比当前节点大就进入其右子树，直到找到空位。

前序节点就是比它小的最大节点，直接连上去就行。搜索树性质保证了不会出现多叉

本题中，搜索路径从20-45-28变为20-38-28，查询次数为边的个数，因此是2。而比较次数是节点个数，应该是3。

编辑于 2023-09-06 14:02:42 回复(0)

什么时候把绿色换掉

纠结于查询需要几次，请问这个题中查询数字28的话答案是3么？

发表于 2019-08-19 01:23:38 回复(0)

戴假发的猫

前序节点调整是什么意思呢

发表于 2018-10-15 15:26:43 回复(0)

坏坏62

我想请问一下，直接给定一个数组也不说是什么顺序遍历的序列如何能够确定这棵二叉搜索树的具体形态啊？求大神解我疑惑

发表于 2018-09-04 14:33:10 回复(1)

提交观点

问题信息

C++工程师 iOS工程师商汤科技安卓工程师运维工程师前端工程师算法工程师测试工程师技术支持数据挖掘工程师 2018 产品运营大数据开发工程师 Java工程师

上传者：小小

难度：

7条回答 78收藏 3369浏览