尾遞歸遍歷樹沒有循環

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