binary-search-tree - 反向二叉搜索树中的中序后继

Question

如果翻转 BST，我对有序的继任者/前任者有一点困惑。当 BST 被翻转/反转时，我的意思是当右子树中的所有元素都更小而左子树中的所有元素都更大时。通常右子树具有更大的价值。如果反过来呢，顺序后继者/前继者的定义是否仍然保持不变？

对于普通树，中序后继者将是右子树的最左边的孩子，不是吗？

对于翻转的 BST，如下例所示：

    8
    /\
   15 4
  /\  /\
20 10 6 2

8的顺序后继是10吗？或者如果我们遵循中序继任者的“通常”定义，它是 6 吗？

谢谢！

Answer 1

如果您对反向 BST 进行中序遍历，您将获得按降序排序的数字。因此，在这种情况下，您的值的顺序将是：20、15、10、8、6、4、2。因此 8 的后继将是 6。