不创建新节点的递归后序树遍历 [英] 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?

推荐答案

stack-safe

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

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

相互递归

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

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.

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

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屋！