遍历树

2025年03月28日

柏拉文

越努力，越幸运

一、深度优先递归

---

function traverseTreeRecursive(tree, callback) {
  function traverse(node) {
    callback(node);

    if (node.children && node.children.length > 0) {
      node.children.forEach((child) => traverse(child));
    }
  }

  tree.forEach((node) => traverse(node));
}

二、广度优先递归

---

三、深度优先循环

---

function traverseTreeIterativeByDeep(tree, callback) {
  const stack = [...tree];

  while (stack.length > 0) {
    const node = stack.pop();
    callback(node);

    if (node.children && node.children.length > 0) {
      for (let i = node.children.length - 1; i >= 0; i--) {
        stack.push(node.children[i]);
      }
    }
  }
}

四、广度优先遍历

---

function traverseTreeIterativeByBreadth(tree, callback) {
  const queue = [...tree];

  while (queue.length > 0) {
    const node = queue.shift();
    callback(node);

    if (node.children && node.children.length > 0) {
      queue.push(...node.children);
    }
  }
}