binary-tree - 二叉搜索树路径

Question

在二叉搜索树中，如果您沿着某个搜索路径，哪些键被认为在路径的左侧，哪些在右侧？

例如，如果我的树是：

              25
      12             30
   10    15       28   32
       14  20

假设我当前的搜索路径是 20->12->15->20。

1) 10 和 14 是否都被认为在此搜索路径的左侧，还是只有 10？

2) 搜索路径右侧是否考虑了所有 3 个数字 30、28 和 32？

Answer 1

假设您的意思是 path 25-12-15-20，我会说两者10 并且 14都离开了这条路径。那是因为为了找到它们中的任何一个，您必须回溯树（到15或12）并在路径向右的地方选择左分支。

三个数字 和 的30处理28相同32。由于您必须回溯到25然后向右而不是向左走，因此可以考虑将它们放在该路径的右侧：