BinarySearchTree (简称，BST) 二叉搜索树。又称
二叉查找树，二叉排序树。
其应满足以下性质：
- 二叉搜索树是一颗二叉树，可以为空。
- 如果不为空，满足以下性质：
1）非空左子树的所有键值都小于根节点的键值
2）非空右子树的所有键值都大于根节点的键值
3）左子树和右子树也是一颗二叉树
// 基础代码
class Node {
constructor(key, left = null, right = null) {
this.key = key;
this.left = left;
this.right = right;
}
}
class BST {
constructor() {
this.root = null;
}
// 插入节点
insert(key) {
const newNode = new Node(key);
// 根节点为null => 创建根节点
if (this.root === null) {
this.root = newNode;
} else {
this.insertNode(this.root, newNode);
}
}
// 插入节点
insertNode(node, newNode) {
if (newNode.key > node.key) {
if (node.right === null) {
node.right = newNode;
} else {
this.insertNode(node.right, newNode);
}
} else if (newNode.key < node.key) {
if (node.left === null) {
node.left = newNode;
} else {
this.insertNode(node.left, newNode);
}
} else {
return;
}
}
const bst = new BST();
bst.insert(11);
bst.insert(13);
bst.insert(9);
bst.insert(7);
bst.insert(12);
bst.insert(18);
bst.insert(6);
bst.insert(8);
bst.insert(10);
bst.insert(16);
bst.insert(20);
-
以上代码图示
iShot2021-08-01 20.17.08.png
1. 先序遍历（先根节点，后左子树，再右子树）
preOrderTraverse() {
this.preOrderTraverseNode(this.root);
}
preOrderTraverseNode(node) {
if (node === null) return;
console.log(node.key); //
this.preOrderTraverseNode(node.left); // 递归调用左子树
this.preOrderTraverseNode(node.right); // 递归调用左子树
}
-
以上代码图示
iShot2021-08-01 20.19.16.png
2. 中序遍历（先左子树，后根节点，再右子树）
inOrderTraverse() {
return this.inOrderTraverseNode(this.root);
}
inOrderTraverseNode(node) {
if (node === null) return;
this.inOrderTraverseNode(node.left);
console.log(node.key);
this.inOrderTraverseNode(node.right);
}
-
以上代码图示
iShot2021-08-01 20.21.24.png
3. 后序遍历（先左子树，后右子树，再根节点）
postOrderTraverse() {
return this.postOrderTraverseNode(this.root);
}
postOrderTraverseNode(node) {
if (node === null) return;
this.postOrderTraverseNode(node.left);
this.postOrderTraverseNode(node.right);
console.log(node.key);
}
-
以上代码图示
iShot2021-08-01 20.22.06.png
