散列表也是支持这些操作的，并且散列表的这些操作比二叉查找树更高效，时间复杂度是 O(1)。既然有了这么高效的散列表，使用二叉树的地方是不是都可以替换成散列表呢？有没有哪些地方是散列表做不了，必须要用二叉树来做的呢？

概念

二叉查找树是二叉树中最常用的一种类型，也叫二叉搜索树。
二叉查找树特点：在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。image.png

代码实现

查找

先取根节点，如果它等于要查找的数据，那就返回。如果要查找的数据比根节点的值小，那就在左子树中递归查找；如果要查找的数据比根节点的值大，那就在右子树中递归查找。

插入

类似查找操作。新插入的数据一般都是在叶子节点上，所以只需要从根节点开始，依次比较要插入的数据和节点的大小关系。
如果要插入的数据比节点的数据大，并且节点的右子树为空，就将新数据直接插到右子节点的位置；如果不为空，就再递归遍历右子树，查找插入位置。同理，如果要插入的数据比节点数值小，并且节点的左子树为空，就将新数据插入到左子节点的位置；如果不为空，就再递归遍历左子树，查找插入位置。

删除

针对要删除节点的子节点个数的不同，需要分三种情况来处理：比如图中的删除节点 55。

  1. 如果要删除的节点没有子节点，只需要直接将父节点中，指向要删除节点的指针置为 null。
  2. 如果要删除的节点只有一个子节点（只有左子节点或者右子节点），只需要更新其父节点的指针指向要删除节点的子节点。比如图中的删除节点 13。
  3. 如果要删除的节点有两个子节点，比较复杂。需要找到这个节点的右子树中的最小节点，把它替换到要删除的节点上。然后再删除掉这个最小节点，因为最小节点肯定没有左子节点（如果有左子结点，那就不是最小节点了），所以，可以应用上面两条规则来删除这个最小节点。比如图中的删除节点 18。

image.png
实际上，关于二叉查找树的删除操作，还有个非常简单、取巧的方法，就是单纯将要删除的节点标记为“已删除”，但是并不真正从树中将这个节点去掉。这样原本删除的节点还需要存储在内存中，比较浪费内存空间，但是删除操作就变得简单了很多。而且，这种处理方法也并没有增加插入、查找操作代码实现的难度。

  1. class Node {  // 创建节点
  2.   constructor(data) {
  3.     this.root = this
  4.     this.data = data
  5.     this.left = null
  6.     this.right = null
  7.   }
  8. }
  10. class BinarySearchTree {
  11.   constructor() {
  12.     this.root = null //初始化根节点
  13.   }
  14.   // 插入节点
  15.   insert(data) {
  16.     const newNode = new Node(data)
  17.     const insertNode = (node, newNode) => {
  18.       if (newNode.data < node.data) { // 如果插入的节点值比父节点小则插入到左节点上反之则插入到右节点上
  19.         if (node.left === null) {
  20.           node.left = newNode
  21.         } else {
  22.           insertNode(node.left, newNode) // 递归找下一层的左侧节点（重点）
  23.         }
  24.       } else {
  25.         if (node.right === null) {
  26.           node.right = newNode
  27.         } else {
  28.           insertNode(node.right, newNode)
  29.         }
  30.       }
  31.     }
  32.     if (!this.root) {
  33.       this.root = newNode
  34.     } else {
  35.       insertNode(this.root, newNode)
  36.     }
  37.   }
  38.   // 中序遍历所有节点（左根右）
  39.   inOrderTraverse() {
  40.     let backs = []
  41.     const callback = data => {
  42.       return data
  43.     }
  44.     const inOrderNode = (node, callback) => {
  45.       if (node !== null) {
  46.         inOrderNode(node.left, callback) // 递归遍历出左节点
  47.         backs.push(callback(node.data))  // 将值push到数组里
  48.         inOrderNode(node.right, callback)  // 递归遍历出右节点
  49.       }
  50.     }
  51.     inOrderNode(this.root, callback)
  52.     return backs
  53.   }
  54.   // 前序遍历所有节点（根左右）
  55.   preOrderTraverse() {
  56.     let backs = []
  57.     const callback = data => {
  58.       return data
  59.     }
  60.     const inOrderNode = (node, callback) => {
  61.       if (node !== null) {
  62.         backs.push(callback(node.data))  // 将值push到数组里
  63.         inOrderNode(node.left, callback) // 递归遍历出左节点
  64.         inOrderNode(node.right, callback)  // 递归遍历出右节点
  65.       }
  66.     }
  67.     inOrderNode(this.root, callback)
  68.     return backs
  69.   }
  70.   // 后序遍历所有节点（左右根）
  71.   postOrderTraverse() {
  72.     let backs = []
  73.     const callback = data => {
  74.       return data
  75.     }
  76.     const inOrderNode = (node, callback) => {
  77.       if (node !== null) {
  78.         inOrderNode(node.left, callback) // 递归遍历出左节点     
  79.         inOrderNode(node.right, callback)  // 递归遍历出右节点
  80.         backs.push(callback(node.data))  // 将值push到数组里
  81.       }
  82.     }
  83.     inOrderNode(this.root, callback)
  84.     return backs
  85.   }
  86.   //查找最小值
  87.   // 这里可以利用search 查找指定节点下面的最小值
  88.   min(node) {
  89.     const minNode = (node) => {
  90.       return node ? (node.left ? minNode(node.left) : node) : null
  91.     }
  92.     return minNode(node || this.root)
  93.   }
  94.   // 查找最大值
  95.   max(node) {
  96.     const maxNode = (node) => {
  97.       return node ? (node.right ? maxNode(node.right) : node) : null
  98.     }
  99.     return maxNode(node || this.root)
  100.   }
  101.   //查找特定值
  102.   search(data) {
  103.     const searchNode = (node) => {
  104.       if (node === null) return false
  105.       if (node.data === data) {
  106.         return node
  107.       }
  108.       return searchNode(data < node.data ? node.left : node.right, data)
  109.     }
  110.     return searchNode(this.root, data)
  111.   }
  112.   //从树中移除某个键
  113.   remove(data) { // 删除节点复杂之处在于每次删除节点时候二叉树要根据不同情况改变结构 同样也需要递归
  114.     const removeNode = (node, data) => {
  115.       if (node === null) return null
  116.       if (node.data === data) {
  117.         if (node.left === null && node.right === null) return null
  118.         if (node.left === null) return node.right
  119.         if (node.right === null) return node.left
  120.         if (node.left !== null && node.right !== null) {
  121.           let _node = this.min(node.right)
  122.           node.data = _node.data
  123.           node.right = removeNode(node.right, data)
  124.           return node
  125.         }
  126.       } else if (data < node.data) {
  127.         node.left = removeNode(node.left, data)
  128.         return node
  129.       } else {
  130.         node.right = removeNode(node.right, data)
  131.         return node
  132.       }
  133.     }
  134.     return removeNode(this.root, data)
  135.   }
  136. }
  138. const tree = new BinarySearchTree()
  139. tree.insert(11)
  140. tree.insert(7)
  141. tree.insert(5)
  142. tree.insert(3)
  143. tree.insert(9)
  144. tree.insert(8)
  145. tree.insert(10)
  146. tree.insert(13)
  147. tree.insert(12)
  148. tree.insert(14)
  149. tree.insert(20)
  150. tree.insert(18)
  151. tree.insert(25)
  152. console.log(tree.inOrderTraverse())
  153. console.log(tree.preOrderTraverse())
  154. console.log(tree.postOrderTraverse())
  155. console.log(tree.min())
  156. console.log(tree.max())
  157. console.log(tree.search(20))
  158. console.log(tree.remove(7))

