JavaScript實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)中的二叉搜索樹
二叉樹中的節(jié)點(diǎn)最多只能有兩個(gè)子節(jié)點(diǎn)：左側(cè)節(jié)點(diǎn) and 右側(cè)節(jié)點(diǎn)，這樣定義有助于我們寫出更高效的在樹中插入，查找，刪除節(jié)點(diǎn)的算法。
二叉搜索樹（BST）是二叉樹的一種，但是 只允許你在左側(cè)節(jié)點(diǎn)存儲比`父節(jié)點(diǎn)`小的值 ， 右側(cè)節(jié)點(diǎn)存儲比`父節(jié)點(diǎn)`大的值 ；如下圖：
重點(diǎn)
我在寫二叉樹的時(shí)候有個(gè)疑惑，他是如果插入的呢？為什么有的在坐標(biāo)有的在右邊。
答：其實(shí)可以看上圖圖上面那一樣，
先插入11，
第一次插入7，由于小于11放到左邊
第二次插入5，比11小，又比7小，然后放到7的左側(cè)
第三次插入15，比11大放到右側(cè)
依次類推
我 想如果你看到這里，結(jié)合上面 左側(cè)小于父節(jié)點(diǎn)，右側(cè)大于父節(jié)點(diǎn) 這句話。一定知道怎么放了；??
樹的遍歷
遍歷一棵樹??直指范圍書上的每個(gè)節(jié)點(diǎn)并對他們進(jìn)行某種操作的過程。訪問樹的所有節(jié)點(diǎn)有三種方式：中序，先序。
中序遍歷
中序遍歷是一種已上行順序訪問BST所有節(jié)點(diǎn)的遍歷方式，也就是從最小到最大的順序訪問所有節(jié)點(diǎn)。是一種對樹進(jìn)行排序操作
// 中序遍歷inOrderTraverse(callback){this.inOrderTraverseNode(this.root,callback);}inOrderTraverseNode(node,callback){// 停止遞歸的條件if(node !== null){// 通過棧先把所有小的都放到棧里面// 先遍歷左測 小節(jié)點(diǎn)this.inOrderTraverseNode(node.left,callback);callback(node.key);// 后遍歷右測 大節(jié)點(diǎn)this.inOrderTraverseNode(node.right,callback)}}const b = new BinarySearchTree();b.inOrderTraverse((value) => console.log(value)) //3 5 6 7 8 9 9 10 ...
中序 尋找規(guī)則圖示
先序遍歷
先序遍歷是以優(yōu)先于后代節(jié)點(diǎn)的順序訪問每個(gè)節(jié)點(diǎn)的，先序遍歷的一種應(yīng)用是打印一個(gè)結(jié)構(gòu)化的文檔。
先序遍歷會訪問節(jié)點(diǎn)本身，然后在訪問他的左側(cè)子節(jié)點(diǎn)，最后反問右側(cè)子節(jié)點(diǎn)。
// 先序遍歷perOrderTraverse(callback){this.perOrderTraverseNode(this.root,callback);}perOrderTraverseNode(node,callback){if(node !== null){callback(node.key);this.perOrderTraverseNode(node.left,callback);this.perOrderTraverseNode(node.right,callback);}}b.perOrderTraverse((value) => console.log(value)) // 11 7 5 3 6 9 8 10 15 13 ...
先序 尋找規(guī)則圖示
后序排序
后續(xù)遍歷是先訪問節(jié)點(diǎn)的后代節(jié)點(diǎn)，再訪問節(jié)點(diǎn)本身。后續(xù)遍歷的一種應(yīng)用是計(jì)算一個(gè)目錄及其子目錄中所有文件所占空間的大小；
// 后續(xù)排序postOrderTraverse(callback){this.postOrderTraverseNode(this.root,callback);}postOrderTraverseNode(node,callback){if(node !== null){this.postOrderTraverseNode(node.left,callback)this.postOrderTraverseNode(node.right,callback)callback(node.key)}}b.postOrderTraverse((value) => console.log(value)) // 3 6 5 8 10 9 7 12 14 ...
后序 尋找規(guī)則圖示
搜索樹的中值
搜索最大值和最小值
使用肉眼可以直觀找到樹的最大值和最小值。最小值在最末端左側(cè)，最大值在最末端右側(cè)；
查找最小值，遞歸遍歷left節(jié)點(diǎn)，因?yàn)樽髠?cè)節(jié)點(diǎn)是最小的，遍歷到最下面一個(gè)就是最小的值然后返回；遍歷最大值同理，遍歷right 右側(cè)節(jié)點(diǎn)即可
// 查找最小值min(){return this.minNode(this.root);}minNode(node){while(node !== null && node.left !== null){node = node.left;}return node.key;}// 查找最大值max(){return this.maxNode(this.root)}maxNode(node){while(node !== null && node.right !== null){node = node.right;}return node.key???????}
搜索一個(gè)特定的值
尋找一棵樹或其任意子樹中的一個(gè)特定的值。
// 搜索一個(gè)特定的值search(key) {return this.searchNode(this.root, key)}searchNode(node, key) {if (node === null) return false;let result = this.defaultCompare(key, node.key)if (result === -1) {return this.searchNode(node.left, key);} else if (result === 1) {return this.searchNode(node.right, key)} else {return true;}}console.log(b.search(1)); // falseconsole.log(b.search(8)); // true
移除指定節(jié)點(diǎn)
注意??：這里的移除節(jié)點(diǎn)返回的是移除完節(jié)點(diǎn)后的樹，而不是返回移除完的值（我在這里繞了半天，因?yàn)闆]有仔細(xì)看返回值～～）
// 移除 節(jié)點(diǎn)返回一個(gè)新的root樹，而不是返回移除的節(jié)點(diǎn)值remove(key) {this.root = this.removeNode(this.root, key);}removeNode(node, key) {if (node === null) return false;// key 比 當(dāng)前節(jié)點(diǎn)小if (this.defaultCompare(key, node.key) === -1) {node.left = this.removeNode(node.left, key)return node;} else if (this.defaultCompare(key, node.key) === 1) {// key 比當(dāng)前節(jié)點(diǎn)大node.right = this.removeNode(node.right, key);return node;} else {// { 1 } 情況1: 移除沒有左右葉的節(jié)點(diǎn)if (node.let === null && node.right === null) {node = null;return node;}// { 2 } 情況2：移除只存在 左葉或右葉的 節(jié)點(diǎn)if (node.left === null) {node = node.left; // null 賦值給當(dāng)前節(jié)點(diǎn)表示移除return node;} else if (node.right === null) {node = node.right // null 賦值給當(dāng)前節(jié)點(diǎn)表示移除return node;}// { 3 } 情況3：移除有兩個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)const aux = this.minNode(node.right); // 找到右側(cè)最小節(jié)點(diǎn)node.key = aux.key; // 最小節(jié)點(diǎn)更新 要移除的這個(gè)節(jié)點(diǎn)node.right = this.removeNode(node.right, aux.key); // 移除掉原來位置的值return node;}}
移除沒有左右葉的節(jié)點(diǎn)
見代碼 { 1 }，判斷當(dāng)前節(jié)點(diǎn)的左葉或右葉是否都是null，如果是的話，把當(dāng)前節(jié)點(diǎn)賦值給null（移除當(dāng)前節(jié)點(diǎn)）；
移除存有左側(cè)或右側(cè)節(jié)點(diǎn)的節(jié)點(diǎn)
見代碼{ 2 }，先判斷左側(cè)或右側(cè)節(jié)點(diǎn)是否為null，如果是的話，跳過這個(gè)節(jié)點(diǎn)，直接將父節(jié)點(diǎn)指針指向子節(jié)點(diǎn)。（不存在的這個(gè)節(jié)點(diǎn)肯定是null，null 賦值給當(dāng)前節(jié)點(diǎn)表示刪除）
移除的節(jié)點(diǎn)存在兩子節(jié)點(diǎn)
見代碼{ 3 }，要移除的這個(gè)節(jié)點(diǎn)下面有兩個(gè)節(jié)點(diǎn)。注??：只是移除存在兩個(gè)節(jié)點(diǎn)的這個(gè)節(jié)點(diǎn)，不移除當(dāng)前節(jié)點(diǎn)下面的兩個(gè)子節(jié)點(diǎn)；
先找到右邊節(jié)點(diǎn)下的
最小的節(jié)點(diǎn)，因?yàn)楦福娓腹?jié)點(diǎn)一定比右側(cè)小，左側(cè)大。所有要找到最小節(jié)點(diǎn)；找到右側(cè)最小節(jié)點(diǎn)的值，去更新要移除的這個(gè)節(jié)點(diǎn)的值。也就是移除掉了要移除的值，把比左側(cè)大 右側(cè)小的值，推上了被替換掉的這個(gè)值的位置。
此時(shí)存在兩個(gè)相同的節(jié)點(diǎn)（第一條這個(gè)值），第一個(gè)在原來節(jié)點(diǎn)，第二個(gè)在替換掉的那個(gè)值的位置。所以要把它原來位置的值刪掉，保證樹中不存在兩個(gè)相同的值；
返回樹
完整代碼見 https://github.com/qdwds/data-structure/blob/master/src/binarySearchTree/binarySearchTree.js
https://www.yuque.com/qdwds/uee630/qe52ca