JavaScript 中的树

前一篇博客介绍了 链表数据结构及其操作 的实现，链表相对来说还是很简单的一个数据结构。它为后面的 树、堆 提供了基本思想。

啥是树？

树是一种有趣的数据结构。它在各个领域都有广泛的应用：

• DOM 是一种树形数据结构
• 操作系统中的目录和文件可以表示为树
• 家庭成员的结构

树还有很多变体，例如 堆、BST ... 可用来解决与调度，图像处理，数据库等相关的问题。 许多复杂的问题可能看起来与树无关，但实际上可以表示为一个树。 例如 echarts 的桑基图，在配置数据源的时候结构是 {source: 'xxx', target: 'yyy', value: 1} 的数组，我们在这里称为 标准结构。 看起来和树没啥关联，但我们可以把 标准结构 的数组，转成树的形式（我们在这里称为 格式化结构），来扩展 echarts 没有提供的一些能力。 比如在 setOption 之前，我们可以通过 格式化结构 提前知道当前桑基图有几层数据，可以给不同层级的数据设置不同的样式以及交互。

树的结构如图所示：

二叉树

二叉树是 树结构 中相对比较简单的，它只有两个子节点分别用 left 和 right 指针表示，然后用 value 表示节点的值。我们这里还是用 Node 来表示单个节点：

class Node {
  constructor(value) {
    this.value = value ?? null;
    if (!!value) {
      this.left = null;
      this.right = null;
    }
  }
}