学习数据结构与算法之二叉搜索树

摘要：二叉搜索树是二叉树的一种，其特征是左侧子节点存储比父节点小的值，右侧子节点存储比父节点大或等于父节点的值。实现和这个两个方法其实挺简单的，最小的节点就在二叉搜索树的最左反之，最大的就在最右。

本系列所有文章：
第一篇文章：学习数据结构与算法之栈与队列
第二篇文章：学习数据结构与算法之链表
第三篇文章：学习数据结构与算法之集合
第四篇文章：学习数据结构与算法之字典和散列表
第五篇文章：学习数据结构与算法之二叉搜索树

二叉树是一种非线性数据结构，其中的每个元素我们称为节点，二叉树中每个节点最多只能有两个子节点；没有父节点的节点称为根节点，没有子节点的节点称为叶节点。二叉搜索树是二叉树的一种，其特征是左侧子节点存储比父节点小的值，右侧子节点存储比父节点大（或等于父节点）的值。下图就是一颗典型的二叉搜索树:

二叉搜索树的节点，我们用类似双向链表的方式存储节点（都包含两个对其他节点的引用），但是这里两个引用指向的分别是左右两个子节点。

function BinarySearchTree () {
  // 二叉树的键
  var Node = function (key) {
    // 键值
    this.key = key
    // 左节点
    this.left = null
    // 右节点
    this.right = null
  }
  
  // 根节点
  var root = null
}

二叉搜索树需要实现以下方法：

insert(key)：向树中插入一个新的键

search(key)：在树中查找一个键，如果节点存在返回tue，否则返回false

inOrderTraverse：通过中序遍历方式遍历所有节点

preOrderTraverse：通过先序遍历方式遍历节点

postOrderTraverse：通过后序遍历方式遍历所有节点

min：返回树中最小的值

max：返回树中最大的值

remove(key)：从树中移除某个键

注意：本文中很多地方使用了递归的方法，如果不了解递归，可以先看看这个知乎问题-递归

// 用于插入节点
var insertNode = function (node, newNode) {
  // 在二叉搜索树中，比父节点小的值存在左侧节点，大于等于父节点的存在右侧节点
  // 若要插入一个节点（根节点已存在），首先与根节点比大小，若比根节点小则应插入根节点的左侧
  // 如果左侧已存在节点，则递归调用函数，将左侧节点传入递归函数作为当前节点
  // 如果插入的节点比当前节点大且当前节点右侧为空，则插入右侧
  // 如果插入节点比根节点大，原理同上
  if (newNode.key < node.key) {
    if (node.left === null) {
      node.left = newNode
    } else {
      insertNode(node.left, newNode)
    }
  } else {
    if (node.right === null) {
      node.right = newNode
    } else {
      insertNode(node.right, newNode)
    }
  }
}

// 插入
this.insert = function (key) {
  var node = new Node(key)

  if (root === null) {
    root = node
  } else {
    insertNode(root, node)
  }
}

这里同样借助一个辅助函数使用，辅助函数同样是用了递归，简单比较输入的key与当前节点的key，当相等时（意味着找到了目标节点）就返回true；当查找完最末端的节点时，即传入的node为null时，就返回false，表示未找到。

有人可能会怀疑，这样真的找到吗？实际上，由于二叉搜索树子节点“左小右大”的性质，一个特定的值在二叉搜索树中的大致位置是可预见的（即使是插入那个值也不会跑出那个范围）。所以仅仅通过简单的比较key就能在某个范围中找到目标节点，而且这种方法不用遍历整棵树去找，非常节省性能。

var searchNode = function (node, key) {
  if (node === null) {
    false
  }

  if (key < node.key) {
    return searchNode(node.left, key)
  } else if (key > node.key) {
    return searchNode(node.right, key)
  } else {
    return true
  }
}

// 查找节点
this.search = function (key) {
  return searchNode(root, key)
}

接下来就是三个遍历方法，先从中序遍历开始，其作用是按顺序（从小到大）访问整棵树的所有节点，也就是常见的升序排序。

其实这三种遍历并没有那么复杂，简单地观察一下回调函数（也就是访问key）的位置，就能看出来是哪种排序。

var inOrderTraverseNode = function (node, callback) {
  if (node !== null) { // 停止递归的条件
    inOrderTraverseNode(node.left, callback)
    callback(node.key)
    inOrderTraverseNode(node.right, callback)
  }
}

// 中序遍历
this.inOrderTraverse = function (callback) {
  inOrderTraverseNode(root, callback)
}

var preOrderTraverseNode = function (node, callback) {
  if (node !== null) {
    callback(node.key)
    preOrderTraverseNode(node.left, callback)
    preOrderTraverseNode(node.right, callback)
  }
}

// 先序遍历
this.preOrderTraverse = function (callback) {
  preOrderTraverseNode(root, callback)
}

var postOrderTraverseNode = function (node, callback) {
  if (node !== null) {
    postOrderTraverseNode(node.left, callback)
    postOrderTraverseNode(node.right, callback)
    callback(node.key)
  }
}

