首頁 > 人文
TreeSet-兩種比較方式的對比
由 碼一碼程式碼 發表于 人文2022-12-02
簡介即然實現Comparable介面的類支援排序，如果有一個List列表或者陣列中存的是實現Comparable介面的類的物件，則該List列表或陣列可以透過Collections
承蒙在字典裡的意思是什麼
八 TreeSet-兩種比較方式的對比
1。1 問題提問
1
兩種比較器的區別
2
關於返回值的規則
1。3 問題解答
1
兩種比較器的區別
自然排序
Comparable
是排序介面。
若一個類實現了Comparable介面，就意味著“該類支援排序”
，
在以後的任何位置都能比較大小
。
即然
實現Comparable介面的類支援排序，如果有一個List列表或者陣列中存的是實現Comparable介面的類的物件，
則該List列表或陣列可以透過
Collections
。
sort（或
Arrays
。
sort）進行排序。
比較器排序
：
comparator
是比較器介面。
我們若需要控制某個類的次序，而該類本身不支援排序
（
即沒
有實現Comparable介面
）
；
那麼，我們可以建立一個“該類的比較器”來進行排序。這個“比較器”只需要實現
Comparator介面即可。屬於臨時性的一個比較
2
關於返回值的規則
兩個比較器的返回值規則
：
若是當前物件比目標物件大，則返回1，那麼當前物件會排在目標物件的後面
存右邊
若是當前物件比目標物件小，則返回
-
1
，那麼當前物件會排在目標物件的後面
存左邊
若是兩個物件相等，則返回0
則認為這兩個物件相等不分先後
，
當著兩個物件所比較的內容相同返回0的時候有兩種情況
1
如果是set集合
那麼相同的不會往裡存
2
如果是其他容器
會存入到容器中並且不分先後
注意
：
在使用的時候預設使用自然排序
，
當自然排序不滿足需求的時候使用比較器進行排序
常用的一些類如String
Integer
等有已經實現了自然排序
，
預設按照字典順序排
1。4 補充程式碼
集合服務類排序方法
List
<
Integer
>
list
=
new
ArrayList
<>
（）；
list
。
add
（
1
）；
//Integer也是物件 自定義物件也是可以的不過需要實現排序介面
list
。
add
（
5
）；
list
。
add
（
3
）；
list
。
add
（
2
）；
list
。
add
（
7
）；
Collections
。
sort
（
list
）；
System
。
out
。
println
（
list
）；
九 資料結構-二叉樹
1。1 問題提問
1
為什麼要使用樹
：
2
樹的常用術語
3
樹的分類
1。3 問題解答
1
為什麼要使用樹
：
1
有序陣列插入資料項和刪除資料項太慢
（
要經過資料的移動
）
2
連結串列查詢資料太慢
（
需要一個節點一個節點的找
）
3
在樹中能非常快速的查詢資料項
，
插入資料項和刪除資料項
A
1
層
/
\
B
C
2
層
/
\
\
D
E
F
3
層
/
/
\
/
\
\
G
H
I
J
K
l
4
層
/
z
5
層
樹
：
Tree
n
（
n
>=
0
）
個節點的有限集
，
n
=
0
時稱為空樹
，
在任意一棵非空樹中
：
1
有且僅有一個特定的稱為根
（
root
）
的節點
，
2
當n
>
1
時
其餘節點可以分為m
（
m
>
0
）
個互不相交的有限集T1
，
T2
。。。
其中每個集合本身又是一
個樹
並且稱為根的子樹
（
SubTree
）
windows中的磁碟就是樹結構
：
資料夾結構
注意
：
節點
=
結點
一個意思的不同翻譯
2
樹的常用術語
1
節點
：
節點物件
，
包含節點的基本資訊
（
資料
，
子節點地址
，
父節點地址
。。）
2
路徑
：
順著連線節點的邊從一個節點到另一個節點
，
所經過的節點順序排列稱為路徑
3
根
：
樹最上邊的節點稱為根節點
，
一棵樹只有一個根
，
而且從根到任何節點有且只有一條路徑
（
A就是根節點
）
3
父節點
：
每個節點都有一條邊向上連線到另一個節點
，
這個另一個節點就稱為該節點的父節點
， （
B就是D的父節點
）
4
子節點
：
每個節點都有一條邊向下連線到另一個節點
，
下面這個節點就是該節點的子節點
（
D就是B的子節點
）
5
兄弟節點
：
具有相同父節點的節點互稱為兄弟節點
（
B
C
就是兄弟節點
）
5
葉子節點
：
沒有子節點的節點稱為葉子節點
（
z
H
I
J
K
L
就是葉子節點
）
6
子樹
：
每個節點可以看
做為
一個子樹的根
，
它和它所有的子節點
，
子節點的子節點組合在一起就是一個子樹
7
訪問
：
訪問一個節點是為了在這個節點上執行一些操作
，
如檢視節點的資料項
但是如果僅僅是經過一個節點
，
不認為是訪問了這個節點
8
層
：
從根開始定義，根為第一層，根的子節點為第二層，以此類推
。
9
高度
：
樹中節點的最大層次稱為樹的高度
樹的高度可以這樣理解：把整棵樹想象為一棟樓房，從葉子節點為1，向上開始計數，
到此節點（包括此節點）的數值為此節點的高度，
10
深度
：
樹的深度可以這樣理解，計算一個節點的深度，從根節點算起（記住從1開始計數
，
而不是0）
到該節點所經過的節點數（包括此節點）為樹的深度
11
節點的度
：
***
節點擁有的子樹數量稱為節點的度
，
度為0的節點稱為葉子節點或終端節點
，
度不為0的節點稱為非終端節點或分支節點
，
除了根節點以外分支節點也稱為內部節點
樹的度是指樹內各節點的度的最大值
（
梅開九度
）
A節點度為2
B節點度為2
C節點度為1
F節點度為3
最後一排的節點度為0稱為終端
節點
這個完成的數的度是3
12
節點的權
：
節點值
相當於這個點的編號
有些時候這個權是用路徑來表示的
13
森林
：
多棵子樹構成一個森林
3
樹的分類
二叉樹
二叉查詢樹
平衡二叉樹
紅黑樹
B樹
b
+
樹
1。4 二叉樹詳細講解
1
概念
：
樹的每個節點最多隻能有兩個子節點
（
可以有一個
可以沒有
）
子節點分為左節點和
右節點
A
A
A
A
/
\
/
\
B
C
B
C
2
分類
：
斜樹
：
所有結點
都只有左子樹的
叫做
左斜樹，所有節點都只有右子樹的
叫做
右斜樹
A
A
/
\
B
C
滿二叉樹
：
在一棵二叉樹中
，
如果所有分支節點都存在左子樹和右子樹
，
並且所有葉子節點都
在同一層上
A
/
\
B
C
/
\
/
\
D
E
F
I
完全二叉樹
：
若設二叉樹的深度為k，除第
k
層外，其它各層
（
1
～k
-
1
）
的
結點數
都達到最大個數，第k
層所有的
結點
都連續集中在最左邊，這就是完全二叉樹。
通俗講
：
二叉樹中除去最後一層節點，剩餘的為滿二叉樹
而且最後一層的結點依次從左到右分佈，中間沒有隔開的，就是完全二叉樹
A
/
\
B
C
/
\
/
\
D
E
F
G
/
\
H
I
