javascript - 迭代树序列化函数

Question

这是我正在使用的树和所需的字符串序列化的可视化表示：

这是一个递归解决方案：

function* serialize(root) {
  if (root.length === 0)
    return;

  const [x, xs] = root;
  yield x;

  for (let i = 0; i < xs.length; i++)
    yield* serialize(xs[i]);

  yield ")";
}

const Node = (x, ...xs) => ([x, xs]);

const tree = Node("a",
  Node("b",
    Node("e"),
    Node("f",
      Node("k"))),
  Node("c"),
  Node("d",
    Node("g"),
    Node("h"),
    Node("i"),
    Node("j")));

console.log(
  Array.from(serialize(tree)).join("")); // abe)fk)))c)dg)h)i)j)))

显然，它可以工作，但对于非常深的树来说不是安全的。我怎样才能将它转换成它的迭代对应物？

我知道我需要一个堆栈。但我无法弄清楚细节。我对这种转变的基本机制特别感兴趣。

我设法创建了一个迭代的前序遍历，但奇怪的是，这对迭代序列化它没有帮助：

const Node = (x, ...xs) => ([x, xs]);

const tree = Node("a",
  Node("b",
    Node("e"),
    Node("f",
      Node("k"))),
  Node("c"),
  Node("d",
    Node("g"),
    Node("h"),
    Node("i"),
    Node("j")));

function* preOrderIt(root) {
  if (root.length === 0)
    return;

  const stack = [root];

  while (stack.length > 0) {
    let [x, xs] = stack.pop();

    for (let i = xs.length - 1; i >= 0; i--)
      stack.push(xs[i]);

    yield x;
  }
}

console.log(
  Array.from(preOrderIt(tree)).join("")); // abefkcdghij

标签： javascriptalgorithmloopsrecursiontree

Answer 1

您的序列化基本上为每个节点添加了一个额外的虚拟子节点，因此您必须在迭代时“访问”它：

const Node = (x, ...xs) => ([x, xs]);

const tree = Node("a",
  Node("b",
    Node("e"),
    Node("f",
      Node("k"))),
  Node("c"),
  Node("d",
    Node("g"),
    Node("h"),
    Node("i"),
    Node("j")));

function* preOrderIt(root) {
  if (root.length === 0)
    return;

  const stack = [root];

  while (stack.length > 0) {
    let [x, xs] = stack.pop();

    if (x !== ')')             // <-
      stack.push([')', []]);   // <-

    for (let i = xs.length - 1; i >= 0; i--)
      stack.push(xs[i]);

    yield x;
  }
}



console.log(
  Array.from(preOrderIt(tree)).join(""));