TreeMap_LevelOrder.java

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

public class TreeMap_LevelOrder {
    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;
        }

        // 向二分搜索树中添加新的元素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);
        }


        // 二分搜索树的层序遍历
        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_LevelOrder main = new TreeMap_LevelOrder();
        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.levelOrder();
        System.out.println("level");
    }
}