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

本系列的第一篇文章: 学习JavaScript数据结构和算法（1），堆栈和队列

第二篇文章: 学习JavaScript数据结构和算法（二）: 链表

第三篇文章: 学习JavaScript数据结构和算法（三）: 集合

第四篇: 学习JavaScript数据结构和算法（四）: 二进制搜索树

当我第一次学习编程时，我知道有一个称为“树”的数据结构，而树中的领导者是“二叉树”，“红黑树”等等.

据说，“树”结构在编程世界中是万能的. 无数程序员感到恐惧. 即使在采访中，甚至还有诸如“手写二叉树”，“翻转二叉树”之类的问题.

好的，我承认这些让我很害怕.

但是当我颤抖地打开“学习JavaScript数据结构和算法”并开始输入有关“树”的代码时，我突然觉得这似乎并不困难.

我感到非常兴奋，以至于我一口气完成了本书中的示例，并且在中间思考了很长时间，不断地在纸上进行计算等等. 但是总的来说，我仍然很高兴学习.

以前学习的数据结构（例如堆栈，队列和链表）都是顺序数据结构. 该树将成为我们学习的第一个非顺序数据结构.

实际上，有一个非常生动的例子，公司组织. 看起来像这样:

我们要学习的树看起来像这样:

其中，树中的每个元素称为一个节点. 从该节点延伸的节点称为子节点.

树顶部的节点称为根节点. 每棵树只有一个根节点. （图中的15是根节点）

在节点中，具有子节点的节点也称为内部节点，否则称为内部节点或叶节点.

同时，节点中存在祖先与后代的关系，例如，节点9的祖先有13、7、6、15个.

深度: 节点的深度取决于其祖先的数量，节点9的深度为4.

树的高度. 树的高度是节点的最大深度.

例如，最大节点深度为4，树的高度为4.

二叉树的最大特点是它的节点最多有两个子节点: 左子节点和右子节点.

二进制搜索树是一种二进制树，但是它只允许您在左节点上存储比父节点小的值，而在右节点上存储更大的值.

就像这张图片一样，它是一个二叉搜索树.

在本文中，我们将学习如何编写二进制搜索树.

首先，创建一个构造函数.

/**
 * 二叉搜索树的构造函数
 */
function BinarySearchTree() {
  /**
   * 二叉搜索树键的构造函数
   * @param {Number} key 要生成的键值
   */
  var Node = function(key) {
    // 键值
    this.key = key;
    // 左子节点
    this.left = null;
    // 右子节点
    this.right = null;
  }
  /**
   * 二叉树的根节点，不存在时表示为Null
   * @type {Null or Number}
   */
  var root = null;
}

在前面提到的双向链表中，每个节点包含两个指针，一个指向左侧节点，另一个指向右侧节点. 在二叉搜索树中，每个节点还具有两个指针，一个指向左侧的子节点构造二叉排序树，另一个指向右侧的子节点. 但是在二叉搜索树中，我们将节点设为关键字，即术语.

二进制搜索树需要以下方法:

二叉搜索树的实现基本上与递归有关（对我来说，递归是非常规避的，花了很长时间才能理解）. 如果您不清楚递归，可以查看下面的参考链接.

什么是递归

说明: 将新密钥插入树中

实现:

/**
 * 插入某个键到二叉树中
 * @param  {Number} key 要插入的键值
 */
this.insert = function(key) {
  // 用传入的值生成二叉树的键
  var newNode = new Node(key);
  // 根节点为Null时，传入的键则为根节点
  // 否则调用insertNode函数来插入子节点
  if (root === null) {
    root = newNode;
  } else {
    insertNode(root, newNode)
  }
};
/**
 * 用于插入子节点。
 * @param  {Node} node    根节点
 * @param  {Node} newNode 要插入的节点
 */
var insertNode = function(node, newNode) {
  //由于二叉搜索树的性质，所以当键值小于当前所在节点的键值
  //则使得左子结点成为新的要比较的节点，进行递归调用
  //如果左子结点为null，则将键值赋值给左子结点。
  //如果键值大于当前所在节点的键值，原理同上。
  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)
    }
  }
};

说明: 通过中阶遍历方法遍历所有节点

实现:

/**
 * 中序遍历操作，常用于排序。会把树中元素从小到大的打印出来。
 * 因为在javascript的递归中，遇到递归是，会优先调用递归的函数。直到递归不再进行。
 * 然后会在递归调用的最后一个函数中执行其它语句。再一层层的升上去。
 * 所以中序遍历会有从小到大的输出结果。
 * 后续的先序和后续遍历和这个原理差不多，取决于callback放在哪儿。
 * 
 * @param  {Function} callback 获取到节点后的回调函数
 */
