Итеративная функция сериализации дерева

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

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(""));

Answer 2

Другой подход с использованием массива для уровней и предварительной итерации более глубоких уровней.

function s(root) {
    var i = 0,
        node,
        levels = [[root]],
        result = '';

    while (i !== -1) {
        [node, ...levels[i]] = levels[i];
        if (node) {
            result += node[0];
            if (node[1].length) {
                levels[++i] = node[1];
                continue;
            }
        } else {
            i--;
        }
        result += ')';
    }
    return result.slice(0, -1); remove extra bracket for the outer missing array
}

const
    node = (x, ...xs) => ([x, xs]),
    tree = node("a", node("b", node("e"), node("f", node("k"))), node("c"), node("d", node("g"), node("h"), node("i"), node("j"))),
    result = s(tree);

console.log(result);

Answer 3

Один из вариантов - связать узлы.Таким образом, вы можете пройти по дереву, не сохраняя позицию, в которой вы находитесь:

  const Node = (value, ...children) => {
   const node = { value, children };
   children.forEach(child => child.parent = node);
   if(children.length > 1) 
      children.reduceRight((curr, prev) => ((prev.next = curr), prev));
   return node;
 };

Как это поможет?Скважина:

function serialize(node) {
  let result = node.value;
  while(node) {
    // Deep first
    while(node.children[0]) {
      node = node.children[0];
      result += node.value;
    }

    // then right
    if(node.next) {
      node = node.next;
      result += ")" + node.value;
    } else {
      // and up at the last node
      while(node && !node.next) {
        node = node.parent;   
        result += ")";
       }
       result += ")";
       if(node) {
        node = node.next;
        result += node.value;
       }
     }
   }
   return result;
 }