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

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

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

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

/** * 集合的接口 */public interface Set<E> { void add(E e);//添加 <——<不能添加重復(fù)元素 void remove(E e);//移除 int getSize();//獲取大小 boolean isEmpty();//是否為空 boolean contains(E e);//是否包含元素 }3.2 基于二分搜索樹(shù)實(shí)現(xiàn)集合Set

//基于BST二分搜索樹(shù)實(shí)現(xiàn)的集合Setpublic class BSTSet<E extends Comparable<E>> implements Set<E> {//元素E必須滿足可比較的 //基于BST類(lèi)的對(duì)象 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測(cè)試：兩本名著的詞匯量 和不重復(fù)的詞匯量

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

結(jié)果：

這里需要說(shuō)明一下就是關(guān)于我們統(tǒng)計(jì)的單詞數(shù)只考慮了每個(gè)單詞組成的不用，并沒(méi)有對(duì)單詞的特殊形式做區(qū)分。

在下一小節(jié)中繼續(xù)學(xué)習(xí)【集合和映射--集合Set->底層基于鏈表實(shí)現(xiàn)】。

源碼地址 https://github.com/FelixBin/dataStructure/tree/master/src/SetPart

更多關(guān)于java算法相關(guān)內(nèi)容感興趣的讀者可查看本站專(zhuān)題：《Java數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Java操作DOM節(jié)點(diǎn)技巧總結(jié)》、《Java文件與目錄操作技巧匯總》和《Java緩存操作技巧匯總》

希望本文所述對(duì)大家java程序設(shè)計(jì)有所幫助。