实现二叉搜索树

function BinarySearchTree() {
  this.root = null
  function Node(key) {
    this.key = key 
    this.left = null
    this.right = null
  }
}

insert(key) {
  //创建新节点
  let node = new Node(key)
  //判断根节点是否存在
  if(this.root === null) { //根节点不存在
    this.root = node 
  } else {
    //递归比较新节点和当前节点
    this.insertNode(this.root,node)
  }
}
insertNode(node, newNode) {
  //比较新节点和当前节点
  if(newNode.key < node.key) { //在当前节点的左子节点
    if(node.left === null) { //当前节点左子节点不存在
      node.left = newNode 
    } else { //继续比较
      this.insertNode(node.left, newNode)
    }
  } else { //在当前节点的右子节点
    if(node.right === null) { //当前节点的右子节点不存在
      node.right = newNode
    } else { //继续比较
      this.insertNode(node.right, newNode) 
    }
  }
}

max() {
  let node = this.root
  while(node != null && node.right != null) {
    node = node.right
  }
  return node
}

min() {
  let node = this.root
  while(node != null && node.left != null) {
    node = node.left 
  }
  return node
}

search(key) {
  //从根节点开始寻找
  return this.searchNode(this.root, key)
}
searchNode(node, key) {
  //判断节点是否存在
  if(node === null) {
    return false 
  }
  if(key < node.key) { //向左查找
    return this.searchNode(node.left, key)
  } else if(key > node.key) { //向右查找
    return this.searchNode(node.right, key) 
  } else {
    return true 
  }
}

remove(key) {
  let parent = null
  let current = this.root
  this.isLeftChild = true
  while(key != current.key) {
    parent = current
    if(key < node.key) {
      isLeftChild = true
      current = currrent.left
    } else {
      isLeftChild = false
      current = 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.right === null) {
    if(current === this.root) {
       this.root = current.left
    } else if(isLeftChild) {
      parent.left = current.left 
    } else {
      parent.right = current.left	
    }
  }
  //删除节点只有一个右子节点
  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 {
    //获取后继或前驱节点
    let successor = this.getSuccessor(current)
    if(current === this.root) {
      this.root = successor
    } else if(isLeftChild) {
      parent.left = successor
    } else {
      parent.right = successor
    }
    successor.left = current.left

    let precursor = this.getPrecursor(current)
    if(current === this.root) {
      this.root = precursor 
    } else if(isLeftChild) {
      parent.left = precursor 
    } else {
      parent.right = precursor 
    }
    precursor.right = current.right
  }
}

getSuccessor(delNode) {
  let successor = delNode
  let current = delNode.right
  let successorParent = delNode
  while(current != null) {
    successorParent = successor
    successor = current
    current = current.left
  }
  if(successor != delNode.right) {
    successorParent.left = successor.right
    successor.right = delNode.right
  }
}
getPrecursor(delNode) {
  let precursor = delNode
  let current = delNode.left
  let precursorParent = delNode
  while(current != null) {
    precursorParent = precursor
    precursor = current
    current = current.right
  }
  if(precursor != delNode.left) {
    precursorParent.right = precursor.left
    precursor.left = delNode.left 
  }
}

preorderTraversal(handle) {
  this.preorderTraversalNode(this.root, handle)
}
preorderTraversalNode(node, handle) {
  if(node != null) {
    handle(node.key)
    this.preorderTraversalNode(node.left, handle)
    this.preorderTraversalNode(node.right, handle)
  }
}

middleorderTraversal(handle) {
  this.middleorderTraversalNode(this.root, handle)
}
middleorderTraversalNode(node, handle){
  if(node != null) {
    this.middleorderTraversalNode(node.left, handle)
    handle(node.key)
    this.middleorderTraversalNode(node.right, handle) 
  }
}

postorderTraversal(handle) {
  this.postorderTraversalNode(this.root, handle)
}
postorderTraversalNode(node, handle) {
  if(node ！= null) {
    this.postorderTraversalNode(node.left, handle)
    this.postorderTraversalNode(node.right, handle)
    handle(node.key) 
  }
}