二分搜索树

什么是二分搜索树？
二分搜索树：二分搜索树动态数据结构，里存储的数据必须具有可比性，所以泛型要实现
每个结点最多有两个子节点，
每个结点最多有一个父节点，
每个结点的左子树都小于当前结点的值，
所有右子树都大于当前结点的值

/**
 * 二分搜索树：二分搜索树动态数据结构，里存储的数据必须具有可比性，所以泛型要实现 Comparable接口，
 * 每个结点最多有两个子节点，
 * 每个结点最多有一个父节点，
 * 每个结点的左子树都小于当前结点的值，
 * 所有右子树都大于当前结点的值。
 * @param <E>
 */
public class BSTree<E extends Comparable<E>> {

    private int size;//二分搜索树一共有多少元素
    private Node root;//根节点

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


    private class Node<E extends Comparable<E>>{
        public E e;
        public Node<E> leftNode;
        public Node<E> rightNode;

        public Node(E e) {
            this.e = e;
            leftNode = null;
            rightNode = null;
        }
        
    }



    public int getSize(){
        return size;
    }

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

}

1.增加元素，由于二分搜索树的特性，左子树小于当前结点数据，右子树大于当前结点数据，所以我们添加数据时需要不断的去跟每个结点数据比较大小，如果大于当前结点数据，就去当前结点的右子树去找，如果右子树为空，创建一个节点设置给当前节点的右子树，如果不为空，再跟当前结点的右子树结点的值比较。如果是小于当前结点的数据，就去当前结点的左子树去找，如果当前左子树的节点为空，创建一个节点设置给当前结点的左子树。

 //用户调用的add方法
    public void add(E e){
       root = add(root,e);
    }

    //内部通过递归方式实现的add方法。
    private Node add(Node root,E e){
        if(root==null){
            root = new Node(e);
            size++;
            return root ;
        }

        //添加数据小于当前结点数据，去座子树去查找
        if(root.e.compareTo(e)>0){
            root.leftNode=add(root.leftNode,e);

        }else if(root.e.compareTo(e)<0){
            root.rightNode=add(root.rightNode,e);
        }
        return root;
    }

2.是否包含某元素，和添加元素逻辑差不多

 public boolean contans(E e) {
        return contans(e);
    }

    private boolean contans(Node root, E e) {
        if (root == null) {
            return false;
        }
      
        if (root.e.compareTo(e) > 0) {
            return contans(root.leftNode, e);
        } else if (root.e.compareTo(e) < 0) {
            return contans(root.rightNode, e);
        } else {
            return true;
        }
    }

3.获取最大元素和最小元素

   public Node getMin() {
        if (isEmpty()) {
            throw new IllegalArgumentException("BST is empty");
        }
        return getMin(root);
    }

    /**
     * 获取最小值其实就是获取最左边的子树的节点。
     *
     * @param root
     * @return
     */
    private Node getMin(Node root) {
        if (root.leftNode == null) {
            return root;
        }
        return getMin(root.leftNode);
    }


public Node getMax() {
        if (isEmpty()) {
            throw new IllegalArgumentException("BST is empty");
        }
        return getMax(root);
    }
    

    /**
     * 获取最大值其实就是获取最又边的子树的节点。
     *
     * @param root
     * @return
     */
    private Node getMax(Node root) {
        if (root.rightNode == null) {
            return root;
        }
        return getMin(root.rightNode);
    }

4.删除最小值和最大值

 /**
     * 删除最小节点，并把节点返回
     * @return
     */
    public E removeMin() {
        if(isEmpty()){
            throw new IllegalArgumentException("BST is empty");
        }
        Node<E> min = getMin(root);
        root = removeMin(root);
        return min.e;
    }

    private Node removeMin(Node root) {
        if(root.leftNode==null){
            Node rightNode = root.rightNode;
            root.rightNode = null;
            size--;
            return rightNode;
        }else{
            return removeMin(root.leftNode);
        }
    }

    /**
     * 删除元素
     * @return
     */
    public E removeMax() {
        if(isEmpty()){
            throw new IllegalArgumentException("BST is empty");
        }
        Node<E> max = getMax(root);
        root = removeMax(root);
        return max.e;
    }

    private Node removeMax(Node root) {
        if(root.rightNode==null){
            Node leftNode = root.leftNode;
            root.leftNode = null;
            size--;
            return leftNode;
        }else{
            return removeMin(root.rightNode);
        }
    }

