javascript - 不创建新节点的递归后序树遍历

Question

我想定义一个通用的尾递归树遍历，适用于所有类型的多路树。这适用于预购和等级订购，但我在实现后购遍历时遇到了麻烦。这是我正在使用的多路树:

所需订单:EKFBCGHIJDA

只要我不关心尾递归后序遍历就很容易:

const postOrder = ([x, xs]) => {
  xs.forEach(postOrder);
  console.log(`${x}`);
};

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

postOrder(tree);

另一方面，尾递归方法非常麻烦:

const postOrder = (p, q) => node => {
  const rec = ({[p]: x, [q]: forest}, stack) => {
      if (forest.length > 0) {
        const [node, ...forest_] = forest;
        stack.unshift(...forest_, Node(x));
        return rec(node, stack);
      }

      else {
        console.log(x);
        
        if (stack.length > 0) {
          const node = stack.shift();
          return rec(node, stack);
        }

        else return null;
      }
    };

  return rec(node, []);
};

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

postOrder(0, 1) (tree);

特别是，我想避免创建新节点，这样我就可以遍历任意树而不必了解它们的构造函数。有没有办法做到这一点并仍然保持尾递归？

Answer 1

堆栈安全

我的第一个答案通过编写我们自己的函数式迭代器协议(protocol)解决了这个问题。不可否认，我很想分享这种方法，因为这是我过去探索过的东西。编写您自己的数据结构真的很有趣，它可以为您的问题提供创造性的解决方案 - 如果我先给出简单的答案，您会觉得无聊，不是吗？

const Empty =
  Symbol ()

const isEmpty = x =>
  x === Empty

const postOrderFold = (f = (a, b) => a, acc = null, node = Empty) =>
{
  const loop = (acc, [ node = Empty, ...nodes ], cont) =>
    isEmpty (node)
      ? cont (acc)
      : ???
  return loop (acc, [ node ], identity)
}

const postOrderValues = (node = Empty) =>
  postOrderFold ((acc, node) => [ ...acc, Node.value (node) ], [], node)

console.log (postOrderValues (tree))
// [ 'e', 'k', 'f', 'b', 'c', 'g', 'h', 'i', 'j', 'd', 'a' ]

下面为其他读者提供了完整的解决方案...

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

Node.value = ([ value, _ ]) =>
  value

Node.children = ([ _, children ]) =>
  children
  
const Empty =
  Symbol ()
  
const isEmpty = x =>
  x === Empty

const identity = x =>
  x

// tail recursive
const postOrderFold = (f = (a, b) => a, acc = null, node = Empty) =>
{
  const loop = (acc, [ node = Empty, ...nodes ], cont) =>
    isEmpty (node)
      ? cont (acc)
      : loop (acc, Node.children (node), nextAcc =>
          loop (f (nextAcc, node), nodes, cont))
  return loop (acc, [ node ], identity)
}

const postOrderValues = (node = Empty) =>
  postOrderFold ((acc, node) => [ ...acc, Node.value (node) ], [], node)

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 (postOrderValues (tree))
// [ 'e', 'k', 'f', 'b', 'c', 'g', 'h', 'i', 'j', 'd', 'a' ]

相互递归

不知何故，是您的问题让我能够画出我最受启发的作品。回到树遍历的顶空，我想到了这种伪应用求和类型 Now 和 Later。

Later 没有正确的尾调用，但我认为解决方案太简洁了，不能不分享它

const Empty =
  Symbol ()

const isEmpty = x =>
  x === Empty

const postOrderFold = (f = (a, b) => a, acc = null, node = Empty) =>
{
  const Now = node =>
    (acc, nodes) =>
      loop (f (acc, node), nodes)

  const Later = node =>
    (acc, nodes) =>
      loop (acc, [ ...Node.children (node) .map (Later), Now (node), ...nodes ])

  const loop = (acc, [ reducer = Empty, ...rest ]) =>
    isEmpty (reducer)
      ? acc
      : reducer (acc, rest)

  // return loop (acc, [ ...Node.children (node) .map (Later), Now (node) ])
  // or more simply ...
  return Later (node) (acc, [])
}

互递归演示

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

Node.value = ([ value, _ ]) =>
  value

Node.children = ([ _, children ]) =>
  children
  
const Empty =
  Symbol ()
  
const isEmpty = x =>
  x === Empty

const postOrderFold = (f = (a, b) => a, acc = null, node = Empty) =>
{
  const Now = node =>
    (acc, nodes) =>
      loop (f (acc, node), nodes)
    
  const Later = node =>
    (acc, nodes) =>
      loop (acc, [ ...Node.children (node) .map (Later), Now (node), ...nodes ])
    
  const loop = (acc, [ reducer = Empty, ...rest ]) =>
    isEmpty (reducer)
      ? acc
      : reducer (acc, rest)
  
  // return loop (acc, [ ...Node.children (node) .map (Later), Now (node) ])
  // or more simply ...
  return Later (node) (acc, [])
}

const postOrderValues = (node = Empty) =>
  postOrderFold ((acc, node) => [ ...acc, Node.value (node) ], [], node)

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 (postOrderValues (tree))
// [ 'e', 'k', 'f', 'b', 'c', 'g', 'h', 'i', 'j', 'd', 'a' ]