package mystudy;

import java.io.UnsupportedEncodingException;

import java.util.LinkedList;

import java.util.Queue;

import java.util.Stack;

public class Tree {

    private TreeNode root;

    public Tree() {

    };

    public Tree(TreeNode root) {

        this.root = root;

    }

    public void initTree() {

        root = new TreeNode(8);

        root.setLeft(new TreeNode(5));

        root.getLeft().setLeft(new TreeNode(7));

        root.getLeft().setRight(new TreeNode(4));

        root.setRight(new TreeNode(9));

        root.getRight().setRight(new TreeNode(6));

        root.getRight().setLeft(new TreeNode(10));

    }

    public void preOrderTraverse() {

        preOrderTraverse(root);

    }

    public void preOrderTraverse(TreeNode node) {

        if (node != null) {

            System.out.println(node.getValue());

            preOrderTraverse(node.getLeft());

            preOrderTraverse(node.getRight());

        }

    }

    public void nPreOrderTraverse() {

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

        TreeNode node = root;

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

            while (node != null) {

                System.out.println(node.getValue());

                stack.push(node);

                node = node.getLeft();

            }

            if (!stack.isEmpty()) {

                node = stack.pop();

                node = node.getRight();

            }

        }

    }

    public void inOrderTraverse() {

        inOrderTraverse(root);

    }

    public void inOrderTraverse(TreeNode node) {

        if (node != null) {

            inOrderTraverse(node.getLeft());

            System.out.println(node.getValue());

            inOrderTraverse(node.getRight());

        }

    }

    public void nInOrderTraverse() {

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

        TreeNode node = root;

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

            while (node != null) {

                stack.push(node);

                node = node.getLeft();

            }

            if (!stack.isEmpty()) {

                node = stack.pop();

                System.out.println(node.getValue());

                node = node.getRight();

            }

        }

    }

    public void postOrderTraverse() {

        postOrderTraverse(root);

    }

    public void postOrderTraverse(TreeNode node) {

        if (node != null) {

            postOrderTraverse(node.getLeft());

            postOrderTraverse(node.getRight());

            System.out.println(node.getValue());

        }

    }

    public void nPostOrderTraverse() {

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

        TreeNode node = root;

        TreeNode preNode = null;

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

            while (node != null) {

                stack.push(node);

                node = node.getLeft();

            }

            if (!stack.isEmpty()) {

                node = stack.peek();

                if (node.getRight() == null || node.getRight() == preNode) {

                    node = stack.pop();

                    System.out.println(node.getValue());

                    preNode = node;

                    node = null;

                } else {

                    node = node.getRight();

                }

            }

        }

    }

    public void levelTraverse() {

        levelTraverse(root);

    }

    public void levelTraverse(TreeNode node) {

        if (node != null) {

            Queue<TreeNode> queue = new LinkedList<TreeNode>();

            queue.offer(node);

            while (!queue.isEmpty()) {

                TreeNode mNode = queue.poll();

                if (mNode != null) {

                    System.out.println(mNode.getValue());

                    if (mNode.getLeft() != null) {

                        queue.offer(mNode.getLeft());

                    }

                    if (mNode.getRight() != null) {

                        queue.offer(mNode.getRight());

                    }

                }

            }

        }

    }

    public int treeDepth() {

        return treeDepth(root);

    }

    public int treeDepth(TreeNode node) {

        if (node == null) {

            return 0;

        }

        int leftDepth = treeDepth(node.getLeft());

        int rightDepth = treeDepth(node.getRight());

        return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;

    }

    public int minMaxSpan() {

        Queue<TreeNode> queue = new LinkedList<TreeNode>();

        if (root != null) {

            int visitedNum = 0, addedNum = 1, levelNum = 1, min, max, depth = 0, minLevel = 0, maxLevel = 0;

            min = max = root.getValue();

            queue.offer(root);

            while (!queue.isEmpty()) {

                TreeNode mNode = queue.poll();

                if (min > mNode.getValue()) {

                    min = mNode.getValue();

                    minLevel = depth;

                } else if (max < mNode.getValue()) {

                    max = mNode.getValue();

                    maxLevel = depth;

                }

                visitedNum++;

                if (mNode.getLeft() != null) {

                    queue.offer(mNode.getLeft());

                    addedNum++;

                }

                if (mNode.getRight() != null) {

                    queue.offer(mNode.getRight());

                    addedNum++;

                }

                if (visitedNum == levelNum) {

                    depth++;

                    levelNum = addedNum;

                }

            }

            System.out.println("min:" + min + "max:" + max + "minLevel:"

                    + minLevel + "maxLevel:" + maxLevel + "树的高度：" + depth);

            return Math.abs(minLevel - maxLevel);

        }

        return -1;

    }

    public class TreeNode {

        private TreeNode left;

        private TreeNode right;

        private int value;

        public TreeNode(TreeNode left, TreeNode right, int value) {

            this.left = left;

            this.right = right;

            this.value = value;

        }

        public TreeNode(int value) {

            this(null, null, value);

        }

        public TreeNode getLeft() {

            return left;

        }

        public void setLeft(TreeNode left) {

            this.left = left;

        }

        public TreeNode getRight() {

            return right;

        }

        public void setRight(TreeNode right) {

            this.right = right;

        }

        public int getValue() {

            return value;

        }

        public void setValue(int value) {

            this.value = value;

        }

    }

    /**

     * @param args

     * @throws UnsupportedEncodingException

     */

    public static void main(String[] args) throws UnsupportedEncodingException {

        // TODO Auto-generated method stub

        Tree tree = new Tree();

        tree.initTree();

        System.out.println("树中最大值最小值层数之差：" + tree.minMaxSpan());

        System.out.println("前序递归：");

        tree.preOrderTraverse();

        System.out.println("前序非递归：");

        tree.nPreOrderTraverse();

        System.out.println("中序递归：");

        tree.inOrderTraverse();

        System.out.println("中序非递归：");

        tree.nInOrderTraverse();

        System.out.println("后序递归：");

        tree.postOrderTraverse();

        System.out.println("后序非递归：");

        tree.nPostOrderTraverse();

        System.out.println("按层次遍历：");

        tree.levelTraverse();

        System.out.println("树的高度：" + tree.treeDepth());

    }

}