前言

本文主要将前序遍历、中序遍历、后序遍历的非递归方法。

递归方法和层序遍历请看

递归前序遍历、递归中序遍历、递归后序遍历、层序遍历和判断一棵树是否为完全二叉树

非递归前序遍历二叉树

第一种方法：

利用栈实现

1.设置 node = root

2.循环执行以下操作

• 如果 node != null ，对 node 进行访问，将 node.right入栈，设置 node = node.left
• 如果 node == null，如果栈为空，结束遍历；如果栈不为空，弹出栈顶元素并赋值给 node

代码：

/*
    * 非递归前序遍历
    * */
    public void preorder1(Visitor<E> visitor){
        if (root == null || visitor == null) return;
        Node<E> node = root;
        Stack<Node<E>> stack = new Stack<>();
        while(true){
            if (node != null){
                //访问 node 节点
                if (visitor.visit(node.element)) return;
                //将右子节点入栈
                if (node.right != null){
                    stack.push(node.right);
                }
                //向左走
                node = node.left;
            }else if (stack.isEmpty()){
                return;
            }else {
            	//处理右边
                node = stack.pop();
            }
        }
    }

	public static interface Visitor<E>{
        boolean visit(E element);
    }

第二种方法：

利用栈实现

1.将 root 入栈

2.循环执行以下操作，直到栈为空

• 弹出栈顶节点top，进行访问
• 将top.right入栈
• 将top.left入栈

代码：

	public void preorder2(Visitor<E> visitor){
        if (root == null || visitor == null) return;
        Stack<Node<E>> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            Node<E> node = stack.pop();
            //访问node节点
            if (visitor.visit(node.element)) return;

            if (node.right != null){
                stack.push(node.right);
            }

            if (node.left != null){
                stack.push(node.left);
            }
        }
    }
    public static interface Visitor<E>{
        boolean visit(E element);
    }

非递归中序遍历二叉树

利用栈实现

1.设置 node = root

2.循环执行以下操作

• 如果 node != null ，将node入栈，设置 node = node.left
• 如果 node == null，如果栈为空，结束遍历；如果栈不为空，弹出栈顶元素并赋值给node，对 node 进行访问，设置 node = node.right

代码：

	/*
     * 非递归 中序遍历
     * */
    public void inorder(Visitor<E> visitor){
        if (root == null || visitor == null) return;
        
        Node<E> node = root;
        Stack<Node<E>> stack = new Stack<>();
        
        while(true){
            if (node != null){
                stack.push(node);
                //向左走
                node = node.left;
            }else if (stack.isEmpty()){
                return;
            }else {
                node = stack.pop();
                //访问 node 节点
                if (visitor.visit(node.element)) return;
                //让右节点进行中序遍历
                node = node.right;
            }
        }
    }
    public static interface Visitor<E>{
        boolean visit(E element);
    }

非递归后序遍历二叉树

利用栈实现

1.将 root 入栈

2.循环执行以下操作，直至栈为空

• 如果栈顶节点是叶子节点 或者 上一次访问的节点是栈顶节点的子节点，弹出栈顶节点，进行访问
• 否则，将栈顶节点的 right 、left 按顺序入栈

代码：

	/*
    * 非递归 后序遍历
    * */
    public void postorder(Visitor<E> visitor){
        if (root == null || visitor == null) return;
        //记录上一次弹出访问的节点
        Node<E> prev = null;
        Stack<Node<E>> stack = new Stack<>();
        stack.push(root);

        while(!stack.isEmpty()){
            Node<E> top = stack.peek();
            if (top.isLeaf() || (prev != null && prev.parent == top)){
                prev = stack.pop();
                //访问节点
                if (visitor.visit(prev.element)) return;
            }else {
                if (top.right != null){
                    stack.push(top.right);
                }
                if (top.left != null){
                    stack.push(top.left);
                }
            }
        }
    }

	public static interface Visitor<E>{
        boolean visit(E element);
    }

    protected static class Node<E>{
        E element;
        Node<E> left;
        Node<E> right;
        Node<E> parent;
        public Node(E element, Node<E> parent){
            this.element = element;
            this.parent = parent;
        }
        public boolean isLeaf(){
            return left == null && right == null;
        }
        public boolean hasTwoChildren(){
            return left != null && right != null;
        }
    }

总结代码

	import java.util.Stack;

	public class Front {
	//非递归前序遍历
	public void front(TreeNode node) {
		Stack<TreeNode> stack = new Stack<>();
		stack.push(node);
		while(!stack.isEmpty()) {
			TreeNode newnode = stack.pop();
			System.out.println(newnode.data);
			if(newnode.right != null) {
				stack.push(newnode.right);
			}
			if(newnode.left != null) {
				stack.push(newnode.left);
			}
		}
	}
	//非递归中序遍历
	public void mid(TreeNode node) {
		Stack<TreeNode> stack = new Stack<>();
		while(!stack.isEmpty() || node != null) {
			if(node != null) {
				stack.push(node);
				node = node.left;
			}else {
				TreeNode newnode = stack.pop();
				System.out.println(newnode.data);
				node = node.right;
			}
		}
	} 
	//非递归后序遍历
	public void bih(TreeNode node) {
		Stack<TreeNode> stack1 = new Stack<>();
		Stack<TreeNode> stack2 = new Stack<>();
		stack1.push(node);
		while(!stack1.isEmpty()) {
			TreeNode newnode = stack1.pop();
			stack2.push(newnode);
			if(newnode.left != null) {
				stack1.push(newnode.left);
			}
			if(newnode.right != null) {
				stack1.push(newnode.right);
			}
		}
		while(!stack2.isEmpty()) {
			System.out.println(stack2.pop().data);
		}
	}
}