二叉樹和二叉搜索樹
二叉樹中的節(jié)點(diǎn)最多只能有2個(gè)子節(jié)點(diǎn)：一個(gè)是左側(cè)子節(jié)點(diǎn)，另外一個(gè)是右側(cè)子節(jié)點(diǎn)。
二叉搜索樹(BST)是二叉樹的一種，但是它只允許你在左側(cè)節(jié)點(diǎn)存儲(chǔ)（比父節(jié)點(diǎn)）小的值，在右側(cè)節(jié)點(diǎn)存儲(chǔ)（比父節(jié)點(diǎn)）大(或等于)的值
創(chuàng)建二叉搜索樹
1.我們要先聲明二叉搜索樹的結(jié)構(gòu):
function BinarySearchTree(){
let Node = function(key){
this.key = key;
this.left = null;
this.right = null;
};
let root = null;
function show(){
return this.key;
}
}
上面的數(shù)據(jù)結(jié)構(gòu)，和鏈表很相似，都是東莞指針表示節(jié)點(diǎn)之間的關(guān)系(術(shù)語(yǔ)稱其為邊),對(duì)于樹來說，我們也是通過指針來指定下一個(gè)元素的，但是從圖中，我們也看到了，節(jié)點(diǎn)的指針，一個(gè)指向左側(cè)子節(jié)點(diǎn)，另外一個(gè)指向右側(cè)的子節(jié)點(diǎn)，其中，鍵是樹相關(guān)術(shù)語(yǔ)對(duì)節(jié)點(diǎn)的稱呼。
向樹中插入一個(gè)人鍵（節(jié)點(diǎn)）
向樹中插入一個(gè)新的節(jié)點(diǎn)，要經(jīng)歷三個(gè)步驟
第一步：創(chuàng)建用來表示新節(jié)點(diǎn)的Node的實(shí)例，只要向構(gòu)造函數(shù)中傳入我們想要傳入的節(jié)點(diǎn)的值，做指針和右指針會(huì)由構(gòu)造函數(shù)自動(dòng)的設(shè)置為null
第二步：需要驗(yàn)證這個(gè)插入的操作是否為一種特殊的情況，這個(gè)特殊的情況就是我們插入的節(jié)點(diǎn)是樹的第一個(gè)節(jié)點(diǎn)，這個(gè)時(shí)候只需要將根節(jié)點(diǎn)指向新節(jié)點(diǎn)。
第三步：將節(jié)點(diǎn)加在非根節(jié)點(diǎn)的其他位置。
let insert = function(key){
let newNode = new Node(key);
if(root === null){
root = newNode;
}else{
insertNode(root,newNode)
}
};
//當(dāng)為非空樹的時(shí)候，我們進(jìn)行節(jié)點(diǎn)的插入的時(shí)候，進(jìn)行的步驟
let indsertNode = function(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);
}
}
}
首先我們先構(gòu)造出一個(gè)二叉搜索樹:
let tree = new BinarySearchTree();
tree.insert (11);
tree.insert (7);
tree.insert (15);
tree.insert (5);
tree.insert (3);
tree.insert (9);
tree.insert (8);
tree.insert (10);
tree.insert (13);
tree.insert (12);
tree.insert (14);
tree.insert (20);
tree.insert (18);
tree.insert (25);
我們現(xiàn)在構(gòu)造出來的二叉樹是:
當(dāng)我們想要插入一個(gè)鍵值為6的鍵，執(zhí)行下面的代碼：
tree.insert(6);
看一下我們究竟是怎么插入的：
中序遍歷
中序遍歷是一種以上行順序訪問BST所有節(jié)點(diǎn)的遍歷方式，也就是是從小到大的順序訪問所有的節(jié)點(diǎn)，讓我們看看具體的實(shí)現(xiàn)過程。
let inOrderTraverse = function (root){
inOrderTraverseNode(root);
}
inOrderTraverse方法接受一個(gè)根節(jié)點(diǎn)作為參數(shù)。在回調(diào)函數(shù)中定義我們對(duì)遍歷到的每一個(gè)節(jié)點(diǎn)進(jìn)行操作。由于我們?cè)贐ST中最常實(shí)現(xiàn)的算法就是遞歸。
var inOrderTraverseNode = function(node){
if(node !== null){
inOrderTraverseNode(node.left);
console.log(node.show());
inOrderTraverseNode(node.right);
}
};
tree.inOrderTraverse (tree.root);
最終輸出的結(jié)果是:3 5 6 7 8 9 10 11 12 13 14 15 18 20 25
先序遍歷
先序遍歷是以優(yōu)先于后代節(jié)點(diǎn)的順序訪問每一個(gè)節(jié)點(diǎn)，先序遍歷的一種應(yīng)用是打印一個(gè)結(jié)構(gòu)化的文件。我們看一下代碼的實(shí)現(xiàn)方式
let preOrderTraverse = function (root){
preOrderTraverseNode(root);
}
先序遍歷和中序遍歷的不同點(diǎn)是：先序遍歷會(huì)訪問節(jié)點(diǎn)的本身，然后訪問它的左側(cè)節(jié)點(diǎn)，最后是右側(cè)節(jié)點(diǎn)，而中序遍歷，先訪問左子節(jié)點(diǎn)，自身，右子節(jié)點(diǎn)，還是上面的二叉搜索樹，我們對(duì)其進(jìn)行先序遍歷。
var preOrderTraverseNode = function(node){
if(node !== null){
console.log(node.show());
preOrderTraverseNode (node.left);
preOrderTraverseNode (node.right);
}
};
tree.preOrderTraverse (tree.root);
最終輸出的結(jié)果是:11 7 5 3 6 9 8 10 15 13 12 14 20 18 25
后序遍歷
后續(xù)遍歷就是先訪問節(jié)點(diǎn)的后代節(jié)點(diǎn)，再訪問節(jié)點(diǎn)本身，后序遍歷的一種應(yīng)用是計(jì)算一個(gè)目錄和它的子目錄中所有的文件所占空間的大小。
let postOrderTraverse = function (root){
postOrderTraverseNode(root);
}
var postOrderTraverseNode = function(node){
if(node !== null){
postOrderTraverseNode (node.left);
postOrderTraverseNode (node.right);
console.log(node.show());
}
};
tree.preOrderTraverse (tree.root);
搜索樹中的值
搜索樹上的最大值和最小值
在上面的二叉搜索樹中我們可以清楚的看見，最左側(cè)的子節(jié)點(diǎn)的值是最小的，最右側(cè)的子節(jié)點(diǎn)的值是最大的，這條信息為我們實(shí)現(xiàn)二叉搜索樹上的最大值和最小值提供了很大的幫助。
現(xiàn)在編寫一下查找最小值的代碼：
let min = function (){
return minNode(root);
};
let minNode = function(node){
if(node){
while(node && node.left !== null){
node = node.left;
}
return node.key;
}
return null;
}
minNode方法允許我們從樹中任意一個(gè)節(jié)點(diǎn)開始尋找最小的鍵，我們可以使用來找到一棵樹或是他子樹最小的鍵。因此我們?cè)谡{(diào)用minNode方法的時(shí)候傳入了樹的根節(jié)點(diǎn)，最終體現(xiàn)的結(jié)果是我們找到了最左邊的子節(jié)點(diǎn)。類似的我們可以找到樹中的最大值，代碼如下：
let max= function (){
return maxNode(root);
};
let maxNode= function(node){
if(node){
while(node && node.right !== null){
node = node.right;
}
return node.key;
}
return null;
}
搜索特定的值
當(dāng)我們想要查找在二叉樹中存不存在一個(gè)特定的值的時(shí)候，我們需要搜索二叉樹，現(xiàn)在看一下我們的搜索過程。
let search = function(key){
return searchNode(root,key);
};
let searchNode = function(node, 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;
}
}
searchNode方法可以用來尋找一棵樹或是它的任意子樹中的一個(gè)特定的值，這也是為什么在調(diào)用的時(shí)候傳入一個(gè)節(jié)點(diǎn)作為參數(shù)。我們?cè)诔绦蜷_始的時(shí)候，需要判斷節(jié)點(diǎn)的合法性，如果是null的話，說明要找的鍵沒有找到，返回false。如果傳入的節(jié)點(diǎn)不為null，就要比較節(jié)點(diǎn)的鍵值和傳入值的鍵值大小。如果傳入值要大，那就向右邊遍歷二叉搜索樹，否則，就向左邊遍歷二叉樹。
移除節(jié)點(diǎn)
移除節(jié)點(diǎn)是我們?cè)诙嫠阉鳂渲凶顝?fù)雜的一個(gè)，首先我們先創(chuàng)建這個(gè)方法。
let remove = function(key){
root = removeNode (root,key);
};
這個(gè)方法接收要移除的鍵并且調(diào)用了removeNode方法，傳入root和要移除的鍵作為參數(shù)。我們?cè)谝瞥倪^程中，root被賦予removeNode方法的返回值，是有一定的意義的。我們會(huì)在下面進(jìn)行詳細(xì)的講述。
let removeNode = function(node, key){
if (node === null){
return null;
}
if(key < node.key){
node.left = removeNode (node.left, key);
return mdoe;
}else if(key > node.key){
node.right = removeNode(node.right, key);
return node;
}else{ // 鍵等于node.key
// 第一種情況-- 一個(gè)葉節(jié)點(diǎn)
if(node.left === null && node.right === null){
node = null;
return node;
}
// 第二種情況-- 一個(gè)只有一個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)
if(node.left=== null){
node = node.right;
return node;
}else if(node.right === null){
node = node.left;
return node;
}
// 第三種情況-- 一個(gè)有兩個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)
let aux = findMinNode(node.right);
node.key = aux.key;
node.right = removeNode (node.right,aux.key);
return node;
}
}
檢測(cè)到的節(jié)點(diǎn)是null，說明鍵值不存在于樹中，返回null。我們要做的第一件事情就是從樹中找到這個(gè)節(jié)點(diǎn)。因此，如果要找的鍵比當(dāng)前節(jié)點(diǎn)的值小，就沿著樹的左邊一直找到下一個(gè)節(jié)點(diǎn)，如果找到的鍵比當(dāng)前節(jié)點(diǎn)的鍵值大，那么就沿著樹的右邊找到下一個(gè)節(jié)點(diǎn)。
如果我們要找到的鍵(鍵和node.key相等)，據(jù)需要三種不同的情況
let findMinNode = function (node){
while(node && node.left !== null ){
node = node.left;
}
return node;
}
移除一個(gè)葉節(jié)點(diǎn)
這種情況是最簡(jiǎn)單最易懂的刪除方式。
我們要做的就是給這個(gè)節(jié)點(diǎn)賦予null值移除它。但是當(dāng)學(xué)習(xí)了鏈表的實(shí)現(xiàn)之后，我們知道僅僅是賦予了一個(gè)null值是不夠的，還需要處理指針，這個(gè)節(jié)點(diǎn)沒有任何的子節(jié)點(diǎn)，但是有一個(gè)父節(jié)點(diǎn)，需要通過返回null來將對(duì)應(yīng)的父節(jié)點(diǎn)指針賦予null值。
現(xiàn)在節(jié)點(diǎn)的值已經(jīng)是null，父節(jié)點(diǎn)指向它的指針也會(huì)接受到這個(gè)值，這也是我們要在函數(shù)中返回節(jié)點(diǎn)的值的原因。父節(jié)點(diǎn)總是會(huì)接受到函數(shù)的返回值。另外一種可行的辦法是將父節(jié)點(diǎn)和節(jié)點(diǎn)本身都作為參數(shù)傳入方法的內(nèi)部。
移除有一個(gè)左側(cè)或右側(cè)子節(jié)點(diǎn)的節(jié)點(diǎn)
現(xiàn)在讓我們來看第二種情況，移除一個(gè)有左側(cè)子節(jié)點(diǎn)，或是右側(cè)子節(jié)點(diǎn)的節(jié)點(diǎn)，在這種情況下，我們需要跳過這個(gè)節(jié)點(diǎn)，直接將父節(jié)點(diǎn)指向它指針指向的子節(jié)點(diǎn)。
如果這個(gè)節(jié)點(diǎn)沒有左側(cè)子節(jié)點(diǎn)，也就是它只有一個(gè)右側(cè)子節(jié)點(diǎn)，因此我們那對(duì)他的引用改成了對(duì)它右側(cè)子節(jié)點(diǎn)的引用，并返回更新后的節(jié)點(diǎn)。現(xiàn)在讓我們以一張圖片的形式來展現(xiàn)移除只有一個(gè)左子節(jié)點(diǎn)或右側(cè)子節(jié)點(diǎn)的節(jié)點(diǎn)的過程。
移除有兩個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)
現(xiàn)在是第三種情況，也就是最復(fù)雜的情況，那么就是要移除節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)-- 左側(cè)子節(jié)點(diǎn)和右側(cè)子節(jié)點(diǎn)。要移除有兩個(gè)知己誒單的節(jié)點(diǎn)的時(shí)候，需要執(zhí)行四個(gè)步驟:
（1）找到需要?jiǎng)h除的節(jié)點(diǎn)。找到他右邊子樹最小的節(jié)點(diǎn)(來代替該節(jié)點(diǎn)的位置)
（2）然后，用他右邊子樹最小的節(jié)點(diǎn)來更新這個(gè)節(jié)點(diǎn)的值，通過這一步，我們改變了這個(gè)節(jié)點(diǎn)的鍵，也就是說，他被移除了
（3）但是，這樣的話，樹上就有兩個(gè)擁有相同鍵的節(jié)點(diǎn)了，怎樣是不行的，要繼續(xù)把右子樹的最小節(jié)點(diǎn)進(jìn)行移除，畢竟它已經(jīng)被移到被刪除的節(jié)點(diǎn)的位置了。
（4） 最后，向它的父節(jié)點(diǎn)返回更新后的節(jié)點(diǎn)的引用。
findMinNode方法的實(shí)現(xiàn)和min方法的實(shí)現(xiàn)方式是一樣的，唯一的不同之處在于，在min方法中只返回鍵，但是findMinNode返回了節(jié)點(diǎn)。
