使用 ECMAScript 2021 实现 JavaScript 中的树数据结构

前言

树是计算机科学中非常重要的数据结构，它在许多领域都有广泛应用。在前端开发中，我们经常需要使用树来处理各种数据结构，例如菜单、目录、组织结构等。在本文中，我们将使用 ECMAScript 2021 的新特性来实现 JavaScript 中的树数据结构。

什么是树？

树是一种非常常用的非线性数据结构，它由若干个节点组成，这些节点之间通过边连接。每个节点都可以有零个或多个子节点，但每个节点最多只有一个父节点。树有一个根节点，它是整棵树的唯一起点。叶子节点是没有子节点的节点。

实现树数据结构

在 ECMAScript 2021 中，我们可以使用 class 来实现树数据结构。首先，我们定义一个 TreeNode 类来表示每个树节点。

class TreeNode {
  constructor(data) {
    this.data = data;
    this.children = [];
  }

  addNode(node) {
    this.children.push(node);
  }
}

TreeNode 类有一个 data 属性来存储节点的数据，以及一个 children 数组来存储子节点。它还定义了一个 addNode 方法来添加子节点。这里我们使用了数组的 push 方法来将新节点添加到子节点列表末尾。

接下来，我们定义一个 Tree 类来表示整棵树。它只需要一个根节点即可。我们可以把整棵树看作从根节点开始的一颗子树。

class Tree {
  constructor() {
    this.root = null;
  }
}

在 Tree 类中，我们还需要定义一些方法来操作树。首先，我们定义一个 add 方法来添加新节点。新增节点的逻辑就是遍历整棵树，寻找合适的位置来插入新节点。

add(data) {
  const node = new TreeNode(data);
  if (!this.root) {
    this.root = node;
  } else {
    let current = this.root;
    while (true) {
      if (data < current.data) {
        if (!current.children.length || data < current.children[0].data) {
          node.parent = current;
          current.children.unshift(node);
          break;
        }
        current = current.children[0];
      } else {
        if (!current.children.length || data > current.children[current.children.length - 1].data) {
          node.parent = current;
          current.children.push(node);
          break;
        }
        current = current.children[current.children.length - 1];
      }
    }
  }
}

这里我们首先判断根节点是否为空，如果是，则直接将新节点作为根节点。否则，从根节点开始遍历整个树，查找合适的插入位置。

在插入节点时，我们需要考虑两种情况。如果节点值小于当前节点的值，则将其插入到当前节点的子节点列表的开头；如果节点值大于当前节点的值，则将其插入到当前节点的子节点列表的末尾。同时，我们还需要处理重复插入的情况。

接下来，我们实现一个 remove 方法来删除节点。删除节点的逻辑是先查找要删除的节点，然后将其与父节点和子节点进行连接。

remove(data) {
  const node = this.getNodeByData(data);

  if (!node) {
    return;
  }

  const parent = node.parent;
  if (!parent) {
    this.root = null;
    return;
  }

  const index = parent.children.indexOf(node);
  if (index > -1) {
    parent.children.splice(index, 1, ...node.children);
  }
}

在删除节点时，我们先查找要删除的节点，如果找到，则将其与父节点和子节点进行连接。如果要删除的节点是根节点，我们需要特殊处理一下。

最后，我们还需要实现一个 getNodeByData 方法用于查找指定值的节点。

getNodeByData(data) {
  let current = this.root;

  while (current) {
    if (current.data === data) {
      return current;
    } else if (data < current.data) {
      current = current.children[0];
    } else {
      current = current.children[current.children.length - 1];
    }
  }

  return null;
}

在查找节点时，我们也需要遍历整个树，查找到指定节点即停止。

使用示例

我们来实现一个简单的示例，创建一棵树并添加四个节点，然后删除一个节点。

const tree = new Tree();
tree.add(4);
tree.add(1);
tree.add(5);
tree.add(3);
tree.remove(5);

console.log(tree);

以上代码执行完毕后，输出结果如下：

Tree {
  root: TreeNode {
    data: 4,
    children: [
      [TreeNode] {
        data: 1,
        children: []
      },
      [TreeNode] {
        data: 3,
        children: []
      }
    ]
  }
}

总结

在本文中，我们使用 ECMAScript 2021 的新特性来实现了 JavaScript 中的树数据结构。我们定义了一个 TreeNode 类来表示每个树节点，以及一个 Tree 类来表示整棵树。我们还实现了一些方法来操作树，例如添加节点、删除节点和查找节点等。最后，我们还提供了一个简单的使用示例来演示如何使用这个树数据结构。

如果你对树学习的更多知识，可以参照算法书籍中的相关知识。

来源：JavaScript中文网 ，转载请注明来源 本文地址：https://www.javascriptcn.com/post/65a7dcb0add4f0e0ff0ff668