java - 似乎无法理解二叉搜索树中的递归

Question

称呼社区

这更像是一个概念性问题，所以请多多包涵。

由于二叉树的遍历中递归的多个实例和操作顺序，我对以下算法感到困惑。我在用着以Preorder算法为例。

这是代码。

1    public static void Preorder(Node node){
2    if (node == null)
3        return;
4    System.out.print(node.element + " ");
5    Preorder(node.left);
6    Preorder(node.right);
7 }

令我困惑的是，递归调用的命令链。在第一次“迭代”的算法中，首先是同时激活的两种 Preorder 方法。就像第 5 行和第 6 行的方法同时发生一样，没有“等待”另一个完成的方法。

或者更像是 #6 Prerder() 一直被调用，直到满足基本情况。然后 #7 被调用直到它的底部被击中？此外，如果这是真的，那么子树左侧的所有右侧节点是如何到达的，反之亦然？

假设你有这个，树(N = 任意数字)

    N
   /  \ 
  N    N
 / \    \
 N  N    N
    \
     N
    /  \
   N    N
      /
     N

如果算法不断重复 node.left 参数，算法究竟如何“到达”右子树上最右边的这些节点？好像你只会得到最左边的节点，没有别的。

我仍然在思考 nodes.left 和 nodes.right 的整个概念，以及递归和其他算法如何有效地使用它们。似乎是一个神秘的过程，但至少可以说是迷人的。

Answer 1

一张图片胜过一千个单词:这发生在预先排序时对每个步骤进行编号:

    1
   /  \ 
  2    9
 / \    \
3   4    10
    \
     5
    /  \
   6    7
      /
     8