算法篇 - 二叉树

在前端的工作当中，二叉树不怎么常见，虽然没有快排、冒泡、去重、二分、希尔等算法常见，但是它的作用，在某些特定的场景下，是非常重要的。

目前es6的使用场景比较多，所以我准备能用es6的地方就用es6去实现。
复制代码

正文

上图是我从网上找的，最主要是让大家看一下，树长啥样。

在这里简单的介绍一下有关二叉树的术语，在后续讨论中将会提到。一棵树最上面的节点称为 根节点，如果一个节点下面连接两个节点，那么该节点称为父节点，它下面的节点称为子 节点。一个节点最多只有 0 - 2 个子节点。没有任何子节点的节点称为叶子节点。

什么是二叉树

二叉树就是一种非线性的数据结构，一般是用来存储具有层级关系的数据，比如，我们要做一个可视化的文件系统，类似于云盘网页版，它有区分不同的文件夹，每个文件夹下面都有不同的内容，它们每个文件夹，是没有任何的关系的，唯一的关系，就是同一层级的文件夹，都有一个父级文件夹。

和非线性数据结构相反的，是线性数据结构，线性数据结构其实在平时就比较常见了，前端常用的线性数据结构有：栈、队列、数组。

为什么要用二叉树

选择二叉树而不是那些基本的数据结构，是因为在二叉树上进行查找非常快，为二叉树添加或删除元素 也非常快。

二叉树特点

• 二叉树的每个节点的子节点不允许超过两个；
• 每个节点的左节点永远都比自己小，右节点反之；

二叉树的实现

二叉树的实现功能包括 添加节点 、 删除节点 、 查询节点（最大值、最小值，某一个指定值） ；

二叉树的遍历方式包括 中序遍历 、 先序遍历 、 后序遍历 ；

创建二叉树节点和节点的操作类

创建一个节点

在创建一个节点时，我们要记住二叉树节点的特性，子节点不允许超过两个：

class Node {
    constructor({data = null, left = null, right = null}){
        this._data = data
        this._left = left
        this._right = right
    }
    show(){
        return this._data
    }
}
复制代码

这样，创建了一个节点，默认为 null，有 left 和 right 两个节点,添加一个 show 方法，显示当前节点的数据；

创建一个操作节点的类

现在，我们有了一个节点，知道了这个节点有哪些属性，接下来，我们创建一个可以操作这些节点的类：

class BinarySearchTree {
    constructor(){
        this._root = null
    }
}
复制代码

这里我们创建了一个根节点，这个根节点就是二叉树最底层的那个根，接下来，我们先添加一个添加节点的方法。

添加节点

class BinarySearchTree {
  constructor() {
    this._root = null
  }
  insert(data) {
    let node = new Node({
      data: data
    })
    if (this._root == null) {
      this._root = node
    }
    else { 
      let current, parent
      current = this._root
      while (true) { 
        parent = current
        if (data < current.data) {
          current = current.left
          if (current == null) {
            parent.left = node
            break
          }
        }
        else { 
          current = current.right
          if (current == null) { 
            parent.right = node
            break
          }
        }
      }
    }
  }
}
复制代码

这里，我们添加了一个 insert 方法，这个方法就是用来添加节点的；

初始化先检查根节点 root 是否是 null，如果是 null，那说明不存在根节点，以当前添加的节点为根节点；

如果存在根节点的话，那么接下来值的对比目标，初始化以根节点做对比目标，确认大于根节点，还是小于根节点；

如果小于的话，那么就下次用根节点的左节点 left 来做对比，当然，如果左节点是空的，直接把当前要添加的节点当作左节点 left 就ok了。

如果大于的话，和小于反之；

然后我们现在，开始添加值，测试一些方法：

let bst = new BinarySearchTree()
bst.insert(2)
bst.insert(1)
bst.insert(3)
复制代码

我们添加了一个根节点，是2，然后添加了两个叶子的节点 1 和 3 ，1 就在根节点 2 的左侧， 3 就在根节点 2 的右侧，接下来我们加一个删除节点的方法。

删除节点

class BinarySearchTree {
  constructor() {
    this._root = null
  }
  remove(data) {
    this._root = this._removeNode(this._root, data)
  }
  _removeNode(node, data) {
    if (node == null) {
      return null
    }
    if (data == node._data) {
      if (node._left == null && node._right == null) {
        return null
      }
      if (node._left == null) {
        return node._right
      }
      if (node._right == null) {
        return node._left
      }
      var tempNode = this._getSmallest(node._right)
      node._data = tempNode._data
      node._right = this._removeNode(node._right, tempNode._data)
      return node
    } else if (data < node._data) {
      node._left = this._removeNode(node._left, data)
      return node
    } else {
      node._right = this._removeNode(node._right, data)
      return node
    }
  }
  _getSmallest(node) {
    if (node._left == null) {
      return node
    } else {
      return this._getSmallest(node._left)
    }
  }
}
复制代码

