本文內(nèi)容學習自JavaScript實現(xiàn)二叉樹
二叉樹
二叉樹是每個節(jié)點最多有兩個子樹的樹結(jié)構(gòu)压昼。通常子樹被稱
左子樹和右子樹。二叉樹的每個結(jié)點至多只有二棵子樹(不存在度大于2的結(jié)點)瘤运，二叉樹的子樹有左右之分窍霞，次序不能顛倒。
二叉樹的第i層至多有2^{i-1} 個結(jié)點（頂層為第一層）
二叉樹遍歷
前序遍歷就是先訪問樹的根節(jié)點拯坟，再訪問樹的左子節(jié)點但金，再訪問右子節(jié)點。中序遍歷就是先訪問樹的左子節(jié)點郁季，再訪問樹的根節(jié)點冷溃，再訪問右子節(jié)點。后序遍歷就是先訪問樹的左子節(jié)點梦裂，再訪問樹的右子節(jié)點似枕，再訪問根節(jié)點。
創(chuàng)建二叉樹
<!DOCTYPE html>
<html>
<head>
<meta charset="UTF-8">
<title>二叉樹</title>
</head>
<body>
<script>
function BinaryTree() {
//創(chuàng)建節(jié)點
var Node = function (key) {
this.key = key;
this.left = null;
this.right = null;
}
//創(chuàng)建根節(jié)點
var root = null;
this.insert = function (key) { //創(chuàng)建二叉樹數(shù)據(jù)結(jié)構(gòu)
var newNode = new Node(key);
if (root === null) {
root = newNode;
} else {
insertNode(root, newNode);
}
}
var insertNode = function (node, newNode) { // 比較節(jié)點年柠，插入到相應節(jié)點的左右節(jié)點上
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);
}
}
}
}
</script>
</body>
</html>
中序遍歷
// 中序遍歷
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);
}
前序遍歷
// 前序遍歷
this.preOrderTraverse = function (callback) {
preOrderTraverseNode(root, callback);
}
var preOrderTraverseNode = function (node, callback) {
if (node !== null) {
callback(node.key);
preOrderTraverseNode(node.left, callback);
preOrderTraverseNode(node.right, callback);
}
}
var callback = function (key) {
console.log(key);
}
后序遍歷
this.postOrderTraverse = function (callback) {
postOrderTraverseNode(root, callback);
}
var postOrderTraverseNode = function (node, callback) {
if (node !== null) {
postOrderTraverseNode(node.left, callback);
postOrderTraverseNode(node.right, callback);
callback(node.key);
}
}
var callback = function (key) {
console.log(key);
}
最小值
this.min = function () {
return minNode(root);
}
var minNode = function (node) {
if (node) {
while (node && node.left !== null) {
node = node.left;
}
return node.key;
}
return null;
}
最大值
this.max = function () {
return maxNode(root);
}
var maxNode = function (node) {
if (node) {
while (node && node.right !== null) {
node = node.right;
}
return node.key;
}
return null;
}
查找某個值
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);
} else if (key > node.key) {
return searchNode(node.right, key);
} else {
return true;
}
}
刪除末節(jié)點
this.remove = function (key) {
root = removeNode(root, key);
}
var removeNode = function (node, key) {
if (node === null) {
return null;
}
if (key < node.key) {
node.left = removeNode(node.left, key);
return node;
} else if (key > node.key) {
node.right = removeNode(node.right, key);
return node;
} else {
if (node.left === null && node.right === null) {
node = null;
return node;
}
}
}
刪除節(jié)點 包括末節(jié)點和中間節(jié)點
this.remove = function (key) {
root = removeNode(root, key);
}
var removeNode = function (node, key) {
if (node === null) {
return null;
}
if (key < node.key) { // 小于此節(jié)點的key凿歼，node賦值為 node.left 繼續(xù)遍歷
node.left = removeNode(node.left, key);
return node;
} else if (key > node.key) { // 大于此節(jié)點的key，node賦值為 node.right 繼續(xù)遍歷
node.right = removeNode(node.right, key);
return node;
} else { // 等于此節(jié)點的key 冗恨， 1 末節(jié)點 答憔， 2 中間節(jié)點
// 末節(jié)點直接把此key賦值為null
if (node.left === null && node.right === null) {
node = null;
return node;
}
// 中間節(jié)點
// 1，有right 或 left時掀抹，把此節(jié)點的left或right賦值為node = node.left 或 node = node.right
if (node.left === null) {
node = node.right;
return node;
} else if (node.right === null) {
node = node.left;
return node;
}
// 2攀唯，同時有right和left ， 找到此節(jié)點右側(cè)的最小值賦值 node = node.right的最小值
var aux = findMinNode(node.right);
node.key = aux.key;
node.right = removeNode(node.right, aux.key);
return node;
}
}
//找到最小節(jié)點
var findMinNode = function (node) {
if (node) {
while (node && node.left !== null) {
node = node.left;
}
return node;
}
return null;
}
完整代碼
<!DOCTYPE html>
<html>
<head>
<meta charset="UTF-8">
<title>二叉樹</title>
</head>
<body>
<script>
function BinaryTree() {
//創(chuàng)建節(jié)點
var Node = function (key) {
this.key = key;
this.left = null;
this.right = null;
}
//創(chuàng)建根節(jié)點
var root = null;
this.insert = function (key) { //創(chuàng)建二叉樹數(shù)據(jù)結(jié)構(gòu)
var newNode = new Node(key);
if (root === null) {
root = newNode;
} else {
insertNode(root, newNode);
}
}
var insertNode = function (node, newNode) { // 比較節(jié)點渴丸，插入到相應節(jié)點的左右節(jié)點上
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);
}
}
}
// 中序遍歷
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);
}
}
// 前序遍歷
this.preOrderTraverse = function (callback) {
preOrderTraverseNode(root, callback);
}
var preOrderTraverseNode = function (node, callback) {
if (node !== null) {
callback(node.key);
preOrderTraverseNode(node.left, callback);
preOrderTraverseNode(node.right, callback);
}
}
// 后序遍歷
this.postOrderTraverse = function (callback) {
postOrderTraverseNode(root, callback);
}
var postOrderTraverseNode = function (node, callback) {
if (node !== null) {
postOrderTraverseNode(node.left, callback);
postOrderTraverseNode(node.right, callback);
callback(node.key);
}
}
// 最小值
this.min = function () {
return minNode(root);
}
var minNode = function (node) {
if (node) {
while (node && node.left !== null) {
node = node.left;
}
return node.key;
}
return null;
}
// 最大值
this.max = function () {
return maxNode(root);
}
var maxNode = function (node) {
if (node) {
while (node && node.right !== null) {
node = node.right;
}
return node.key;
}
return null;
}
// 查找某個值
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);
} else if (key > node.key) {
return searchNode(node.right, key);
} else {
return true;
}
}
// 刪除末節(jié)點
// this.remove = function (key) {
// root = removeNode(root, key);
// }
// var removeNode = function (node, key) {
// if (node === null) {
// return null;
// }
// if (key < node.key) {
// node.left = removeNode(node.left, key);
// return node;
// } else if (key > node.key) {
// node.right = removeNode(node.right, key);
// return node;
// } else {
// if (node.left === null && node.right === null) {
// node = null;
// return node;
// }
// }
// }
// 刪除節(jié)點
this.remove = function (key) {
root = removeNode(root, key);
}
var removeNode = function (node, key) {
if (node === null) {
return null;
}
if (key < node.key) { // 小于此節(jié)點的key，node賦值為 node.left 繼續(xù)遍歷
node.left = removeNode(node.left, key);
return node;
} else if (key > node.key) { // 大于此節(jié)點的key，node賦值為 node.right 繼續(xù)遍歷
node.right = removeNode(node.right, key);
return node;
} else { // 等于此節(jié)點的key 谱轨， 1 末節(jié)點 戒幔， 2 中間節(jié)點
// 末節(jié)點直接把此key賦值為null
if (node.left === null && node.right === null) {
node = null;
return node;
}
// 中間節(jié)點
// 1，有right 或 left時土童，把此節(jié)點的left或right賦值為node = node.left 或 node = node.right
if (node.left === null) {
node = node.right;
return node;
} else if (node.right === null) {
node = node.left;
return node;
}
// 2诗茎，同時有right和left ， 找到此節(jié)點右側(cè)的最小值賦值 node = node.right的最小值
var aux = findMinNode(node.right);
node.key = aux.key;
node.right = removeNode(node.right, aux.key);
return node;
}
}
//找到最小節(jié)點
var findMinNode = function (node) {
if (node) {
while (node && node.left !== null) {
node = node.left;
}
return node;
}
return null;
}
}
var callback = function (key) {
console.log(key);
}
var nodes = [8, 3, 10, 1, 6, 14, 4, 7, 13];
var binaryTree = new BinaryTree();
nodes.forEach(function (key) {
binaryTree.insert(key);
})
console.log('------中序遍歷---------')
binaryTree.inOrderTraverse(callback);
console.log('------前序遍歷---------')
binaryTree.preOrderTraverse(callback);
console.log('------后序遍歷---------')
binaryTree.postOrderTraverse(callback);
console.log('------最小值---------')
console.log(binaryTree.min());
console.log('------最大值---------')
console.log(binaryTree.max());
console.log('------某個值---------')
console.log(binaryTree.search(3));
console.log(binaryTree.search(2));
// console.log('------刪除末節(jié)點‘1’值---------')
// binaryTree.remove(1);
// binaryTree.postOrderTraverse(callback);
console.log('------刪除節(jié)點3---------')
binaryTree.remove(3);
binaryTree.postOrderTraverse(callback);
</script>
</body>
</html>
