❓介绍下深度优先遍历和广度优先遍历，如何实现？

这道题目对于没怎么接触算法的童鞋来说肯定是十脸懵逼的。当然我对于我来说---也是一样的😂。

所以说去查阅了一些资料，以及看了大多数童鞋的解答。

自己理解：

	定义
深度优先遍历	如下面对象，从 root 开始向下遍历，依次从所有未访问子元素深度优先遍历直到最终子元素，如果还有相邻元素未遍历就以此类推。
广度优先遍历	如下面对象，从 root 开始向下遍历，优先遍历兄弟节点，再依次遍子字节点，以此类推。

---

// 假设我们有一对象
const TreeRoot = {
  value: "root",
  children: [
    {
      value: "A",
      children: [
        { value: "A-a", children: [{ value: "A-a-1" }, { value: "A-a-2" }] },
        { value: "A-b", children: [{ value: "A-b-1" }, { value: "A-b-2" }] }
      ]
    },
    {
      value: "B",
      children: [
        { value: "B-a", children: [{ value: "B-a-1" }, { value: "B-a-2" }] },
        { value: "B-b", children: [{ value: "B-b-1" }, { value: "B-b-2" }] }
      ]
    },
    {
      value: "C",
      children: [
        { value: "C-a", children: [{ value: "C-a-1" }, { value: "C-a-2" }] },
        { value: "C-b", children: [{ value: "C-b-1" }, { value: "C-b-2" }] }
      ]
    }
  ]
};

[图]

深度优先遍历

// 递归实现
function myDfs1(root) {
  const result = []; // 存放最终结果
  // 递归方法
  const dfs = target => {
    result.push(target.value); // 添加单个节点自己
    const children = target.children;
    // 检测子节点，存在就递归遍历
    if (children && children.length) {
      children.forEach(element => {
        // 我们可以看每次递归的值
        // 其实就是结果值的节点
        // console.log(element);
        // console.log("----------------------");
        dfs(element);
      });
    }
  };

  dfs(root);
  return result;
}

const myDfs1Result = myDfs1(TreeRoot);
console.log(myDfs1Result);

// 非递归实现
function myDfs2(root) {
  const result = []; // 存放最终返回
  const stack = []; // 存放遍历对象

  if (root) {
    stack.push(root); // 推入处理对象
    while (stack.length) {
      const element = stack.pop();
      result.push(element.value);
      const children = element.children;
      if (children && children.length) {
        for (let index = children.length - 1; index >= 0; index--) {
          // 我们可以看一下堆栈每次被推入的值
          // 其实就是结果值的节点
          // console.log(children[index]);
          // console.log("----------------------");
          stack.push(children[index]);
        }
      }
    }
  }

  return result;
}

const myDfs2Result = myDfs2(TreeRoot);
console.log(myDfs2Result);

// 最终的结果都是一样的
// [ 'root',
//   'A',
//   'A-a',
//   'A-a-1',
//   'A-a-2',
//   'A-b',
//   'A-b-1',
//   'A-b-2',
//   'B',
//   'B-a',
//   'B-a-1',
//   'B-a-2',
//   'B-b',
//   'B-b-1',
//   'B-b-2',
//   'C',
//   'C-a',
//   'C-a-1',
//   'C-a-2',
//   'C-b',
//   'C-b-1',
//   'C-b-2' ]

[图解]

广度优先遍历

function myBfs(root) {
  const result = []; // 存放最终值
  const queue = [];
  if (root) {
    queue.push(root); // 推入队列
    while (queue.length) {
      const elementRoot = queue.shift();
      const children = elementRoot.children;
      result.push(elementRoot.value);
      // 检测字节点，存在添加队列 先进先出
      if (children && children.length) {
        children.forEach(element => {
          // 我们可以看一下队列每次被推入的值
          // 其实就是结果值的节点
          // console.log(element);
          // console.log("----------------------");
          queue.push(element);
        });
      }
    }
  }

  return result;
}

const myBfsResult = myBfs(TreeRoot);
console.log(myBfsResult);
// [ 'root',
//   'A',
//   'B',
//   'C',
//   'A-a',
//   'A-b',
//   'B-a',
//   'B-b',
//   'C-a',
//   'C-b',
//   'A-a-1',
//   'A-a-2',
//   'A-b-1',
//   'A-b-2',
//   'B-a-1',
//   'B-a-2',
//   'B-b-1',
//   'B-b-2',
//   'C-a-1',
//   'C-a-2',
//   'C-b-1',
//   'C-b-2' ]

[图解]