js数据结构第九弹：二叉树和二叉查找树
树是一种非线性的数据结构， 以分层的方式存储数据。 树被用来存储具有层级关系的数据， 比如文件系统中的文件； 树还被用来存储有序列表。
优点：在二叉树上进行查找非常快（而在链表上查找则不是这样）， 为二叉树添加或删除元素也非常快（而对数组执行添加或删除操作则不是这样）。
1 树的定义
树由一组以边连接的节点组成。 每个方框都是一个节点， 连接方框的线叫做边。
一棵树最上面的节点称为根节点， 如果一个节点下面连接多个节点， 那么该节点称为父节点， 它下面的节点称为子节点。 一个节点可以有 0 个、 1 个或多个子节点。 没有任何子节点的节点称为叶子节点。
二叉树是一种特殊的树， 它的子节点个数不超过两个。
沿着一组特定的边， 可以从一个节点走到另外一个与它不直接相连的节点。 从一个节点到另一个节点的这一组边称为路径， 在图中用虚线表示。 以某种特定顺序访问树中所有的节点称为树的遍历。
树可以分为几个层次， 根节点是第 0 层， 它的子节点是第 1 层， 子节点的子节点是第 2层， 以此类推。 树中任何一层的节点可以都看做是子树的根， 该子树包含根节点的子节点， 子节点的子节点等。 我们定义树的层数就是树的深度。
每个节点都有一个与之相关的值， 该值有时被称为键。
2 二叉树和二叉查找树
一个父节点的两个子节点分别称为左节点和右节点。二叉查找树是一种特殊的二叉树， 相对较小的值保存在左节点中， 较大的值保存在右节点中。
1 实现二叉查找树
//保存数据， 保存和其他节点的链接
function Node(data, left, right) {
this.data = data;
this.left = left;
this.right = right;
this.show = show;
}
//显示保存在节点中的数据。
function show() {
return this.data;
}
创建一个类， 用来表示二叉查找树（BST）。
类只包含一个数据成员： 一个表示二叉查找树根节点的 Node 对象。 该类的构造函数将根节点初始化为 null， 以此创建一个空节点。
BST 先要有一个 insert() 方法， 用来向树中加入新节点。
首先要创建一个 Node 对象， 将数据传入该对象保存。
其次检查 BST 是否有根节点， 如果没有， 那么这是棵新树， 该节点就是根节点， 这个方法到此也就完成了； 否则， 进入下一步。
如果待插入节点不是根节点， 那么就需要准备遍历 BST， 找到插入的适当位置。 该过程类似于遍历链表。 用一个变量存储当前节点， 一层层地遍历 BST。进入 BST 以后， 下一步就要决定将节点放在哪个地方。 找到正确的插入点时， 会跳出循环。 查找正确插入点的算法如下。
(1) 设根节点为当前节点。
(2) 如果待插入节点保存的数据小于当前节点， 则设新的当前节点为原节点的左节点； 反之， 执行第 4 步。
(3) 如果当前节点的左节点为 null， 就将新的节点插入这个位置， 退出循环； 反之， 继续执行下一次循环。
(4) 设新的当前节点为原节点的右节点。
(5) 如果当前节点的右节点为 null， 就将新的节点插入这个位置， 退出循环； 反之， 继续执行下一次循环。
// 二叉查找树BST
// 有一个节点属性，还有一些其他的方法，以下定义一个二叉查找树BST类
function BST(){
// 根节点初始化为空
this.root = null;
// 方法
// 插入
this.insert = insert;
// 中序遍历
this.inorder = inorder;
// 先序遍历
this.preorder = preorder;
// 后序遍历
this.postorder = postorder;
}
//实现insert插入方法
function insert(data){
// 创建一个节点保存数据
var node = new Node(data,null,null);
// 下面将节点node插入到树中
// 如果树是空的，就将节点设为根节点
if(!this.root){
this.root = node;
}else{ //树不为空
// 判断插在父节点的左边还是右边
// 所以先要保存一下父节点
var current = this.root;
var parent;
// 如果要插入的节点键值小于父节点键值，则插在父节点左边，
// 前提是父节点的左边为空，否则要将父节点往下移一层，
// 然后再做判断
//while(true)表示无限循环
while(true){
// data小于父节点的键值
parent = current;
if(data < parent.data){
// 将父节点往左下移(插入左边)
//注意：父节点不断下移！！！
current = current.left;
// 如果节点为空，则直接插入
if(current == null){
parent.left = node;
break;
}
}else{ // 将父节点往右下移(插入右边)
current = current.right;
if(!current){
parent.right = node;
break;
}
}
}
}
}
写一个二叉树：
var nums = new BST();
nums.insert(23);
nums.insert(45);
nums.insert(16);
nums.insert(37);
nums.insert(3);
nums.insert(99);
nums.insert(22);
print("Inorder traversal: ");
inOrder(nums.root);
输出为：
2 遍历二叉查找树
(1)中序遍历使用递归的方式最容易实现。 该方法需要以升序访问树中所有节点， 先访问左子树， 再访问根节点， 最后访问右子树。
function inOrder(node) {
if (!(node == null)) {
inOrder(node.left);
putstr(node.show() + " ");
inOrder(node.right);
}
}
结果显示：
(2)先序遍历的定义如下：先序遍历先访问根节点， 然后以同样方式访问左子树和右子树。
function preOrder(node) {
if (!(node == null)) {
putstr(node.show() + " ");
preOrder(node.left);
preOrder(node.right);
}
}
结果显示
得到输出50，10，5，15，70，60，80
注意： inOrder() 和 preOrder() 方法的唯一区别， 就是 if 语句中代码show() 函数的顺序。 在 inOrder()方法中， show() 函数像三明治一样夹在两个递归调用之间； 在 preOrder() 方法中， show()函数放在两个递归调用之前。
(3)后序遍历：后序遍历先访问叶子节点， 从左子树到右子树， 再到根节点。
function postOrder(node) {
if (!(node == null)) {
postOrder(node.left);
postOrder(node.right);
putstr(node.show() + " ");
}
}
得到输出5，15，10，60，80，70，50
3 在二叉查找树上进行查找
1 查找最小值和最大值
getMin() 方法查找 BST 上的最小值， 因为较小的值总是在左子节点上， 在 BST 上查找最小值， 只需要遍历左子树， 直到找到最后一个节点。 该方法的定义如下：
function getMin() {
var current = this.root;
//沿着 BST 的左子树挨个遍历， 直到遍历到 BST 最左边的节点
while (!(current.left == null)) {
current = current.left;
}
return current.data;
}
getMax() 方法的定义如下：
function getMax() {
var current = this.root;
while (!(current.right == null)) {
current = current.right;
}
return current.data;
}
2 查找给定值
在 BST 上查找给定值， 需要比较该值和当前节点上的值的大小。 通过比较， 就能确定如果给定值不在当前节点时， 该向左遍历还是向右遍历。
function find(data) {
var current = this.root;
while (current != null) {
if (current.data == data) {
return current;
}
else if (data < current.data) {
current = current.left;
}
else {
current = current.right;
}
}
return null;
}
4 从二叉查找树上删除节点
二叉树节点的删除也是可以分为几种情况:
被删除节点为叶子节点；
被删除节点仅有一个子节点（子树）；
被删除节点有两个子节点（子树）
(1)被删除节点为叶子节点
思路：将该叶子节点的父节点指向的子节点的引用值设为空
(2)被删除节点仅有一个子树
思路：将该节点的父节点指向该节点的引用改成指向该节点的子节点。
(3)删除节点有两个子树
思路：处理这种情况有两种方法：
从待删除节点的左子树找节点值最大的节点A，替换待删除节点，并删除节点A；
从待删除节点的右子树找节点值最小的节点A，替换待删除节点，并删除节点A。
----->选择第二种,同时需要一个查找子树上最小值的方法
// 获取给定节点下的二叉树最小值
BST.prototype.getSmallest = function(node) {
if(node.left == null) {
return node;
} else {
return getSmallest(node.left);
}
};
// 根据给定删除给定节点下二叉树的对应节点
BST.prototype.removeNode = function(node, data) {
if(node == null) {
return null;
}
if(data == node.data) {
// 没有子节点（子树）
if(node.left == null && node.right == null) {
return null;
}
// 只有右子节点（子树）
else if(node.left == null ) {
return node.right;
}
// 只有左子节点（子树）
else if(node.right == null){
return node.left;
}
// 有两个子节点（子树）
else {
var tempNode = this.getSmallest(node.right);
node.data = tempNode.data;
node.right = this.removeNode(node.right, tempNode.data);
return node;
}
} else if(data < node.data) {
node.left = this.removeNode(node.left, data);
return node;
} else {
node.right = this.removeNode(node.right, data);
return node;
}
}
5 计数
记录一组数据集中数据出现的次数
//修改 Node 对象的定义， 为其增加记录成绩出现次数的成员
function Node(data, left, right) {
this.data = data;
this.count = 1;
this.left = left;
this.right = right;
this.show = show;
}
// 当次数增加时， 我们就需要一个新方法来更新 BST 中的节点。
function update(data) {
var grade = this.find(data);
grade.count++;
return grade;
}
//随机产生成绩
function genArray(length) {
var arr = [];
for (var i = 0; i < length; ++i) {
arr[i] = Math.floor(Math.random() * 101);
}
return arr;
}
//显示函数
function prArray(arr) {
putstr(arr[0].toString() + ' ');
for (var i = 1; i < arr.length; ++i) {
putstr(arr[i].toString() + ' ');
if (i % 10 == 0) {
putstr("\n");
}
}
}