详解JavaScript树结构

什么是树结构

树结构是一种非常常见的数据结构，它由多个节点（Node）和连接它们的边（Edge）所组成的集合体。其中树的顶部节点被称为根节点（Root），没有子节点的节点称为叶节点（Leaf），除了根节点外，每个节点都有一个父节点（Parent）。

树结构可以被用来表示许多信息，例如文件系统、公司组织架构、网页导航等。

用对象表示树结构

在JavaScript中，我们可以用对象来表示一个树结构。使用对象来表示树结构的好处是，我们不需要显式地定义节点和边，而可以使用JavaScript对象的属性和值来表示它们。

const tree = {
  value: 1,
  children: [
    {
      value: 2,
      children: [
        {
          value: 5,
          children: []
        },
        {
          value: 6,
          children: []
        }
      ]
    },
    {
      value: 3,
      children: [
        {
          value: 7,
          children: []
        }
      ]
    },
    {
      value: 4,
      children: []
    }
  ]
};

上面的示例表示一个根节点为1，有三个子节点2、3、4，2下面有两个子节点5和6，3下面有一个子节点7。

深度优先遍历

深度优先遍历（Depth-First-Search，DFS）是树结构中一种非常重要的遍历方式。它的遍历顺序是：先遍历根节点，再遍历它的第一个子节点的所有子树，然后是第二个子节点的所有子树，以此类推。

下面是一个深度优先遍历的例子：

function dfs(tree) {
  console.log(tree.value);

  for (let i = 0; i < tree.children.length; i++) {
    dfs(tree.children[i]);
  }
}

dfs(tree);
// 输出：1, 2, 5, 6, 3, 7, 4

广度优先遍历

广度优先遍历（Breadth-First-Search，BFS）也是树结构中的另一种非常重要的遍历方式。它的遍历顺序是：先遍历根节点，然后遍历它的所有子节点，接着遍历所有子节点的所有子节点，以此类推。也就是说，它是以层次的顺序进行遍历的。

下面是一个广度优先遍历的例子：

function bfs(tree) {
  const queue = [tree];

  while (queue.length > 0) {
    const node = queue.shift();
    console.log(node.value);

    for (let i = 0; i < node.children.length; i++) {
      const child = node.children[i];
      queue.push(child);
    }
  }
}

bfs(tree);
// 输出：1, 2, 3, 4, 5, 6, 7

总结

树结构是一种非常常见的数据结构，它由多个节点和边所组成的集合体。我们可以用JavaScript对象来表示树结构，并利用深度优先遍历和广度优先遍历来遍历它们。