树非递归遍历

树的非递归代码（Java实现）

建树：

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;

public class TreeBuilder {
    /**
     * 从文件读取数据按层次遍历的方式创建一个二叉树 (测试用)
     * 文件输入只能是'#'或数字，'#'表示null
     * 测试用例1： 1 2 3 4 5 # # 6 # 7 9
     * 测试用例2： 1 2 3 4 5
     *
     * @return
     */
    public TreeNode<Integer> createTree(Scanner in) {
        String val = in.next();
        if (val.equals("#")) {
            return null;
        }
        TreeNode<Integer> node = new TreeNode<>(Integer.valueOf(val));
        TreeNode<Integer> root = node;
        Queue<TreeNode<Integer>> queue = new ArrayDeque<>();
        queue.add(node);
        while (!queue.isEmpty()) {
            int len = queue.size();
            for (int i = 0; i < len; i++) {
                node = queue.remove();
                if (!in.hasNext()) {
                    break;
                }
                val = in.next();
                if (val.equals("#")) {
                    node.left = null;
                } else {
                    node.left = new TreeNode<>(Integer.valueOf(val));
                    queue.add(node.left);
                }
                if (!in.hasNext()) {
                    break;
                }
                val = in.next();
                if (val.equals("#")) {
                    node.right = null;
                } else {
                    node.right = new TreeNode<>(Integer.valueOf(val));
                    queue.add(node.right);
                }
            }
        }
        return root;
    }
}

树节点定义：

public class TreeNode<T> {
    TreeNode(T val) {
        this.val = val;
    }
    T val;
    TreeNode<T> left;
    TreeNode<T> right;
}

层次遍历、前中后遍历的代码：

import java.util.*;

public class TreeIter<T> {

    /**
     * 层次遍历，用队列实现
     *
     * @param root
     * @return
     */
    public List<T> levelOrder(TreeNode<T> root) {
        List<T> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Queue<TreeNode<T>> queue = new ArrayDeque<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode<T> node = queue.remove();
                res.add(node.val);
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
        }
        return res;
    }

    /**
     * 前序遍历非递归
     *
     * @param root
     * @return
     */
    public List<T> preOrder(TreeNode<T> root) {
        List<T> res = new ArrayList<>();
        if (root == null) {
            return res;
        }

        TreeNode<T> curNode = root;
        Stack<TreeNode<T>> stack = new Stack<>();
        while (curNode != null || !stack.isEmpty()) {
            while (curNode != null) {
                stack.add(curNode);
                res.add(curNode.val);
                curNode = curNode.left;
            }
            curNode = stack.pop();
            curNode = curNode.right;
        }
        return res;
    }

    /**
     * 中序遍历非递归
     *
     * @param root
     * @return
     */
    public List<T> midOrder(TreeNode<T> root) {
        List<T> res = new ArrayList<>();
        if (root == null) {
            return res;
        }

        Stack<TreeNode<T>> stack = new Stack<>();
        TreeNode<T> curNode = root;
        while (curNode != null || !stack.isEmpty()) {
            while (curNode != null) {
                stack.push(curNode);
                curNode = curNode.left;
            }
            curNode = stack.pop();
            res.add(curNode.val);
            curNode = curNode.right;
        }
        return res;
    }

    /**
     * 后序遍历非递归(双栈法，好理解)
     *
     * @param root
     * @return
     */
    public List<T> postOrder(TreeNode<T> root) {
        List<T> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Stack<TreeNode<T>> stackRes = new Stack<>();
        Stack<TreeNode<T>> stackTmp = new Stack<>();
        stackTmp.push(root);
        TreeNode<T> curNode;

        while (!stackTmp.isEmpty()) {
            curNode = stackTmp.pop();
            stackRes.push(curNode);
            if (curNode.left != null) {
                stackTmp.add(curNode.left);
            }
            if (curNode.right != null) {
                stackTmp.add(curNode.right);
            }
        }

        while (!stackRes.isEmpty()) {
            res.add(stackRes.pop().val);
        }
        return res;
    }

    /**
     * 后序遍历非递归
     * <p>
     * 参考链接，注释非常详细
     * http://www.cnblogs.com/ybwang/archive/2011/10/04/lastOrderTraverse.html
     *
     * @param root
     * @return
     */
    public List<T> postOrder2(TreeNode<T> root) {
        List<T> res = new ArrayList<>();
        if (root == null) {
            return res;
        }

        Stack<TreeNode<T>> stack = new Stack<>();
        stack.push(root);
        TreeNode<T> curNode = null;
        TreeNode<T> preNode = null;
        while (!stack.isEmpty()) {
            curNode = stack.peek();
            if (preNode == null || preNode.left == curNode || preNode.right == curNode) {
                if (curNode.left != null) {
                    stack.push(curNode.left);
                } else if (curNode.right != null) {
                    stack.push(curNode.right);
                } else {
                    res.add(stack.pop().val);
                }
            } else if (curNode.left == preNode) {
                if (curNode.right != null) {
                    stack.push(curNode.right);
                } else {
                    res.add(stack.pop().val);
                }
            } else if (curNode.right == preNode) {
                res.add(stack.pop().val);
            }
            preNode = curNode;
        }
        return res;
    }
}

测试用例：
input.txt

1 2 3 4 5 # # 6 # 7 9

测试代码：

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws FileNotFoundException {
        TreeIter<Integer> treeIter = new TreeIter<>();
        Scanner in = new Scanner(new FileInputStream("input.txt"));
        TreeNode<Integer> root = new TreeBuilder().createTree(in);

        List<Integer> preOrder = treeIter.preOrder(root);
        System.out.println(preOrder);

        List<Integer> midOrder = treeIter.midOrder(root);
        System.out.println(midOrder);

        List<Integer> postOrder = treeIter.postOrder(root);
        System.out.println(postOrder);

        List<Integer> postOrder2 = treeIter.postOrder2(root);
        System.out.println(postOrder2);

        List<Integer> levelOrder = treeIter.levelOrder(root);
        System.out.println(levelOrder);
    }
}