二分查找树(完全二叉搜索树)

集合的特点：不包含重复元素、最多只包含一个null元素、没有索引。

集合的底层实现：

由链表实现、有序      -------linkedSet由二分搜索树实现、有序(自然排序)      ---------TreeSet由哈希表实现、无序       -------------HashSet

本篇博客主要讲的是由二分搜索树实现集合。

package p1.接口;

public interface Set extends Iterable{
    public void add(E e);
    public void remove(E e);
    public boolean contains(E e);
    public int size();
    public boolean isEmpty();
}

        因为TreeSet类的底层是由BST（BinarySearchTree 二分搜索树）实现的。而二分搜索树是具有可比性的。所以TreeSet的元素类型也应该具有可比性。

代码如下：

package 二分搜索树;

import p1.接口.Set;

import java.util.Iterator;

//底层由二分搜索树BinarySearchTree(BST)实现的集合
public class TreeSet> implements Set {


    @Override
    public void add(E e) {

    }

    @Override
    public void remove(E e) {

    }

    @Override
    public boolean contains(E e) {
        return false;
    }

    @Override
    public int size() {
        return 0;
    }

    @Override
    public boolean isEmpty() {
        return false;
    }

    @Override
    public Iterator iterator() {
        return null;
    }
}

//创建二分搜索树的对象
    private BinarySearchTree bst;
    public TreeSet(){
        //实例化二分搜索树
        bst = new BinarySearchTree<>();
    }

        TreeSet的底层是由BST实现的，所以我们可以直接运用BST的方法；

总体代码如下：

package 二分搜索树;

import p1.接口.Set;

import java.util.Iterator;

//底层由二分搜索树BinarySearchTree(BST)实现的集合
public class TreeSet> implements Set {

    //创建二分搜索树的对象
    private BinarySearchTree bst;
    public TreeSet(){
        //实例化二分搜索树
        bst = new BinarySearchTree<>();
    }

    @Override
    public void add(E e) {
        bst.add(e);
    }

    @Override
    public void remove(E e) {
        bst.remove(e);
    }

    @Override
    public boolean contains(E e) {
        return bst.contains(e);
    }

    @Override
    public int size() {
        return bst.size();
    }

    @Override
    public boolean isEmpty() {
        return bst.isEmpty();
    }

    @Override
    public String toString() {
        return bst.toString();
    }

    @Override
    public Iterator iterator() {
        return bst.iterator();
    }
}