树遍历

树遍历

对于树结构的遍历一般有深度优先和广度优先

广度优先和深度优先的概念很简单，区别如下：

• 深度优先,访问完一颗子树再去访问后面的子树，而访问子树的时候，先访问根再访问根的子树，称为先序遍历；先访问子树再访问根，称为后序遍历。
• 广度优先，即访问树结构的第 n+1 层前必须先访问完第 n 层

深度优先

先序遍历

const treeForEach = (tree, func) => {
  tree.forEach(data => {
    func(data);
    data.children && treeForEach(data.children, func);
  });
};

后序遍历，只需要调换一下节点遍历和子树遍历的顺序即可

const treeForEach = (tree, func) => {
  tree.forEach(data => {
    data.children && treeForEach(data.children, func);
    func(data);
  });
};

广度优先

广度优先的思路是，维护一个队列，队列的初始值为树结构根节点组成的列表，重复执行以下步骤直到队列为空。取出队列中的第一个元素，进行访问相关操作，然后将其后代元素（如果有）全部追加到队列最后。

const treeForEach = (tree, func) => {
  let node,
    list = [...tree];
  while ((node = list.shift())) {
    func(node);
    node.children && list.push(...node.children);
  }
};