了解JavaScript数据结构和算法（四）: 二进制搜索树(2)

说明: 从树上移除要处理的场景的键:

只是一个叶子节点

有一个子节点

具有两个子节点的节点

因为您必须处理不同的情况，所以这是最麻烦的方法. 我花了很长时间才了解. 如果您不了解，则可以下载源代码并再次编写本段.

实现:

/**
 * 从树中移除某个键
 * @param  {Key} key 要移除的键值
 * @return {Function}     remove函数的辅助函数
 */
this.remove = function(key) {
  root = removeNode(root, key);
};
/**
 * remove函数的辅助函数
 * @param  {Node} node 搜索开始的节点，默认为root
 * @param  {Key} key   要移除的键值
 * @return {Boolean}   移除成功则返回true，否则返回false
 */
var removeNode = function(node, key) {
  // 如果根节点不存在，则直接返回null
  if (node === root) {
    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 {
    // 第一种场景：只是一个叶节点
    // 这种情况只需要直接把节点赋值为null即可
    if (node.left === null && node.right === null) {
      node = null;
      // 处理完直接return节点
      return node;
    }
    // 第二种场景：有一个子节点
    // 如果左节点为null，则代表右节点存在。
    // 于是把当前节点赋值为存在的那个子节点
    if (node.left === null) {
      node = node.right;
      // 处理完直接return节点
      return node;
    } else if (node.right == null) {
      node = node.left;
      // 处理完直接return节点
      return node;
    }
    // 第三种场景：有两个子节点
    // 首先加入辅助节点，同时找寻右子节点中的最小节点
    // 并把当前节点替换为右子节点中的最小节点
    // 同时为了避免节点重复，移除右子节点中的最小节点
    var aux = findMinNode(node.right);
    node.key = aux.key;
    node.right = removeNode(node.right, aux.key);
    // 处理完直接return节点
    return node;
  }
};
/**
 * remove函数的辅助函数
 * @param  {Node} node 查找开始的节点，默认为root
 * @return {Node}      最小的节点
 */
var findMinNode = function(node) {
  // 如果node存在，则开始搜索。能避免树的根节点为Null的情况
  if (node) {
    // 只要树的左侧子节点不为null，则把左子节点赋值给当前节点。
    // 若左子节点为null，则该节点肯定为最小值。
    while (node && node.left !== null) {
      node = node.left;
    }
    return node;
  }
  return null;
};

源代码在这里〜

二叉搜索树源代码

撰写文章时，人们会感到有些头晕目眩. 但是写完之后好多了，我的头脑更加清晰了.

二叉树的这一章对我来说非常激动. 可以将它视为暂时满足我对数据结构中“树”的渴望和渴望，而不是对数据结构中的困惑.

我很高兴能够使用JavaScript做到这一点.

前端是很长的路，是一首歌〜

Lxxyx的前端公园

原始链接: 寒假前端学习（6）-学习JavaScript数据结构和算法（4）: 二进制搜索树

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-262415-2.html