code前端网Javascript数据结构和算法：二叉树和二叉搜索树
1 树
树结构包含一系列具有父子关系的节点。每个节点都有一个父节点（上面第一个节点除外）和零个或多个子节点。树顶部的节点称为根节点 (11)。没有父节点。树中的每个元素称为节点，节点分为内部节点和外部节点。具有至少一个子节点的节点称为内部节点。没有子元素的节点称为外部节点或叶节点。节点的属性之一是其深度，这取决于其祖先的数量。树的高度由所有节点的最大宽度决定。树也可以分为层次。根节点位于级别 0，子节点位于级别 1，依此类推。
1.1 二叉树和二叉搜索树
二叉树中的一个节点最多只能有两个子节点：一个是左子节点，一个是右子节点。这些定义帮助我们编写更有效的算法来插入、查找和删除树中的节点。
对于二叉搜索树，我们一般需要实现如下方法：
- insert(key)：在书中插入一个新的key。
- search(key)：在树中搜索key，如果节点存在则返回true，否则返回false。
- inOrderTraverse：通过遍历顺序遍历所有节点。
- preOrderTraverse：通过前序遍历的方式遍历所有节点。
- postOrderTraverse：通过订单发布遍历所有节点。
- min：返回树中最小的键/值。
- max：返回树中最大的键/值。
- remove(key)：从树中删除一个键。
1.1.1 二叉搜索树遍历
二叉搜索树（BST）是二叉树的一种，但它只允许你在左节点存储较小的值（来自父节点），而在右节点存储大于（或等于）父节点的较大值。
中序遍历是按照升序访问所有BST节点的遍历方法，即按照从小到大的顺序访问所有节点。中序遍历的一种应用是树排序。
前序遍历根据每个节点对其后代节点的偏好来访问该节点。预序遍历的一种应用是打印结构化文档。前序遍历和中序遍历的区别在于，前序遍历首先访问节点，然后访问左子节点，最后访问右子节点。
后序遍历首先访问节点的后代，然后访问节点本身。后序遍历的一种应用是计算目录及其子目录中所有文件的大小。
在树中经常执行三种类型的搜索：最小值、最大值和特定值搜索。
1.1.2 二叉搜索树的基本实现和使用
下面的 minNode 方法允许我们从树中的节点开始找到最小的键。我们可以用它来查找树或子树中的最小键。因此，我们在调用minNode方法时传递树的根节点（第{1}行），因为我们要找到整棵树的最小键。
代码中的一些内部方法也可以写成二叉树结构的属性，以便灵活引用。这里我们不会做任何具体的修改。
function BinarySearchTree() {
function Node(key) {
this.key = key;
this.left = null;
this.right = null;
}
this.root = null;
if ((typeof this.insert !== 'function') && (typeof this.insert !== 'string')) {
//内部私有方法，用于插入节点
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);
}
}
}
BinarySearchTree.prototype.insert = function(key) {
var newNode = new Node(key);
if (this.root === null) {
this.root = newNode;
} else {
insertNode(this.root, newNode);
}
};
BinarySearchTree.prototype.inOrderTraverse = function(callback) {
//中序遍历的私有方法,从小到大遍历
function inOrderTraverseNode(node, callback) {
if (node !== null) {
inOrderTraverseNode(node.left, callback);
callback(node.key);
inOrderTraverseNode(node.right, callback);
}
}
inOrderTraverseNode(this.root, printNode);
};
BinarySearchTree.prototype.preOrderTraverse = function(callback){
function preOrderTraverseNode(node,callback){
if (node !== null) {
callback(node.key);
preOrderTraverseNode(node.left,callback);
preOrderTraverseNode(node.right,callback);
}
}
preOrderTraverseNode(this.root,callback);
};
BinarySearchTree.prototype.postOrderTraverse = function(callback){
function postOrderTraverseNode(node,callback){
if (node !== null) {
postOrderTraverseNode(node.left,callback);
postOrderTraverseNode(node.right,callback);
callback(node.key);
}
}
postOrderTraverseNode(this.root,callback);
};
BinarySearchTree.prototype.min = function(){
function minNode(node){
if (node) {
while(node && node.left !== null){
node = node.left;
}
return node.key;
}
return null;
}
//调用内部方法
return minNode(this.root);
};
BinarySearchTree.prototype.max = function(){
function maxNode(node){
if (node) {
while(node && node.right !== null){
node = node.right;
}
return node.key;
}
return null;
}
//调用内部方法
return maxNode(this.root);
};
BinarySearchTree.prototype.search = function(key){
function searchNode(node,key){
if (node === null) {
return false;
}
if (node.key < key) {
return searchNode(node.right,key);
}else if(node.key > key){
return searchNode(node.left,key);
}else{
return true;
}
}
return searchNode(this.root,key);
};
BinarySearchTree.prototype.remove = function(key){
function findMinNode(node){
if (node) {
while(node && node.left !== null){
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{//键等于node.key
//第一种情况，一个叶节点
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;
}
//第三种情况 一个有两个子节点的节点
var aux = findMinNode(node.right);
node.key = aux.key;
node.right = removeNode(node.right,aux.key);
return node;
}
}
this.root = removeNode(this.root,key);
};
}
}
二叉树基的使用：
//遍历节点操作
function printNode(value) {
console.log(value);
}
var tree = new BinarySearchTree();
tree.insert(11);
tree.insert(7);
tree.insert(15);
tree.insert(5);
tree.insert(3);
tree.insert(9);
tree.insert(8);
tree.insert(10);
tree.insert(13);
tree.insert(12);
tree.insert(14);
tree.insert(20);
tree.insert(18);
tree.insert(25);
tree.insert(6);
//中序遍历
tree.inOrderTraverse(printNode);//3 5 6 7 8 9 10 11 12 13 14 15 18 20 25
//先序遍历
tree.preOrderTraverse(printNode);//11 7 5 3 6 9 8 10 15 13 12 14 20 18 25
//后序遍历
tree.postOrderTraverse(printNode);//3 6 5 8 10 9 7 12 14 13 18 25 20 15 11
console.log(tree.min());
console.log(tree.max());
//搜索
console.log(tree.search(1) ? 'Key 1 found.' : 'Key 1 not found.');//Key 1 not found.
console.log(tree.search(8) ? 'Key 8 found.' : 'Key 8 not found.');//Key 8 found.
//移除节点
tree.remove(15);
tree.inOrderTraverse(printNode);////3 5 6 7 8 9 10 11 12 13 14 15 18 20 25
//console.log(tree.remove(100));版权声明
本文仅代表作者观点，不代表Code前端网立场。
本文系作者Code前端网发表，如需转载，请注明页面地址。
相关文章
