每當放完小長假，我都會習慣性的反思和覆盤一下自己的技術，尤其是端午節。為什麼我會寫二叉樹的文章呢？其實這涉及到程序員的一個成長性的問題。對於0-3年的前端程序員來説，可能很少有機會涉及到數據結構和算法的工作中，除非去大廠或者做架構相關的工作。但是很多工作2-3年的前端工程師，業務工作已經相對熟悉了，各種技術或多或少也都使用過，那麼在這個階段，對於每個有追求的程序員，是不是應該突破一下自己的技術瓶頸，去研究一些更深層次的知識呢？沒錯，這個階段我們最應該瞭解的就是數據結構，算法，設計模式相關的知識，設計模式和算法筆者在之前的文章中已經系統的總結過了，感興趣的可以學習瞭解一下。
接下來筆者就係統的總結一下二叉樹相關的知識，並且通過實際代碼一步步來帶大家實現一個二叉搜索樹。
二叉樹介紹
二叉樹（Binary tree）是樹形結構的一個重要類型。許多實際問題抽象出來的數據結構往往是二叉樹形式，即使是一般的樹也能簡單地轉換為二叉樹，而且二叉樹的存儲結構及其算法都較為簡單，因此二叉樹顯得特別重要。二叉樹特點是每個結點最多隻能有兩棵子樹，且有左右之分。
二叉樹中的節點最多隻能有兩個子節點：左側子節點和右側子節點。我們接下來主要來實現一個二叉搜索樹（BST）。它是二叉樹的一種，但是隻允許你在左側節點存儲比父節點小的值，在右側節點存儲比父節點大（或者等於）的值。如下圖：
接下來我們就一起實現一下BST樹。
實現一個二叉搜索（BST）樹
在實現之前，我們需要先分析一下BST（二叉搜索）樹。我們要想構建一棵實用的樹，我們需要節點和方法，如下圖所示：
我們先實現一個基類，如下：
function BinarySearchTree() { let Node = function(key) { this.key = key; this.left = null; this.right = null; } let root = null;}複製代碼
我們按照上圖的二叉搜索樹的結構組織方式，來實現二叉樹的基本方法。
// 插入this.insert = function(key) { let newNode = new Node(key); if(root === null) { root = newNode; }else { insertNode(root, newNode); }}複製代碼
其中insertNode方法用來判斷在根節點不為空時的執行邏輯，具體代碼如下：
function insertNode(node, newNode) { // 如果新節點值小於當前節點值，則插入左子節點 if(newNode.key < node.key) { if(node.left === null) { node.left = newNode; }else{ insertNode(node.left, newNode); } }else { // 如果新節點值大於當前節點值，則插入右子節點 if(node.right === null) { node.right = newNode; }else { insertNode(node.right, newNode); } }}複製代碼
以上代碼即實現了BST的插入部分邏輯，具體使用方式如下：
let tree = new BinarySearchTree()tree.insert(19)tree.insert(10)tree.insert(20)複製代碼
以上代碼生成的二叉樹結構如下：
樹的遍歷
樹的遍歷是指訪問樹的每個節點並對它們進行某種操作的過程。具體分為中序遍歷，先序遍歷和後序遍歷。接下來我會一一介紹給大家。
中序遍歷
中序遍歷是一種以從最小到最大的順序訪問所有節點的遍歷方式，具體實現如下：
this.inOrderTraverse = function(cb) { inOrderTraverseNode(root, cb)}function inOrderTraverseNode(node, cb) { if(node !== null) { inOrderTraverseNode(node.left, cb) cb(node.key) inOrderTraverseNode(node.right, cb) }}複製代碼
具體遍歷過程如下圖所示：
先序遍歷
先序遍歷是以優先於後代節點的順序訪問每一個節點。具體實現如下：
this.preOrderTraverse = function(cb) { preOrderTraverseNode(root, cb)}function preOrderTraverseNode(node, cb) { if(node !== null) { cb(node.key) preOrderTraverseNode(node.left, cb) preOrderTraverseNode(node.right, cb) }}複製代碼
具體遍歷如下圖所示：
後序遍歷
後序遍歷是先訪問節點的後代節點，再訪問節點本身。。具體實現如下：
this.postOrderTraverse = function(cb) { preOrderTraverseNode(root, cb)}function postOrderTraverseNode(node, cb) { if(node !== null) { postOrderTraverseNode(node.left, cb) postOrderTraverseNode(node.right, cb) cb(node.key) }}複製代碼
具體遍歷順序如下圖所示：
樹的搜索
我們一般的搜索會有最值搜索（也就是最大值，最小值，中值）和對特定值的搜索，接下來我們就來實現它們。
搜索特定的值
在BST樹中搜索特定的值，具體實現如下：
this.search = function(key) { return searchNode(root, key)}function searchNode(ndoe, key) { if(node === null) { return false } if(key < node.key) { return searchNode(node.left, key) }else if(key > node.key) { return searchNode(node.right, key) }else { return true }}複製代碼
實現邏輯也很簡單，這裏大家可以研究一下。
搜索最小值
由二叉樹的結構特徵我們可以發現，二叉樹的最左端就是最小值，二叉樹的最右端就是最大值，所以我們可以通過遍歷來找到最小值，代碼如下：
this.min = function() { return minNode(root)}function minNode(node) { if(node) { while(node && node.left !== null) { node = node.left; } return node.key } return null}複製代碼 搜索最大值
和求最小值一樣，最大值也可以用類似的方法，代碼如下：
this.max = function() { return maxNode(root)}function maxNode(node) { if(node) { while(node && node.right !== null) { node = node.right; } return node.key } return null}複製代碼 移除節點
移除BST中的節點相對來説比較複雜，需要考慮很多情況，具體情況如下：
移除一個葉節點
移除有一個左側或右側子節點的節點
移除有兩個子節點的節點
瞭解了上述3種情況之後我們開始實現刪除節點的邏輯：
this.remove = function(key) { root = removeNode(root, key)}function removeNode(node, key) { if(node === null) { return null } if(key < node.key) { node.left = removeNode(node.left, key) return node }else if(key > node.key) { node.right = removeNode(node.right, key) return node }else { // 一個葉節點 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 } // 有兩個子節點的節點情況 let aux = findMinNode(node.right); node.key = aux.key; node.right = removeNode(node.right, aux.key); return node }}function findMinNode(node) { if(node) { while(node && node.left !== null) { node = node.left; } return node } return null}複製代碼
至此，一棵完整的搜索二叉樹就實現了，是不是很有成就感呢？本文的源碼以上傳至筆者的github，感興趣的朋友可以感受一下。
二叉樹的應用
二叉樹一般可以用來：
生成樹結構
數據庫的搜索算法
利用二叉樹加密
計算目錄和子目錄中所有文件的大小，
打印一個結構化的文檔
在遊戲中用來做路徑規劃等
擴展
其實樹的類型還有很多種，這些不同類型的樹在計算機中有很廣泛的用途，比如紅黑樹，B樹，自平衡二叉查找樹，空間劃分樹，散列樹，希爾伯特R樹等，如果對這些樹敢興趣的朋友可以深入研究一下，畢竟對自己未來的技術視野還是很有幫助的。
最後