//删除元素E
    public void remove(E e) {
        if (isEmpty())
            throw new IllegalArgumentException("thi BST is empty");
        root = remove(root, e);
    }

    private Node remove(Node root, E e) {
        if (root.e.compareTo(e) > 0) {
            root.leftNode = remove(root.leftNode, e);
        } else if (root.e.compareTo(e) < 0) {
            root.rightNode = remove(root.rightNode, e);
        } else {

            if (root.leftNode == null) {
                size--;
                return root.rightNode;
            }

            //如果右子树为空
            if (root.rightNode == null) {
                size--;
                return root.leftNode;
            }
            // 都不为空
            Node minNode = getMin(root.rightNode);
            minNode.rightNode = removeMin(root.rightNode);
            minNode.leftNode = root.leftNode;
            root = minNode;

        }
        return root;
    }

5.深度遍历

/**
     * 前序遍历，深度遍历
     */
    public void preOrder() {
        preOrder(root);
    }

    private void preOrder(Node root) {
        if (root == null) {
            return;
        }
        System.out.println(root.e);
        preOrder(root.leftNode);
        preOrder(root.rightNode);
    }

    //中序遍历，深度遍历
    public void inOrder() {
        inOrder(root);
    }

    private void inOrder(Node root) {

        if (root == null) {
            return;
        }
        preOrder(root.leftNode);
        System.out.println(root.e);
        preOrder(root.rightNode);
    }

    //后序遍历，深度遍历
    public void postOrder() {
        postOrder(root);
    }

    private void postOrder(Node root) {
        if (root == null) {
            return;
        }
        preOrder(root.leftNode);
        preOrder(root.rightNode);
        System.out.println(root.e);
    }

6.广度遍历

    //层次遍历
    public void levelOrder() {
        List<Node> list = new ArrayList<>();
        list.add(root);
        while (!list.isEmpty()) {
            Node temp = list.remove(0);
            System.out.println(temp.e);
            if (temp.leftNode != null)
                list.add(temp.leftNode);
            if (temp.rightNode != null)
                list.add(temp.rightNode);
        }
    }

整体代码：

import java.util.ArrayList;
import java.util.List;

/**
 * 二分搜索树：二分搜索树动态数据结构，里存储的数据必须具有可比性，所以泛型要实现 Comparable接口，
 * 每个结点最多有两个子节点，
 * 每个结点最多有一个父节点，
 * 每个结点的左子树都小于当前结点的值，
 * 所有又子树都大于当前结点的值。
 *
 * @param <E>
 */
public class BSTree<E extends Comparable<E>> {

    private int size;//二分搜索树一共有多少元素
    private Node root;//根节点

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


    private class Node<E extends Comparable<E>> {
        public E e;
        public Node<E> leftNode;
        public Node<E> rightNode;

        public Node(E e) {
            this.e = e;
            leftNode = null;
            rightNode = null;
        }

    }


    public int getSize() {
        return size;
    }

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

    //用户调用的add方法
    public void add(E e) {
        root = add(root, e);
    }

    //内部通过递归方式实现的add方法。
    private Node add(Node root, E e) {
        if (root == null) {
            root = new Node(e);
            size++;
            return root;
        }

        //添加数据小于当前结点数据，去座子树去查找
        if (root.e.compareTo(e) > 0) {
            root.leftNode = add(root.leftNode, e);

        } else if (root.e.compareTo(e) < 0) {
            root.rightNode = add(root.rightNode, e);
        }
        return root;
    }

    public boolean contans(E e) {
        return contans(e);
    }

    private boolean contans(Node root, E e) {
        if (root == null) {
            return false;
        }
        //添加数据小于当前结点数据，去座子树去查找
        if (root.e.compareTo(e) > 0) {
            return contans(root.leftNode, e);

        } else if (root.e.compareTo(e) < 0) {
            return contans(root.rightNode, e);
        } else {
            return true;
        }
    }

