首页 > 试题广场 >

以下哪个输出序列不可能是二叉查找树（Binary Searc

[单选题]

以下哪个输出序列不可能是二叉查找树（Binary Search Tree）后序遍历的输出。

查看答案及解析

Suu_翠時期

对于二叉查找树的后序遍历序列，最后一位是它的根结点，那从左往右数，第一个比这个根结点大的结点就属于根结点的右子树（二叉排序树的一个结点的右子树上的结点都大于它自己，而左子树则都小于它自己）因此在这个结点后面不会存在比根结点小的数字

编辑于 2019-08-03 20:19:58 回复(6)

abserver

假设输入的数组是二叉查找树的后序遍历，分步骤分析思路：

1 对于一个数组输入：{e1, e2, e3, e4, e5}，最后一个结点e5是父节点，其余元素分成两派：左子树，右子树(分派依据是比根结点大/小)

2 对左右子树重复使用1的规则。

可以看到，这是递归的算法。

以选项C为例：

输入：{1, 3, 2, 4, 5}，最后一个结点5是父结点，发现有左子树，没有右子树，规模调整为{1, 3, 2}

输入：{1, 3, 2}，最后一个结点2是父节点，有左子树，右子树，且没有孙结点，问题规模调整为{1}，{3}

由以上两次输入分析可以画出这颗二叉搜索树：

/ \

1 3

以选项D为例：

输入：{1, 2, 5, 3, 4}，最后一个结点4是父结点，发现剩下元素不能成为左右子树两派，故该输入不是二叉查找树的后序遍历。

发表于 2019-07-11 14:34:19 回复(2)

小小苏苏

二叉查找树,左儿子小于根,右儿子大于根

发表于 2019-06-20 15:37:17 回复(0)

提交观点

问题信息

C++工程师 iOS工程师安卓工程师运维工程师前端工程师算法工程师测试工程师 PHP工程师 2019 流利说 Java工程师

上传者：小小

难度：

3条回答 147收藏 8357浏览

扫一扫，把题目装进口袋