來(lái)自慕課網(wǎng)免費(fèi)教程：https://www.imooc.com/video/15751
做做筆記。
最近才發(fā)現(xiàn)原來(lái)這是《學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)和算法》上的代碼，這是JavaScript中比較好的一本算法書吧，淺顯易懂炊汹。但是作者的一些書寫習(xí)慣有點(diǎn)想不通趴梢，類中所有的屬性包括方法都作為私有屬性皿曲，而應(yīng)該作為私有屬性的卻又作為局部變量蔬将，形成閉包匕累。后面發(fā)現(xiàn)快速排序也有點(diǎn)變種，跟以前學(xué)過(guò)的不太一樣迂求。
但總之也值得一看吧碾盐。
之前也實(shí)現(xiàn)過(guò)鏈表，現(xiàn)在一回憶都忘了揩局，再找當(dāng)時(shí)學(xué)習(xí)時(shí)的代碼文件毫玖，都不知道去哪里了，看來(lái)記錄總是好的凌盯。
二叉排序樹(shù)付枫，又叫二叉搜索樹(shù)，又叫二叉查找樹(shù)驰怎。
其特點(diǎn)就是左子節(jié)點(diǎn)一定小于父節(jié)點(diǎn)阐滩，而右子節(jié)點(diǎn)一定大于父節(jié)點(diǎn)。
如圖就是一個(gè)二叉排序樹(shù)：
（1）創(chuàng)建二叉排序樹(shù)县忌，直接貼代碼了：
function BinaryTree() {
var Node = function(key) {
this.key = key;
this.left = null;
this.right = null;
};
var root = null;
this.getRoot = function() { // 從root開(kāi)始通過(guò)left和right跟其他節(jié)點(diǎn)連接一起掂榔，得到root就相當(dāng)于得到整顆樹(shù)了
return root;
}
this.insert = function(key) {
var newNode = new Node(key);
if (root === null) {
root = newNode;
} else {
insertNode(root, newNode);
}
};
var insertNode = function(node, newNode) { // 構(gòu)建二叉排序樹(shù)
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);
}
}
};
}
var nodes = [8, 3, 10, 1, 6, 14, 4, 7, 13];
var binaryTree = new BinaryTree();
nodes.forEach((key) => {
binaryTree.insert(key);
});
console.log(binaryTree.getRoot());
(2)遍歷
二叉排序樹(shù)的中序遍歷是有序且升序的址儒！
this.inOrderTraverse = function(callback) {
inOrderTraverseNode(root, callback);
};
var inOrderTraverseNode = function(node, callback) { // 中序遍歷
if (node !== null) {
inOrderTraverseNode(node.left, callback); // 遍歷完左子樹(shù)
callback(node.key); //
inOrderTraverseNode(node.right, callback);
}
};
var callback = function(key) {
console.log(key);
}
console.log('中序遍歷:');
binaryTree.inOrderTraverse(callback);
前序，后序都一樣衅疙，之前自己不知道怎么用代碼寫，敲了一遍發(fā)現(xiàn)挺簡(jiǎn)單的鸳慈，換個(gè)位置而已饱溢。直接貼代碼：
this.preOrderTraverse = function(callback) {
preOrderTraverseNode(root, callback)
};
this.postOrderTraverse = function(callback) {
postOrderTraverseNode(root, callback)
};
var preOrderTraverseNode = function(node, callback) {
if (node !== null) {
callback(node.key);
preOrderTraverseNode(node.left, callback);
preOrderTraverseNode(node.right, callback);
}
};
var postOrderTraverseNode = function(node, callback) {
if (node !== null) {
postOrderTraverseNode(node.left, callback);
postOrderTraverseNode(node.right, callback);
callback(node.key);
}
};
前序遍歷對(duì)拷貝一個(gè)二叉樹(shù)來(lái)說(shuō)，比新創(chuàng)建一個(gè)二叉樹(shù)的成本要低很多走芋，前序遍歷效率要高很多绩郎。后序遍歷則可用于文件路徑系統(tǒng)中。
輸出一下：
console.log('前序遍歷:');
binaryTree.preOrderTraverse(callback);
console.log('后序遍歷:');
binaryTree.postOrderTraverse(callback);
（3）最大值翁逞、最小值節(jié)點(diǎn)：
可以看到二叉排序樹(shù)的最小值肋杖、最大值，就是最左邊挖函、最右邊的節(jié)點(diǎn)状植。
this.getMin = function() {
return getMinNode(root);
};
this.getMax = function() {
return getMaxNode(root);
};
var getMinNode = function(node) {
if (node) {
while (node.left) {
node = node.left;
}
return node.key;
}
return null;
};
var getMaxNode = function(node) {
if (node) {
while (node.right) {
node = node.right;
}
return node.key;
}
return null;
};
（4）查找節(jié)點(diǎn)是否存在，返回boolean值
this.search = function(key) {
return searchNode(root, key);
};
var searchNode = function(node, key) {
if (node === null) {
return false;
}
if (key < node.key) {
return searchNode(node.left, key); // 注意遞歸中要return回來(lái)
} else if (key > node.key) {
return searchNode(node.right, key);
} else {
return true;
}
};
（5）刪除節(jié)點(diǎn)
刪除節(jié)點(diǎn)就有點(diǎn)麻煩了怨喘，可分為三種情況：
①刪除葉子節(jié)點(diǎn)：如果是葉子節(jié)點(diǎn)津畸，直接刪除
②刪除有左子樹(shù)或右子樹(shù)其一的節(jié)點(diǎn)：如果只有右子樹(shù)，直接用右子樹(shù)取代該節(jié)點(diǎn)必怜。如果只有左子樹(shù)肉拓，直接用左子樹(shù)取代該節(jié)點(diǎn)。由于二叉排序樹(shù)的特點(diǎn)梳庆，你可以畫一下（比如刪除10或14）暖途，會(huì)發(fā)現(xiàn)結(jié)果還是符合二叉排序樹(shù)的。
③刪除左右子樹(shù)都有的節(jié)點(diǎn)
this.remove = function(key) {
root = removeNode(root, key);
//removeNode(root, key);
};
var removeNode = function(node, key) { // 最終返回的是root元素
if (node === null) {
return null;
}
if (key < node.key) {
node.left = removeNode(node.left, key); // 遞歸的最后一層返回是null膏执，而此時(shí)node即為刪除的節(jié)點(diǎn)的父節(jié)點(diǎn)驻售。遞歸的最前一層返回的是root
return node;
// removeNode(node.left, key);
//return
} else if (key > node.key) {
node.right = removeNode(node.right, key);
//removeNode(node.right, key);
return node;
//return
} else {
if (node.left === null && node.right === null) { // 如果是葉子節(jié)點(diǎn)，直接刪除
//console.log(root.left.left)
node = null;
//root.left.left = null
//console.log(node === root.left.left)
return node;
//return
}
if (node.left === null) { // 如果只有右子樹(shù)胧后，直接用右子樹(shù)取代該節(jié)點(diǎn)
node = node.right;
return node;
//return
} else if (node.right === null) {
node = node.left;
return node;
//return
}
// 當(dāng)有兩個(gè)孩子時(shí)
var aux = findMinNode(node.right);
node.key = aux.key;
node.right = removeNode(node.right, aux.key);
return node;
}
};
var findMinNode = function(node) {
if (node) {
while (node.left) {
node = node.left;
}
return node; // 與前面不同的是返回了node而不是其值芋浮。
}
return null;
};
具體記錄一下，對(duì)于刪除左右子樹(shù)都存在的節(jié)點(diǎn)的情況壳快，比如刪除節(jié)點(diǎn)3纸巷。
其操作是：找到右子樹(shù)所有節(jié)點(diǎn)中的最小節(jié)點(diǎn)（即4），然后將3賦值為該節(jié)點(diǎn)值：
然后再把最小節(jié)點(diǎn)刪除眶痰，結(jié)果如下：
這樣操作后就刪除掉節(jié)點(diǎn)3了瘤旨，且還是保持為二叉排序樹(shù)。
看了這門課還是學(xué)到不少東西的竖伯，這對(duì)于刷編程題會(huì)很有用存哲，后面練習(xí)還沒(méi)看完因宇。看完再記錄一下祟偷。
另外察滑，對(duì)于對(duì)于刪除節(jié)點(diǎn)時(shí)，我開(kāi)始想：不是對(duì)樹(shù)的操作嗎修肠，為什么還要把節(jié)點(diǎn)一層一層的返回贺辰，直接操作完return結(jié)束不就好了？（可以看到我注釋掉的代碼）嵌施。
node = null; // 刪除后不return node會(huì)失敗
//root.left.left = null // 刪除成功
//console.log(node === root.left.left) // true
可是我改完后發(fā)現(xiàn)不成功饲化。才發(fā)現(xiàn)自己的理解還有待加深，趁這個(gè)機(jī)會(huì)再好好總結(jié)了一下關(guān)于JS的引用：http://www.reibang.com/p/bf043921ff58
另外吗伤，必須得刷一下題目才能鞏固：
中序遍歷
前序遍歷
后序遍歷
二叉搜索樹(shù)結(jié)點(diǎn)最小距離
翻轉(zhuǎn)二叉樹(shù)
二叉樹(shù)的最小深度
二叉樹(shù)的最大深度
加一個(gè)層次遍歷：
this.levelOrder = function(callback) {
var arr = [];
levelOrderNode(root, callback, arr);
}
var levelOrderNode = function(node, callback, arr) {
if (node === null) {
return;
}
arr.push(node);
while (arr.length > 0) {
var node = arr.shift();
callback(node.key);
if (node.left) {
arr.push(node.left);
}
if (node.right) {
arr.push(node.right);
}
}
}
