目錄

數(shù)據(jù)結(jié)構(gòu)

二叉樹

二叉查找樹? ? ? ?

平衡二叉樹

紅黑樹

Set系列集合??

HashSet集合

LinkedHashSet集合

TreeSet集合?? ? ? ? ? ? ? ? ? ? ??

---

?

??????????前言：學(xué)習(xí)JAVA的第十四天（基礎(chǔ)）-CSDN博客

數(shù)據(jù)結(jié)構(gòu)

二叉樹

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 元素：結(jié)點（節(jié)點）

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 度：每個節(jié)點的子節(jié)點數(shù)量

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 二叉樹：度<=2

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 樹高：樹的總層數(shù)????????????????

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 根節(jié)點：最頂部的節(jié)點

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 左子結(jié)點：左下方的節(jié)點

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 右子節(jié)點：右下方的節(jié)點

---

二叉查找樹? ? ? ?

特點：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 每個節(jié)點最多有2個子節(jié)點? ? ? ?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 任意節(jié)點左子樹上的值小于當(dāng)前節(jié)點?

? ??????????????????????????????任意節(jié)點右子樹上的值大于當(dāng)前節(jié)點? ? ? ? ?

添加節(jié)點：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 小的存左邊、大的存右邊、一樣的不存

遍歷方式：? ?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?①前序遍歷

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?②中序遍歷

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ③ 后序遍歷

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ④ 層序遍歷

前序遍歷??

? ? ? ? ? ? ? ? ? ? ? ? 從根節(jié)點開始，按照當(dāng)前節(jié)點、左子節(jié)點、右子節(jié)點的順序遍歷

中序遍歷

? ? ? ? ? ? ? ? ? ? ? ? 從最左邊的子節(jié)點開始，按照左子節(jié)點、當(dāng)前節(jié)點、右子節(jié)點的順序遍歷

后序遍歷

????????????????????????從最左邊的子節(jié)點開始，按照左子節(jié)點、、右子節(jié)點、當(dāng)前節(jié)點的順序遍歷

層序遍歷

? ? ? ? ? ? ? ? ? ? ? ? 從根節(jié)點開始，一層一層遍歷

---

平衡二叉樹

? ????????????????????????規(guī)則：?任意節(jié)點的左右子樹高度差不超過1??

旋轉(zhuǎn)機(jī)制

? ? ? ? ? ? ? ? ? ? ? ? 當(dāng)添加一個節(jié)點時，該樹不是一個平衡二叉樹

左旋

? ? ? ? ? ? ? ? ? ? ? ? 確認(rèn)支點：從添加的節(jié)點開始，不斷的從父節(jié)點中找出不平衡的節(jié)點

? ? ? ? ? ? ? ? ? ? ? 步驟：不平衡節(jié)點作為支點。將支點左旋降級，變成左子節(jié)點。晉升原來的右子節(jié)點

右旋

????????????????????????確認(rèn)支點：從添加的節(jié)點開始，不斷的從父節(jié)點中找出不平衡的節(jié)點

? ? ? ? ? ? ? ? ? ? ??步驟：不平衡節(jié)點作為支點。將支點右旋降級，變成右子節(jié)點。晉升原來的左子節(jié)點

---

紅黑樹

特征：

? ? ? ? ? ? ? ? ? ? ? ? 紅黑樹是一種自平衡的二叉樹

? ? ? ? ? ? ? ? ? ? ? ? 每個節(jié)點可以是紅或黑，紅黑樹不是高度平衡的，它的平衡是通過“紅黑規(guī)則”實現(xiàn)

紅黑規(guī)則：

?①每個節(jié)點是紅色或者是黑色的

?②根節(jié)點必須是黑色的

? ③如果一個節(jié)點沒有子節(jié)點或者父節(jié)點，則該節(jié)點的指針屬性值為Nil，這些Nil會視為葉節(jié)點，每個葉節(jié)點是黑色的

④如果某一個節(jié)點是紅色，那么它的子節(jié)點必須是黑色(不能出現(xiàn)兩個紅色節(jié)點相連)

⑤對每一個節(jié)點，從該節(jié)點到其所有后代葉節(jié)點的簡單路徑.上,均包含相同數(shù)目的黑色節(jié)點

添加節(jié)點：

