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

我们首先编写Node.value并Node.children从您的节点获取两个值

// -- Node -----------------------------------------------

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

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

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

接下来，我们创建一个泛型Iterator类型。这个模仿了原生的可迭代行为，只有我们的迭代器是持久的（不可变的）

// -- Empty ----------------------------------------------

const Empty =
  Symbol ()

const isEmpty = x =>
  x === Empty

// -- Iterator -------------------------------------------

const Yield = (value = Empty, it = Iterator ()) =>
  isEmpty (value)
    ? { done: true }
    : { done: false, value, next: it.next }

const Iterator = (next = Yield) =>
  ({ next })

const Generator = function* (it = Iterator ())
{
  while (it = it.next ())
    if (it.done)
      break
    else
      yield it.value
}

最后，我们可以实现PostorderIterator

const PostorderIterator = (node = Empty, backtrack = Iterator (), visit = false) =>
  Iterator (() =>
    visit
      ? Yield (node, backtrack)
      : isEmpty (node)
        ? backtrack.next ()
        : Node.children (node)
            .reduceRight ( (it, node) => PostorderIterator (node, it)
                         , PostorderIterator (node, backtrack, true)
                         )
            .next ())

tree我们可以在这里看到它与您的合作

// -- Demo ---------------------------------------------

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

const postOrderValues =
  Array.from (Generator (PostorderIterator (tree)), Node.value)

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

程序演示

// -- Node ----------------------------------------------

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

// -- Empty ---------------------------------------------

const Empty =
  Symbol ()

const isEmpty = x =>
  x === Empty

// -- Iterator ------------------------------------------

const Yield = (value = Empty, it = Iterator ()) =>
  isEmpty (value)
    ? { done: true }
    : { done: false, value, next: it.next }
    
const Iterator = (next = Yield) =>
  ({ next })
  
const Generator = function* (it = Iterator ())
{
  while (it = it.next ())
    if (it.done)
      break
    else
      yield it.value
}

const PostorderIterator = (node = Empty, backtrack = Iterator (), visit = false) =>
  Iterator (() =>
    visit
      ? Yield (node, backtrack)
      : isEmpty (node)
        ? backtrack.next ()
        : Node.children (node)
            .reduceRight ( (it, node) => PostorderIterator (node, it)
                         , PostorderIterator (node, backtrack, true)
                         )
            .next ())
            
// -- Demo --------------------------------------------              

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

const postOrderValues =
  Array.from (Generator (PostorderIterator (tree)), Node.value)
  
console.log (postOrderValues)
// [ 'e', 'k', 'f', 'b', 'c', 'g', 'h', 'i', 'j', 'd', 'a' ]

与只有和字段的节点类型相比，可变参数children字段使算法稍微复杂一些leftright

这些迭代器的简化实现使它们更容易比较。在其他迭代器中编写对可变参数子代的支持留给读者作为练习

// -- Node ---------------------------------------------

const Node = (value, left = Empty, right = Empty) =>
  ({ value, left, right })

// -- Iterators ----------------------------------------

const PreorderIterator = (node = Empty, backtrack = Iterator ()) =>
  Iterator (() =>
    isEmpty (node)
      ? backtrack.next ()
      : Yield (node,
          PreorderIterator (node.left,
            PreorderIterator (node.right, backtrack))))

const InorderIterator = (node = Empty, backtrack = Iterator (), visit = false) =>
  Iterator (() =>
    visit
      ? Yield (node, backtrack)
      : isEmpty (node)
        ? backtrack.next ()
        : InorderIterator (node.left,
            InorderIterator (node,
              InorderIterator (node.right, backtrack), true)) .next ())

const PostorderIterator = (node = Empty, backtrack = Iterator (), visit = false) =>
  Iterator (() =>
    visit
      ? Yield (node, backtrack)
      : isEmpty (node)
        ? backtrack.next ()
        : PostorderIterator (node.left,
            PostorderIterator (node.right,
              PostorderIterator (node, backtrack, true))) .next ())

而且很特别LevelorderIterator，只是因为我认为你可以应付

const LevelorderIterator = (node = Empty, queue = Queue ()) =>
  Iterator (() =>
    isEmpty (node)
      ? queue.isEmpty ()
        ? Yield ()
        : queue.pop ((x, q) =>
            LevelorderIterator (x, q) .next ())
      : Yield (node,
          LevelorderIterator (Empty,
            queue.push (node.left) .push (node.right))))

// -- Queue ---------------------------------------------

const Queue = (front = Empty, back = Empty) => ({
  isEmpty: () =>
    isEmpty (front),
  push: x =>
    front
      ? Queue (front, Pair (x, back))
      : Queue (Pair (x, front), back),
  pop: k =>
    front ? front.right ? k (front.left, Queue (front.right, back))
                        : k (front.left, Queue (List (back) .reverse () .pair, Empty))
          : k (undefined, undefined)
})

// -- List ----------------------------------------------

const List = (pair = Empty) => ({
  pair:
    pair,
  reverse: () =>
    List (List (pair) .foldl ((acc, x) => Pair (x, acc), Empty)),
  foldl: (f, acc) =>
    {  
      while (pair)
        (acc = f (acc, pair.left), pair = pair.right)
      return acc
    }
})

// -- Pair ----------------------------------------------
const Pair = (left, right) =>
  ({ left, right })

过度设计？有罪的。您可以将上面的接口换成 JavaScript 原语。在这里，我们将惰性流换成急切的值数组

const postOrderValues = (node = Empty, backtrack = () => [], visit = false) =>
  () => visit
      ? [ node, ...backtrack () ]
      : isEmpty (node)
        ? backtrack ()
        : Node.children (node)
            .reduceRight ( (bt, node) => postOrderValues (node, bt)
                         , postOrderValues (node, backtrack, true)
                         )
            ()

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

Answer 2

堆栈安全

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

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