// 后序遍历
this.postOrderTraverse = function (callback) {
  postOrderTraverseNode(root, callback)
}

这里先停一下：的确看回调函数就能知道这是哪种遍历，但是这些函数递归理解起来确实有点困难，这里我建议在重复的大问题面前先拆成小问题来看：

请看这个最简单的二叉树

如果现在先序遍历这个二叉树，它的顺序应该是M -> H -> Z；中序遍历的顺序是H -> M -> Z；后序遍历是：H -> Z -> M

那么再看下面这棵大树的中序遍历就会好理解了：先从根节点左侧子树开始遍历，左侧子树里面又有小左侧子树，里面最小的由3，5，6组成的子树就和上面最简单的二叉树一样了。这时遍历从3开始，以正常的中序遍历顺序3 -> 5 -> 6。当遍历完6之后我们可以将这个小的子树看成一个整体，这个整体和上面的父节点7以及右边的子树也组成了一个简单的二叉树结构，然后正常遍历7 -> 右侧子树，右侧子树中依旧按照中序遍历的顺序：8 -> 9 -> 10，按此顺序不断遍历完所有的节点。

这个两个方法其实挺简单的，最小的节点就在二叉搜索树的最左；反之，最大的就在最右。

var minNode = function(node) {
  // 如果node存在，则开始搜索。能避免树的根节点为Null的情况
  if (node) {
    // 只要树的左侧子节点不为null，则把左子节点赋值给当前节点。
    // 若左子节点为null，则该节点肯定为最小值。
    while (node && node.left !== null) {
      node = node.left
    }
    return node.key
  }
  return null
}

var maxNode = function(node) {
  if (node) {
    while (node && node.right !== null) {
      node = node.right
    }
    return node.key
  }
  return null
}

// 找到最小节点
this.min = function () {
  return minNode(root)
}

// 找到最大节点
this.max = function () {
  return maxNode(root)
}

好了，现在剩下最后一个方法了，先深吸一口气。。。

接下来实现的方法号称全书最复杂的方法，鉴于本人目前水平有限，我只能将自己看懂的思路写出来，如果讲得不好大家可以去看原书《学习JavaScript数据结构与算法》。

下面进入正题：

移除二叉搜索树中的一个节点需要考虑三种情况：

删除的是叶节点（没有子节点的节点）

删除的节点有一侧子节点

删除的节点有两侧子节点

还是老原则，化繁为简。

先看第一个比较简单的：既然它没有子节点，那就先找到它，再直接将它与父节点的联系切断就行了；

第二个就稍微复杂一点：你得先把它删掉，然后把它的子节点接到它的父节点上去；

第三个最复杂：你不能直接删掉它，你应该在它的右侧子树里面找到最小的那个节点把它替换掉，然后为防止重复，把替换它的节点删掉就万事大吉了。

这里前两种情况都还能理解，所以我只解释为什么是右侧子树的最小节点。

其实这是为了防止顺序乱掉而做的处理，举个例子：

还是之前的那张图，我要删掉15这个节点，那么这时无论是把20还是13接到根节点11下面都会导致二叉搜索树“左小右大”的结构大乱（就像曹操如果没有接班人就死了北方就会大乱），因此最好的办法是找一个比他大一点的节点来替换它（找一个强一点的接班人坐他的位子维持秩序）。

这里为啥是大一点而不是大很多？因为大太多也会导致结构混乱（过于强势成为暴君就不给底下人活路了）。所以就选了一个大一点的节点替换到这个位置上来，同时为防止重复就删掉了原来的节点（接班人不能身兼两职所以要辞掉原来的职位）。

说到这里我就直接贴代码了，反正现在让我写，一时半会是写不出来的，因此仅供观摩：

// 这个辅助函数和minNode函数是一样的，只不过返回值不一样
var findMinNode = function (node) {
  if (node === null) {
    while (node && node.left !== null) {
      node = node.left
    }
    return node
  }
  return null
}

var removeNode = function (node, key) {
  if (node === null) {
    return null
  }

  if (key < node.key) {
    node.left = removeNode(node.left, key)
    return node
  } else if (key > node.key) {
    node.right = removeNode(node.right, key)
    return node
  } else {
    // 第一种情况：删除叶节点
    if (node.left === null && node.right === null) {
      node = null
      return node
    }

    // 第二种情况：删除一侧有子节点的节点
    // 将一侧的子节点替换为当前节点
    if (node.left === null) {
      node = node.right
      return node
    } else if (node.right === null) {
      node = node.left
      return node
    }

    // 第三种情况：删除两侧都有子节点的节点
    // 找到当前节点右侧子树中最小的那个节点，替换掉要删除的节点
    // 然后再把右侧子树中最小的节点移除
    var aux = findMinNode(node.right)
    node.key = aux.key
    node.right = removeNode(node.right, aux.key)
    return node
  }
}

// 删除节点
this.remove = function (key) {
  root = removeNode(root, key)
}

源代码在此：

二叉搜索树的实现-源代码

实现二叉搜索树花了好长时间，后面的图也是挺麻烦的数据结构，但是这段时间不停地学习数据结构也是让自己得到了很大成长。继续加油～