Tail Recursive przechodzenie drzewa bez pętli

Question

chcę przechodzić przez następujące struktury drzewa, ogon rekurencyjnie bez upadku z powrotem na pętli:

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 

pożądany wynik: /0/1/2/3/4/5/6/7/8/9

Chyba zamknięcie jest wymagane włączyć rekursję ogonową. Próbowałem tego do tej pory:

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 

Rodzeństwo nie jest prawidłowo prowadzone. Jak to zrobić?

Answer 1

Jak @Bergi napisał, jeśli ręcznie utrzymuje stos, rozwiązanie jest proste.

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