java - 这个中序遍历算法是如何工作的？

Question

我在递归方面没有太多经验，所以我很难确定这个算法是如何工作的:

 public static void inorder(Node<?> n)
 {
  if (n != null)
  {
   inorder(n.getLeft());
   System.out.print(n.data + " ");
   inorder(n.getRight());
  }
 }

我知道它会访问树中每个节点的左右子节点，但我就是想不通为什么它能正常工作。

Answer 1

我会尝试一下。

想象一棵树

           a
      b          c
   d    e     f     g

每个字母代表一个节点对象。

当您传入“a”节点时会发生什么，它将查看第一个左节点并找到“b”。然后它将在 'b' 上调用相同的方法并等待它返回

在“b”中，它将查找第一个左节点并找到“d”。然后它将在 'd' 上调用相同的方法并等待直到它返回

在“d”中，它将查找第一个左节点并运行相同的方法。由于左节点为空，函数将返回。然后它将打印出'd' 在打印出'd'之后，它将调用右侧节点上的函数'd'也是null并立即返回。然后该方法的实例将返回到“b”节点函数。

它现在将打印出“b”，然后调用“b”右侧节点上的方法。

它将找到节点 'e' 然后它将调用 e 的左侧节点上的方法，该节点将为 null 并返回。然后打印出'e'。然后调用 'e' 的右节点上的方法，该节点也是 null 并返回到 'e' 方法调用。然后它将返回到“b”节点。

从'b'开始，它会返回到'a'，打印出'a'并在'a'的右侧开始相同的过程。

最终会打印出来:

d b e a f c g