>[success] # 二叉搜索樹 ~~~ 1.二叉查找樹是為了實現快速查找而生的。能做到的原因也是因為，只允許你在左側節點存儲（比父節點）小的值， 在右側節點存儲（比父節點）大的值 ~~~ >[info] ## 分析概念 ~~~ 1.根據二叉查找樹的特點來分析他的操作 ~~~ >[danger] ##### 查 ~~~ 1.首先左側節點存儲（比父節點）小的值，右側節點存儲（比父節點）大的值，也就當我們每次去查的時候， 只要去比較查詢節點和當前比較父節點大小，來決定他是走左面查詢，還是右面查詢，這樣就不用去遍歷 整個樹 ~~~ >[danger] ##### 查最大值 ~~~ 1.只需要去右側樹查找 ~~~ >[danger] ##### 查最小值 ~~~ 1.只需要去左側樹查找 ~~~  >[danger] ##### 插入 ~~~ 1.插入的后的數據一定要符合左側節點存儲（比父節點）小的值，右側節點存儲（比父節點）大的值， 因此插入的時候也是要先和跟節點比較，直到一直找到末尾，來決定插入的值是作為葉節點左側還是右側 ~~~ * 插入重復數據解決 ~~~ 1.二叉查找樹中每一個節點不僅會存儲一個數據，因此我們通過鏈表和支持動態擴容的數組等數據結構，把值相同的數 據都存儲在同一個節點上 2.每個節點仍然只存儲一個數據。在查找插入位置的過程中，如果碰到一個節點的值，與要插入數據的值相同，我們就 將這個要插入的數據放到這個節點的右子樹，也就是說，把這個新插入的數據當作大于這個節點的值來處理 ~~~  >[danger] ##### 二叉樹的刪除 ~~~ 1.如果要刪除的節點沒有子節點，我們只需要直接將父節點中，指向要刪除節點的指針置為 null。比如圖中的刪除節點 55。 2.如果要刪除的節點只有一個子節點（只有左子節點或者右子節點），我們只需要更新父節點中，指向要刪除節點的指 針，讓它指向要刪除節點的子節點就可以了。比如圖中的刪除節點 13。 3.如果要刪除的節點有兩個子節點，這就比較復雜了。我們需要找到這個節點的右子樹中的最小節點，把它替換到要刪 除的節點上。然后再刪除掉這個最小節點，因為最小節點肯定沒有左子節點（如果有左子結點，那就不是最小節點 了），所以，我們可以應用上面兩條規則來刪除這個最小節點。比如圖中的刪除節點 18。 ~~~  >[danger] ##### js 代碼實現 ~~~ const Compare = { LESS_THAN: -1, BIGGER_THAN: 1, EQUALS: 0 } // 比較節點 function defaultCompare(a, b) { if (a === b) { return Compare.EQUALS; } return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN; } // 創建節點對象 class Node { constructor(key) { this.key = key; this.left = undefined; this.right = undefined; } toString() { return `${this.key}`; } } // 創建一個二叉搜索樹 class BinarySearchTree { constructor(compareFn = defaultCompare) { this.compareFn = compareFn; this.root = undefined; } insert(key) { // 如果根節點為空說明樹沒有被創建 if (this.root == null) { this.root = new Node(key); } else { this.insertNode(this.root, key); } } /* 遵循子節點和父親節點關系為左小右大原則 */ insertNode(node, key) { // 先比和根節點大小，如果小于，看當前父節點左側是否有值 // 如果沒有就加入當前左側，如果有就遞歸依次找到能插入的位置 // 同理右側也是一樣的 if (this.compareFn(key, node.key) === Compare.LESS_THAN) { if (node.left == null) { node.left = new Node(key); } else { this.insertNode(node.left, key); } } else if (node.right == null) { node.right = new Node(key); } else { this.insertNode(node.right, key); } } // 遍歷每個節點 這里采用中期調用 // callback 是個回調函數 可以傳參(node)=>{console.log(node)} inOrderTraverseNode(node, callback) { if (node != null) { this.inOrderTraverseNode(node.left, callback); callback(node.key); this.inOrderTraverseNode(node.right, callback); } } // 最小值 min() { return this.minNode(this.root); } minNode(node) { let current = node; while (current != null && current.left != null) { current = current.left; } return current; } // 最大值 max() { return this.maxNode(this.root); } maxNode(node) { let current = node; while (current != null && current.right != null) { current = current.right; } return current; } // 搜索當前值是否在樹中 search(key) { return this.searchNode(this.root, key); } // 先判讀當前值是大于根節點還是小于，然后決定左面分支還是右面分支 // 當然這種方法是針對二叉搜索樹 searchNode(node, key) { if (node == null) { return false; } if (this.compareFn(key, node.key) === Compare.LESS_THAN) { return this.searchNode(node.left, key); } if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) { return this.searchNode(node.right, key); } return true; } remove(key) { console.log(this.removeNode(this.root, key)); } removeNode(node, key) { if (node == null) { return undefined; } if (this.compareFn(key, node.key) === Compare.LESS_THAN) { node.left = this.removeNode(node.left, key); return node; } if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) { node.right = this.removeNode(node.right, key); return node; } // key is equal to node.item // handle 3 special conditions // 1 - a leaf node // 2 - a node with only 1 child // 3 - a node with 2 children // case 1 if (node.left == null && node.right == null) { node = undefined; return 1; } // case 2 if (node.left == null) { node = node.right; return node; } if (node.right == null) { node = node.left; return node; } // case 3 const aux = this.minNode(node.right); node.key = aux.key; node.right = this.removeNode(node.right, aux.key); return node; } getRoot() { return this.root; } } const tt = new BinarySearchTree(); tt.insert(10); tt.insert(15); tt.insert(14); tt.insert(16); tt.insert(8); tt.insert(7); tt.remove(10); console.log(tt.getRoot()); ~~~