背景

去年下半年，我在微信书架里加入了许多技术书籍，各种类别的都有，断断续续的读了一部分。

没有计划的阅读，收效甚微。

新年伊始，我准备尝试一下其他方式，比如阅读周。每月抽出1~2个非连续周，完整阅读一本书籍。

这个“玩法”虽然常见且板正，但是有效，已经坚持阅读四个月。

已读完书籍：《架构简洁之道》、《深入浅出的Node.js》、《你不知道的JavaScript（上卷）》、《你不知道的JavaScript（中卷）》、《你不知道的JavaScript（下卷）》。

当前阅读周书籍：《数据结构与算法JavaScript描述》。

二叉树和二叉查找树

树的定义

树由一组以边连接的节点组成。公司的组织结构图就是一个树的例子。

二叉树是一种特殊的树，它的子节点个数不超过两个。二叉树具有一些特殊的计算性质，使得在它们之上的一些操作异常高效。

沿着一组特定的边，可以从一个节点走到另外一个与它不直接相连的节点。从一个节点到另一个节点的这一组边称为路径，在图中用虚线表示。以某种特定顺序访问树中所有的节点称为树的遍历。

树可以分为几个层次，根节点是第0层，它的子节点是第1层，子节点的子节点是第2层，以此类推。树中任何一层的节点可以都看做是子树的根，该子树包含根节点的子节点，子节点的子节点等。我们定义树的层数就是树的深度。

二叉树和二叉查找树

二叉树每个节点的子节点不允许超过两个。通过将子节点的个数限定为2，可以写出高效的程序在树中插入、查找和删除数据。

在使用JavaScript构建二叉树之前，需要给我们关于树的词典里再加两个新名词。一个父节点的两个子节点分别称为左节点和右节点。在一些二叉树的实现中，左节点包含一组特定的值，右节点包含另一组特定的值。

当考虑某种特殊的二叉树，比如二叉查找树时，确定子节点非常重要。二叉查找树是一种特殊的二叉树，相对较小的值保存在左节点中，较大的值保存在右节点中。这一特性使得查找的效率很高，对于数值型和非数值型的数据，比如单词和字符串，都是如此。

实现二叉查找树

二叉查找树由节点组成，所以我们要定义的第一个对象就是Node，该对象和前面介绍链表时的对象类似。Node类的定义如下：

function Node(data, left, right) {
  this.data = data;
  this.left = left;
  this.right = right;
  this.show = show;
}

function show() {
  return this.data;
}

Node对象既保存数据，也保存和其他节点的链接（left和right）, show()方法用来显示保存在节点中的数据。

现在可以创建一个类，用来表示二叉查找树（BST）。我们让类只包含一个数据成员：一个表示二叉查找树根节点的Node对象。该类的构造函数将根节点初始化为null，以此创建一个空节点。

BST先要有一个insert()方法，用来向树中加入新节点。这个方法有点复杂，需要着重讲解。首先要创建一个Node对象，将数据传入该对象保存。

其次检查BST是否有根节点，如果没有，那么这是棵新树，该节点就是根节点，这个方法到此也就完成了；否则，进入下一步。

如果待插入节点不是根节点，那么就需要准备遍历BST，找到插入的适当位置。该过程类似于遍历链表。用一个变量存储当前节点，一层层地遍历BST。

进入BST以后，下一步就要决定将节点放在哪个地方。找到正确的插入点时，会跳出循环。查找正确插入点的算法如下。

1. 设根节点为当前节点。
2. 如果待插入节点保存的数据小于当前节点，则设新的当前节点为原节点的左节点；反之，执行第4步。
3. 如果当前节点的左节点为null，就将新的节点插入这个位置，退出循环；反之，继续执行下一次循环。
4. 设新的当前节点为原节点的右节点。
5. 如果当前节点的右节点为null，就将新的节点插入这个位置，退出循环；反之，继续执行下一次循环。

BST类和Node类的定义：

function Node(data, left, right) {
  this.data = data;
  this.left = left;
  this.right = right;
  this.show = show;
}

function show() {
  return this.data;
}

function BST() {
  this.root = null;
  this.insert = insert;
  this.inOrder = inOrder;
}

