目錄

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

二叉樹

二叉查找樹? ? ? ?

平衡二叉樹

紅黑樹

Set系列集合??

HashSet集合

LinkedHashSet集合

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

---

?

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

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

二叉樹

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

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 度：每個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)量

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

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

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

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

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

---

二叉查找樹? ? ? ?

特點(diǎn)：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 每個(gè)節(jié)點(diǎn)最多有2個(gè)子節(jié)點(diǎn)? ? ? ?

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

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

添加節(jié)點(diǎn)：

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

遍歷方式：? ?

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

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

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

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

前序遍歷??

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

中序遍歷

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

后序遍歷

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

層序遍歷

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

---

平衡二叉樹

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

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

? ? ? ? ? ? ? ? ? ? ? ? 當(dāng)添加一個(gè)節(jié)點(diǎn)時(shí)，該樹不是一個(gè)平衡二叉樹

左旋

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

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

右旋

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

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

---

紅黑樹

特征：

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

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

紅黑規(guī)則：

?①每個(gè)節(jié)點(diǎn)是紅色或者是黑色的

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

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

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

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

添加節(jié)點(diǎn)：

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

---

Set系列集合??

特點(diǎn)：?

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

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

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

Set實(shí)現(xiàn)類：

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

Set集合遍歷測(cè)試類

  public static void main(String[] args) {//創(chuàng)建Set集合對(duì)象 利用多態(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)建迭代器對(duì)象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);}});//簡(jiǎn)化Lambda表達(dá)式s.forEach(str -> System.out.print(str));//aaacccbbb}

HashSet集合

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

哈希表：

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

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

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

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

?測(cè)試類

 public static void main(String[] args) {//創(chuàng)建對(duì)象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)依然是哈希表，只是每個(gè)元素又多了雙鏈表的機(jī)制記錄存儲(chǔ)數(shù)據(jù)的順序

測(cè)試類

 public static void main(String[] args) {//創(chuàng)建對(duì)象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)建集合的對(duì)象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集合?? ? ? ? ? ? ? ? ? ? ??

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

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

測(cè)試類：

    public static void main(String[] args) {//創(chuàng)建TreeSet集合對(duì)象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}//實(shí)現(xiàn)類ts.forEach(new Consumer<Integer>() {@Overridepublic void accept(Integer integer) {System.out.print(integer);//12348}});//Lambda表達(dá)式簡(jiǎn)化ts.forEach(integer -> System.out.print(integer));//12348}

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

? ? ?