二叉树中的节点最多只能有两个子节点：一个是左侧子节点，另一个是右侧子节点。这些定义有助于我们写出更高效的向/从树中插入、查找和删除节点的算法。二叉树在计算机科学中的应用非常广泛。
二叉搜索树（BST）是二叉树的一种，但是它只允许你在左侧节点存储（比父节点）小的值，
在右侧节点存储（比父节点）大（或者等于）的值。
// 节点类
class Node {
constructor(key) {
this.key = key;
this.left = null;
this.right = null;
}
}
// 二叉搜索树
class BinarySearchTree {
constructor() {
this.root = null;
}
// 新增节点
insert(key) {
var newNode = new Node(key); //{1}
if (this.root === null) {
//{2}
this.root = newNode;
} else {
insertNode(this.root, newNode); //{3}
}
function insertNode(node, newNode) {
if (newNode.key < node.key) {
//{4}
if (node.left === null) {
//{5}
node.left = newNode; //{6}
} else {
insertNode(node.left, newNode); //{7}
}
} else {
if (node.right === null) {
//{8}
node.right = newNode; //{9}
} else {
insertNode(node.right, newNode); //{10}
}
}
}
}
// 中序遍历（从小到大）
inOrderTraverse(callback) {
inOrderTraverseNode(this.root, callback); //{1}
function inOrderTraverseNode(node, callback) {
// 因为是同步执行，所以虽然看起来第一次进来的时候就执行了{{4}}但其实{{3}}会分解成无数个callback,然后按照二叉搜索树的特性，会从小到大依次打印
if (node !== null) {
//{2}
inOrderTraverseNode(node.left, callback); //{3}
callback(node.key); //{4}
inOrderTraverseNode(node.right, callback); //{5}
}
}
}
// 先序遍历（先输出最下面的子节点，子节点全部输出完之后才会输出父节点）
postOrderTraverse(callback) {
postOrderTraverseNode(root, callback);
function postOrderTraverseNode(node, callback) {
if (node !== null) {
postOrderTraverseNode(node.left, callback); //{1}
postOrderTraverseNode(node.right, callback); //{2}
callback(node.key); //{3}
}
}
}
// 搜索最小值
minNode(node) {
if (node) {
while (node && node.left !== null) {
//{2}
node = node.left; //{3}
}
return node.key;
}
return null; //{4}
}
// 搜索最大值
maxNode(node) {
if (node) {
while (node && node.right !== null) {
//{2}
node = node.right; //{3}
}
return node.key;
}
return null; //{4}
}
// 搜索值是否存在
search(key) {
return searchNode(root, key); //{1}
function searchNode(node, key) {
if (node === null) {
//{2}
return false;
}
if (key < node.key) {
//{3}
return searchNode(node.left, key); //{4}
} else if (key > node.key) {
//{5}
return searchNode(node.right, key); //{6}
} else {
return true; //{7}
}
}
}
removeNode(node, key) {
if (node === null) {
//{2}
return null;
}
if (key < node.key) {
//{3}
node.left = removeNode(node.left, key); //{4}
return node; //{5}
} else if (key > node.key) {
//{6}
node.right = removeNode(node.right, key); //{7}
return node; //{8}
} else {
//键等于node.key
//第一种情况——一个叶节点
if (node.left === null && node.right === null) {
//{9}
node = null; //{10}
return node; //{11}
}
//第二种情况——一个只有一个子节点的节点
if (node.left === null) {
//{12}
node = node.right; //{13}
return node; //{14}
} else if (node.right === null) {
//{15}
node = node.left; //{16}
return node; //{17}
}
//第三种情况——一个有两个子节点的节点
var aux = findMinNode(node.right); //{18}
node.key = aux.key; //{19}
node.right = removeNode(node.right, aux.key); //{20}
return node; //{21}
}
function findMinNode(node) {
while (node && node.left !== null) {
node = node.left;
}
return node;
}
}
}
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.inOrderTraverse(console.log);