尾递归遍历树没有循环

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 

兄弟姐妹没有正确穿过。如何才能做到这一点？

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) { 
 
    \t 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')