如何在树形结构中优雅关联节点的前驱与后继？

问题背景 #

给定如下树形结构：

{
  label: 'a',
  children: [
    {
      label: 'a.a',
      children: [
        {
          label: 'a.a.a',
          children: [
            { label: 'a.a.a.a' },
            { label: 'a.a.a.b' },
            { label: 'a.a.a.c' },
            { label: 'a.a.a.d' }
          ]
        },
        {
          label: 'a.a.b',
          children: [
            { label: 'a.a.b.a' },
            { label: 'a.a.b.b' }
          ]
        },
        {
          label: 'a.a.c',
          children: [ { label: 'a.a.c.a' } ]
        },
        {
          label: 'a.a.d',
          children: [
            { label: 'a.a.d.a' },
            { label: 'a.a.d.b' }
          ]
        }
      ]
    },
    {
      label: 'a.b',
      children: [
        {
          label: 'a.b.a',
          children: [
            { label: 'a.b.a.a' },
            { label: 'a.b.a.b' },
            { label: 'a.b.a.c' },
            { label: 'a.b.a.d' }
          ]
        },
        {
          label: 'a.b.b',
          children: [
            { label: 'a.b.b.a' },
            { label: 'a.b.b.b' }
          ]
        }
      ]
    }
  ]
}

需要实现按叶子节点深度优先遍历顺序，确定任意叶子节点的前驱（previous）和后继（next）节点，例如：

• a.b.a.a 是 a.a.d.b 的后继
• a.b.a.d 是 a.b.b.a 的前驱

规则说明：

• 遍历顺序为先遍历完一个分支的所有叶子，再处理下一个分支
• 若节点是兄弟节点，直接取相邻兄弟；若不是，则需上下遍历树形结构定位

当前尝试的增量检查方式繁琐易出错，可给节点添加.parent属性，现有初始代码逻辑卡壳：

function linkNext(node) {
  const i = node.parent.indexOf(node)
  if (i < node.parent.children.length - 1) {
    node.next = node.parent.children[i + 1]
  } else {
    if (node.parent.parent) {
      // 此处逻辑混乱
    }
  }
}

function linkPrevious(node) {
  const i = node.parent.indexOf(node)
  if (i > 0) {
    node.next = node.parent.children[i - 1] // 此处应为node.previous，笔误
  } else {
    // 同样逻辑卡壳
  }
}

解决方案 #

核心思路：先收集所有叶子节点，再建立双向链表 #

这种方式跳过复杂的上下遍历逻辑，直观易懂，步骤如下：

1. 预处理树形结构，给每个节点添加parent属性，并收集所有叶子节点（无children或children为空的节点）
2. 遍历叶子节点列表，给每个节点设置next和previous属性

代码实现 #

// 第一步：预处理树，添加parent属性并收集叶子节点
function processTree(root) {
  const leaves = [];
  const stack = [{ node: root, parent: null }];

  while (stack.length > 0) {
    const { node, parent } = stack.pop();
    node.parent = parent;

    // 判断是否为叶子节点
    if (!node.children || node.children.length === 0) {
      leaves.push(node);
      continue;
    }

    // 反向推入栈，保证深度优先遍历顺序正确
    for (let i = node.children.length - 1; i >= 0; i--) {
      stack.push({ node: node.children[i], parent: node });
    }
  }

  return leaves;
}

// 第二步：给叶子节点建立前驱后继关联
function linkLeafNodes(root) {
  const leaves = processTree(root);

  leaves.forEach((leaf, index) => {
    leaf.previous = leaves[index - 1] || null;
    leaf.next = leaves[index + 1] || null;
  });

  return leaves;
}

// 使用示例
const tree = { /* 放入题目中的树形结构 */ };
const linkedLeaves = linkLeafNodes(tree);

// 测试：找a.a.d.b的后继
const targetLeaf = linkedLeaves.find(leaf => leaf.label === 'a.a.d.b');
console.log(targetLeaf.next?.label); // 输出 'a.b.a.a'

// 测试：找a.b.b.a的前驱
const targetLeaf2 = linkedLeaves.find(leaf => leaf.label === 'a.b.b.a');
console.log(targetLeaf2.previous?.label); // 输出 'a.b.a.d'

方案优势 #

• 逻辑清晰：先通过深度优先遍历收集所有叶子，再按顺序直接关联，避免递归上下查找的复杂逻辑
• 易于维护：后续修改遍历顺序（如广度优先）只需调整processTree中的栈处理逻辑
• 性能高效：仅需遍历树一次+遍历叶子列表一次，时间复杂度为O(n)（n为节点总数）

可选方案：单个节点查找前驱/后继（无需预关联） #

如果不需要给所有叶子节点预先添加属性，可实现单个节点的查找函数：

// 复用processTree获取叶子节点
function getLeaves(root) {
  return processTree(root);
}

// 查找节点的后继
function findNext(node, root) {
  const leaves = getLeaves(root);
  const index = leaves.indexOf(node);
  return index !== -1 && index < leaves.length - 1 ? leaves[index + 1] : null;
}

// 查找节点的前驱
function findPrevious(node, root) {
  const leaves = getLeaves(root);
  const index = leaves.indexOf(node);
  return index > 0 ? leaves[index - 1] : null;
}

// 使用示例
const nextNode = findNext(targetLeaf, tree);
const prevNode = findPrevious(targetLeaf2, tree);

这种方式适合不需要频繁查找的场景，缺点是每次查找都要重新遍历树，性能不如预关联方案。

内容的提问来源于stack exchange，提问作者Lance Pollard