这个inorder遍历算法如何工作？ [英] How does this inorder traversal algorithm work?

问题描述

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

I don't have much experience with recursion, so I'm having a hard time determining exactly how this algorithm works:

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

我知道它访问左右子节点在树中的每个节点，但我无法理解为什么确切地说它的工作原理。

I know that it visits the left and right child nodes of every node in the tree, but I just can't get my head around why exactly it works.

推荐答案

我会试着试一试。

想象一棵树

           a
      b          c
   d    e     f     g

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

Each letter represents a Node object.

传入a节点时会发生的情况是，它将查看第一个左侧节点并找到b。然后它将在'b'上调用相同的方法并等待直到返回

What happens when you pass in the 'a' node is that it will look at the first left node and find 'b'. It will then call the same method on 'b' and wait until that returns

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

In 'b' it will look for the first left node and find 'd'. It will then call the same method on 'd' and wait until that returns

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

In 'd' it will look for the first left node and run the same method. Since the left node is null the function will return. It will then print out 'd' After it prints out 'd' it will call the function on the right node to 'd' which is also null and immediately return. Then that instance of the method will return back to the 'b' node function.

现在打印出'b'然后调用右边节点上的方法'b'。

It will now print out 'b' then call the method on the right hand node of 'b'.

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

It will find node 'e' Then it will call the method on the left node of e which will be null and return. Then print out 'e'. then call the method on the right node of 'e' which is also null and return back to the 'e' method call. Then it will return out to the 'b' node.

从'b'它将返回到'a'，打印出'a'并开始相同在'a'的右侧进行处理。

From 'b' it will return back up to 'a', print out 'a' and start the same process on the right side of 'a'.

最终会打印出来：

dbeafcg

这篇关于这个inorder遍历算法如何工作？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！