1. 树的介绍

树是一种常见的数据结构。在前端领域中，DOM结构就是一颗树。

<html>
  <head>
    <title>DOM结构</title>
  </head>
  <body>
    <div id="app"></div>
  </body>
</html>

树 - 图1
上面画的是一个二叉树，所谓二叉树就是每个节点的下面最多只有两个节点。DOM结构是一个多叉树，因为它可以有多个节点。对于一棵二叉树，通常将其左子节点称为左孩子，右子节点称为右孩子。由于二叉树比较常见且相对于多叉树结构更简单，因此数据结构中常见的结构是二叉树。
二叉树的节点通常使用如下定义：

class TreeNode {
  constructor (val) {
    this.val = val
    this.left = null
    this.right = null
  }
}

2. 二叉搜索树

二叉搜索树(Binary Search Tree，后续简称BST)是一种所有子树的左孩子的值均小于根节点，右孩子的值均大于根节点的二叉树。BST的左子树和右子树都是BST。
树 - 图2

2.1 初始化

class TreeNode {
  constructor (val = null) {
    this.val = val
    this.left = null
    this.right = null
  }
}
class BST {
  constructor () {
    this.root = null
    this.size = 0
  }
  getSize () {
    return this.size
  }
  isEmpty () {
    return this.size === 0
  }
}

2.2 添加

给BST添加子节点的难点在于要保证添加后依然符合BST的定义。由于树是一种典型的递归结构，我们首先可以考虑使用递归的思想。将BST分为根节点、左子树和右子树。显然，此时要添加一个节点到BST中，只需将这个节点的值和根节点进行比较，如果小于根节点，则说明应该将这个节点插入左子树，如果大于根节点，则说明需要插入右子树，等于的情况则不做处理(也可以在节点中维护一个变量count保存其相同的子节点数量)。
因此，首先定义一个add方法和一个私有的_add方法，_add用于递归，add给用户调用。

class BST {
  // 省略其余代码
  add (val) {}
  _add (node, val) {}
}

add方法很容易实现，首先判断是否有根节点，如果没有则直接将添加的节点赋值给根节点。否则调用_add递归添加。

class BST {
  // 省略其余代码
  add (val) {
    if (this.root === null) {
      this.root = new TreeNode(val)
      this.size ++
      return
    }
    this._add(this.root, val)
  }
  _add (node, val) {}
}

好了，重点来了，怎么实现_add？由于递归实际每次都是在判断子树，因此我们可以将问题缩小到最简单的树的结构：
树 - 图3

class BST {
  // 省略其余代码
  add (val) {
    if (this.root === null) {
      this.root = new TreeNode(val)
      this.size ++
      return
    }
    this._add(this.root, val)
  }
  _add (node, val) {
    if (node.val === val) return
    if (node.left === null && node.val > val) {
      node.left = new TreeNode(val)
      return
    } else if (node.right === null && node.val < val) {
      node.right = new TreeNode(val)
      return
    } else if (node.val > val) {
      this._add(node.left, val)
    } else {
      this._add(node.right, val)
    }
  }
}

上述方式虽然可以实现添加节点的功能，但是_add函数写的太啰嗦了。我们可以换一种思路：首先依旧将BST分成根节点和左右子树，通过新增节点和根节点的值做判断我们可以知道是应当将添加的节点放入左子树还是右子树(如果和根节点相同则直接返回根节点):

class BST {
  // 省略其余代码
  add (val) {
    this.root = _add(this.root, val)
  }
  _add (node, val) {
    if (node === null) {
      this.size ++
      return new TreeNode(val)
    }
    if (node.val > val) node.left = this._add(node.left, val)
    else if (node.val < val) node.right = this._add(node.right, val)
    return node
  }
}