这个是用来删除某一个节点的方法。

这个方法最后返回的是一个新的 node 节点，如果第一次调用的时候 node 是 null 的话，说明这个二叉树是空的，不存在任何值，直接返回空；

如果当前要删除的值，是当前节点的值，那么去检查它的左右节点是否存在值，如果都不存在，直接返回 null，因为说明当前的节点下面没有子级节点，就不需要对子级节点做处理了，直接删除当前节点就好；

如果左节点是 null 的，那么直接用当前节点的右节点替换当前节点；

反之，右节点是 null 的，那么直接用当前节点的左节点替换当前节点；

如果，当前要删除的节点，左右节点都存在的话，那么就去遍历要删除节点的右侧节点，如果右侧节点不存在它的左节点，那么直接返回右侧节点，如果存在，一直递归，找到最底层的一个左侧节点返回结果；

这里其实简要概括一下，就是去找删除节点右节点树当中的最小值，来代替当前被删除节点的位置
复制代码

如果当前要删除的值，比当前节点的值小，就递归调用，一直找到当前值并删除为止；

如果当前要删除的值，比当前节点的值大，与上面反之；

接下来，我们添加一个查找的方法：

查找当前节点

class BinarySearchTree {
  constructor() {
    this._root = null
  }
  find(data) {
    let current = this._root
    while (current != null) {
      if (current._data == data) {
        return true
      } else if (data < current._data) {
        current = current._left
      } else {
        current = current._right
      }
    }
    return false
  }
}
复制代码

这个方法是用来查找一个值的，如果当前查询的值小于当前节点的值，那就从当前的节点左侧去查询；

反之，如果大于，就直接去右侧查询；

如果这个值始终查询不到，那么就返回 false，否则就是 true。

查找最小值

class BinarySearchTree {
  constructor() {
    this._root = null
  }
  getMin() {
    let current = this._root
    while (current._left != null) {
      current = current._left
    }
    return current._data
  }
}
复制代码

这是一个查询最小值的方法，由于二叉树数据结构的特殊性，左侧的值永远是最小的，所以一直查询到低，找到最底层的左节点返回就可以了。

查询最大值

class BinarySearchTree {
  constructor() {
    this._root = null
  }
  getMax() {
    let current = this._root
    while (current._right != null) {
      current = current._right
    }
    return current._data
  }
}
复制代码

和查询最小值相反。

操作二叉树节点的方式都有了，接下来该遍历二叉树了。

遍历二叉树

把二叉树的数据遍历一遍，用 中序 、 先序 、 后序遍历 ，代码量比较少，代码也不是伪代码都是我自己测过的，结果就不截图了，把执行顺序的流程图发一下，结果大家感兴趣自己跑一下就好了：

中序遍历

class BinarySearchTree {
  constructor() {
    this._root = null
  }
  inOrder(node) {
    if (node != null) {
      this.inOrder(node._left)
      console.log(node.show())
      this.inOrder(node._right)
    }
  }
}
复制代码

先遍历左节点，在遍历根节点，最后遍历右节点，步骤如下：

先序遍历

class BinarySearchTree {
  constructor() {
    this._root = null
  }
  preOrder(node) {
    if (node != null) {
      console.log(node.show())
      this.inOrder(node._left)
      this.inOrder(node._right)
    }
  }
}
复制代码

这是先序遍历，先遍历根节点，在遍历左节点，最后遍历右节点，步骤如下：

后序遍历

class BinarySearchTree {
  constructor() {
    this._root = null
  }
  postOrder(node) {
    if (node != null) {
      this.inOrder(node._left)
      this.inOrder(node._right)
      console.log(node.show())
    }
  }
}
复制代码

这是后序遍历，先遍历叶子节点，从左到右，最后遍历根节点，步骤如下：

结束语

到这里，二叉树讲解的就差不多了，大家对于哪里有疑问，随时欢迎评论。

本来这一章是应该写 vue 源码解析（实例化前）的最终章的，但是涉及到的东西比较多，而且我想把前几章的总结一下写到最后一章。

所以这一章就先写一章有关算法的文章，谢谢大家支持:pray: