JAVA中以先根次序非递归遍历二叉树的程序

以下是JAVA中以先根次序非递归遍历二叉树的程序：

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

该程序使用栈实现先根次序非递归遍历二叉树。具体来说，程序首先将根节点入栈，然后循环执行以下操作：弹出栈顶节点并输出其值，将其右儿子（如果有）入栈，将其左儿子（如果有）入栈。由于先入栈左儿子，再入栈右儿子，所以在下次循环时会先访问左子树。这样，就可以实现以先根次序遍历二叉树的效果。

相关问题

JAVA中以先根次序非递归遍历二叉树

可以使用栈来实现二叉树的先根次序非递归遍历，具体的实现方法是：先将根节点入栈，然后开始循环，如果栈不为空，则弹出栈顶元素，访问该节点，并依次将其右子节点和左子节点入栈。重复执行这个循环，直到栈为空。这样就完成了二叉树的先根次序非递归遍历。

Java代码实现二叉树后根次序遍历的非递归算法

好的，以下是Java代码实现二叉树后根次序遍历的非递归算法：

import java.util.Stack;

class Node {
    int val;
    Node left, right;

    public Node(int val) {
        this.val = val;
        left = right = null;
    }
}

public class BinaryTree {
    Node root;

    public void postOrderTraversal() {
        if (root == null) {
            return;
        }

        Stack<Node> stack = new Stack<>();
        Node node = root;
        Node lastVisited = null;

        while (!stack.isEmpty() || node != null) {
            if (node != null) {
                stack.push(node);
                node = node.left;
            } else {
                Node peekNode = stack.peek();
                if (peekNode.right != null && lastVisited != peekNode.right) {
                    node = peekNode.right;
                } else {
                    lastVisited = stack.pop();
                    System.out.print(lastVisited.val + " ");
                }
            }
        }
    }

    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);

        System.out.println("Postorder traversal of binary tree is :");
        tree.postOrderTraversal();
    }
}

这里使用了一个栈 `stack` 和一个指针 `node`，首先将根节点赋值给 `node`，然后进入循环，当 `stack` 不为空或者 `node` 不为 null 时循环继续。对于每个节点，首先将其左子节点入栈，然后将指针 `node` 指向左子节点，直到最左边的子节点。当一个节点的左子节点为空时，从栈中弹出该节点并打印，然后将指针 `node` 指向该节点的右子节点。如果该节点的右子节点为空或者已经被访问过（即 `lastVisited == peekNode.right`），则说明该节点的右子树已经被遍历过了，可以将该节点弹出并打印。

上述代码的输出结果为：

Postorder traversal of binary tree is :
4 5 2 6 7 3 1