[复习]二分搜索树（上）

昨天在做 leetCode 的题时，我发现可以使用搜索树来实现，于是今天就复习一下，现在这个版本是我凭着记忆写出来的，明天我会按照课程再学习一遍并把二分搜素树的改进版本也学习了。昨天的那道题是： LeetCode 数据流中的第 K 大元素（上） ；这篇是没有解决问题的，等下次会使用这个方式再一次尝试。

先定义节点的数据：

    class Node {
      val = undefined;
      leftChild = null;
      rightChild = null;
      constructor(_val, left, right) {
        this.val = _val;
        this.leftChild = left;
        this.rightChild = right;
      }
    }

主要是包含值和两个孩子节点。这里我主要实现添加操作，删除明天补上。下面是实现对应的数据结构了：

    class SearchTree {
      data = null;
      len = 0
      constructor(arr = []) {
        this.initData(arr);
      }

      initData = (data = []) => {
        for (let i = 0; i < data.length; i ++) {
          this.add(data[i])
        }
      }

      _add = (node, e) => {
        // 如果是到最后了，那么就返回一个新节点
        if (!node) {
          return new Node(e, null, null)
        }
        // 如果当前节点比插入的要大，那么插入节点应当插入到左边
        if (node.val > e) {
          node.leftChild = this._add(node.leftChild, e)
        } else {
          node.rightChild = this._add(node.rightChild, e)
        }
        // 最后返回当前节点
        return node;
      }
      add = (ele) => {
        this.data = this._add(this.data, ele)
      }
    }

其实删除的算法也是挺多考虑的，甚至我觉得比添加要麻烦。看递归最好的办法就是看本身的函数实现，也就是明白函数是干什么的，比如我这里添加函数：

if (!node) {
  return new Node(e, null, null)
}

先看这里，当传入的节点为空时则返回新节点；如果不为空，那么将改节点插入到正确的位置，也就是如果插入节点比当前传入节点要大则需要插入到这个节点的右边，否则就是左边；同时返回当前的节点。也就是函数的目的是插入的同时返回本身；因为按刚才说的，应该是这样：

const temNode = new Node(e, null, null)
node[node.val > e ? 'leftChild' : 'rightChild'] = temNode

由于插入的位置不能是存在节点的位置，那么就需要找到最终要插入的位置，所以得继续寻找最终的位置：

if (node.val > e) {
   // 继续添加，这次是从 node.leftChild 的位置上添加
   node.leftChild = this._add(node.leftChild, e)
} else {
   node.rightChild = this._add(node.rightChild, e)
}

这样就能很容易看到递归的代码了，反正现在我是这样看的，不是很复杂都能很快看明白。