读【数据结构与算法】之二叉树
树是在计算机科学中经常用到的一种数据结构。树是非线性的数据结构，以分层的方式存储数据。在二叉树上进行查找非常快（在链表上查找就不是这样了），为二叉树添加或删除元素也非常快的（对数组添加或删除则不是这样）。
树由一组以边连接的节点组成。一棵树最上面的节点叫根节点，如果一个节点下面连接多个节点，那么该节点就称为父节点，他下面的节点称为子节点。没有任何子节点的节点称为叶子节点。沿着一组特定的边，可以从一个节点走到另外一个与他不直接连接的节点。从一个节点到另一个节点的这一组边称为路径。以某种特定顺序访问树中所有的节点称为树的遍历。
树可以分为几个层次，根节点就是第0层，他的子节点就是第1层，子节点的子节点是第2层，以此类推。树中的任何一层的节点都可以看做是子树的根。我们定义树的层数就是树的深度。
一个父节点的两个子节点分别称为左节点和右节点。
二叉树是一种特殊的树，他的子节点个数不超过两个。在一些二叉树的实现中，左节点包含一组特定的值，右节点包含另一组特定的值。
二叉查找树（BST）是一种特殊的二叉树，相对较小的值保存在左节点中，较大的值保存在右节点中。这样的特性使得他的查找效率很高。
BST由节点组成，所以需要定义节点Node类。下边的是其基本实现：
/**
* Class Node
* 节点 Node
*/
function Node(data, left, right) {
this.data = data;
this.left = left;
this.right = right;
}
Node.prototype = {
constructor: Node,
/**
* 显示保存节点中的数据
* @return {Any} 数据
*/
show: function show() {
return this.data;
}
};
有了节点，现在就可以实现一个简单的BST类了，目前只有一个加入节点insert操作：
/**
* Class BST
* 二叉查找树 BST
*/
function BST() {
this.root = null;
}
BST.prototype = {
constructor: BST,
/**
* 加入新节点
* @param {Any} data 节点数据
* @return {Undefined} undefined
*/
insert: function insert(data) {
var n = new Node(data, null, null);
if (this.root == null) {
this.root = n;
} else {
var current = this.root, parent, k;
while (true) {
parent = current;
if (data < current.data) {
// 进入左节点
k = 'left';
} else {
// 进入左节点
k = 'right';
}
current = current[k];
if (current == null) {
// 没有k节点
parent[k] = n;
break;
}
}
}
}
};
下一步就需要对二叉树进行遍历了，有三种遍历方式：中序、先序和后序。中序遍历就是按照节点上的键值，以升序访问BST节点上的所有节点。先序遍历就是先访问根节点，然后以同样的方式访问左子树和右子树。后序遍历就是先访问叶子节点，从左子树到右子树，然后再到根节点。
下边的代码是加入了三种遍历之后的样子：
/**
* Class BST
* 二叉查找树 BST
*/
function BST() {
this.root = null;
}
BST.prototype = {
constructor: BST,
/**
* 加入新节点
* @param {Any} data 节点数据
* @return {Undefined} undefined
*/
insert: function insert(data) {
var n = new Node(data, null, null);
if (this.root == null) {
this.root = n;
} else {
var current = this.root, parent, k;
while (true) {
parent = current;
if (data < current.data) {
// 进入左节点
k = 'left';
} else {
// 进入左节点
k = 'right';
}
current = current[k];
if (current == null) {
// 没有k节点
parent[k] = n;
break;
}
}
}
},
/**
* 中序遍历
* @param {Node} node 节点
* @param {Array} ret 结果
* @return {Array} 结果数组
*/
inOrder: function inOrder(node, ret) {
if (!ret) ret = [];
if (node != null) {
inOrder(node.left, ret);
ret.push(node.show());
inOrder(node.right, ret);
}
return ret;
},
/**
* 先序遍历
* @param {Node} node 节点
* @param {Array} ret 结果
* @return {Array} 结果数组
*/
preOrder: function preOrder(node, ret) {
if (!ret) ret = [];
if (node != null) {
ret.push(node.show());
preOrder(node.left, ret);
preOrder(node.right, ret);
}
return ret;
},
/**
* 后序遍历
* @param {Node} node 节点
* @param {Array} ret 结果
* @return {Array} 结果数组
*/
postOrder: function postOrder(node, ret) {
if (!ret) ret = [];
if (node != null) {
postOrder(node.left, ret);
postOrder(node.right, ret);
ret.push(node.show());
}
return ret;
}
};
对BST通常有三种类型查找：
-
查找给定值
-
查找最小值
-
查找最大值
在BST上查找最小值和最大值很简单，因为较小的值总是在左子节点上，在BST上查找最小值，只需要遍历左子树，直到找到最后一个节点。查找最大值类似，遍历右子树，直到找到最后一个节点。
那么怎么查找给定值呢，就需要比较该值和当前节点上的值大小，如果比当前值小，那么就遍历左子树，反之就是遍历右子树。
实现的代码（部分）：
/**
* 得到最小值
* @return {Any} 最小值
*/
getMin: function getMin() {
var current = this.root;
while (current.left != null) {
current = current.left;
}
return current.data;
},
/**
* 得到最大值
* @return {Any} 最大值
*/
getMax: function getMax() {
var current = this.root;
while (current.right != null) {
current = current.right;
}
return current.data;
},
/**
* 查找指定值
* @param {Any} data 指定值
* @return {Node|Null} 保存该值的节点或null
*/
find: function find(data) {
var current = this.root;
while (current != null) {
if (current.data === data) {
return current;
} else if (current.data > data) {
current = current.left;
} else {
current = current.right;
}
}
return null;
}
在BST上还有一个最复杂的操作，那就是删除节点，其复杂程度取决于删除哪个节点。如果删除没有子节点的节点就很简单，直接删除。如果节点只有一个子节点，不管是左节点还是右节点，就复杂了；当然删除带有两个子节点的节点是最为复杂的。
删除节点的第一步是判断当前节点是否包含待删除的数据，如果包含，则删除该节点；如果不包含，则比较当前节点上的数据和待删除的数据。如果说待删除的数据小于当前节点上的数据，那么就移至当前节点的左子节点继续比较；否则就移至当前节点的右节点继续比较。
如果待删除节点是一个叶子节点，那么只需要将父节点指向他的链接指向null即可。
如果待删除节点只包含一个子节点，那么原本指向他的节点就得做一些调整，使其指向他的子节点。
最后，如果待删除节点包含两个子节点，正确的做法有两种：要么查找待删除节点左子树上的最大值，要么查找其右子树上的最小值。
删除实现代码（部分）：
/**
* 删除指定数据
* @param {Any} data 指定数据
* @return {Node|Null} 移除后节点或者null
*/
remove: function remove(data) {
return this.removeNode(this.root, data);
},
/**
* 从节点上删除指定数据
* @param {Node|Null} node 节点
* @param {Any} data 待删除数据
* @return {Node|Null} 移除后节点或者null
*/
removeNode: function removeNode(node, data) {
if (node == null) return null;
if (data === node.data) {
// 没有子节点
if (node.left == null && node.right == null) {
return null;
}
// 没有左节点
if (node.left == null) {
return node.right;
}
// 没有右节点
if (node.right == null) {
return node.left;
}
// 有两个子节点
// 这里采用查找其右子树上的最小值
var tmpNode = this.getSmallest(node.right);
node.data = tmpNode.data;
node.right = removeNode(node.right, tmpNode.data);
return node;
} else if (data < node.data) {
node.left = removeNode(node.left, data);
return node;
} else {
node.right = removeNode(node.right, data);
return node;
}
},
/**
* 得到节点上有最小值的子节点
* @param {Node} node 节点
* @return {Node} 有最小值的节点
*/
getSmallest: function getSmallest(node) {
// 没有左节点，意味着当前节点是最小
if (node.left == null) return node;
return getSmallest(node.left);
}
具体运行例子请看demojs实现二叉树