二叉树和二叉查找树
本文共--字 阅读约--分钟 | 浏览: -- Last Updated: 2021-12-21
树是一种非线性的数据结构，以分层的方式存储数据，用来存储具有层级关系的数据，也可以用来存储有序列表。本章将研究一种特殊的树：二叉树。在二叉树上进行查找非常快，为二叉树添加或删除元素也非常快。
树的定义
一棵树最上面的节点称为根节点，如果一个节点下面连接多个节点，那么该节点称为父节点，它下面的节点称为子节点，一个节点可以有0个、1个或多个子节点，没有任何子节点的节点称为叶子节点。
沿着一组特定的边，可以从一个节点走到另外一个与它不直接相连的节点。从一个节点到另一个节点的这一组边称为路径，如下图中虚线表示的 23到46。以某种特定的顺序访问树中所有的节点称为树的遍历。
树可以分为几个层次，根节点是第0层，它的子节点是第1层，以此类推。树中的任何一层的节点可以都看做子树的根，我们定义树的层次就是树的深度。最后每个节点都有与之相关的值，该值有时候被称为键。
二叉树和二叉查找树
二叉树是一种特殊的树，它的每个节点的子节点不允许超过两个，通过将子节点的个数限定为2，可以写出高效的程序在树中插入、查找和删除数据。在二叉树中一个父节点的两个子节点分别称为左节点和右节点，在一些二叉树的实现中，左右节点都包含一组特定的值，比如二叉查找树，相对较小的值保存在左节点中，较大的值保存在右节点中，这一特性使得查找效率很高。
实现二叉查找树
二叉查找树(BST, Binary search tree)由节点组成，所以要定义的第一个对象就是 Node。与链表类似，Node 对象既把保存对象，也保存和其他节点的链接(left 和 right)。
而二叉查找树这个类(BST)，该类值包含一个数据成员：一个表示二叉查找树根节点的Node对象(类似链表中的Head)。
BST 还拥有 insert 方法用来向树中插入新节点，这个方法有点复杂，首先需要根据要插入的数据创建一个Node对象，其次检查BST有没有根节点，如果没有，则插入的节点就是根节点；如果有根节点，那么就需要遍历BST，找到适当的位置插入，查找正确插入点的算法如下：
- 从根节点出发，首先将根节点当做锚点节点，用插入节点与锚点节点进行比较
- 如果插入节点的数据小于锚点节点，那么将锚点节点的左节点当做下一个锚点节点，然后判断锚点节点的左节点如果为null，则将插入节点插入这个位置，反之继续执行下一次循环。
- 如果插入节点的数据大于等于锚点节点，那么将锚点节点的右节点当做下一个锚点节点，然后判断锚点节点的右节点如果为null，则将插入节点插入这个位置，反之继续执行下一次循环。
初步实现：
function Node(data, left, right) {
this.data = data;
this.left = left;
this.right = right;
}
function BST() {
this.root = null;
this.insert = insert;
this.inOrder = inOrder;
}
function insert(data) {
var n = new Node(data, null, null)
if (this.root == null) {
this.root = n;
} else {
var current = this.root;
var 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;
}
}
}
}
}
需要注意的是，插入顺序的不同，会导致树的深度的不同和形状不同。
如果是这样的插入顺序：
var nums = new BST()
nums.insert(56)
nums.insert(22)
nums.insert(81)
nums.insert(92)
nums.insert(77)
nums.insert(10)
nums.insert(30)
对应的树应该如下：
如果换一种插入顺序：
var nums = new BST()
nums.insert(56)
nums.insert(92)
nums.insert(77)
nums.insert(81)
nums.insert(10)
nums.insert(30)
nums.insert(22)
对应的树却是这样的：
提供一个 getDepth 方法获取二叉查找树的深度：
function BST() {
this.root = null;
// ...
// new line
this.getDepth = function () {
return getDepth(this.root)
};
}
function getDepth(node) {
if (node != null) {
return Math.max(getDepth(node.left), getDepth(node.right)) + 1;
}
return 0;
}
关于获取深度的调用逻辑如下，（以上面的4层深度的树为例）：
遍历二叉查找树
同样我们需要有能力遍历BST，有三种方式：中序、先序和后序。
1、中序遍历，按照节点上的键值，以升序方式访问BST上的所有节点。左中右
function BST() {
// ...
// new line
this.inOrder = inOrder;
}
// 中序遍历
function inOrder(node) {
if (!(node == null)) {
inOrder(node.left);
console.log(node.data);
inOrder(node.right)
}
}
var nums = new BST()
nums.insert(56)
nums.insert(22)
nums.insert(81)
nums.insert(92)
nums.insert(77)
nums.insert(10)
nums.insert(30)
nums.inOrder(nums.root) // 10 22 30 56 77 81 92
其中中序遍历的逻辑大概如下：
2、先序遍历，先访问根节点，再依次访问左右子树，访问左右子树也是先访问左右子树的根节点，再依次访问对应子树的左右节点。中左右
先序遍历的定义如下：
function BST() {
// ...
// new line
this.preOrder = preOrder;
}
function preOrder(node) {
if (!(node == null)) {
console.log(node.data);
preOrder(node.left)
preOrder(node.right)
}
}
var nums = new BST()
nums.insert(56)
nums.insert(22)
nums.insert(81)
nums.insert(92)
nums.insert(77)
nums.insert(10)
nums.insert(30)
nums.preOrder(nums.root); // 56 22 10 30 81 77 92
可以看到，与 inOrder 不同的只是代码执行的顺序，console 放在两个递归之前，不再是像 inOrder 那样放在中间。
先序遍历的逻辑大概如下：
3、后序遍历，先访问叶子节点，从左子树到右子树，再到根节点。左右中
function BST() {
// ...
// new line
this.postOrder = postOrder;
}
function postOrder(node) {
if (!(node == null)) {
postOrder(node.left)
postOrder(node.right)
console.log(node.data);
}
}
var nums = new BST()
nums.insert(56)
nums.insert(22)
nums.insert(81)
nums.insert(92)
nums.insert(77)
nums.insert(10)
nums.insert(30)
nums.postOrder(nums.root); // 10 30 20 77 92 81 56
后序遍历的逻辑大概如下：
在二叉查找树上进行查找
查找最小值和最大值
查找BST上的最小值和最大值非常简单，因为较小的值总在左子节点上，较大的值总在右子节点上。只要遍历树，找到“最左”和“最右”的节点就可以了。
function getMin(parentNode) { // 可选参数 如果传入一个父节点，则找到该父节点下的最小值
var current = parentNode || this.root;
while (current.left != null) {
current = current.left;
}
return current;
}
function getMax(parentNode) { // 可选参数，如果传入一个父节点，则找到该父节点下的最大值
var current = parentNode || this.root;
while (current.right != null) {
current = current.right;
}
return current;
}
查找给定值
在BST上查找给定值，需要比较该值和当前节点上的值的大小。通过比较，就能确定给定值不是当前节点时，该向左还是向右遍历。
function find(data) {
var current = this.root;
while (current != null) {
if (current.data === data) {
return current;
} else if (data > current.data) {
current = current.right
} else {
current = current.left;
}
}
return null;
}
从二叉查找树上删除节点
删除节点的操作最为复杂，其复杂程度取决于删除哪个节点，被删除的节点的子节点个数越多越复杂，如果删除没有子节点的节点非常节点，如果删除的节点有一个或两个子节点就变得复杂起来。
-
1、遍历节点，如果当前节点不是待删除的节点，就比较这两个节点，如果被删除节点大于当前节点，就移至当前节点的右子树上继续遍历，反正，则移动到左子树上继续遍历。
-
2、如果待删除节点是叶子节点（left和right都为null），那么只需要将其本身指向null，以及将它的父节点原本的指向它链接也指向null
-
3、如果待删除节点包含一个子节点，那么就将其父节点指向它（待删除节点）的链接指向它的唯一一个子节点就可以了
-
4、最后，如果待删除节点包含两个子节点，正确的做法有两种，要么查找待删除节点左子树上的最大值；要么查找其右子树上的最小值。我们这里采取查找右子树上的最小值这种方式，会使用找到的最小值创造一个临时节点，将临时节点的值复制到待删除节点，然后删除临时节点。
以下图为例：
-
当需要删除一个叶子节点81时，则只需将77节点的right指向null即可。
-
当需要删除一个包含一个子节点的节点30时，则将节点30的父节点10的right指向节点30的唯一子节点22即可。
-
当需要删除一个包含两个子节点的节点10时：
- 找到该节点右子树上的最小值即节点22，将其复制到原先节点10的位置，然后删除节点10和这个最小值节点22即可；
- 或者找到该节点左子树上的最大值即节点8，将其复制到原先节点10的位置，然后删除节点10和这个最大值节点8即可。
remove 实现如下：
function remove(data) {
var node = this.root;
var parent = node; // 用于存储当前节点的父节点
var curOrder = 'mid'; // 存储当前遍历的子树
var tmpData = data;
while (true) {
// 1、节点为null无需递归了
// 2、如果被删除的节点不存在树中 最终遍历下来这个Node一定是null
if (node == null) {
return
}
// 找到了待删除节点
if (tmpData == node.data) {
// 没有子节点的节点
if (node.left == null && node.right == null) {
if (curOrder === 'mid') {
parent = null;
} else {
parent[curOrder] = null;
}
node = null;
return;
}
// 只有右子节点
if (node.left == null) {
parent[curOrder] = node.right
node = null
return;
}
// 只有左子节点
if (node.right == null) {
parent[curOrder] = node.left
node = null;
return;
}
// 有两个子节点
// 找到该节点右子树上的最小值
var rightMinNode = this.getMin(node.right);
let rightMinData = rightMinNode.data;
// 复制
node.data = rightMinData;
// 遍历右子树 并删除最小值在树中原来的位置
parent = node;
node = node.right;
curOrder = 'right';
tmpData = rightMinData;
} else if (tmpData < node.data) {
// 遍历当前节点的左子树
parent = node;
node = node.left
curOrder = 'left';
} else {
// 遍历当前节点的右子树
parent = node;
node = node.right
curOrder = 'right';
}
}
}
测试代码如下：
var nums = new BST()
nums.insert(56)
nums.insert(22)
nums.insert(81)
nums.insert(92)
nums.insert(77)
nums.insert(10)
nums.insert(30)
nums.remove(22)
console.log(nums.root);
// Node {
// data: 56,
// left:
// Node {
// data: 30,
// left: Node { data: 10, left: null, right: null },
// right: null },
// right:
// Node {
// data: 81,
// left: Node { data: 77, left: null, right: null },
// right: Node { data: 92, left: null, right: null } } }
nums.remove(30)
console.log(nums.root);
// Node {
// data: 56,
// left: Node { data: 10, left: null, right: null },
// right:
// Node {
// data: 81,
// left: Node { data: 77, left: null, right: null },
// right: Node { data: 92, left: null, right: null } } }
nums.remove(56)
console.log(nums.root);
// Node {
// data: 77,
// left: Node { data: 10, left: null, right: null },
// right:
// Node {
// data: 81,
// left: null,
// right: Node { data: 92, left: null, right: null } } }
nums.remove(92)
console.log(nums.root);
// Node {
// data: 77,
// left: Node { data: 10, left: null, right: null },
// right: Node { data: 81, left: null, right: null } }
其过程大概如下：
计数
BST的一个用途是记录一组数据中数据出现的次数。
场景：给定一组考试成绩，写一段程序将其加入一个BST，如果某成绩尚未在BST出现就将其加入，否则就将出现的次数加1。
// 修改Node类，以记录多次出现的次数
function Node(data, left, right) {
this.data = data;
this.count = 1;
this.left = left;
this.right = right;
}
function BST() {
this.root = null;
this.insert = insert;
this.inOrder = inOrder;
this.find = find;
this.update = update;
}
function insert(data) {
var n = new Node(data, null, null)
if (this.root == null) {
this.root = n;
} else {
var current = this.root;
var 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 find(data) {
var current = this.root;
while (current != null) {
if (current.data === data) {
return current;
} else if (data > current.data) {
current = current.right
} else {
current = current.left;
}
}
return null;
}
// 当次数增加时，更新BST中的节点的count
function update(data) {
var grade = this.find(data);
grade.count++;
return grade;
}
场景业务代码：
function prArray(arr) {
var str = '';
for (var i = 0; i < arr.length; i++) {
str += arr[i] + ' ';
if (i > 0 && i % 10 == 0) {
str += '\n'
}
}
console.log(str);
}
function genArray(length) {
var arr = [];
for (var i = 0; i < length; ++i) {
arr[i] = Math.floor(Math.random() * 101)
}
return arr;
}
var grades = genArray(100);
prArray(grades)
var gradeBST = new BST();
for (var i = 0; i < grades.length; ++i) {
var g = grades[i];
var grade = gradeBST.find(g);
if (grade == null) {
gradeBST.insert(g);
} else {
gradeBST.update(g);
}
}
// 获取100出现的次数
var a = gradeBST.find(100)
console.log('成绩100出现的次数：', (a && a.count) || 0)
// 获取80出现的次数
var b = gradeBST.find(80)
console.log('成绩80出现的次数：', (b && b.count) || 0)