——記錄下來以便將來看看現(xiàn)在的自己
看到掘金上@MaevynZhang有篇博文講關(guān)于JS二叉樹的，寫得有點(diǎn)骨干竟贯，處女座表示看不下去了码泛！ 我來自遙遠(yuǎn)的燕國，為了天下黎民澄耍，以正視聽。
??上面那位作者他直接把一個(gè)二叉樹的結(jié)構(gòu)數(shù)據(jù)生成一個(gè)二叉樹實(shí)例
這數(shù)據(jù)定的太絕了吧+_+這要要前端搬板凳吃瓜的節(jié)奏啊晌缘。吐槽截止齐莲，開始講二叉樹！
??二叉樹的一個(gè)節(jié)點(diǎn)Node由data磷箕，left选酗，right組成，data保存本節(jié)點(diǎn)的值岳枷，left指向左節(jié)點(diǎn)芒填，right指向右節(jié)點(diǎn)。二叉樹有一個(gè)<b>特殊性:相對(duì)本節(jié)點(diǎn)較小的值保存在左節(jié)點(diǎn)空繁，相對(duì)本節(jié)點(diǎn)較大的值保存在右節(jié)點(diǎn)</b>殿衰，該特性能讓查值效率提高！
創(chuàng)建Node實(shí)例
/*
* parameter: data:本節(jié)點(diǎn)的數(shù)據(jù)盛泡；left：做節(jié)點(diǎn)闷祥；right：右節(jié)點(diǎn)
*/
function Node(data,left,right){
this.data = data;
this.left = left;
this.right = right;
}
function BST(){
this.root = null;
this.insert = insert;
}
/*
* parameter: data:本節(jié)點(diǎn)的數(shù)據(jù)；
* 創(chuàng)建節(jié)點(diǎn)示例并插入到二叉樹的正確位置
*/
function Node(data,left,right){
this.data = data;
this.left = left;
this.right = right;
}
function BST(){
this.root = null;
this.insert = insert;
}
function insert(data){
var node = new Node(data,null,null);
if(this.root == null){
this.root = node;
}else{
var current = this.root;
while(true){
if(current.data > data){
if(current.left === null){
current.left = node;
break;
}
current = current.left;
}else{
if(current.right === null){
current.right = node;
break;
}
current = current.right;
}
}
}
}
var bst = new BST();
bst.insert(5);
bst.insert(3);
bst.insert(7);
bst.insert(2);
看代碼應(yīng)該能看出Node是怎么插入二叉樹的傲诵，下圖是代碼打印出來的樹狀結(jié)構(gòu)
??創(chuàng)建二叉樹代碼完成凯砍，現(xiàn)在你可能高潮了，原來創(chuàng)建二叉樹這么簡單啊拴竹，那它有什么優(yōu)點(diǎn)或者缺點(diǎn)呢悟衩？二叉樹的優(yōu)點(diǎn)是查找值最快，最小值和最大值分別位于兩端栓拜，查找指定值如下：
function find(data){
var current = this.root;
while(true){
if(data === current.data){
return current;
}
current = data < current.data ? current.left : current.right;
if(current === null){
return null;
}
}
}
這種查找值類似二分法座泳，比列表查值快了很多惠昔，數(shù)據(jù)量越多，二叉樹比列表查值的速度就越快钳榨！ （如果只是比查值效率舰罚，二分法肯定比二叉樹快，但是應(yīng)用場景不同薛耻，二分法適用在如1~100依次遞增順序列表中营罢；二叉樹可以應(yīng)用在任何數(shù)字或者字符組成的數(shù)據(jù)結(jié)構(gòu)中）。
??刪除節(jié)點(diǎn)中心思想：如果刪除節(jié)點(diǎn)是葉子節(jié)點(diǎn)饼齿，則將父節(jié)點(diǎn)指向null饲漾；如果刪除節(jié)點(diǎn)有一個(gè)子節(jié)點(diǎn)，則將父節(jié)點(diǎn)指向刪除節(jié)點(diǎn)的子節(jié)點(diǎn)缕溉；如果刪除節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)考传，這個(gè)本文不寫，因?yàn)檫@個(gè)有點(diǎn)不合適（腦補(bǔ)）证鸥！
function remove(data){
this.root = removeNode(this.root,data);
}
function removeNode(node,data){
if(node === null){
return null;
}
if(data === node.data){
if(node.left === null && node.right === null){
return null;
}
if(node.left === null){
return node.right;
}
if(node.right === null){
return node.left;
}
}else if(data < node.data){
node.left = removeNode(node.left,data);
return node;
}else{
node.right = removeNode(node.right,data);
return node;
}
}
刪除節(jié)點(diǎn)的代碼我摘抄自《數(shù)據(jù)結(jié)構(gòu)與算法JavaScript描述》僚楞，寫得確實(shí)驚艷，感嘆代碼魅力枉层。
最后整合代碼:
function Node(data,left,right){
this.data = data;
this.left = left;
this.right = right;
}
function BST(){
this.root = null;
this.insert = insert;
this.find = find;
this.remove = remove;
}
/*
* 二叉樹增加節(jié)點(diǎn)
*/
function insert(data){
var node = new Node(data,null,null);
if(this.root == null){
this.root = node;
}else{
var current = this.root;
while(true){
if(current.data > data){
if(current.left === null){
current.left = node;
break;
}
current = current.left;
}else{
if(current.right === null){
current.right = node;
break;
}
current = current.right;
}
}
}
}
/*
* 二叉樹查節(jié)點(diǎn)
*/
function find(data){
var current = this.root;
while(true){
if(data === current.data){
return current;
}
current = data < current.data ? current.left : current.right;
if(current === null){
return null;
}
}
}
/*
* 二叉樹刪除節(jié)點(diǎn) (只刪除葉子節(jié)點(diǎn)泉褐、只有一個(gè)子節(jié)點(diǎn)的Node
*/
function remove(data){
this.root = removeNode(this.root,data);
}
function removeNode(node,data){
if(node === null){
return null;
}
if(data === node.data){
if(node.left === null && node.right === null){
return null;
}
if(node.left === null){
return node.right;
}
if(node.right === null){
return node.left;
}
}else if(data < node.data){
node.left = removeNode(node.left,data);
return node;
}else{
node.right = removeNode(node.right,data);
return node;
}
}
var bst = new BST();
bst.insert(5);
bst.insert(3);
bst.insert(7);
bst.insert(2);
bst.remove(2);
二叉樹的缺點(diǎn)：如果節(jié)點(diǎn)要頻繁刪除的話，不適合使用二叉樹鸟蜡，特別是被刪除的節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)的膜赃；
??二叉樹的優(yōu)點(diǎn)：查找無規(guī)律的數(shù)字或者字母的數(shù)據(jù)結(jié)構(gòu)適合二叉樹的使用場景！
數(shù)據(jù)結(jié)構(gòu)路路漫漫揉忘，吾將上下其手跳座，老妹驚叫連連。有什么問題可以在評(píng)論區(qū)留言哦泣矛，共同進(jìn)步+_+
