二叉樹和二叉搜索樹

二叉樹中的節(jié)點最多只能有2個子節(jié)點：一個是左側(cè)子節(jié)點工碾，另外一個是右側(cè)子節(jié)點岸啡。
二叉搜索樹(BST)是二叉樹的一種鸵赖，但是它只允許你在左側(cè)節(jié)點存儲（比父節(jié)點）小的值毕贼，在右側(cè)節(jié)點存儲（比父節(jié)點）大(或等于)的值
創(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;
  }
}

二叉搜索樹的結(jié)構(gòu)

上面的數(shù)據(jù)結(jié)構(gòu)温赔，和鏈表很相似，都是東莞指針表示節(jié)點之間的關(guān)系(術(shù)語稱其為邊),對于樹來說鬼癣，我們也是通過指針來指定下一個元素的陶贼，但是從圖中，我們也看到了待秃，節(jié)點的指針拜秧，一個指向左側(cè)子節(jié)點，另外一個指向右側(cè)的子節(jié)點章郁，其中枉氮，鍵是樹相關(guān)術(shù)語對節(jié)點的稱呼。

向樹中插入一個人鍵（節(jié)點）

向樹中插入一個新的節(jié)點暖庄，要經(jīng)歷三個步驟
第一步：創(chuàng)建用來表示新節(jié)點的Node的實例嘲恍，只要向構(gòu)造函數(shù)中傳入我們想要傳入的節(jié)點的值，做指針和右指針會由構(gòu)造函數(shù)自動的設(shè)置為null
第二步：需要驗證這個插入的操作是否為一種特殊的情況雄驹，這個特殊的情況就是我們插入的節(jié)點是樹的第一個節(jié)點佃牛，這個時候只需要將根節(jié)點指向新節(jié)點。
第三步：將節(jié)點加在非根節(jié)點的其他位置医舆。

let insert = function(key){
  let newNode = new Node(key);
  if(root === null){
    root = newNode;
  }else{
    insertNode(root,newNode)
  }
};
//當(dāng)為非空樹的時候俘侠，我們進(jìn)行節(jié)點的插入的時候，進(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)造出一個二叉搜索樹:

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)造出來的二叉樹是:

插入二叉樹的結(jié)構(gòu)

當(dāng)我們想要插入一個鍵值為6的鍵蔬将，執(zhí)行下面的代碼：

tree.insert(6);

看一下我們究竟是怎么插入的：

插入二叉搜索樹

中序遍歷

中序遍歷是一種以上行順序訪問BST所有節(jié)點的遍歷方式爷速，也就是是從小到大的順序訪問所有的節(jié)點，讓我們看看具體的實現(xiàn)過程霞怀。

let inOrderTraverse = function (root){
  inOrderTraverseNode(root);
}

inOrderTraverse方法接受一個根節(jié)點作為參數(shù)惫东。在回調(diào)函數(shù)中定義我們對遍歷到的每一個節(jié)點進(jìn)行操作。由于我們在BST中最常實現(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é)點的順序訪問每一個節(jié)點廉沮，先序遍歷的一種應(yīng)用是打印一個結(jié)構(gòu)化的文件。我們看一下代碼的實現(xiàn)方式

let preOrderTraverse = function (root){
  preOrderTraverseNode(root);
}

先序遍歷和中序遍歷的不同點是：先序遍歷會訪問節(jié)點的本身徐矩，然后訪問它的左側(cè)節(jié)點滞时，最后是右側(cè)節(jié)點，而中序遍歷滤灯，先訪問左子節(jié)點坪稽，自身曼玩，右子節(jié)點，還是上面的二叉搜索樹窒百，我們對其進(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é)點的后代節(jié)點，再訪問節(jié)點本身篙梢，后序遍歷的一種應(yīng)用是計算一個目錄和它的子目錄中所有的文件所占空間的大小样悟。

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é)點的值是最小的庭猩，最右側(cè)的子節(jié)點的值是最大的，這條信息為我們實現(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方法允許我們從樹中任意一個節(jié)點開始尋找最小的鍵蔼水，我們可以使用來找到一棵樹或是他子樹最小的鍵。因此我們在調(diào)用minNode方法的時候傳入了樹的根節(jié)點录肯，最終體現(xiàn)的結(jié)果是我們找到了最左邊的子節(jié)點趴腋。類似的我們可以找到樹中的最大值，代碼如下：

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)我們想要查找在二叉樹中存不存在一個特定的值的時候论咏，我們需要搜索二叉樹优炬，現(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方法可以用來尋找一棵樹或是它的任意子樹中的一個特定的值厅贪，這也是為什么在調(diào)用的時候傳入一個節(jié)點作為參數(shù)蠢护。我們在程序開始的時候，需要判斷節(jié)點的合法性养涮，如果是null的話葵硕，說明要找的鍵沒有找到，返回false贯吓。如果傳入的節(jié)點不為null懈凹，就要比較節(jié)點的鍵值和傳入值的鍵值大小。如果傳入值要大悄谐，那就向右邊遍歷二叉搜索樹介评，否則，就向左邊遍歷二叉樹爬舰。

移除節(jié)點

移除節(jié)點是我們在二叉搜索樹中最復(fù)雜的一個们陆，首先我們先創(chuàng)建這個方法。

let remove = function(key){
  root = removeNode (root,key);
};

這個方法接收要移除的鍵并且調(diào)用了removeNode方法情屹，傳入root和要移除的鍵作為參數(shù)棒掠。我們在移除的過程中，root被賦予removeNode方法的返回值屁商，是有一定的意義的烟很。我們會在下面進(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
    // 第一種情況-- 一個葉節(jié)點
    if(node.left === null && node.right === null){
      node = null;
      return node;
    }
    // 第二種情況-- 一個只有一個子節(jié)點的節(jié)點
    if(node.left=== null){
      node = node.right;
      return node;
    }else if(node.right === null){
      node = node.left;
      return node;
   }
   // 第三種情況-- 一個有兩個子節(jié)點的節(jié)點
    let aux = findMinNode(node.right);
    node.key = aux.key;
    node.right = removeNode (node.right,aux.key);
    return node;
  }
}

