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

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

当你传入“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' 的右侧开始相同的过程。

最终会打印出来：

dbeafcg

Answer 2

在你习惯递归之前，一小段代码就可以完成这么多事情，这似乎很神奇。在这种情况下，您应该尝试在实际的树上手动检查算法，看看会发生什么。

在下面来自Wikipedia的树中，您可以看到打印出 A、B、C、D、E、F、G、H、I 的有序遍历。

1. 它从 F 开始并调用inorder最左边的节点。
2. 然后它调用inorderB，然后调用inorderA。
3. A被打印出来，然后算法继续它在 B 上的先前调用中的位置......

（请参阅我的树遍历教程。）

Answer 3

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

顺序搜索的工作方式如下：

假设我在节点 n ：

1）首先访问节点n左侧的所有节点。（即 n.getLeft()) 在inorder时尚中，实现这一点的最佳方法是递归调用 inorder() 并将其传递给 n 的左孩子。

2) 现在当函数到达这一步时，它已经打印了节点 n 的所有左子节点。所以现在打印节点 n。

3) 现在访问节点 x 右侧的所有节点。（即 n.getRight()） 在inorder时尚中，实现这一点的最佳方法是递归调用 inorder() 并将其传递给 n 的右孩子。

Answer 4

递归方法对于中序遍历非常简单，如下所示 -

中序遍历 (LNR) - 左节点右

1. 在inorder(L)中遍历root的左子树。
2. 访问根 (N)。
3. 在 inorder(R) 中遍历根的右子树。

中序遍历的递归函数 -

class Node
{
    int data;
    Node left, right;
    public Node(int item)
    {
        data = item;
        left = right = null;
    }

    boolean isLeaf() { return left == null ? right == null : false; }
}

public class BinaryTree {
    Node root;
    Stack<Node> nodeStack = new Stack<>();

    public BinaryTree() {
        root = null;
    }

    public static void main(String args[]) {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);
        tree.root.right.left = new Node(6);
        tree.root.right.right = new Node(7);
        tree.root.right.left.left = new Node(8);
        tree.root.right.left.right = new Node(9);
        tree.inorder_recursive(tree.root);
    }

    public void inorder_recursive(Node root) {
        if (root == null) {
            return;
        }
        inorder_recursive(root.left);
        System.out.printf("%s  ", root.data);
        inorder_recursive(root.right);
    }
}   

使用堆栈的非递归函数如下 -

public void inorder_nrec(Node current){
        System.out.println("In order traversal !!! ");
        if(current == null){
            System.out.println("Tree is empty");
            return;
        }
        while (!nodeStack.isEmpty() || current != null)
        {
            if (current != null)
            {
                nodeStack.push(current);
                current = current.left;
            } else
                {
                    Node node = nodeStack.pop();
                    System.out.printf("%s ", node.data);
                    current = node.right;
                }
        }
        System.out.println("\n");
    }

递归和非递归都是用非常简单的方法编写的，只需尝试逐行遍历代码以更好地理解。