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

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

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

我知道它访问了树中每个节点的左右子节点，但我无法理解为什么它确实有效。

我会试着试一试。

想象一棵树

  a bc defg

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

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

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

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

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

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

从’b’开始，它将返回’a’，打印’a’并在’a’的右侧开始相同的过程。

最终会打印出来：

dbeafcg

在你习惯递归之前，一些小代码可以实现这么多，这似乎令人惊讶。在这种情况下，您应该尝试在实际树上手动完成算法，看看会发生什么。

在维基百科下面的树中，您可以看到打印出A，B，C，D，E，F，G，H，I的有序遍历。

（有关我的Tree Traversal教程的更多信息，请参阅。）

维基树

理解递归的最好方法是尝试口头陈述你的问题然后通过一个例子（你可以参考@Mark Carpenter的例子）：

顺序搜索的方式如下：

说我在节点n：

1）首先访问节点n左侧的所有节点。（即n.getLeft（））以顺序方式，实现此目的的最佳方法是递归调用inorder（）并将其传递给n的左子元素。

2）现在当函数到达此步骤时，它已经打印了Node n的所有左子节点。所以现在打印Node n。

3）现在访问节点x右边的所有节点。（即n.getRight（））以顺序方式，实现此目的的最佳方法是递归调用inorder（）并将其传递给n的右子。