递归邮政订单树遍历而不创建新节点 [英] Recursive post order tree traversal without creating new nodes

问题描述

我想定义一个适用于各种多路树的通用尾递归树遍历。这适用于预订和水平顺序，但我无法实现后订单遍历。这是我正在使用的多方树：

I want to define a generalized tail recursive tree traversal that works for all kinds of multi-way trees. This works fine with pre-order and level-order, but I'm having trouble to implement post order traversals. Here is the multi-way tree I am working with:

所需订单：EKFBCGHIJDA

Desired order: EKFBCGHIJDA

只要我不关心尾递归，订单遍历很容易：

As long as I don't care about tail recursion post order traversal is easy:

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

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

The tail recursive approach, on the other hand, is quite cumbersome:

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

特别是，我想避免创建新节点以便我可以遍历任意树而无需了解其构造函数。有没有办法做到这一点仍然保持尾递归？

In particular, I'd like to avoid creating new nodes so that I can traverse arbitrary trees without having to know anything about their constructors. Is there a way to do this and still remain tail recursive?

推荐答案

堆栈安全

我的第一个答案是通过编写我们自己的函数迭代器协议来解决这个问题。不可否认，我渴望分享这种方法，因为这是我过去探索过的。编写自己的数据结构非常有趣，它可以为您的问题提供创造性的解决方案 - 如果我先给出简单的答案，您会感到无聊，不是吗？

My first answer solves this problem by writing our own functional iterator protocol. Admittedly, I was eager to share this approach as it's something I've explored in the past. Writing your own data structures is really fun and it can yield creative solutions to your problem - and you'd be bored if I gave out the easy answers first, wouldn't you?

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

下面包含其他读者的完整解决方案......

Full solution included below for other readers...

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

相互递归

不知何故，这是你的问题，让我能够画出我最有灵感的作品。回到树遍历的顶空中，我想出了这种伪应用和类型现在和以后。

Somehow it's your questions that allow me to canvas my most inspired works. Back in the headspace of tree traversals, I came up with this sort of pseudo-applicative sum type Now and Later.

稍后没有正确的尾调用，但我认为解决方案太过于整洁而不能分享 p>

Later does not have a proper tail call but I thought the solution was too neat not to share it

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

这篇关于递归邮政订单树遍历而不创建新节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！