來自慕課網(wǎng)免費教程：https://www.imooc.com/video/15751
做做筆記。
最近才發(fā)現(xiàn)原來這是《學習JavaScript數(shù)據(jù)結(jié)構(gòu)和算法》上的代碼，這是JavaScript中比較好的一本算法書吧，淺顯易懂。但是作者的一些書寫習慣有點想不通，類中所有的屬性包括方法都作為私有屬性，而應(yīng)該作為私有屬性的卻又作為局部變量，形成閉包。后面發(fā)現(xiàn)快速排序也有點變種，跟以前學過的不太一樣。
但總之也值得一看吧。
之前也實現(xiàn)過鏈表，現(xiàn)在一回憶都忘了，再找當時學習時的代碼文件，都不知道去哪里了，看來記錄總是好的。
二叉排序樹，又叫二叉搜索樹，又叫二叉查找樹。
其特點就是左子節(jié)點一定小于父節(jié)點，而右子節(jié)點一定大于父節(jié)點。
如圖就是一個二叉排序樹：
（1）創(chuàng)建二叉排序樹，直接貼代碼了：
function BinaryTree() {
var Node = function(key) {
this.key = key;
this.left = null;
this.right = null;
};
var root = null;
this.getRoot = function() { // 從root開始通過left和right跟其他節(jié)點連接一起，得到root就相當于得到整顆樹了
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)建二叉排序樹
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)遍歷
二叉排序樹的中序遍歷是有序且升序的！
this.inOrderTraverse = function(callback) {
inOrderTraverseNode(root, callback);
};
var inOrderTraverseNode = function(node, callback) { // 中序遍歷
if (node !== null) {
inOrderTraverseNode(node.left, callback); // 遍歷完左子樹
callback(node.key); //
inOrderTraverseNode(node.right, callback);
}
};
var callback = function(key) {
console.log(key);
}
console.log('中序遍歷:');
binaryTree.inOrderTraverse(callback);
前序，后序都一樣，之前自己不知道怎么用代碼寫，敲了一遍發(fā)現(xiàn)挺簡單的，換個位置而已。直接貼代碼：
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);
}
};
前序遍歷對拷貝一個二叉樹來說，比新創(chuàng)建一個二叉樹的成本要低很多，前序遍歷效率要高很多。后序遍歷則可用于文件路徑系統(tǒng)中。
輸出一下：
console.log('前序遍歷:');
binaryTree.preOrderTraverse(callback);
console.log('后序遍歷:');
binaryTree.postOrderTraverse(callback);
（3）最大值、最小值節(jié)點：
可以看到二叉排序樹的最小值、最大值，就是最左邊、最右邊的節(jié)點。
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é)點是否存在，返回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回來
} else if (key > node.key) {
return searchNode(node.right, key);
} else {
return true;
}
};
（5）刪除節(jié)點
刪除節(jié)點就有點麻煩了，可分為三種情況：
①刪除葉子節(jié)點：如果是葉子節(jié)點，直接刪除
②刪除有左子樹或右子樹其一的節(jié)點：如果只有右子樹，直接用右子樹取代該節(jié)點。如果只有左子樹，直接用左子樹取代該節(jié)點。由于二叉排序樹的特點，你可以畫一下（比如刪除10或14），會發(fā)現(xiàn)結(jié)果還是符合二叉排序樹的。
③刪除左右子樹都有的節(jié)點
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，而此時node即為刪除的節(jié)點的父節(jié)點。遞歸的最前一層返回的是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é)點，直接刪除
//console.log(root.left.left)
node = null;
//root.left.left = null
//console.log(node === root.left.left)
return node;
//return
}
if (node.left === null) { // 如果只有右子樹，直接用右子樹取代該節(jié)點
node = node.right;
return node;
//return
} else if (node.right === null) {
node = node.left;
return node;
//return
}
// 當有兩個孩子時
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;
};
具體記錄一下，對于刪除左右子樹都存在的節(jié)點的情況，比如刪除節(jié)點3。
其操作是：找到右子樹所有節(jié)點中的最小節(jié)點（即4），然后將3賦值為該節(jié)點值：
然后再把最小節(jié)點刪除，結(jié)果如下：
這樣操作后就刪除掉節(jié)點3了，且還是保持為二叉排序樹。
看了這門課還是學到不少東西的，這對于刷編程題會很有用，后面練習還沒看完?？赐暝儆涗浺幌?。
另外，對于對于刪除節(jié)點時，我開始想：不是對樹的操作嗎，為什么還要把節(jié)點一層一層的返回，直接操作完return結(jié)束不就好了？（可以看到我注釋掉的代碼）。
node = null; // 刪除后不return node會失敗
//root.left.left = null // 刪除成功
//console.log(node === root.left.left) // true
可是我改完后發(fā)現(xiàn)不成功。才發(fā)現(xiàn)自己的理解還有待加深，趁這個機會再好好總結(jié)了一下關(guān)于JS的引用：http://www.itdecent.cn/p/bf043921ff58
另外，必須得刷一下題目才能鞏固：
中序遍歷
前序遍歷
后序遍歷
二叉搜索樹結(jié)點最小距離
翻轉(zhuǎn)二叉樹
二叉樹的最小深度
二叉樹的最大深度
加一個層次遍歷：
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);
}
}
}