檢測到的節(jié)點是null，說明鍵值不存在于樹中雾袱，返回null恤筛。我們要做的第一件事情就是從樹中找到這個節(jié)點。因此芹橡，如果要找的鍵比當(dāng)前節(jié)點的值小毒坛，就沿著樹的左邊一直找到下一個節(jié)點，如果找到的鍵比當(dāng)前節(jié)點的鍵值大林说，那么就沿著樹的右邊找到下一個節(jié)點煎殷。
如果我們要找到的鍵(鍵和node.key相等)，據(jù)需要三種不同的情況

let findMinNode = function (node){
  while(node && node.left !== null ){
    node = node.left;
  }
  return node;
}

移除一個葉節(jié)點
這種情況是最簡單最易懂的刪除方式腿箩。
我們要做的就是給這個節(jié)點賦予null值移除它豪直。但是當(dāng)學(xué)習(xí)了鏈表的實現(xiàn)之后，我們知道僅僅是賦予了一個null值是不夠的珠移，還需要處理指針弓乙，這個節(jié)點沒有任何的子節(jié)點，但是有一個父節(jié)點钧惧，需要通過返回null來將對應(yīng)的父節(jié)點指針賦予null值暇韧。
現(xiàn)在節(jié)點的值已經(jīng)是null，父節(jié)點指向它的指針也會接受到這個值浓瞪，這也是我們要在函數(shù)中返回節(jié)點的值的原因懈玻。父節(jié)點總是會接受到函數(shù)的返回值。另外一種可行的辦法是將父節(jié)點和節(jié)點本身都作為參數(shù)傳入方法的內(nèi)部乾颁。

刪除一個葉節(jié)點

移除有一個左側(cè)或右側(cè)子節(jié)點的節(jié)點
現(xiàn)在讓我們來看第二種情況酪刀，移除一個有左側(cè)子節(jié)點，或是右側(cè)子節(jié)點的節(jié)點钮孵，在這種情況下骂倘，我們需要跳過這個節(jié)點，直接將父節(jié)點指向它指針指向的子節(jié)點巴席。
如果這個節(jié)點沒有左側(cè)子節(jié)點历涝，也就是它只有一個右側(cè)子節(jié)點，因此我們那對他的引用改成了對它右側(cè)子節(jié)點的引用漾唉，并返回更新后的節(jié)點∮猓現(xiàn)在讓我們以一張圖片的形式來展現(xiàn)移除只有一個左子節(jié)點或右側(cè)子節(jié)點的節(jié)點的過程。

移除只有一個子節(jié)點的節(jié)點

移除有兩個子節(jié)點的節(jié)點
現(xiàn)在是第三種情況赵刑，也就是最復(fù)雜的情況分衫，那么就是要移除節(jié)點的兩個子節(jié)點-- 左側(cè)子節(jié)點和右側(cè)子節(jié)點。要移除有兩個知己誒單的節(jié)點的時候般此，需要執(zhí)行四個步驟:
（1）找到需要刪除的節(jié)點蚪战。找到他右邊子樹最小的節(jié)點(來代替該節(jié)點的位置)
（2）然后牵现，用他右邊子樹最小的節(jié)點來更新這個節(jié)點的值，通過這一步邀桑，我們改變了這個節(jié)點的鍵瞎疼，也就是說，他被移除了
（3）但是壁畸，這樣的話贼急，樹上就有兩個擁有相同鍵的節(jié)點了，怎樣是不行的捏萍，要繼續(xù)把右子樹的最小節(jié)點進(jìn)行移除太抓，畢竟它已經(jīng)被移到被刪除的節(jié)點的位置了。
（4） 最后令杈，向它的父節(jié)點返回更新后的節(jié)點的引用走敌。
findMinNode方法的實現(xiàn)和min方法的實現(xiàn)方式是一樣的，唯一的不同之處在于这揣，在min方法中只返回鍵，但是findMinNode返回了節(jié)點影斑。

移除有兩個子節(jié)點的節(jié)點