树

• 一种分层数据的抽象模型
• 前端工作中常见的树包括：DOM 树、级联选择、树形控件...
• Js 中没有树，但可以用 Object 和 Array 构建树
• 树的常用操作：深度/广度优先遍历、先中后序遍历【二叉树】

var tree = {
  value: "a",
  children: [
    {
      value: "b",
      children: [
        {
          value: "e",
          children: [(value: "g")],
        },
      ],
    },
    {
      value: "c",
      children: [
        {
          value: "f",
        },
      ],
    },
  ],
};

深度优先遍历：尽可能深的搜索树的分支

• 1. 访问根节点
• 2. 对根节点的 children 挨个进行深度优先遍历

const dfs = (root) => {
  console.log(root.value);
  if (root.children) root.children.forEach(dfs);
};

广度优先遍历：先访问离根节点最近的节点

• 1. 新建一个队列，把根节点入队
• 2. 把对头出队并访问
• 3. 把对头的 children 挨个入队
• 4. 重复第二、三步，直到队列为空

const bfs = (root) => {
  const q = [root]; // 新建队列
  while (q.length > 0) {
    const n = q.shift(); // 出队
    console.log(n.val);
    n.children.forEach((child) => {
      q.push(child); // 入队
    });
  }
};