    public Node getMin() {
        if (isEmpty()) {
            throw new IllegalArgumentException("BST is empty");
        }
        return getMin(root);
    }

    /**
     * 获取最小值其实就是获取最左边的子树的节点。
     *
     * @param root
     * @return
     */
    private Node getMin(Node root) {
        if (root.leftNode == null) {
            return root;
        }
        return getMin(root.leftNode);
    }

    public Node getMax() {
        if (isEmpty()) {
            throw new IllegalArgumentException("BST is empty");
        }
        return getMax(root);
    }


    /**
     * 获取最大值其实就是获取最又边的子树的节点。
     *
     * @param root
     * @return
     */
    private Node getMax(Node root) {
        if (root.rightNode == null) {
            return root;
        }
        return getMin(root.rightNode);
    }


    /**
     * 删除最小节点，并把节点返回
     *
     * @return
     */
    public E removeMin() {
        if (isEmpty()) {
            throw new IllegalArgumentException("BST is empty");
        }
        Node<E> min = getMin(root);
        root = removeMin(root);
        return min.e;
    }

    private Node removeMin(Node root) {
        if (root.leftNode == null) {
            Node rightNode = root.rightNode;
            root.rightNode = null;
            size--;
            return rightNode;
        } else {
            return removeMin(root.leftNode);
        }
    }

    /**
     * 删除最大节点，并把节点返回
     *
     * @return
     */
    public E removeMax() {
        if (isEmpty()) {
            throw new IllegalArgumentException("BST is empty");
        }
        Node<E> max = getMax(root);
        root = removeMax(root);
        return max.e;
    }

    private Node removeMax(Node root) {
        if (root.rightNode == null) {
            Node leftNode = root.leftNode;
            root.leftNode = null;
            size--;
            return leftNode;
        } else {
            return removeMin(root.rightNode);
        }
    }


    //删除元素E
    public void remove(E e) {
        if (isEmpty())
            throw new IllegalArgumentException("thi BST is empty");
        root = remove(root, e);
    }

    private Node remove(Node root, E e) {
        if (root.e.compareTo(e) > 0) {
            root.leftNode = remove(root.leftNode, e);
        } else if (root.e.compareTo(e) < 0) {
            root.rightNode = remove(root.rightNode, e);
        } else {

            if (root.leftNode == null) {
                size--;
                return root.rightNode;
            }

            //如果右子树为空
            if (root.rightNode == null) {
                size--;
                return root.leftNode;
            }
            // 都不为空
            Node minNode = getMin(root.rightNode);
            minNode.rightNode = removeMin(root.rightNode);
            minNode.leftNode = root.leftNode;
            root = minNode;

        }
        return root;
    }

    /**
     * 前序遍历，深度遍历
     */
    public void preOrder() {
        preOrder(root);
    }

    private void preOrder(Node root) {
        if (root == null) {
            return;
        }
        System.out.println(root.e);
        preOrder(root.leftNode);
        preOrder(root.rightNode);
    }

    //中序遍历，深度遍历
    public void inOrder() {
        inOrder(root);
    }

    private void inOrder(Node root) {

        if (root == null) {
            return;
        }
        preOrder(root.leftNode);
        System.out.println(root.e);
        preOrder(root.rightNode);
    }

    //后序遍历，深度遍历
    public void postOrder() {
        postOrder(root);
    }

    private void postOrder(Node root) {
        if (root == null) {
            return;
        }
        preOrder(root.leftNode);
        preOrder(root.rightNode);
        System.out.println(root.e);
    }

    //层次遍历
    public void levelOrder() {
        List<Node> list = new ArrayList<>();
        list.add(root);
        while (!list.isEmpty()) {
            Node temp = list.remove(0);
            System.out.println(temp.e);
            if (temp.leftNode != null)
                list.add(temp.leftNode);
            if (temp.rightNode != null)
                list.add(temp.rightNode);
        }
    }

}