数据结构-二叉树和二叉查找树
lickylin 2019-06-28
树的定义
树是一组以 边 连接的 节点 组成. 这里不做过多赘述. 深入了解点这里)
二叉树 是一种特殊的树, 它的子节点个数不超过两个. 二叉树具有一些特殊的计算性质, 使得它们之上的一些操作异常高效.
二叉树和二叉查找树
正如前面提到的那样, 二叉树 每一个节点的子节点不允许超过两个. 通过将子节点的个数限定为2, 可以写出高效的程序在树中插入、查找和删除数据.
在使用JS构建二叉树之前, 需要给我们关于树的词典里再加两个新名词.
- 左节点: 一组特定的值.
- 右节点: 另一组特定的值.
当考虑某种特殊的二叉树, 比如 二叉查找树 时, 确定子节点非常重要.
二叉查找树是一种特殊的二叉树.
- 相对较小的值保存在左节点中.
- 较大的值保存在右节点中.
这一特性使得查找效率很高, 对于数值型和非数值型的数据, 比如单词和字符串, 都是如此.
实现二叉查找树
二叉查找树由节点组成, 所以我们要定义的第一个对象就是Node, 该对象和前面介绍链表时的对象类似.Node对象及保存数据, 也保存和其它节点的链接(left和right), show()方法用来显示保存在节点中的数据.
创建BST类用来表示二叉查找树. 我们让类只包含一个数据成员: 一个表示二叉查找树根节点的Node对象. 该类的构造函数将根节点初始化为null, 以此创建一个空节点.
BST先要有一个insert()方法, 用来向树中加入新节点. 这个方法有点复杂, 需要着重讲解. 首先要创建一个Node对象, 将数据传入该对象保存.
其次检查BST是否有根节点, 如果没有, 那么这是棵新树, 该节点就是根节点, 这个方法到此也就完成了; 否则进入下一步.
如果待插入节点不是根节点, 那么就需要准备遍历BST, 找到插入的适当位置. 该过程类似于遍历链表. 用一个变量存储当前节点, 一层层地遍历BST.
进入BST以后, 下一步就决定将节点放在哪个地方. 找到正确的插入点时, 会跳出循环. 查找正确插入点的算法如下:
- 设根节点为当前节点.
- 如果待插入节点保存的数据小于当前节点, 则设新的当前节点为原节点的左节点; 反之, 执行第
4步. - 如果当前节点的左节点为
null, 就将新的节点插入这个位置, 退出循环; 反之, 继续执行下一次循环. - 设新的当前节点为源节点的右节点.
- 如果当前节点的右节点为
null, 就将新的节点插入这个位置, 退出循环; 反之, 继续执行下一次循环.
有了上面的算法, 就可以开始实现BST类了.
window.log = console.log.bind(console)
class Node {
constructor(data, left = null, right = null) {
this.data = data;
this.left = left;
this.right = right;
}
show() {
return this.data;
}
};
class BST {
constructor() {
this.root = null;
}
insert(data) {
const n = new Node(data);
if(this.root === null) {
this.root = n;
} else {
let current = this.root;
let parent;
while(true) {
parent = current;
if(data < current.data) {
current = current.left;
if(current === null) {
parent.left = n;
break;
}
} else {
current = current.right;
if(current === null) {
parent.right = n;
break
}
}
}
}
}
};遍历二叉查找树
现在BST类已经初步成型, 但是操作上还只能插入节点, 我们需要有能力遍历BST, 这样就可以按照不同顺序, 比如按照数字大小或字母先后, 显示节点上的数据.
有三种遍历BST的方式:
- 中序: 按照节点上的键值, 以升序访问
BST上的所有节点. - 先序: 先访问根节点, 然后以同样方式访问左子树和右子树.
- 后序: 先访问叶子节点, 从左子树到右子树, 再到根节点.
需要中序遍历的原因显而易见, 但为什么需要先序遍历和后序遍历就不是那么明显了. 我们先来实现这三种遍历方式, 在后序再解释它们的用途.
中序遍历使用递归方式最容易实现. 该方法需要以升序访问树中所有节点, 先访问左子树, 再访问根节点, 最后访问右子树.
function inOrder(node) {
if (node !== null) {
inOrder(node.left);
log(node.show() + ' ')
inOrder(node.right)
}
};
const bst = new BST();
bst.insert(4);
bst.insert(34);
bst.insert(43);
bst.insert(98);
bst.insert(71);
bst.insert(1);
inOrder(bst.root);先序遍历(preOrder())和中序遍历(inOrder())方法的唯一区别, 就是if语句中代码的顺序.
在inOrder()方法中, show()函数像三明治一样夹在两个递归调用之间;
在preOrder()方法中, show()函数放在两个递归调用之前.
function preOrder(node) {
if (node !== null) {
log(node.show() + ' ');
preOrder(node.left);
preOrder(node.right);
}
};后序遍历postOrder():
function postOrder(node) {
if (node !== null) {
postOrder(node.left);
postOrder(node.right);
log(node.show() + ' ');
}
}在二叉查找树上进行查找
对BST通常有下列三种类型的查找:
- 查找给定值.
- 查找最小值.
- 查找最大值.
查找最小值和最大值
查找BST上的最小值和最大值非常简单. getMin()查找最小值, 因为较小的值总是在左子节点上, 只需要遍历左子树, 直到找到最后一个节点.
getMin() {
let current = this.root;
while (current.left !== null) {
current = current.left;
};
return current.data;
}getMax()查找最大值, 只需要遍历右子树, 直到找到最后一个节点, 该节点上保存的值即为最大值.
getMax() {
let current = this.root;
while (current.right !== null) {
current = current.right;
};
return current.data;
}测试:
const bst = new BST();
bst.insert(4);
bst.insert(34);
bst.insert(43);
bst.insert(98);
bst.insert(71);
bst.insert(1);
log('最小值: ' + bst.getMin());
log('最大值: ' + bst.getMax());
// 输出:
// 最小值: 1
// 最大值: 98这两个方法返回最小值和最大值, 但有时, 我们希望方法返回存储最小值和最大值的节点. 这很好实现, 只需要修改方法, 让它返回当前节点, 而不是节点中存储的数据即可.
查找给定值
在BST上查找给定值, 需要比较该值和当前节点上的值的大小. 通过比较, 就能确定如果给定值不在当前节点时, 该向左遍历还是右遍历.
find(data) {
let current = this.root;
while (current !== null) {
if (current.data === data) {
return current;
} else if (data < current.data) {
current = current.left;
} else if (data > current.data) {
current = current.right;
}
};
return null;
}从二叉查找树上删除节点
删除节点的操作最复杂, 其复杂程度取决于删除哪个节点. 如果删除没有子节点的节点, 那么非常简单. 如果节点只有一个子节点, 不管是左子节点还是右子节点, 就变得稍微有点复杂了. 删除包含两个子节点的节点最复杂. 为了管理删除操作的复杂度, 我们使用递归操作, 同时定义两个方法: remove()和removeNode().
删除节点的第一步是判断当前节点是否包含带删除的数据.
如果包含, 则删除节点;
如果不包含, 则比较当前节点上的数据和待删除的数据
如果待删除数据小于当前节点上的数据, 则移至当前节点的左子节点继续比较; 如果待删除数据大于当前节点上的数据, 则移至当前节点的右子节点继续比较;
如果待删除节点是叶子节点(没有子节点的节点), 那么只需要将从父节点指向它的链接指向null.
如果待删除节点只包含一个子节点, 那么原本指向它的节点就得做些调整, 使其指向它的子节点.
最后, 如果待删除节点包含两个子节点, 正确的做法有两种:
- 查找待删除节点左子树上的最大值.
- 查找待删除节点右子树的最小值.
这里我们选择后一种方式
我们需要一个查找子树最小值的方法getSmallest(), 后面会用它找到最小值创建一个临时节点. 将临时节点上的值复制到待删除节点, 然后再删除临时节点.
整个删除过程由两个方法完成. remove()方法只是简单地接受待删除数据, 调用removeNode()删除它, 后者才是完成主要工作的方法.
window.log = console.log.bind(console)
class Node {
constructor(data, left = null, right = null) {
this.data = data;
this.left = left;
this.right = right;
}
show() {
return this.data;
}
};
class BST {
constructor() {
this.root = null;
}
getMin() {
let current = this.root;
while (current.left !== null) {
current = current.left;
};
return current.data;
}
getMax() {
let current = this.root;
while (current.right !== null) {
current = current.right;
};
return current.data;
}
find(data) {
let current = this.root;
while (current !== null) {
if (current.data === data) {
return current;
} else if (data < current.data) {
current = current.left;
} else if (data > current.data) {
current = current.right;
}
};
return null;
}
remove(data) {
this.root = removeNode(this.root, data);
}
insert(data) {
const n = new Node(data);
if(this.root === null) {
this.root = n;
} else {
let current = this.root;
let parent;
while(true) {
parent = current;
if(data < current.data) {
current = current.left;
if(current === null) {
parent.left = n;
break;
}
} else {
current = current.right;
if(current === null) {
parent.right = n;
break
}
}
}
}
}
};
function inOrder(node) {
if (node !== null) {
inOrder(node.left);
log(node.show() + ' ')
inOrder(node.right)
}
};
function preOrder(node) {
if (node !== null) {
log(node.show() + ' ');
preOrder(node.left);
preOrder(node.right);
}
};
function postOrder(node) {
if (node !== null) {
postOrder(node.left);
postOrder(node.right);
log(node.show() + ' ');
}
};
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;
};
// 有两个子节点的节点
const tempNode = getSmallest(node.right);
node.data = tempNode.data;
node.right = removeNode(node.right, tempNode.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;
}
}计数
BST的一个用途是记录一组数据集中数据出现的次数. 比如, 可以使用BST记录考试成绩的分布. 给定一组考试成绩, 可以写一段程序将它们加入一个BST, 如果某成绩尚未在BST中出现, 就将其加入BST; 如果已经出现, 就将出现的次数加1;
为了解决该问题, 我们来修改Node对象, 为其增加一个记录成绩出现频次的成员, 同时我们还需要一个方法, 当在BST中发现某成绩时, 需要将出现的次数加1, 并且更新该节点.
先修改Node对象的定义, 为其增加记录成绩出现次数的成员:
class Node {
constructor(data, left = null, right = null) {
this.data = data;
this.count = 1;
this.left = left;
this.right = right;
}
show() {
return this.data;
}
};当向BST插入一条成绩(Node对象)时, 将出现频次设为1. 此时BST的insert()方法还能正常工作, 但是, 当次数增加时, 我们就需要一个新方法来更新BST中的节点. 这个方法就是update().
完整程序:
window.log = console.log.bind(console)
class Node {
constructor(data, left = null, right = null) {
this.data = data;
this.count = 1;
this.left = left;
this.right = right;
}
show() {
return this.data;
}
};
class BST {
constructor() {
this.root = null;
}
getMin() {
let current = this.root;
while (current.left !== null) {
current = current.left;
};
return current.data;
}
getMax() {
let current = this.root;
while (current.right !== null) {
current = current.right;
};
return current.data;
}
find(data) {
let current = this.root;
while (current !== null) {
if (current.data === data) {
return current;
} else if (data < current.data) {
current = current.left;
} else if (data > current.data) {
current = current.right;
}
};
return null;
}
update(data) {
const grade = this.find(data);
grade.count++;
return grade;
}
remove(data) {
this.root = removeNode(this.root, data);
}
insert(data) {
const n = new Node(data);
if(this.root === null) {
this.root = n;
} else {
let current = this.root;
let parent;
while(true) {
parent = current;
if(data < current.data) {
current = current.left;
if(current === null) {
parent.left = n;
break;
}
} else {
current = current.right;
if(current === null) {
parent.right = n;
break
}
}
}
}
}
};
function inOrder(node) {
if (node !== null) {
inOrder(node.left);
log(node.show() + ' ')
inOrder(node.right)
}
};
function preOrder(node) {
if (node !== null) {
log(node.show() + ' ');
preOrder(node.left);
preOrder(node.right);
}
};
function postOrder(node) {
if (node !== null) {
postOrder(node.left);
postOrder(node.right);
log(node.show() + ' ');
}
};
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;
};
// 有两个子节点的节点
const tempNode = getSmallest(node.right);
node.data = tempNode.data;
node.right = removeNode(node.right, tempNode.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;
}
};
// 产生随机成绩
function genArray(length) {
const arr = [];
for(let i = 0; i < length; i++) {
arr[i] = Math.floor(Math.random() * 101);
};
return arr;
};
const grades = genArray(100);
log(grades);
const bst = new BST();
grades.forEach(i => {
const grade = bst.find(i);
if (grade) {
bst.update(i)
} else {
bst.insert(i)
}
});
const aGrade = bst.find(33);
if (aGrade) {
log(`33出现的次数为: ${aGrade.count}`)
} else {
log(`未出现33`)
}输出:
(100) [19, 85, 71, 52, 80, 3, 84, 13, 32, 20, 35, 10, 61, 54, 11, 49, 17, 6, 52, 66, 28, 7, 83, 71, 69, 84, 3, 2, 61, 12, 38, 97, 94, 10, 44, 14, 4, 69, 17, 10, 0, 28, 46, 74, 74, 18, 69, 70, 33, 32, 75, 81, 75, 52, 51, 34, 74, 75, 74, 0, 89, 71, 21, 28, 71, 42, 37, 92, 24, 39, 64, 75, 87, 46, 66, 37, 85, 55, 85, 21, 44, 16, 8, 81, 92, 72, 16, 4, 69, 32, 37, 48, 54, 91, 80, 57, 70, 88, 55, 32] 33出现的次数为: 1
