无循环尾递归树遍历

Question

我希望您能够进行尾递归遍历以下树形结构，而不必回到循环。

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

我猜需要一个闭包来启用尾递归。到目前为止我已经尝试了这个：

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

兄弟节点没有被正确遍历。如何解决这个问题？

- user6445533

---

http://codereview.stackexchange.com/questions/47932/recursion-vs-iteration-of-tree-structure - user57508

除非您想手动维护堆栈，否则无法仅使用尾递归遍历树。 - Bergi

你会如何使用循环来编写它？首先尝试使用循环，然后将循环转换为尾递归函数。 - Bergi

@Bergi 真遗憾！我试了好几个小时都没有成功。我想也许使用闭包处理 index 作为自由变量可能是一个可行的选项。那可能就是你所说的模拟堆栈。 - user6445533

@Bergi 你确定这不可能吗？如果你递归遍历树的“层级”（选择所有相关子节点进入下一级递归），而不是递归遍历单个节点，会怎样呢？ - Magne

@Magne 那么你已经用队列构建了一个广度优先搜索。OP想要深度优先搜索。 - Bergi

Answer 1

正如@Bergi写的那样，如果您手动维护堆栈，则解决方案就很简单。

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

- Yury Tarabanko

---

非常好的尾递归解决方案，谢谢！处理自己的堆栈似乎并不那么困难。 - user6445533

这是我在SO上很长时间以来看到的最好的问题/答案之一。 - Mulan