二叉树

20180119144120781.png

public class Main {

private static class TreeNode {

    private int value;
    private TreeNode left;
    private TreeNode right;

    public TreeNode(int value) {
        this.value = value;
    }

}

public static void main(String[] args) {

    TreeNode a = new TreeNode(1);
    TreeNode b = new TreeNode(2);
    TreeNode c = new TreeNode(3);
    TreeNode d = new TreeNode(4);
    TreeNode e = new TreeNode(5);
    TreeNode f = new TreeNode(6);
    TreeNode g = new TreeNode(7);

    a.left = b;
    a.right = c;
    b.right = d;
    c.left = e;
    c.right = f;
    f.left = g;

    postSort(a);
    recutionPostSort(a);
}

private static void visit(TreeNode node) {
    System.out.println(node.value);
}

//先序递归（中左右）
private static void preSort(TreeNode node) {
    if (node == null) {
        return;
    }
    visit(node);
    preSort(node.left);
    preSort(node.right);
}


//中序非递归（左中右）
private static void inSort(TreeNode node) {
    if (node == null) {
        return;
    }
    inSort(node.left);
    visit(node);
    inSort(node.right);
}

//后序（左右中）
private static void postSort(TreeNode node) {
    if (node == null) {
        return;
    }
    postSort(node.left);
    postSort(node.right);
    visit(node);
}

//先序非递归
private static void recutionPreSort(TreeNode node) {

    Stack stack = new Stack();

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

        while (node != null) {
            visit(node);
            stack.push(node);
            node = node.left;
        }

        if (!stack.isEmpty()) {
            node = (TreeNode) stack.pop();
            node = node.right;
        }

    }

}

//先序非递归
private static void recutionInPreSort(TreeNode node) {

    Stack stack = new Stack();

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

        while (node != null) {
            stack.push(node);
            node = node.left;
        }

        if (!stack.isEmpty()) {
            node = (TreeNode) stack.pop();
            visit(node);
            node = node.right;
        }

    }
}

//后序非递归
private static void recutionPostSort(TreeNode root) {

    Stack<TreeNode> stack = new Stack<>();

    while (true) {

        if (root != null) {
            stack.push(root);
            root = root.left;
        } else {

            if (stack.isEmpty()) {
                return;
            }

            if (null == stack.peek().right) {
                root = stack.pop();
                visit(root);
                while (root == stack.peek().right) {
                    root = stack.pop();
                    visit(root);
                    if (stack.isEmpty()) {
                        break;
                    }
                }
            }

            if (!stack.isEmpty()) {
                root = stack.peek().right;
            } else {
                root = null;
            }
        }

    }
}

}