数据结构-二叉搜索树

二叉搜索树：BST(Binary Search Tree)
二叉搜索树是二叉树，可以为空，如果不为空，满足以下性质：

• 非空左子树的所有键值小于其根节点的键值
• 非空右子树的所有键值大于其根节点的键值
• 左、右字数本身也都是二叉搜索树

二叉搜索树的特点：

• 二叉搜索树的特点就是相对较小的值总是保存在左节点上，相对较大的值总是保存在右节点上
• 查找效率非常高

二叉搜索树常见的操作：

• insert(key, value)：向树中插入数据
• search(key)：在树中查找
• remove(key)：从树中移除
• update(key,value)：修改节点数据
• inOrderTraverse：通过中序遍历方式遍历所有节点
• preOrderTraverse：通过先序遍历方式遍历所有节点
• postOrderTraverse：通过后序遍历方式遍历所有节点
• min：返回树中最小的键/值
• max：返回树中最大的键/值

class Node {constructor(key) {this._key = key;this._left = null;this._right = null;}
}
class BinarySearchTree {constructor() {this._root = null;}insert(key) {const insertNode = (node, newNode) => {if(newNode._key <= node._key) {if(node._left === null) {node._left = newNode;} else {insertNode(node._left, newNode);}} else {if(node._right === null) {node._right = newNode;} else {insertNode(node._right, newNode);}}}const newNode = new Node(key)if (this._root === null) {this._root = newNode} else {insertNode(this._root, newNode)   }}preOrderTraverse(handler = (value) => {console.log(value)}) {const preOrderTraverseNode = (node) => {if (node === null) {return }handler(node._key)preOrderTraverseNode(node._left)preOrderTraverseNode(node._right)}preOrderTraverseNode(this._root)}midOrderTraverse(handler = (value) => {console.log(value)}) {const midOrderTraverseNode = (node) => {if (node === null) {return }midOrderTraverseNode(node._left)handler(node._key)midOrderTraverseNode(node._right)}midOrderTraverseNode(this._root)}postOrderTraverse(handler = (value) => {console.log(value)}) {const postOrderTraverseNode = (node) => {if (node === null) {return }postOrderTraverseNode(node._left)postOrderTraverseNode(node._right)handler(node._key)}postOrderTraverseNode(this._root)}min() {if (this._root === null) {return null}let node = this._rootwhile(true) {if (node._left === null) {return node._key}node = node._left}}max() {if (this._root === null) {return null}let node = this._rootwhile(true) {if (node._right === null) {return node._key}node = node._right}}search(key) {const searchNode = (node, key) => {if (node === null) {return false}if (node._key === key) {return true}if (key < node._key) {return searchNode(node._left, key)} else {return searchNode(node._right, key)}}return searchNode(this._root, key)}remove(key) {if (this._root === null) {return false}let current = this._rootlet parent = nulllet isLeftChild = truewhile (current._key !== key) {parent = currentif (key < current._key) {isLeftChild = truecurrent = current._left} else {isLeftChild = falsecurrent = current._right}if (current === null) {return false}}// 删除叶子节点if (current._left === null && current._right === null) {if (current === this._root) {this._root = null} else {if (isLeftChild) {parent._left = null} else {parent._right = null}}}// 删除有一个子节点else if (current._left === null ) {if (current === this._root) {this._root = current._right} else if (isLeftChild) {parent._left = current._right} else {parent._right = current._right}} else if (current._right === null) {if (current === this._root) {this._root = current._left} else if (isLeftChild) {parent._left = current._left} else {parent._right = current._left}} else {const getExChangeTargetNode = (current) => {let node = current._rightlet parentNode = currentlet isRightClick = truewhile(true) {if (node._left === null) {if (isRightClick)  {parentNode._right = node._right} else  {parentNode._left = node._right}return node}isRightClick = falseparentNode = nodenode = node._left}}const targetNode = getExChangeTargetNode(current);if (current !== this._root) {if (isLeftChild)  {parent._left = targetNode} else  {parent._right = targetNode}} else {this._root = targetNode}targetNode._right = current._righttargetNode._left = current._left}return true}}