樹的非遞歸代碼（Java實現(xiàn)）

建樹：

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

public class TreeBuilder {
    /**
     * 從文件讀取數(shù)據(jù)按層次遍歷的方式創(chuàng)建一個二叉樹 (測試用)
     * 文件輸入只能是'#'或數(shù)字，'#'表示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;
    }
}

樹節(jié)點定義：

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> {

    /**
     * 層次遍歷，用隊列實現(xiàn)
     *
     * @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);
    }
}