java栈实现二叉树的非递归遍历的示例代码

让我们来详细讲解一下“Java栈实现二叉树的非递归遍历的示例代码”的完整攻略。

什么是非递归遍历？

在讲解“Java栈实现二叉树的非递归遍历的示例代码”之前，我们先来了解一下什么是非递归遍历。

二叉树的遍历有三种方式：

• 前序遍历：根节点 → 左子树 → 右子树。
• 中序遍历：左子树 → 根节点 → 右子树。
• 后序遍历：左子树 → 右子树 → 根节点。

在使用递归方式进行二叉树遍历时，会使用函数调用栈进行操作。而非递归方式则需要使用辅助数据结构，这里我们可以使用栈来帮助实现非递归遍历。

实现非递归遍历

前序遍历

对于前序遍历，我们可以使用栈来辅助实现。

首先将根节点压入栈中，然后重复下列步骤：

• 弹出栈顶元素，记录该节点的值。
• 如果该节点有右孩子，则将右孩子压入栈中。
• 如果该节点有左孩子，则将左孩子压入栈中。

代码示例：

public void preorderTraversal(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    if (root != null) {
        stack.push(root);
    }
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        System.out.print(node.val + " ");
        if (node.right != null) {
            stack.push(node.right);
        }
        if (node.left != null) {
            stack.push(node.left);
        }
    }
}

中序遍历

对于中序遍历，我们可以通过先将左子树全部压入栈中，再弹出栈顶节点进行操作。

首先将根节点压入栈中，然后重复下列步骤：

• 将该节点的所有左孩子依次压入栈中。
• 弹出栈顶元素，记录该节点的值。
• 如果该节点有右孩子，则将右孩子压入栈中。

代码示例：

public void inorderTraversal(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode curr = root;
    while (curr != null || !stack.isEmpty()) {
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }
        curr = stack.pop();
        System.out.print(curr.val + " ");
        curr = curr.right;
    }
}

后序遍历

对于后序遍历，我们需要记录节点是否已经被访问过。如果当前节点的左右子树都已经被访问过，则可以将当前节点出栈，否则，先将右子树压入栈中，再将左子树压入栈中。

首先将根节点压入栈中，然后重复下列步骤：

• 如果该节点的左右子树都已经被访问过，则弹出栈顶元素并记录该节点的值。
• 否则，依次检查右孩子和左孩子是否存在，如果存在则将它们压入栈中，否则记录该节点已经被访问过。

代码示例：

public void postorderTraversal(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode curr = root;       
    while (curr != null || !stack.isEmpty()) {
        while (curr != null) {
            stack.push(curr);
            curr = curr.left;
        }
        TreeNode topNode = stack.peek();
        if (topNode.right != null && topNode.right != curr) {
            curr = topNode.right;
        } else {
            System.out.print(topNode.val + " ");
            stack.pop();
            curr = null;
        }
    }
}

示例说明

针对于以上三种遍历方式的示例代码，我们可以使用以下二叉树进行测试：

        1
       / \
      2   3
     / \   \
    4   5   6

先序遍历结果为：1 2 4 5 3 6。

中序遍历结果为：4 2 5 1 3 6。

后序遍历结果为：4 5 2 6 3 1。

以上就是完整的“Java栈实现二叉树的非递归遍历”的详细攻略了。希望能对你有所帮助。