将二叉查找树转换成一个排序的双向链表

  • 思路

因为二叉搜索树是左子树的所有节点比根节点小，右子树的所有节点比根节点大，所以如果要转换成一个有序的双向链表应该以中序遍历：左子树 -> 根节点 -> 右子树的顺序遍历二叉树，进行递归

  • 解法1

先用递归中序遍历二叉树并将结果保存在list中
遍历list修改指针指向

  • 解法2

递归，先将左子树调整为双向链表，并用变量pLast指向最后一个节点
再将中间节点和pLast连起来
再去调整右子树
最后返回最后一个节点，再向前移到第一个节点并返回

// 1
function Convert(pRootOfTree) {
  // write code here
  if (!pRootOfTree) return null
  let list = new Array()
  ConvertNode(pRootOfTree, list)  //中序遍历
  for (let i = 0; i < list.length - 1; i++) { //注意是list.length-1
    list[i].right = list[i + 1]
    list[i + 1].left = list[i]
  }
  return list[0]
}

function ConvertNode(root, list) {
  if (root.left)
    ConvertNode(root.left, list)
  list.push(root)
  if (root.right)
    ConvertNode(root.right, list)
}

// 2
function Convert(pRootOfTree) {
  // write code here
  if (!pRootOfTree)
    return null
  let pLast = null
  pLast = ConvertNode(pRootOfTree, pLast)  //最后一个节点
  let pHead = pLast
  while (pHead.left) {  //移到第一个节点
    pHead = pHead.left
  }
  return pHead
}

function ConvertNode(pNode, pLast) {
  if (pNode.left) {
    pLast = ConvertNode(pNode.left, pLast)
  }
  pNode.left = pLast  //该节点的left指针指向上一个节点
  if (pLast) {  //上一个节点的right指针指向下一个节点
    pLast.right = pNode
  }
  pLast = pNode
  if (pNode.right) {
    pLast = ConvertNode(pNode.right, pLast)
  }
  return pLast
}

复杂度

image.png
最理想的二叉查找树是一客完全二叉树(或满二叉树)，时间复杂度跟树的高度成正比，也就是 O(height) ≤ O(log**2**n)；
最坏的情况就是极度不平衡的二叉树，完全退化成了链表，时间复杂度是O(n)；
平衡二叉树的时间复杂度是O(logn)；