1.概念

二叉树：树中每个节点最多只能有两个子节点，这样的树就成为"二叉树"。

完美二叉树（满二叉树）：除了最下一层的叶结点外，每层节点都有2个子结点，就构成了满二叉树。

完全二叉树：除二叉树最后一层外，其他各层的节点数都达到最大个数。且最后一层从左向右的叶结点连续存在，只缺右侧若干节点。

如下图所示：

二叉树的遍历：先序遍历、中序遍历、后续遍历

（1）先序遍历：访问根结点，先序遍历其左子树，先序遍历其右子树。

（2）中序遍历：中序遍历其左子树，访问根结点，中序遍历其右子树。

（3）后续遍历：后序遍历其左子树，后序遍历其右子树，访问根结点。

2.封装二叉数

function BinarySerachTree() {
  // 创建结点构造函数
  function Node(key) {
    this.key = key
    this.left = null
    this.right = null
  }
  // 保存根的属性
  this.root = null

  BinarySerachTree.prototype.insert = function (key) {
    var newNode = new Node(key)
    if (this.root === null) {
      this.root = newNode
    } else {
      this.insertNode(this.root, newNode)
    }
  }
  BinarySerachTree.prototype.insertNode = function (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)
      }
    }
  }

  //前序遍历
  BinarySerachTree.prototype.preOrderTraversal = function (handler) {
    this.preOrderTranversalNode(this.root, handler)
  }
  BinarySerachTree.prototype.preOrderTranversalNode = function (node, handler) {
    if(node!==null){
      handler(node.key)
      this.preOrderTranversalNode(node.left, handler)
      this.preOrderTranversalNode(node.right, handler)
    }
  }

  // 中序遍历
  BinarySerachTree.prototype.inOrderTraversal = function (handler) {
    this.inOrderTraversalNode(this.root, handler)
  }
  BinarySerachTree.prototype.inOrderTraversalNode = function (node, handler) {
    if (node !== null) {
      this.inOrderTraversalNode(node.left, handler)
      handler(node.key)
      this.inOrderTraversalNode(node.right, handler)
    }
  }

  // 后续遍历
  BinarySerachTree.prototype.postOrderTraversal = function (handler) {
    this.postOrderTraversalNode(this.root, handler)
  }

  BinarySerachTree.prototype.postOrderTraversalNode = function (node, handler) {
    if (node !== null) {
      this.postOrderTraversalNode(node.left, handler)
      this.postOrderTraversalNode(node.right, handler)
      handler(node.key)
    }
  }

  BinarySerachTree.prototype.min = function () {
    var node = this.root
    while (node.left !== null) {
      node = node.left
    }
    return node.key
  }

  BinarySerachTree.prototype.max = function () {
    var node = this.root
    while (node.right !== null) {
      node = node.right
    }
    return node.key
  }

  BinarySerachTree.prototype.search = function (key) {
    node = this.root
    while(node!==null){
      if(node.key>key){
        node = node.left
      }else if(node.key<key){
        node = node.right
      }else{
        return true
      }
    }
    return false
  }

  // 删除结点
  BinarySerachTree.prototype.remove = function (key) {
    // 1.定义临时保存的变量
    var current = this.root
    var parent = this.root
    var isLeftChild = true
    // 2.开始查找节点
    while (current.key !== key) {
      parent = current
      if (key < current.key) {
        isLeftChild = true
        current = current.left
      } else {
        isLeftChild = false
        current = current.right
      }
      // 如果发现current已经指向null, 那么说明没有找到要删除的数据
      if (current === null) return false
    }

    if (current.left === null && current.right === null) {  // 3.删除的结点是叶结点
      if (current === this.root) {
        this.root = null
      } else if (isLeftChild) {
        parent.left = null
      } else {
        parent.right = null
      }
    } else if (current.right === null) {   // 4.删除有一个子节点的节点
      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 {   //5.删除有两个节点的节点
      // 1.获取后继节点
      var successor = this.getSuccessor(current)
      // 2.判断是否是根节点
      if (current === this.root) {
        this.root = successor
      } else if (isLeftChild) {
        parent.left = successor
      } else {
        parent.right = successor
      }
      // 3.将删除节点的左子树赋值给successor
      successor.left = current.left
    }
    return true
  }

  // 找后继（向右找最小的节点）的方法
  BinarySerachTree.prototype.getSuccessor = function (delNode) {
    // 1.使用变量保存临时的节点
    var successorParent = delNode
    var successor = delNode
    var current = delNode.right // 要从右子树开始找
    // 2.寻找节点
    while (current != null) {
      successorParent = successor
      successor = current
      current = current.left
    }
    if (successor !== delNode.right) {
      successorParent.left = successor.right
      successor.right = delNode.right
    }
    return successor
  }
}

//测试
var bst = new BinarySerachTree()
bst.insert(11)
bst.insert(7)
bst.insert(15)
bst.insert(5)
bst.insert(3)
bst.insert(9)
bst.insert(8)
bst.insert(10)
bst.insert(13)
bst.insert(12)
bst.insert(14)
bst.insert(20)
bst.insert(18)
bst.insert(25)
bst.insert(6)
var resultString = ""
bst.preOrderTraversal(function (key) {
  resultString += key + " "
})
console.log(resultString)  // 11 7 5 3 6 9 8 10 15 13 12 14 20 18 25
resultString = ""
bst.inOrderTraversal(function (key) {
  resultString += key + " "
})
console.log(resultString) // 3 5 6 7 8 9 10 11 12 13 14 15 18 20 25
resultString = ""
bst.postOrderTraversal(function (key) {
  resultString += key + " "
})
console.log(resultString) // 3 5 6 7 8 9 10 11 12 13 14 15 18 20 25
console.log(bst.search(10)) // true
console.log(bst.search(21)) // false