📢 大家好，我是小丞同學，一名大二的前端愛好者
📢 這篇文章将講解資料結構中的樹
📢 非常感謝你的閱讀，不對的地方歡迎指正 🙏
📢 願你忠于自己，熱愛生活
💡 知識點搶先看
什麼是樹結構？
樹的相關術語
樹結構有哪些類型
樹的前中後序周遊
樹的層序周遊
手寫實作一顆樹
一、什麼是樹結構？
樹和哈希表一樣是一種非順序的資料結構，它對于存儲需要快速查找的資料非常有用
樹是一種分層抽象模型，可以了解為一層一層的，就類似于高中生物的遺傳圖譜
如下圖所示
二、樹的相關術語
根據上面的圖，我們大緻知道了樹是一個怎樣的資料結構，雖然對于實作它還一頭霧水，現在我們先來了解一下關于樹的相關術語
首先我們先列個表
術語 含義
節點 書中的每一個元素都叫節點
節點的深度 它的祖先節點的數量
樹的高度 所有節點深度的最大值
内部節點 至少有一個子節點的節點
外部節點 沒有子元素的節點
節點的度 節點擁有的子樹個數
葉子節點 度為 0 的節點
接下來我們來詳解一下這些分别是什麼意思
首先位于樹頂部的節點，稱為根節點，它不存在父節點，也就是節點 1
樹中的每一個元素都叫做節點
沒有子元素的節點又叫做外部節點，例如圖中的 4,5,7 這幾個節點，它們都不存在子元素
剩下的節點都是内部節點
節點中有一個屬性叫深度，它取決于祖先節點的數量，例如圖中的節點5，它有2個祖先節點，分别是 2 和 1 ，是以它的深度就是2
對于一棵樹而言，它有高度可言，高度取決于節點深度最大的值，也就是節點 7，它的深度是3，是以這顆樹的高度為 3
節點的度，度表示的是節點擁有的子樹的個數，例如節點1，有兩顆子樹，是以節點1的度為2，對于節點3而言，它隻有一顆子樹，是以節點3的度為1
對于葉子節點，也就是度為0的節點，也就是沒有子樹的節點，例如圖中的節點 （4，5，7），這些都稱做葉子節點
三、樹結構有哪些類型
對于樹來說它千變萬化，它有着很多種形态，例如
最常見的二叉樹，二叉搜尋樹
當然它還有
紅黑樹
avl 樹
n 叉樹
平衡二叉樹…
還有很多種類型，這裡主要就講二叉樹，因為其他的有點難，還沒有學
二叉樹：節點最多隻能有兩個子節點，一個是左側節點，一個是右側節點，如圖就是一棵二叉樹
四、樹的前中後序周遊
對于樹的周遊，我們有三種正常的方法，前序周遊，中序周遊，後序周遊
1. 前序周遊
前序周遊的順序是：根節點 -> 左子節點 -> 右子節點，對于子樹而言也是按照這個規律來周遊，如圖所示
自己嘗試用代碼實作一下噢~~
2. 中序周遊
中序周遊的順序是： 左子樹 -> 根節點 -> 右子樹，如圖所示
const inorder = (root) => {
if(!root) { return }
inorder(root.left)
console.log(root.val);
inorder(root.right)
} 3. 後序周遊
後序周遊的順序是：左子樹 -> 右子樹 -> 根節點，如圖所示
const postorder = (root) =>{
if(!root) {return}
// 先通路左子樹，再通路右子樹
postorder(root.left)
postorder(root.right)
// 最後通路根節點
console.log(root.val);
} 前序周遊代碼如何實作呢？自己嘗試一下吧~遞歸和疊代都可以試試噢
五、樹的層序周遊
在 LeetCode 刷題中，經常會有這樣的題目，需要按照層級來周遊，是什麼意思呢
它的意思是：逐層地，從左到右通路所有節點
也就是按照圖中的方式來周遊，并且傳回結果
傳回結果： [ [3], [9,20], [15,7] ]
也就是把每一層的元素放在一個數組中傳回，如何實作呢？
首先我們需要在廣度優先周遊的基礎上，添加層級的判斷
記錄下目前層級的節點數，當目前層級周遊完成之後，從下一個數組繼續周遊
var levelOrder = function (root) {
// 空樹
if (!root) return []
// 隊列 廣度優先周遊,[根節點,層級]
const q = [
root
]
const res = []
while (q.length) {
// 記錄一下目前有多少個節點是上一次循環遺留的,這些節點就是目前層級的全部節點
let len = q.length
res.push([])
// 将這些節點全部出隊
while (len--) {
const n = q.shift()
res[res.length - 1].push(n.val)
if (n.left) q.push(n.left)
if (n.right) q.push(n.right)
}
// 在下一次的外層循環中,又會新建立一個新的空數組
}
return res
}; 六、二叉搜尋樹有哪些方法？
在這裡就羅列幾個常見的方法吧
方法 作用
insert 向二叉搜尋樹中插入資料
serach 查找某個值
remove 移除某個值
還有很多比如傳回最大值，傳回最小值的方法，都可以實作，這裡就不寫那麼多了
七、手寫實作二叉搜尋樹
1. 建立 Node 類
建立一個節點類，用來執行個體化建立新節點，二叉搜尋樹最多隻有兩個節點
通過這個類來建立節點，預設為 null ，有 left，right 兩個子節點都為 null
class Node {
constructor(data = null, left = null, right = null){
this.data = data
this.left = left
this.right = right
}
} 2. 建立 BinarySearchTree 類
用來添加整棵樹的方法
class BinarySearchTree {
constructor() {
this.root = null
}
} 3. 實作 insert 方法
insert 方法實作插入一個元素，根據二叉搜多樹的特性，左子樹值小于右子樹值，我們需要設計出合理的插入方式
首先我們需要建立一個新節點，并且傳入 data 及節點資料
如果插入的是第一個節點，那麼該節點就是根節點
如果不是第一個插入的節點，那麼我們需要通過一個函數來輔助實作插入
insert(data) {
const newNode = new Node(data)
// insertNode為輔助函數
this.root === null ? this.root = newNode : insertNode(this.root, newNode)
} 在這裡我們寫好了 insert 方法，簡單的邏輯判斷，根節點有無，接下來的處理交給 insertNode 函數來實作
如何實作呢？
根據二叉搜尋樹的特性，我們采用遞歸的方式
首先先判斷傳入的節點和根節點的大小關系
如果比根節點小，則放到左子樹，反之
如果目前左（右）子樹為空，則它直接成為左樹第一個節點
如果不為空，我們接着比較它和左（或右）子樹的大小關系，實作遞歸
function insertNode(node, newNode) {
// 如果值小于根節點，插到左子樹
if (newNode.data < node?.data) {
// 如果沒有左子樹，那麼直接是左節點
if (node.left === null) {
node.left = newNode
} else {
// 遞歸
insertNode(node.left, newNode)
}
}else {
if(node.right === null) {
node.right = newNode
}else {
insertNode(node.left,newNode)
}
}
} 這樣我們就實作了一個 insert 方法，我們來看看如何使用吧~
随便測試一下
const tree = new BinarySearchTree()
tree.insert(344)
tree.insert(31114)
tree.insert(324)
tree.insert(34) 看到調試器面闆中的記錄，符合我們的預期
我們再來看看插入是如何一步一步實作的吧~
const tree = new BinarySearchTree()
tree.insert(15)
tree.insert(31)
tree.insert(6)
tree.insert(48) 4. 實作 search 方法
search 方法需要接收一個查找的值，我們傳回 true 或者 false ，這和之前的 has 方法類似，那我們該如何實作呢？
同樣的我們需要借助一個輔助函數來實作
首先，我們先聲明 search 方法，傳入樹和需要查找的值
當我們的樹為空時，說明一定不可能查找到值
當查找的 data 小于根節點的 data 時，我們需要遞歸左子樹繼續判斷
當大于根節點時，遞歸右子樹判斷
如果剛好等于根節點就傳回 true
實作 search 方法
search(data) {
return searchNode(this.root, data)
} 實作 searchNode 方法來實作查找
function searchNode(node, data) {
if (node === null) {
return false
}
if (data < node.data) {
return searchNode(node.left, data)
} else if (data > node.data) {
return searchNode(node.right, data)
} else {
return true
}
} 實作效果如何，我們來試試
const tree = new BinarySearchTree()
tree.insert(59)
tree.insert(29)
tree.insert(48)
tree.insert(18)
tree.insert(79)
tree.search(48)
tree.search(1) 5. 實作 remove 方法
remove 方法删除節點，這個方法是最複雜的一個方法，它要考慮的東西有很多
對于删除節點，可以分為三種類型
删除葉子節點
删除的節點隻有一個子節點
删除的節點有2個子節點
如何實作，我們一步步來看
首先我們需要實作一個 removeNode 函數，來保證我們的類中的幹淨，我們先聲明這個 remove 方法，在這裡我們預定 removeNode 需要傳回根節點
remove(data) {
this.root = removeNode(this.root, data)
} 來實作 removeNode 方法
首先我們先處理一些邊界判斷的工作
在這裡我們先處理了空樹的情況，當樹為空時傳回 null 即可，接着我們對需要删除的節點進行了搜尋，這裡利用的是遞歸實作的，當我們找到了這個節點時，目前的 node 就會指向了要删除的節點，然後進行判斷
function removeNode(node, data) {
if (node === null) return null
if (data < node.data) {
node.left = removeNode(node.left, key)
return node
} else if (data > node.key) {
node.right = removeNode(node.right, key)
} else {
// 三個情況
}
} 第一種情況：删除葉子節點，也就是 left,right 都為 null 時，可以直接删除，讓目前節點 node = null 即可
if(node.left === null && node.right === null) {
node = null
return node
} 第二種情況：删除隻有一個子節點的節點
這種情況下，我們需要跳過目前節點，指向它的子節點，也可以說是用子節點替代它的位置
if(node.left === null) {
node = node.right
return node
}else if(node.right === null) {
node = node.left
return node
} 第三種情況：删除兩個子節點的節點
這種情況是最複雜的
找到該節點的右子樹中的最小值
然後用這個最小值，去替代目前的這個被删除的節點
之後我們需要删除右子樹中的那個節點
最後傳回更新後節點的引用
在這裡我們使用了一個自己封裝的方法 findMinNode ，可以自己去試試如何實作，它的功能是，傳回最小值的節點
const min = findMinNode(node.right)
node.data = min.data
node.right = removeNode(node.right,min.data)
return node 這樣我們就實作了這三種情況的判斷，結合起來就可以正常工作了