public class BinarySearhTree {
    // 属性
    private TreeNode root;  //根节点
    private int size;

    public void add(String s) {
        if (root == null) {
            root = new TreeNode(null, s, null);
            return;
        }
        TreeNode node = root;
        while (node != null) {
            int cmp = s.compareTo(node.data);
            if (cmp < 0) {   //左，比父亲节点小
                if (node.left == null) {
                    node.left = new TreeNode(null, s, null);
                    break;
                }
                node = node.left;
            } else if (cmp > 0) { //右，比父亲节点大
                if (node.right == null) {
                    node.right = new TreeNode(null, s, null);
                    break;
                }
                node = node.right;
            } else {
                return;
            }
        }
        size++;
    }

    private TreeNode add(TreeNode node, String s) {
        if (node == null) {
            node = new TreeNode(null, s, null);
            return node;
        }
        int cmp = s.compareTo(node.data);
        if (cmp < 0) {
            return node.left = add(node.left, s);
        } else if (cmp > 0) {
            return node.right = add(node.right, s);
        } else {
            return node;
        }
    }

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

    public int size() {
        return size();
    }

    public void preOrder() {
        preOrder(root);
        System.out.println();
    }

    private void preOrder(TreeNode node) {
        if (node == null) {
            return;
        }
        System.out.print(node.data + " ");
        preOrder(node.left);
        preOrder(node.right);
    }

    public void inOrder() {
        inOrder(root);
        System.out.println();
    }

    private void inOrder(TreeNode node) {
        if (node == null) {
            return;
        }
        inOrder(node.left);
        System.out.print(node.data + " ");
        inOrder(node.right);
    }

    public void postOrder() {
        postOrder(root);
        System.out.println();
    }

    private void postOrder(TreeNode node) {
        if (node == null) {
            return;
        }
        postOrder(node.left);
        postOrder(node.right);
        System.out.print(node.data + " ");
    }

    public void levelOrder() {
        levelOrder(root);
        System.out.println();
    }

    public void levelOrder(TreeNode node) {   //层次遍历借助队列
        LinkedList<TreeNode> queue = new LinkedList<>();
        if (node == null) {
            return;
        }
        queue.offer(root);  //根节点入队
        while (!queue.isEmpty()) {
            node = queue.poll();  //出队
            System.out.print(node.data + " ");
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }

    }


    private static class TreeNode {
        private TreeNode left;
        private String data;
        private TreeNode right;

        public TreeNode() {
        }

        public TreeNode(TreeNode left, String data, TreeNode right) {
            this.left = left;
            this.data = data;
            this.right = right;
        }
    }