algorithm - 在二叉搜索树中查找有效序列

Question

假设1到1000之间的整数排列在一棵二叉搜索树中，希望找到363这个数，下面的一些序列，哪个不能是遍历的节点序列？

a) 2, 252, 401, 398, 330, 344, 397, 363 ;

b) 924, 220, 911, 244, 898, 258, 362, 363 ;

c) 925, 202, 911, 240, 912, 245, 363;

d) 2, 399, 387, 219, 266, 382,​​ 381, 278, 363 ;

e) 935、278、347、621、299、392、358、363。

有必要制作图案吗？写一个最小形式的属性来检查。谢谢。

Answer 1

转到这里:https://www.cs.usfca.edu/~galles/visualization/BST.html在“插入”旁边的左上角一次输入每个数字，然后单击“插入”。当您输入数字时，它将构建一个二叉树。

对每个序列执行此操作并比较它们的外观。

这是通过“a)”的路线:

这是一个单链。这是通过“c)”的尝试路线:

这不是从上到下的单一路径，它有一个错误的分支。如果 363 在树上，您就不会拐错弯，而您只是直接前往它。

在 c) 中，911 在 240 上向左拆分，在 912 上向右拆分。

在 e) 中，347 在 621 上向右拆分，在 299 上向左拆分。

它们不可能是去往 363 的路上遍历的序列，因为每个列表中的一个节点不在去往 363 的路上。

[截图来自https://www.cs.usfca.edu/~galles/visualization/BST.html ]