this.inOrderTraverse = function(callback) {
  inOrderTraverseNode(root, callback);
};
/**
 * 中序遍历的辅助函数，用于遍历节点
 * @param  {Node}   node     遍历开始的节点，默认为root
 * @param  {Function} callback 获取到节点后的回调函数
 * @return {[type]}            [description]
 */
var inOrderTraverseNode = function(node, callback) {
  // 当前节点不为NULL则继续递归调用
  if (node != null) {
    inOrderTraverseNode(node.left, callback);
    // 获取到节点后，调用的函数
    callback(node.key);
    inOrderTraverseNode(node.right, callback);
  }
};

如果我们在此处添加函数以打印节点值:

var printNode = function(value) {
  console.log(value);
};
inOrderTraverse(printNode) // 输出排序后树的值

说明: 以顺序遍历模式遍历所有节点

实现:

/**
 * 前序遍历操作，常用于打印一个结构化的文档
 * @param  {Function} callback 获取到节点后的回调函数
 */
this.preOrderTranverse = function(callback) {
  preOrderTranverseNode(root, callback);
};
/**
 * 前序遍历的辅助函数，用于遍历节点
 * @param  {Node}   node     遍历开始的节点，默认为root
 * @param  {Function} callback 获取到节点后的回调函数
 */
var preOrderTranverseNode = function(node, callback) {
  if (node != null) {
    callback(node.key);
    preOrderTranverseNode(node.left, callback);
    preOrderTranverseNode(node.right, callback);
  }
};

说明: 通过后遍历方法遍历所有节点

实现:

/**
 * 后序遍历操作，常用于计算所占空间
 * @param  {Function} callback 获取到节点后的回调函数
 */
this.postOrderTranverse = function(callback) {
  postOrderTranverseNode(root, callback);
};
/**
 * 后序遍历的辅助函数，用于遍历节点
 * @param  {Node}   node     遍历开始的节点，默认为root
 * @param  {Function} callback 获取到节点后的回调函数
 */
var postOrderTranverseNode = function(node, callback) {
  postOrderTranverseNode(node.left, callback);
  postOrderTranverseNode(node.right, callback);
  callback(node.key);
};

说明: 返回树中的最小值. 二进制搜索树的性质很容易理解. 最左边的是最小值. 然后只需获取最左边的值即可.

实现:

/**
 * 返回树中最小的值
 * @return {Function} min函数的辅助函数
 */
this.min = function() {
  return minNode(root);
};
/**
 * min函数的辅助函数
 * @param  {Node} node 查找开始的节点，默认为root
 */
var minNode = function(node) {
  // 如果node存在，则开始搜索。能避免树的根节点为Null的情况
  if (node) {
    // 只要树的左侧子节点不为null，则把左子节点赋值给当前节点。
    // 若左子节点为null，则该节点肯定为最小值。
    while (node && node.left !== null) {
      node = node.left;
    }
    return node.key;
  }
  return null;
};

说明: 返回树中的最大值构造二叉排序树，通过min函数易于理解，最大值在最右边.

实现:

/**
 * 返回树中最大的值
 * @return {Function} max函数的辅助函数
 */
this.max = function() {
  return maxNode(root);
};
/**
 * max函数的辅助函数
 * @param  {Node} node 查找开始的节点，默认为root
 * @return {Key}      节点的值
 */
var maxNode = function(node) {
  if (node) {
    while (node && node.right !== null) {
      node = node.right;
    }
    return node.key;
  }
  return null;
};

说明: 搜索特定值并在树中返回true

实现:

/**
 * 搜索某个值是否存在于树中
 * @param  {Node} key 搜索开始的节点，默认为root
 * @return {Function}     search函数的辅助函数
 */
this.search = function(key) {
  return searchNode(root, key);
};
/**
 * search函数的辅助函数
 * @param  {Node} node 搜索开始的节点，默认为root
 * @param  {Key} key  要搜索的键值
 * @return {Boolean}      找到节点则返回true，否则返回false
 */
var searchNode = function(node, key) {
  // 如果根节点不存在，则直接返回null
  if (node === null) {
    return false;
  } else if (key < node.key) {
    searchNode(node.left, key)
  } else if (key > node.key) {
    searchNode(node.right, key)
  } else {
    // 如果该节点值等于传入的值，返回true
    return true;
  }
};

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