二叉树基本操作实现

package com.cskaoyan.bst;

import sun.reflect.generics.tree.Tree;

import javax.swing.text.AsyncBoxView;
import java.util.ArrayList;
import java.util.List;

/* 增： boolean add(E e) 删： boolean remove(E e) 查找： boolean contains(E e) E min() E max() 遍历： List<E> preOrder() List<E> inOrder() List<E> postOrder() List<E> levelOrder() 获取集合的属性： int height() boolean isEmpty() int size() 建树： static <T> BinarySearchTree buildTree(List<T> preOrder, List<T> inOrder); */
public class BinarySearchTree<E extends Comparable<? super E>> {
    // 属性
    private TreeNode root;
    private int size;

    private class TreeNode {
        TreeNode left;
        E value;
        TreeNode right;

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

        public TreeNode(TreeNode left, E value, TreeNode right) {
            this.left = left;
            this.value = value;
            this.right = right;
        }
    }

    /** * 在BST添加元素e * * @param e 待添加的元素 * @return 如果添加成功返回true, 否则返回false */
    public boolean add(E e) {
        /*// 空树 if (root == null) { root = new TreeNode(e); size++; return true; } // 根结点不为空 TreeNode p = null; TreeNode x = root; int cmp; do { cmp = e.compareTo(x.value); if (cmp == 0) return false; else if (cmp < 0) { p = x; x = x.left; } else { p = x; x = x.right; } } while (x != null); // x == null, 当前位置就是要添加的位置 if (cmp < 0) p.left = new TreeNode(e); else p.right = new TreeNode(e); size++; return true;*/
        // 递归实现
        int oldSize = size;
        root = add(root, e);
        return size > oldSize;
    }

    private TreeNode add(TreeNode node, E e) {
        if (node == null) {
            size++;
            return new TreeNode(e);
        }
        int cmp = e.compareTo(node.value);
        // 通过赋值语句把新建的结点链接起来的
        if (cmp < 0) node.left = add(node.left, e);
        else if (cmp > 0) node.right = add(node.right, e);
        return node;
    }

    /** * 删除BST中与指定对象e相等的元素 * * @param e 指定对象 * @return 如果删除成功返回true, 否则返回false */
    public boolean remove(E e) {
        TreeNode p = null;
        TreeNode x = root;
        while (x != null) {
            int cmp = e.compareTo(x.value);
            if (cmp == 0) break;
            else if (cmp < 0) {
                p = x;
                x = x.left;
            } else {
                p = x;
                x = x.right;
            }
        }
        // 没有与指定对象相等的元素 x == null
        if (x == null) return false;

        // 判断x是不是度为2的结点
        if (x.left != null && x.right != null) {
            // 将右子树中最小结点替换x结点的值
            TreeNode minP = x;
            TreeNode minX = x.right;
            while (minX.left != null) {
                minP = minX;
                minX = minX.left;
            }
            // minX.left == null
            // 用右子树中元素替换该结点的元素
            x.value = minX.value;
            // 删除右子树中最小结点
            p = minP;
            x = minX;
        }

        // 删除x结点(度为0或者度为1)
        TreeNode child = x.left != null ? x.left : x.right;
        // 判断删除的是不是根结点
        if (p == null) root = child;
        else {
            if (p.left == x) p.left = child;
            else p.right = child;
        }
        size--;
        return true;
    }

    public boolean contains(E e) {
        TreeNode x = root;
        while (x != null) {
            int cmp = e.compareTo(x.value);
            if (cmp == 0) return true;
            else if (cmp < 0) x = x.left;
            else x = x.right;
        }
        // x == null
        return false;
    }

    /** * 获取BST中最小的元素,如果是空树返回null * * @return BST中最小的元素, 如果是空树返回null */
    public E min() {
        if (isEmpty()) return null;
        TreeNode x = root;
        while (x.left != null) {
            x = x.left;
        }
        // x.left == null
        return x.value;
    }

    /** * 获取BST中最大的元素,如果是空树返回null * * @return BST中最大的元素, 如果是空树返回null */
    public E max() {
        if (isEmpty()) return null;
        TreeNode x = root;
        while (x.right != null) {
            x = x.right;
        }
        // x.right == null
        return x.value;
    }

    public int size() {
        return size;
    }

    /** * 判断BST是否是一棵空树 * * @return 如果BST是空树返回true, 否则返回false */
    public boolean isEmpty() {
        return root == null;
    }

    public List<E> preOrder() {
        // 如果是空树,就返回空集合,不要返回null
        List<E> list = new ArrayList<>();
        preOrder(root, list);
        return list;
    }

    private void preOrder(TreeNode node, List<E> list) {
        if (node == null) return;
        // 遍历根节点
        list.add(node.value);
        // 遍历左子树
        preOrder(node.left, list);
        // 遍历右子树
        preOrder(node.right, list);
    }

    public List<E> inOrder() {
        List<E> list = new ArrayList<>();
        inOrder(root, list);
        return list;
    }

    private void inOrder(TreeNode node, List<E> list) {
        if (node == null) return;
        // 遍历左子树
        inOrder(node.left, list);
        // 遍历根节点
        list.add(node.value);
        // 遍历右子树
        inOrder(node.right, list);
    }

    public static void main(String[] args) {
        BinarySearchTree<Character> tree = new BinarySearchTree<>();
        /*System.out.println(tree.size()); System.out.println(tree.preOrder()); System.out.println(tree.inOrder());*/
        tree.add('C');
        tree.add('A');
        tree.add('D');
        tree.add('B');
        tree.add('E');
        /*System.out.println(tree.size()); System.out.println(tree.preOrder()); // [C, A, B, D, E] // 中序是排好序的 System.out.println(tree.inOrder()); // [A, B, C, D, E]*/

        // contains(E e)
        /*System.out.println(tree.contains('A')); // true System.out.println(tree.contains('X')); // false System.out.println(tree.contains(null)); // NullPointerException*/

        /*System.out.println(tree.isEmpty()); System.out.println(tree.min()); System.out.println(tree.max());*/

        // remove()
        // 删除度为0
        /*System.out.println(tree.remove('B')); System.out.println(tree.size()); System.out.println(tree.preOrder()); //[C, A, D, E] System.out.println(tree.inOrder());*/

        //删除度为1
        /*System.out.println(tree.remove('D')); System.out.println(tree.size()); System.out.println(tree.preOrder()); //[C, A, B, E] System.out.println(tree.inOrder());*/

        // 删除度为2
        /*System.out.println(tree.remove('C')); System.out.println(tree.size()); System.out.println(tree.preOrder()); //[D, A, B, E] System.out.println(tree.inOrder());*/

        // 删除不存在的
        System.out.println(tree.remove('X'));
        System.out.println(tree.size());
        System.out.println(tree.preOrder()); //[C, A, B, D, E]
        System.out.println(tree.inOrder());
    }
}