这个inorder遍历算法如何工作？

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

每个字母代表一个Node对象.

传递'a'节点时会发生什么,它将查看第一个左节点并找到'b'.然后它将在'b'上调用相同的方法并等待直到返回

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

在'd'中,它将查找第一个左节点并运行相同的方法.由于左节点为null,因此函数将返回.然后打印出'd'打印出'd'后,它会将右边节点上的函数调用为'd',该函数也为空并立即返回.然后该方法的实例将返回到'b'节点函数.

现在它将打印出'b',然后在'b'的右侧节点上调用该方法.

它将找到节点'e'然后它将调用e的左边节点上的方法,该方法将为null并返回.然后打印出'e'.然后在'e'的右边节点上调用方法,该方法也为null并返回'e'方法调用.然后它将返回'b'节点.

从'b'开始,它将返回'a',打印'a'并在'a'的右侧开始相同的过程.

最终会打印出来:

dbeafcg