data-structures - 为什么下一个/上一个有序遍历节点总是外部节点？

Question

在二叉搜索树中，如果取任何内部（非叶）节点，为什么该节点的下一个（或上一个）有序遍历节点总是外部（叶）节点？

Answer 1

这不一定是真的。试试这棵树：

1
 \
  2
   \
    3
     \
      4

这里，2的中序后继是3，是一个内部节点，它的中序前导是1，也是一个内部节点。

希望这可以帮助！