function insert(data) {
  var n = new Node(data, null, null);
  if (this.root == null) {
    this.root = n;
  } else {
    var current = this.root;
    var parent;
    while (true) {
      parent = current;
      if (data < current.data) {
        current = current.left;
        if (current == null) {
          parent.left = n;
          break;
        }
      } else {
        current = current.right;
        if (current == null) {
          parent.right = n;
          break;
        }
      }
    }
  }
}

遍历二叉查找树

现在BST类已经初步成型，但是操作上还只能插入节点，我们需要有能力遍历BST，这样就可以按照不同的顺序，比如按照数字大小或字母先后，显示节点上的数据。

有三种遍历BST的方式：中序、先序和后序。中序遍历按照节点上的键值，以升序访问BST上的所有节点。先序遍历先访问根节点，然后以同样方式访问左子树和右子树。后序遍历先访问叶子节点，从左子树到右子树，再到根节点。

需要中序遍历的原因显而易见，但为什么需要先序遍历和后序遍历就不是那么明显了。我们先来实现这三种遍历方式，在后续章节中再解释它们的用途。

中序遍历使用递归的方式最容易实现。该方法需要以升序访问树中所有节点，先访问左子树，再访问根节点，最后访问右子树。如果你还不熟悉递归，请参考第1章有关如何写递归函数那一节。

中序遍历的代码如下：

function inOrder(node) {
  if (!(node == null)) {
    inOrder(node.left);
    putstr(node.show() + ' ');
    inOrder(node.right);
  }
}

BST的中序遍历：

var nums = new BST();
nums.insert(23);
nums.insert(45);
nums.insert(16);
nums.insert(37);
nums.insert(3);
nums.insert(99);
nums.insert(22);
console.log('Inorder traversal: ');
inOrder(nums.root);

输出为：

Inorder traversal:
3 16 22 23 37 45 99

在二叉查找树上进行查找

对BST通常有下列三种类型的查找：

1. 查找给定值；
2. 查找最小值；
3. 查找最大值。

查找最小值和最大值

查找BST上的最小值和最大值非常简单。因为较小的值总是在左子节点上，在BST上查找最小值，只需要遍历左子树，直到找到最后一个节点。

getMin()方法查找BST上的最小值，该方法的定义如下：

function getMin() {
  var current = this.root;
  while (!(current.left == null)) {
    current = current.left;
  }
  return current.data;
}

该方法沿着BST的左子树挨个遍历，直到遍历到BST最左边的节点，该节点被定义为：

current.left = null;

这时，当前节点上保存的值就是最小值。

在BST上查找最大值，只需要遍历右子树，直到找到最后一个节点，该节点上保存的值即为最大值。

getMax()方法的定义如下：

function getMax() {
  var current = this.root;
  while (!(current.right == null)) {
    current = current.right;
  }
  return current.data;
}

使用前面用过的BST数据测试了getMin()和getMax()方法：

var nums = new BST();
nums.insert(23);
nums.insert(45);
nums.insert(16);
nums.insert(37);
nums.insert(3);
nums.insert(99);
nums.insert(22);
var min = nums.getMin();
console.log('The minimum value of the BST is: ' + min);
console.log('\n');
var max = nums.getMax();
console.log('The maximum value of the BST is: ' + max);

程序输出如下：

The minimum value of the BST is: 3
The maximum value of the BST is: 99

总结

树是计算机科学中经常用到的一种数据结构。树是一种非线性的数据结构，以分层的方式存储数据。树被用来存储具有层级关系的数据，比如文件系统中的文件；树还被用来存储有序列表。

二叉树是一种特殊的树。选择树而不是那些基本的数据结构，是因为在二叉树上进行查找非常快（而在链表上查找则不是这样），为二叉树添加或删除元素也非常快（而对数组执行添加或删除操作则不是这样）。

作者介绍
非职业「传道授业解惑」的开发者叶一一。
《趣学前端》、《CSS畅想》等系列作者。华夏美食、国漫、古风重度爱好者，刑侦、无限流小说初级玩家。
如果看完文章有所收获，欢迎点赞👍 | 收藏⭐️ | 留言📝。