JS实现BinaryTree

60 阅读 0 评论 40 点赞

我是靠谱客的博主粗暴香菇，最近开发中收集的这篇文章主要介绍JS实现BinaryTree，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

JS实现BinaryTree


<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<meta http-equiv="X-UA-Compatible" content="ie=edge">
<title>Document</title>
</head>
<body>
<script>
function BinaryTree() {
function Node(key) {
this.key = key;
this.left = null;
this.right = null;
}
this.root = null;
function insertNode(node, newNode) {
if (node.key > newNode.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.insert = function (key) {
var newNode = new Node(key);
if (this.root === null) {
this.root = newNode;
} else {
insertNode(this.root, newNode);
}
}
function inOrderTraverseNode(node, callback) {
if (node !== null) {
inOrderTraverseNode(node.left, callback);
callback(node.key);
inOrderTraverseNode(node.right, callback);
}
}
this.inOrderTraverse = function (callback) {
inOrderTraverseNode(this.root, callback);
}
function preOrderTraverseNode(node, callback) {
if (node !== null) {
callback(node.key);
preOrderTraverseNode(node.left, callback);
preOrderTraverseNode(node.right, callback);
}
}
this.preOrderTraverse = function (callback) {
preOrderTraverseNode(this.root, callback);
}
function postOrderTraverseNode(node, callback) {
if (node !== null) {
postOrderTraverseNode(node.left, callback);
postOrderTraverseNode(node.right, callback);
callback(node.key);
}
}
this.postOrderTraverse = function (callback) {
postOrderTraverseNode(this.root, callback);
}
function minNode(node) {
if (node) {
while (node.left) {
node = node.left;
}
return node.key;
}
return null;
}
this.min = function () {
return minNode(this.root);
}
function maxNode(node) {
if (node) {
while (node.right) {
node = node.right;
}
return node.key;
}
return null;
}
this.max = function () {
return maxNode(this.root);
}
function searchNode(node, key) {
if (node === null) {
return false;
}
if (key > node.key) {
return searchNode(node.right, key);
} else if (node.key > key) {
return searchNode(node.left, key);
} else {
return node.key;
}
}
this.search = function (key) {
return searchNode(this.root, key);
}
function findMinNode(node) {
if (node) {
while (node.left) {
node = node.left;
}
return node;
}
return null;
}
function removeNode(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;
}
if (node.left === null) {
node = node.right;
return node;
} else if (node.right === null) {
node = node.left;
return node;
} else {
var aux = findMinNode(node.right);
node.key = aux.key;
node.right = removeNode(node.right, aux.key);
return node;
}
}
}
this.remove = function (key) {
return removeNode(this.root, key);
}
}
let items = [8, 3, 13, 1, 6, 14, 4, 7, 10];
const binaryTree = new BinaryTree();
items.forEach((item, index) => {
binaryTree.insert(item);
});
// 先序遍历
binaryTree.inOrderTraverse(key => console.log(key));
// 后序遍历
binaryTree.preOrderTraverse(key => console.log(key));
// 寻找二叉树最大节点元素
console.log('binaryTree max node is: ' + binaryTree.max());
// 寻找二叉树最小节点元素
console.log('binaryTree min node is: ' + binaryTree.min());
// 寻找二叉树节点元素
console.log(binaryTree.search(7) ? 'key 7 is found' : 'key 7 is not found');
console.log(binaryTree.search(9) ? 'key 9 is found' : 'key 9 is not found');
// binaryTree.remove(3);
// 二叉树的根节点
console.log(binaryTree.root)
</script>
</body>
</html>