什么是樹
樹是由結(jié)點(diǎn)和邊組成的民轴，不存在環(huán)的一種數(shù)據(jù)結(jié)構(gòu)涝开』澄牵看下圖：
與樹相關(guān)的術(shù)語
樹的結(jié)點(diǎn)（node）：包含一個(gè)數(shù)據(jù)元素及若干指向子樹的分支；
孩子結(jié)點(diǎn)（child node）：結(jié)點(diǎn)的子樹的根稱為該結(jié)點(diǎn)的孩子曾沈；
雙親結(jié)點(diǎn)：B 結(jié)點(diǎn)是A 結(jié)點(diǎn)的孩子这嚣，則A結(jié)點(diǎn)是B 結(jié)點(diǎn)的雙親鸥昏；
兄弟結(jié)點(diǎn)：同一雙親的孩子結(jié)點(diǎn)塞俱；堂兄結(jié)點(diǎn)：同一層上結(jié)點(diǎn)；
葉子結(jié)點(diǎn)：也叫終端結(jié)點(diǎn)吏垮，是度為 0 的結(jié)點(diǎn)障涯；
樹的深度：樹中最大的結(jié)點(diǎn)層數(shù)；
二叉樹是什么
二叉樹是一種被高頻使用的特殊樹膳汪。在二叉樹中唯蝶，每個(gè)結(jié)點(diǎn)最多有兩個(gè)分支，即每個(gè)結(jié)點(diǎn)最多有兩個(gè)子結(jié)點(diǎn)遗嗽，分別稱作左子結(jié)點(diǎn)和右子結(jié)點(diǎn)粘我。
在二叉樹中，有下面兩個(gè)特殊的類型：
滿二叉樹痹换，定義為只有最后一層無任何子結(jié)點(diǎn)征字，其他所有層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)的二叉樹。
完全二叉樹娇豫，定義為除了最后一層以外匙姜，其他層的結(jié)點(diǎn)個(gè)數(shù)都達(dá)到最大，并且最后一層的葉子結(jié)點(diǎn)都靠左排列冯痢。
完全二叉樹看上去并不完全氮昧，但為什么這樣稱呼它呢框杜？這和二叉樹的存儲(chǔ)有關(guān)系。存儲(chǔ)二叉樹有兩種辦法袖肥，一種是基于指針的鏈?zhǔn)酱鎯?chǔ)法咪辱，另一種是基于數(shù)組的順序存儲(chǔ)法。
鏈?zhǔn)酱鎯?chǔ)法椎组，也就是像鏈表一樣梧乘，每個(gè)結(jié)點(diǎn)有三個(gè)字段，一個(gè)存儲(chǔ)數(shù)據(jù)庐杨，另外兩個(gè)分別存放指向左右子結(jié)點(diǎn)的指針选调，如下圖所示：
順序存儲(chǔ)法，就是按照規(guī)律把結(jié)點(diǎn)存放在數(shù)組里灵份，如下圖所示仁堪，為了方便計(jì)算，我們會(huì)約定把根結(jié)點(diǎn)放在下標(biāo)為 1 的位置填渠。隨后弦聂，B 結(jié)點(diǎn)存放在下標(biāo)為 2 的位置，C 結(jié)點(diǎn)存放在下標(biāo)為 3 的位置氛什，依次類推莺葫。
存儲(chǔ)方法：
根據(jù)這種存儲(chǔ)方法，我們可以發(fā)現(xiàn)如果結(jié)點(diǎn) X 的下標(biāo)為 i枪眉，那么 X 的左子結(jié)點(diǎn)總是存放在 2 * i 的位置捺檬，X 的右子結(jié)點(diǎn)總是存放在 2 * i + 1 的位置。
之所以稱為完全二叉樹贸铜，是從存儲(chǔ)空間利用效率的視角來看的堡纬。對(duì)于一棵完全二叉樹而言，僅僅浪費(fèi)了下標(biāo)為 0 的存儲(chǔ)位置蒿秦。而如果是一棵非完全二叉樹烤镐，則會(huì)浪費(fèi)大量的存儲(chǔ)空間。
樹的基本操作
- 樹的遍歷
遍歷一棵樹棍鳖，有非常經(jīng)典的三種方法炮叶，分別是前序遍歷、中序遍歷渡处、后序遍歷镜悉。這里的序指的是父結(jié)點(diǎn)的遍歷順序，前序就是先遍歷父結(jié)點(diǎn)骂蓖，中序就是中間遍歷父結(jié)點(diǎn)积瞒，后序就是最后遍歷父結(jié)點(diǎn)。不管哪種遍歷登下，都是通過遞歸調(diào)用完成的茫孔。
前序遍歷叮喳，對(duì)樹中的任意結(jié)點(diǎn)來說，先打印這個(gè)結(jié)點(diǎn)缰贝，然后前序遍歷它的左子樹馍悟，最后前序遍歷它的右子樹。
中序遍歷剩晴，對(duì)樹中的任意結(jié)點(diǎn)來說锣咒，先中序遍歷它的左子樹，然后打印這個(gè)結(jié)點(diǎn)赞弥，最后中序遍歷它的右子樹毅整。
后序遍歷，對(duì)樹中的任意結(jié)點(diǎn)來說绽左，先后序遍歷它的左子樹竖独，然后后序遍歷它的右子樹氮帐，最后打印它本身。
三種遍歷方式的代碼方式：
// 先序遍歷
func preOrder( _ root: TreeNode?) {
guard let rt = root else {
return
}
print(rt.val)
preOrder(rt.left)
preOrder(rt.right)
}
// 中序遍歷
func inOrderTraverse(_ root: TreeNode?) {
guard let rt = root else {
return
}
preOrder(rt.left)
print(rt.val)
preOrder(rt.right)
}
// 后序遍歷
func postOrderTraverse(_ root: TreeNode?) {
guard let rt = root else {
return
}
preOrder(rt.left)
preOrder(rt.right)
print(rt.val)
}
二叉樹遍歷過程中废恋，每個(gè)結(jié)點(diǎn)都被訪問了一次刊侯，其時(shí)間復(fù)雜度是 O(n)年鸳。執(zhí)行增加和刪除數(shù)據(jù)的操作時(shí)妖枚，在找到位置后,我們只需要通過指針建立連接關(guān)系就可以了运提。對(duì)于沒有任何特殊性質(zhì)的二叉樹而言，拋開遍歷的時(shí)間復(fù)雜度以外改含，真正執(zhí)行增加和刪除操作的時(shí)間復(fù)雜度是 O(1)情龄。
這里穿插講下遞歸
遞歸是指在函數(shù)的定義中使用函數(shù)自身的方法。
遞歸有兩層含義：
- 遞歸問題必須可以分解為若干個(gè)規(guī)模較小候味、與原問題形式相同的子問題刃唤。并且這些子問題可以用完全相同的解題思路來解決；
- 遞歸問題的演化過程是一個(gè)對(duì)原問題從大到小進(jìn)行拆解的過程白群，并且會(huì)有一個(gè)明確的終點(diǎn)（臨界點(diǎn)）。一旦原問題到達(dá)了這個(gè)臨界點(diǎn)硬霍，就不用再往更小的問題上拆解了帜慢。最后，從這個(gè)臨界點(diǎn)開始唯卖，把小問題的答案按照原路返回粱玲，原問題便得以解決。
通過二叉樹的定義和特性可知拜轨，二叉樹的遍歷可用遞歸的方式處理抽减，臨界點(diǎn)是葉子結(jié)點(diǎn)的左子樹和右子樹皆為空，為空就return返回了橄碾。
二叉查找樹
二叉查找樹（也稱作二叉搜索樹）具備以下幾個(gè)的特性：
- 在二叉查找樹中的任意一個(gè)結(jié)點(diǎn)卵沉，其左子樹中的每個(gè)結(jié)點(diǎn)的值颠锉，都要小于這個(gè)結(jié)點(diǎn)的值。
- 在二叉查找樹中的任意一個(gè)結(jié)點(diǎn)史汗，其右子樹中每個(gè)結(jié)點(diǎn)的值琼掠，都要大于這個(gè)結(jié)點(diǎn)的值。
- 在二叉查找樹中停撞，會(huì)盡可能規(guī)避兩個(gè)結(jié)點(diǎn)數(shù)值相等的情況瓷蛙。
- 對(duì)二叉查找樹進(jìn)行中序遍歷，就可以輸出一個(gè)從小到大的有序數(shù)據(jù)隊(duì)列戈毒。
二叉查找樹的查找操作
在利用二叉查找樹執(zhí)行查找操作時(shí)艰猬，我們可以進(jìn)行以下判斷：
- 首先判斷根結(jié)點(diǎn)是否等于要查找的數(shù)據(jù)，如果是就返回埋市。
- 如果根結(jié)點(diǎn)大于要查找的數(shù)據(jù)姥宝，就在左子樹中遞歸執(zhí)行查找動(dòng)作，直到葉子結(jié)點(diǎn)恐疲。
- 如果根結(jié)點(diǎn)小于要查找的數(shù)據(jù)腊满，就在右子樹中遞歸執(zhí)行查找動(dòng)作，直到葉子結(jié)點(diǎn)培己。
這樣的“二分查找”所消耗的時(shí)間復(fù)雜度就可以降低為 O(logn)碳蛋。代碼如下：
func searchBST(_ root: TreeNode?, _ val: Int) -> TreeNode? {
guard let rt = root else {
return nil
}
if rt.val > val {
return searchBST(rt.left, val)
} else if rt.val < val {
return searchBST(rt.right, val)
} else {
return rt
}
}
二叉查找樹的增加操作
從根結(jié)點(diǎn)開始，如果要插入的數(shù)據(jù)比根結(jié)點(diǎn)的數(shù)據(jù)大省咨，且根結(jié)點(diǎn)的右子結(jié)點(diǎn)不為空肃弟，則在根結(jié)點(diǎn)的右子樹中繼續(xù)嘗試執(zhí)行插入操作。直到找到為空的子結(jié)點(diǎn)執(zhí)行插入動(dòng)作零蓉。
二叉查找樹插入數(shù)據(jù)的時(shí)間復(fù)雜度是 O(logn)笤受。但這并不意味著它比普通二叉樹要復(fù)雜。原因在于這里的時(shí)間復(fù)雜度更多是消耗在了遍歷數(shù)據(jù)去找到查找位置上敌蜂，真正執(zhí)行插入動(dòng)作的時(shí)間復(fù)雜度仍然是 O(1)箩兽。
func insertIntoBST(_ root: TreeNode?, _ val: Int) -> TreeNode? {
guard let currNode = root else {
return TreeNode(val)
}
if val > currNode.val {
root?.right = insertIntoBST(root?.right, val)
} else {
root?.left = insertIntoBST(root?.left, val)
}
return root
}
二叉查找樹的刪除操作
/*
根據(jù)二叉搜索樹的性質(zhì)
如果目標(biāo)節(jié)點(diǎn)大于當(dāng)前節(jié)點(diǎn)值，則去右子樹中刪除章喉；
如果目標(biāo)節(jié)點(diǎn)小于當(dāng)前節(jié)點(diǎn)值汗贫，則去左子樹中刪除；
如果目標(biāo)節(jié)點(diǎn)就是當(dāng)前節(jié)點(diǎn)秸脱，分為以下三種情況：
其無左子：其右子頂替其位置落包，刪除了該節(jié)點(diǎn)；
其無右子：其左子頂替其位置摊唇，刪除了該節(jié)點(diǎn)咐蝇；
其左右子節(jié)點(diǎn)都有：其左子樹轉(zhuǎn)移到其右子樹的最左節(jié)點(diǎn)的左子樹上，然后右子樹頂替其位置巷查，由此刪除了該節(jié)點(diǎn)有序。
*/
func deleteNode(_ root: TreeNode?, _ key: Int) -> TreeNode? {
guard var root = root else {
return nil
}
if key > root.val {
root.right = deleteNode(root.right, key)
} else if key < root.val{
root.left = deleteNode(root.left, key)
} else {
if nil == root.right {
return root.left
} else if nil == root.left {
return root.right
} else if let _ = root.right, let _ = root.left {
var temp = root.right
while let _ = temp?.left {
temp = temp?.left
}
temp?.left = root.left
if let right = root.right {
root = right
}
}
}
return root
}
總結(jié)
本文主要講解的是二叉樹的基本理解和操作抹腿，理解二叉樹的各類操作無外乎查增刪，鏈?zhǔn)蕉鏄湓鰟h的時(shí)間復(fù)雜度都是0(1),真正耗時(shí)的是查笔呀，時(shí)間復(fù)雜度是O(logn)幢踏，所以二叉樹的增刪查的時(shí)間復(fù)雜度都是0(logn)。另外二叉樹的查找分兩種许师，深度優(yōu)先遍歷還是廣度優(yōu)先遍歷房蝉，本文講的都是深度優(yōu)先的查找操作即遞歸。
