TreeMap.java

import java.util.Stack;
import java.util.Queue;
import java.util.LinkedList;

public class TreeMap {
    class BST<E extends Comparable<E>> {
        private class Node {
            public E e;
            public Node left, right;

            public Node(E e) {
                this.e = e;
                left = null;
                right = null;
            }
        }

        private Node root;
        private int size;

        public BST() {
            root = null;
            size = 0;
        }

        public int size() {
            return size;
        }

        public boolean isEmpty() {
            return size == 0;
        }

        // 向二分搜索树中添加新的元素e
        public void add(E e) {
            root = add(root, e);
        }

        // 向以node为根的二分搜索树中插入元素e，递归算法
        // 返回插入新节点后二分搜索树的根
        private Node add(Node node, E e) {
            if (node == null) {
                size++;
                return new Node(e);
            }

            if (e.compareTo(node.e) < 0)
                node.left = add(node.left, e);
            else if (e.compareTo(node.e) > 0)
                node.right = add(node.right, e);

            return node;
        }

        // 看二分搜索树中是否包含元素e
        public boolean contains(E e) {
            return contains(root, e);
        }

        // 看以node为根的二分搜索树中是否包含元素e, 递归算法
        private boolean contains(Node node, E e) {
            if (node == null)
                return false;
            if (e.compareTo(node.e) == 0)
                return true;
            else if (e.compareTo(node.e) < 0)
                return contains(node.left, e);
            else // e.compareTo(node.e) > 0
                return contains(node.right, e);
        }

        // 前序遍历以node为根的二分搜索树, 递归算法
        private void preOrder(Node node) {
            if (node == null)
                return;
            System.out.print(node.e + " ");
            preOrder(node.left);
            preOrder(node.right);
        }

        // 二分搜索树的非递归前序遍历
        public void preOrderNR() {
            if (root == null)
                return;

            Stack<Node> stack = new Stack<>();
            stack.push(root);
            while (!stack.isEmpty()) {
                Node cur = stack.pop();
                System.out.print(cur.e + " ");

                if (cur.right != null)
                    stack.push(cur.right);
                if (cur.left != null)
                    stack.push(cur.left);
            }
        }

        // 中序遍历以node为根的二分搜索树, 递归算法
        private void inOrder(Node node) {
            if (node == null)
                return;
            inOrder(node.left);
            System.out.print(node.e + " ");
            inOrder(node.right);
        }

        // 后序遍历以node为根的二分搜索树, 递归算法
        private void postOrder(Node node) {
            if (node == null)
                return;
            postOrder(node.left);
            postOrder(node.right);
            System.out.print(node.e + " ");
        }

        // 二分搜索树的层序遍历
        public void levelOrder() {
            if (root == null)
                return;

            Queue<Node> q = new LinkedList<>();
            q.add(root);
            while (!q.isEmpty()) {
                Node cur = q.remove();
                System.out.print(cur.e + " ");

                if (cur.left != null)
                    q.add(cur.left);
                if (cur.right != null)
                    q.add(cur.right);
            }
        }

        @Override
        public String toString() {
            StringBuilder res = new StringBuilder();
            generateString(root, 0, res);
            return res.toString();
        }

        // 生成以node为根节点，深度为depth的描述二叉树的字符串
        private void generateString(Node node, int depth, StringBuilder res) {
            if (node == null) {
                res.append(generateDepthString(depth) + "null\n");
                return;
            }

            res.append(generateDepthString(depth) + node.e + "\n");
            generateString(node.left, depth + 1, res);
            generateString(node.right, depth + 1, res);
        }

        private String generateDepthString(int depth) {
            StringBuilder res = new StringBuilder();
            for (int i = 0; i < depth; i++)
                res.append("--");
            return res.toString();
        }
    }

    public static void main(String[] args) {
        TreeMap main = new TreeMap();
        BST<Integer> bst = main.new BST<>();
        int[] nums = { 5, 3, 6, 8, 4, 2 };
        for (int num : nums)
            bst.add(num);
        /////////////////
        // 5 //
        // / \ //
        // 3 6 //
        // / \ \ //
        // 2 4 8 //
        /////////////////
        bst.preOrder(bst.root);
        System.out.println("pre");

        bst.inOrder(bst.root);
        System.out.println("mid");

        bst.postOrder(bst.root);
        System.out.println("post");

        bst.levelOrder();
        System.out.println("level");
    }
}