本文内容学习自JavaScript实现二叉树
二叉树
二叉树是每个节点最多有两个子树的树结构。通常子树被称
左子树和右子树。二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。
二叉树的第i层至多有2^{i-1} 个结点（顶层为第一层）
二叉树遍历
前序遍历就是先访问树的根节点，再访问树的左子节点，再访问右子节点。中序遍历就是先访问树的左子节点，再访问树的根节点，再访问右子节点。后序遍历就是先访问树的左子节点，再访问树的右子节点，再访问根节点。
创建二叉树
<!DOCTYPE html>
<html>
<head>
<meta charset="UTF-8">
<title>二叉树</title>
</head>
<body>
<script>
function BinaryTree() {
//创建节点
var Node = function (key) {
this.key = key;
this.left = null;
this.right = null;
}
//创建根节点
var root = null;
this.insert = function (key) { //创建二叉树数据结构
var newNode = new Node(key);
if (root === null) {
root = newNode;
} else {
insertNode(root, newNode);
}
}
var insertNode = 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);
}
}
}
}
</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;
}
}
删除末节点
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;
}
}
}
删除节点 包括末节点和中间节点
this.remove = function (key) {
root = removeNode(root, key);
}
var removeNode = function (node, key) {
if (node === null) {
return null;
}
if (key < node.key) { // 小于此节点的key，node赋值为 node.left 继续遍历
node.left = removeNode(node.left, key);
return node;
} else if (key > node.key) { // 大于此节点的key，node赋值为 node.right 继续遍历
node.right = removeNode(node.right, key);
return node;
} else { // 等于此节点的key ， 1 末节点 ， 2 中间节点
// 末节点直接把此key赋值为null
if (node.left === null && node.right === null) {
node = null;
return node;
}
// 中间节点
// 1，有right 或 left时，把此节点的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 ， 找到此节点右侧的最小值赋值 node = node.right的最小值
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 && 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() {
//创建节点
var Node = function (key) {
this.key = key;
this.left = null;
this.right = null;
}
//创建根节点
var root = null;
this.insert = function (key) { //创建二叉树数据结构
var newNode = new Node(key);
if (root === null) {
root = newNode;
} else {
insertNode(root, newNode);
}
}
var insertNode = 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);
}
}
}
// 中序遍历
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;
}
}
// 删除末节点
// 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;
// }
// }
// }
// 删除节点
this.remove = function (key) {
root = removeNode(root, key);
}
var removeNode = function (node, key) {
if (node === null) {
return null;
}
if (key < node.key) { // 小于此节点的key，node赋值为 node.left 继续遍历
node.left = removeNode(node.left, key);
return node;
} else if (key > node.key) { // 大于此节点的key，node赋值为 node.right 继续遍历
node.right = removeNode(node.right, key);
return node;
} else { // 等于此节点的key ， 1 末节点 ， 2 中间节点
// 末节点直接把此key赋值为null
if (node.left === null && node.right === null) {
node = null;
return node;
}
// 中间节点
// 1，有right 或 left时，把此节点的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 ， 找到此节点右侧的最小值赋值 node = node.right的最小值
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 && 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('------删除末节点‘1’值---------')
// binaryTree.remove(1);
// binaryTree.postOrderTraverse(callback);
console.log('------删除节点3---------')
binaryTree.remove(3);
binaryTree.postOrderTraverse(callback);
</script>
</body>
</html>
