如何在树结构中整齐地关联下一个和上一个“节点”？

Question

假设我有一个简单的树结构：

{
  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'
            }
          ]
        }
      ]
    }
  ]
}

例如，我如何巧妙地弄清楚

a.b.a.a

位于

a.a.d.b

(

next

) 之后，而

a.b.a.d

位于

a.b.b.a

(

previous

) 之前？

也就是说，你从一个叶子到另一个叶子，即使这些叶子不是直接的兄弟姐妹。如果他们是兄弟姐妹，您只需转到下一个/上一个兄弟姐妹，但如果他们不是兄弟姐妹，您必须在树上上下导航以查找下一个和上一个兄弟姐妹。

实现这一目标的简单方法是什么？我已经这样做了一段时间，并且一直坚持以一种非黑客的方式来做这件事。基本上，我尝试进行少量的增量手动检查，例如检查父级是否是叶子，如果不是，则向下检查，然后我就迷路了。

如果有帮助，您可以添加

.parent

属性来跟踪父级，或者您可以传递

path

（假设标签实际上不是所示的路径，这仅用于说明目的）。

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) {
      // I get lost about here.
    }
  }
}

function linkPrevious(node) {
  const i = node.parent.indexOf(node)
  if (i > 0) {
    node.next = node.parent.children[i - 1]
  } else {
    // same here...
  }
}

想知道如何以简单的方式完成此操作，我的思绪被这个问题绊倒了。

Answer 1

你的问题有点难以解析，但看起来你需要这个：

function linkTree(tree, precedingNode) {
    if (!tree) {
        return precedingNode;
    }
    if (tree.children) {
        // internal node -- no links
        for(child of tree.children) {
            precedingNode = linkTree(child, precedingNode);
        }
    } else {
        // leaves are linked into a doubly-linked list
        if (precedingNode) {
            tree.prev = precedingNode;
            precedingNode.next = tree;
        }
        precedingNode = tree;
    }
    return precedingNode;
}

Answer 2

为此目的，您可能会受益于 generator 函数：它可以按顺序生成叶子：

function* leaves(node) {
    if (!node.children) { // It's a leaf
        return yield node;
    }
    for (const child of node.children) {
        yield* leaves(child);
    }
}

一旦你有了它，你就可以通过一个简单的

for..of

循环来访问叶子：

for (const leaf of leaves(tree)) {
    console.log(leaf.label); 
}

要以相反的顺序获得相同的结果，您可以使用可选参数扩展生成器：

function* leaves(node, reversed=false) {
    if (!node.children) { // It's a leaf
        return yield node;
    }
    const children = reversed ? node.children.toReversed() : node.children;
    for (const child of children) {
        yield* leaves(child, reversed);
    }
}

也许这已经足以满足您的目的，但如果您确实想向叶节点添加

next

属性，那么您可以从一个函数中受益，该函数将产生叶子及其后继者（作为两个节点的数组）。这是一个通用函数来实现这一点：

function* pairs(iterable) {
    const iterator = iterable[Symbol.iterator]();
    let prev = iterator.next().value;
    for (const next of iterator) {
        yield [prev, next];
        prev = next;
    }
}

然后叶子的链接就很简单：

for (const [prev, next] of pairs(leaves(tree, reversed))) {
    prev.next = next;
}

以下是使用示例树作为输入的所有内容：

function* leaves(node, reversed=false) {
    if (!node.children) { // It's a leaf
        return yield node;
    }
    const children = reversed ? node.children.toReversed() : node.children;
    for (const child of children) {
        yield* leaves(child, reversed);
    }
}

// Generic function to iterate the consecutive pairs of an iterable
function* pairs(iterable) {
    const iterator = iterable[Symbol.iterator]();
    let prev = iterator.next().value;
    for (const next of iterator) {
        yield [prev, next];
        prev = next;
    }
}

function linkNext(node, reversed=false) {
    for (const [prev, next] of pairs(leaves(tree, reversed))) {
        prev.next = next;
    }
}

// Example run
const tree = {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'}]}]}]}

console.log("Iterate the leaves in their order:");
for (const node of leaves(tree)) console.log(node.label);
console.log("Iterate the leaves in reversed order");
for (const node of leaves(tree, true)) console.log(node.label);
// Set the next properties of leaves (only leaves!)
linkNext(tree);