Javascript 数据结构与算法：二叉树和二叉搜索树
1 树
一个树结构包含一系列存在父子关系的节点。每个节点都有一个父节点(除了顶部的第一个节点)以及零个或多个子节点。位于树顶部的节点叫作根节点(11)。它没有父节点。树中的每个元素都叫作节点,节点分 为内部节点和外部节点。至少有一个子节点的节点称为内部节点。没有子元素的节点称为外部节点或叶节点。节点的一个属性是深度,节点的深度取决于它的祖先节点的数量。树的高度取决于所有节点深度的最大值。一棵树也可以被分解成层级。根节点在第0层,它 的子节点在第1层,以此类推。
1.1 二叉树和二叉搜索树
二叉树中的节点最多只能有两个子节点:一个是左侧子节点,另一个是右侧子节点。这些定义有助于我们写出更高效的向树中插入、查找和删除节点的算法。
对于二叉搜索树，我们一般需要实现如下方法：
- insert(key): 向书中插入一个新的键。
- search(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));
THE END
