0

我有一个关于二叉树的问题：

一棵二叉树 T1 有 n 个成员。当我们在 T1 上运行中序遍历时，我们会得到一个从 1 到 n (1,2,3,...n) 的序列。现在 T1 是 BST（二叉搜索树）吗？

我知道如果 T1 是 BST，则中序遍历将导致排序序列，但是相反的方向是否也可以工作？

4

2 回答 2

1

总之是..

二分搜索属性是左树上的每个节点都较小，而右边的每个节点都较大。

考虑到在您的情况下的任何子树上，因为我们正在按顺序遍历并且看到它们之前的每个元素都较小，并且在向右移动时我们正在上升，所以我们有 BST ...

于 2013-05-17T14:00:51.583 回答
1

这听起来太家庭作业，所以没有直接的答案。但：

假设根有 value k。

k现在试试这个：在顺序遍历中出现在左侧的节点是什么意思？在右侧？

此外，之前出现的数字k都小于k。这对这个问题有什么帮助？

于 2013-05-15T13:59:10.150 回答