简介

树是什么

• 一种分层数据的抽象模型

• 前端工作常见的树包括：DOM 树、级联选择、树形控件...

• JS 中没有树，但是可以用 Object 和 Array 构建树

• 树的常用操作：深度/广度优先遍历、先中后续遍历

深度优先遍历与广度优先遍历

什么是深度/广度优先遍历

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

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

深度优先遍历

深度优先遍历算法口诀

1. 访问根节点

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

Codeing Part

const tree = {
  val: "a",
  children: [
    {
      val: "b",
      children: [
        {
          val: "d",
          children: [],
        },
        {
          val: "e",
          children: [],
        },
      ],
    },
    {
      val: "c",
      children: [
        {
          val: "f",
          children: [],
        },
        {
          val: "g",
          children: [],
        },
      ],
    },
  ],
};

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

dfs(tree);

广度优先遍历

广度优先遍历算法口诀

• 新建一个队列，把根节点入队

• 把队头出队并访问

• 把队头的 children 挨个入队

• 重读第二、三步，知道队列为空

Codeing Part

const tree = {
  val: "a",
  children: [
    {
      val: "b",
      children: [
        {
          val: "d",
          children: [],
        },
        {
          val: "e",
          children: [],
        },
      ],
    },
    {
      val: "c",
      children: [
        {
          val: "f",
          children: [],
        },
        {
          val: "g",
          children: [],
        },
      ],
    },
  ],
};

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);
    });
  }
};

bfs(tree);