树的遍历

对整个树形结构进行遍历

const tree = {
  name: 'root',
  children: [
    {
      name: 'a',
      children: [
        { name: 'b', children: [{ name: 'e' }] },
        { name: 'c', children: [{ name: 'f' }] },
        { name: 'd', children: [{ name: 'g' }] },
      ],
    },
    {
      name: 'a2',
      children: [
        { name: 'b2', children: [{ name: 'e2' }] },
        { name: 'c2', children: [{ name: 'f2' }] },
        { name: 'd2', children: [{ name: 'g2' }] },
      ],
    },
  ],
};

深度优先

• 递归实现

const deepTraversal = function (node, result = []) {
  result.push(node.name);
  if (node.children) {
    node.children.forEach((childNode) => {
      deepTraversal(childNode, result);
    });
  }
  return result;
};
console.log(deepTraversal(tree));

• 堆栈实现

const deepTraversalByStacks = function (node) {
  let stacks = [node];
  const result = [];
  while (stacks.length > 0) {
    const current = stacks.shift();
    result.push(current.name);
    if (current.children) {
      stacks = [...current.children, ...stacks];
    }
  }
  return result;
};
console.log(deepTraversalByStacks(tree));

广度优先

• 堆栈实现

const widthTraversal = function (node) {
  const result = [];
  let stacks = [node];
  while (stacks.length) {
    const current = stacks.shift();
    result.push(current.name);
    if (current.children) {
      stacks = [...stacks, ...current.children];
    }
  }
  return result;
};
console.log(widthTraversal(tree));