没有循环的尾递归树遍历 [英] Tail Recursive Tree Traversal without Loops

问题描述

我想递归地遍历下面的树结构尾部而不返回循环:

I want to traverse the following tree structure tail recursively without falling back on loops:

const o = {x:0,c:[{x:1,c:[{x:2,c:[{x:3},{x:4,c:[{x:5}]},{x:6}]},{x:7},{x:8}]},{x:9}]};

        0
       / \
      1   9
    / | \ 
   2  7  8
 / | \
3  4  6
   |
   5

想要的结果:/0/1/2/3/4/5/6/7/8/9

我想启用尾递归需要一个闭包.到目前为止，我已经尝试过:

I guess a closure is required to enable tail recursion. I've tried this so far:

const traverse = o => {
  const nextDepth = (o, index, acc) => {
    const nextBreadth = () => o["c"] && o["c"][index + 1]
     ? nextDepth(o["c"][index + 1], index + 1, acc)
     : acc;

    acc = o["c"]
     ? nextDepth(o["c"][0], index, acc + "/" + o["x"]) // not in tail pos
     : acc + "/" + o["x"];

    return nextBreadth();
  };

  return nextDepth(o, 0, "");
};

traverse(o); // /0/1/2/3/4/5/7/9

兄弟姐妹没有正确遍历.这怎么办?

The siblings are not traversed properly. How can this be done?

推荐答案

正如@Bergi 所写，如果您手动维护堆栈，解决方案很简单.

As @Bergi wrote if you manually maintain stack the solution is straightforward.

const o = {x:0,c:[{x:1,c:[{x:2,c:[{x:3},{x:4,c:[{x:5}]},{x:6}]},{x:7},{x:8}]},{x:9}]}

const traverse = g => {
  const dfs = (stack, head) => (head.c || []).concat(stack)
  
  const loop = (acc, stack) => {
    if (stack.length === 0) {
    	return acc
    }

    const [head, ...tail] = stack
    return loop(`${acc}/${head.x}`, dfs(tail, head))
  }
  
  return loop('', [g])
}

console.log(traverse(o))
console.log(traverse(o) === '/0/1/2/3/4/5/6/7/8/9')

这篇关于没有循环的尾递归树遍历的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！