Java底層基于二叉搜索樹實現(xiàn)集合和映射/集合Set功能詳解

更新時間：2020年03月29日 12:35:12 作者：WFaceBoss

這篇文章主要介紹了Java底層基于二叉搜索樹實現(xiàn)集合和映射/集合Set功能,結(jié)合實例形式分析了Java使用二叉搜索樹實現(xiàn)集合和映射相關(guān)操作技巧,需要的朋友可以參考下

本文實例講述了Java底層基于二叉搜索樹實現(xiàn)集合和映射功能。分享給大家供大家參考，具體如下：

前言：在第5章的系列學習中，已經(jīng)實現(xiàn)了關(guān)于二叉搜索樹的相關(guān)操作，詳情查看第5章即可。在本節(jié)中著重學習使用底層是我們已經(jīng)封裝好的二叉搜索樹相關(guān)操作來實現(xiàn)一個基本的集合（set）這種數(shù)據(jù)結(jié)構(gòu)。
集合set的特性:
集合Set存儲的元素是無序的、不可重復的。為了能達到這種特性就需要尋找可以作為支撐的底層數(shù)據(jù)結(jié)構(gòu)。
這里選用之前自己實現(xiàn)的二叉搜索樹，這是由于該二叉樹是不能盛放重復元素的。因此我們可以使用二叉搜索樹這種底層來實現(xiàn)集合(set)。

1、集合`set`相關(guān)功能

1.1 add()方法特性

二分搜索樹的添加操作add：不能盛放重復元素

2. set應用

典型應用：1.客戶統(tǒng)計 2.詞匯量統(tǒng)計

3.集合實現(xiàn)

3.1 Set接口定義

/**
 * 集合的接口
 */
public interface Set<E> {
  void add(E e);//添加 <——<不能添加重復元素
  void remove(E e);//移除
  int getSize();//獲取大小
  boolean isEmpty();//是否為空
  boolean contains(E e);//是否包含元素
  
}

3.2 基于二分搜索樹實現(xiàn)集合`Set`

//基于BST二分搜索樹實現(xiàn)的集合Set
public class BSTSet<E extends Comparable<E>> implements Set<E> {//元素E必須滿足可比較的
 
  //基于BST類的對象
  private BST<E> bst;
 
  //構(gòu)造函數(shù)
  public BSTSet() {
    bst = new BST<>();
  }
 
  //返回集合大小
  @Override
  public int getSize() {
    return bst.size();
  }
 
  //返回集合是否為空
  @Override
  public boolean isEmpty() {
    return bst.isEmpty();
  }
 
  //Set添加元素
  @Override
  public void add(E e) {
    bst.add(e);
  }
 
  //是否包含元素
  @Override
  public boolean contains(E e) {
    return bst.contains(e);
  }
 
  //移除元素
  @Override
  public void remove(E e) {
    bst.remove(e);
  }
}

3.3測試：兩本名著的詞匯量和不重復的詞匯量

public static void main(String[] args) {
 
    System.out.println("Pride and Prejudice");
    //新建一個ArrayList存放單詞
    ArrayList<String> words1=new ArrayList<>();
    //通過這個方法將書中所以單詞存入word1中
    FileOperation.readFile("pride-and-prejudice.txt",words1);
    System.out.println("Total words : "+words1.size());
 
    BSTSet<String> set1=new BSTSet<>();
    //增強for循環(huán)，定一個字符串word去遍歷words
    //底層的話會把ArrayList words1中的值一個一個的賦值給word
    for(String word:words1)
      set1.add(word);//不添加重復元素
    System.out.println("Total different words : "+set1.getSize());
 
    System.out.println("-------------------");
    System.out.println("Pride and Prejudice");
    //新建一個ArrayList存放單詞
    ArrayList<String> words2=new ArrayList<>();
    //通過這個方法將書中所以單詞存入word1中
    FileOperation.readFile("a-tale-of-two-cities.txt",words2);
    System.out.println("Total words : "+words2.size());
 
    BSTSet<String> set2=new BSTSet<>();
    //增強for循環(huán)，定一個字符串word去遍歷words
    //底層的話會把ArrayList words1中的值一個一個的賦值給word
    for(String word:words2)
      set2.add(word);//不添加重復元素
    System.out.println("Total different words : "+set2.getSize());
  }

結(jié)果：