JS实现二叉搜索树与常见操作

class TreeNode {
  constructor(val) { this.val = val; this.left = null; this.right = null; }
}
class BST {
  constructor() { this.root = null; }
  
  insert(val) {
    const _insert = (node, val) => {
      if (!node) return new TreeNode(val);
      if (val < node.val) node.left = _insert(node.left, val);
      else if (val > node.val) node.right = _insert(node.right, val);
      return node;
    };
    this.root = _insert(this.root, val);
  }
  
  search(val) {
    let cur = this.root;
    while (cur) {
      if (val === cur.val) return true;
      cur = val < cur.val ? cur.left : cur.right;
    }
    return false;
  }
  
  inOrder(node = this.root, res = []) {
    if (!node) return res;
    this.inOrder(node.left, res);
    res.push(node.val);
    this.inOrder(node.right, res);
    return res;
  }
  
  preOrder(node = this.root, res = []) {
    if (!node) return res;
    res.push(node.val);
    this.preOrder(node.left, res);
    this.preOrder(node.right, res);
    return res;
  }
  
  postOrder(node = this.root, res = []) {
    if (!node) return res;
    this.postOrder(node.left, res);
    this.postOrder(node.right, res);
    res.push(node.val);
    return res;
  }
}

时间复杂度：平均O(log n)，最坏O(n)。BST是很多高级数据结构(红黑树、AVL)的基础。