兰溪建设网站,app制作软件多少钱,百度禁止seo推广,wordpress 多说样式二叉搜索树#xff1a;BST(Binary Search Tree) 二叉搜索树是二叉树#xff0c;可以为空#xff0c;如果不为空#xff0c;满足以下性质#xff1a;
非空左子树的所有键值小于其根节点的键值非空右子树的所有键值大于其根节点的键值左、右字数本身也都是二叉搜索树
二叉…二叉搜索树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}}
