二叉树遍历算法

[zhoupj]

public class BiBtreeTracer {

    public static String preNonRecursive(Node root) {

        String rst = "";

        if (root == null) {
            return rst;
        }

        Stack<Node> stack = new Stack<BiBtreeTracer.Node>();
        Node cur = root;

        while (cur != null || !stack.isEmpty()) {

            rst += cur.getData();//visit
            stack.push(cur);

            cur = cur.leftChild;

            while (cur == null && !stack.isEmpty()) {
                cur = stack.pop();
                cur = cur.rightChild;
            }
        }

        return rst;
    }

    public static String middleNonRecursive(Node root) {

        String rst = "";

        if (root == null) {
            return rst;
        }

        Stack<Node> stack = new Stack<BiBtreeTracer.Node>();
        Node cur = root;

        while (cur != null || !stack.isEmpty()) {

            if (cur.leftChild != null) {
                stack.push(cur);
                cur = cur.leftChild;
            } else {
                rst += cur.getData() + " ";
                cur = cur.rightChild;
                while (cur == null && !stack.isEmpty()) {
                    cur = stack.pop();
                    rst += cur.getData() + " ";
                    cur = cur.rightChild;
                }
            }

        }

        return rst;
    }

    public static String postNonRecursive(Node root) {

        String rst = "";

        if (root == null) {
            return rst;
        }

        Stack<Node> stack = new Stack<BiBtreeTracer.Node>();
        Node cur = root;
        Node pre = null;
        stack.push(cur);

        while (!stack.isEmpty()) {

            cur = stack.peek();

            if (cur.leftChild == null && cur.rightChild == null
                || pre != null && (cur.leftChild == pre || cur.rightChild == pre)) {
                rst += cur.getData();
                stack.pop();
                pre = cur;
            } else {
                if (cur.rightChild != null) {
                    stack.push(cur.rightChild);
                }
                if (cur.leftChild != null) {
                    stack.push(cur.leftChild);
                }
            }

        }

        return rst;
    }

    public static void recursive(Node root, List<String> rst) {

        if (root != null) {

            recursive(root.leftChild, rst);

            rst.add(root.getData());

            recursive(root.rightChild, rst);
        }

    }

    static class Node {

        private String data;
        private Node   leftChild;
        private Node   rightChild;

        public Node(String data) {
            this.data = data;
            this.leftChild = null;
            this.rightChild = null;
        }

        public void addChild(Node leftChild, Node rightChild) {
            this.leftChild = leftChild;
            this.rightChild = rightChild;
        }

        /**
         * Getter method for property <tt>data</tt>.
         *
         * @return property value of data
         */
        public String getData() {
            return data;
        }

        /**
         * Setter method for property <tt>data</tt>.
         *
         * @param data value to be assigned to property data
         */
        public void setData(String data) {
            this.data = data;
        }

        /**
         * Getter method for property <tt>leftChild</tt>.
         *
         * @return property value of leftChild
         */
        public Node getLeftChild() {
            return leftChild;
        }

        /**
         * Setter method for property <tt>leftChild</tt>.
         *
         * @param leftChild value to be assigned to property leftChild
         */
        public void setLeftChild(Node leftChild) {
            this.leftChild = leftChild;
        }

        /**
         * Getter method for property <tt>rightChild</tt>.
         *
         * @return property value of rightChild
         */
        public Node getRightChild() {
            return rightChild;
        }

        /**
         * Setter method for property <tt>rightChild</tt>.
         *
         * @param rightChild value to be assigned to property rightChild
         */
        public void setRightChild(Node rightChild) {
            this.rightChild = rightChild;
        }

    }

    public static void main(String[] args) {
        Node parent = new Node("A");
        Node b = new Node("B");
        Node c = new Node("C");
        Node d = new Node("d");
        Node e = new Node("e");
        Node f = new Node("f");
        parent.addChild(b, c);
        b.addChild(d, e);
        c.addChild(f, null);
        System.out.println(preNonRecursive(parent));
        System.out.println(middleNonRecursive(parent));
        System.out.println(postNonRecursive(parent));
        List<String> rst = new ArrayList<String>();
        recursive(parent, rst);
        System.out.println(rst);
    }