二分搜索树

[JesseZhao1990]

二分搜索树（binary search tree）的定义

每个节点的键值大于左子树并且小于右子树的二叉树即使二分搜索树

二分搜索树的实现

/**
 * 节点类
 */
class Node {
  constructor(key,value){
    this.key = key;
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

/**
 * 二分搜索树
 */
class BST {
  constructor(){
    this.root = null;
    this.count = 0;
  }
  
  /**
   * 获取二分搜索树的大小
   */
  size(){
    return this.count;
  }

  /**
   * 向二分搜索树中插入一个值
   * @param key 
   * @param value 
   */
  insert(key,value){
    let self = this;
    function _insert(node,key,value){
      if(node === null){
        self.count++
        return new Node(key,value)
      }
      if(node.key===key){
        node.value = value;
      }
      if(key<node.key){
        node.left = _insert(node.left,key,value);
      }
      if(key>node.key){
        node.right = _insert(node.right,key,value);
      }
      return node;
    }
    this.root  = _insert(this.root,key,value)
  }

  /**
   * 在二分搜索树中查找一个值
   * @param key 
   */
  contain(key){
    function _contain(node,key){
      if(node === null) return false;
      if(node.key === key){
        return node;
      }else if(node.key>key){
        return _contain(node.left,key);
      }else{
        return _contain(node.right,key);
      }
    }
    _contain(this.root,key);
  }

  delete(){

  }

  /**
   * 对二分搜索树进行前序遍历
   */
  preOrder(){
    function _preOrder(node){
      if(node === null) return;
      console.log(node.key);
      _preOrder(node.left);
      _preOrder(node.right);
    }
    _preOrder(this.root);
  }

  /**
   * 对二分搜索树进行中序遍历
   */
  inOrder(){
    function _inOrder(node){
      if(node === null) return;
      _inOrder(node.left);
      console.log(node.key);
      _inOrder(node.right);
    }
    _inOrder(this.root)
  }

  /**
   * 对二分搜索树进行中序遍历
   */
  postOrder(){
    function _postOrder(node){
      if(node===null) return;
      _postOrder(node.left);
      _postOrder(node.right);
      console.log(node.key);
    }
    _postOrder(this.root)
  }

  /**
   * 层序遍历（广度优先遍历）
   */
  levelOrder(){
    let queue = [];
    queue.push(this.root);
    while(queue.length!=0){
      let node = queue.shift()
      console.log(node.key);
      if(node.left) queue.push(node.left);
      if(node.right) queue.push(node.right);
    }
  }

  /**
   * 查找二分搜索树中的最小值
   */
  miniNum(){
    function _miniNum(node){
      if(node.left === null){
        return node;
      }
      return _miniNum(node.left);
    }
    return _miniNum(this.root)
  }

  /**
   * 查找二分搜索树中的最大值
   */
  maxNum(){
    function _maxNum(node){
      if(node.right ===  null){
        return node;
      }
      return _maxNum(node.right);
    }
    return _maxNum(this.root);
  }

  /**
   * 删除二分搜索树中的最小值
   */
  removeMin(){
    let self = this;
    function _removeMin(node){
      if(node.left === null){
        node = node.right;
        self.count--;
      }
      _removeMin(node.left)
    }
    _removeMin(this.root);
  }

  /**
   * 删除二分搜索树中的最大值
   */
  removeMax(){
    let self = this;
    function _removeMax(node){
      if(node.right === null){
        node = node.left;
        self.count--;
      }
      _removeMax(node.right); 
    }
    __removeMax(this.root);
  }

  /**
   * 删除某一个节点
   * @param key 
   */
  remove(key){
    let self = this;
    function _remove(node,key){
      if(node === null) return;
      if(node.key === key){
        // 当左节点为空时，把右节点替换成本节点即可
        if(node.left === null){
          node = node.right;
          return;
        }
        // 当右节点为空时，把左节点替换成本节点即可
        if(node.right === null){
          node = node.left;
          return;
        }
        // 当左右节点都存在时，把左侧节点的最小值替换成本节点即可
        let min = self.miniNum(node.right);
        node.key = min.key;
        node.value = min.value;
        min = null;
        
      }else if(node.key < key){
        _remove(node.right,key);
      }else{
        _remove(node.left,key);
      }
    }
    _remove(this.root,key);

    return this.root;
  }


}

[JesseZhao1990]

二分搜索树的应用