? ? ? ? ? ? ? ? ? ? ? ? 默認(rèn)是紅色（效率高）

---

Set系列集合??

特點：?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?無序：存取順序不一致

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 不重復(fù)：可以用來去重

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 無索引：? 不能用索引遍歷元素

Set實現(xiàn)類：

• HashSet：無序、不重復(fù)、無索引
• LinkedHashSet：有序、不重復(fù)、無索引
• TreeSet：可排序、不重復(fù)、無索引

Set集合遍歷測試類

  public static void main(String[] args) {//創(chuàng)建Set集合對象 利用多態(tài)Set<String> s = new HashSet<>();//添加元素s.add("aaa");s.add("bbb");s.add("ccc");//打印集合System.out.print(s);//[aaa, ccc, bbb]//創(chuàng)建迭代器對象Iterator<String> it = s.iterator();while (it.hasNext()){System.out.print(it.next());//aaacccbbb}//增強(qiáng)for遍歷for(String str : s) {System.out.print(str);//aaacccbbb}System.out.println();//利用Lambda表示式遍歷s.forEach(new Consumer<String>() {@Overridepublic void accept(String str) {System.out.print(str);}});//簡化Lambda表達(dá)式s.forEach(str -> System.out.print(str));//aaacccbbb}

HashSet集合

解釋：底層是用哈希表存儲數(shù)據(jù)的

哈希表：

? ? ? ? ? ? ? ? JDK8之前：數(shù)組+鏈表

? ? ? ? ? ? ? ? JDK8開始：數(shù)組+鏈表+紅黑樹

哈希值：對象的整數(shù)表現(xiàn)形式

• 根據(jù)hashCode方法算出來的int類型整數(shù)
• 該方法定義在Object中，所有對象都可以調(diào)用，默認(rèn)使用地址值計算哈希值
• 一般情況下，會重寫hashCode方法，利用對象內(nèi)部的屬性值計算哈希值?? ? ? ? ? ??

?測試類

 public static void main(String[] args) {//創(chuàng)建對象Student s1 = new Student("zhj",32);Student s2 = new Student("zhj",32);//哈希值System.out.println(s1.hashCode());//2133927002System.out.println(s2.hashCode());//1836019240}

LinkedHashSet集合

原理：底層數(shù)據(jù)結(jié)構(gòu)依然是哈希表，只是每個元素又多了雙鏈表的機(jī)制記錄存儲數(shù)據(jù)的順序

測試類

 public static void main(String[] args) {//創(chuàng)建對象Student s1 = new Student("aaa",12);Student s2 = new Student("bbb",15);Student s3 = new Student("ccc",18);Student s4 = new Student("ddd",42);//創(chuàng)建集合的對象LinkedHashSet<Student> lhs = new LinkedHashSet<>();System.out.println(lhs.add(s3));//trueSystem.out.println(lhs.add(s2));//trueSystem.out.println(lhs.add(s1));//trueSystem.out.println(lhs.add(s4));//trueSystem.out.println(lhs);//[Student{name='ccc', age=18}, Student{name='bbb', age=15}, Student{name='aaa', age=12}, Student{name='ddd', age=42}]}

TreeSet集合?? ? ? ? ? ? ? ? ? ? ??

特點：可排序（默認(rèn)情況按照從小到大排列）、無索引、不重復(fù)

實現(xiàn)：TreeSet集合底層是基于紅黑樹的數(shù)據(jù)結(jié)構(gòu)進(jìn)行排序的

測試類：

    public static void main(String[] args) {//創(chuàng)建TreeSet集合對象TreeSet<Integer>  ts = new TreeSet<>();//添加元素ts.add(4);ts.add(8);ts.add(1);ts.add(3);ts.add(2);//打印數(shù)據(jù)System.out.println(ts);//[1, 2, 3, 4, 8]//迭代器遍歷Iterator<Integer>  it = ts.iterator();while(it.hasNext()){System.out.print(it.next());//12348}//增強(qiáng)for遍歷for (Integer t : ts) {System.out.print(t);//12348}//實現(xiàn)類ts.forEach(new Consumer<Integer>() {@Overridepublic void accept(Integer integer) {System.out.print(integer);//12348}});//Lambda表達(dá)式簡化ts.forEach(integer -> System.out.print(integer));//12348}

????????????????????????

? ? ?