Schwanz rekursive Baum Traversal ohne Loops

Question

ich die folgende Baumstruktur Schwanz rekursiv ohne Rückgriff auf Schleifen zu durchqueren wollen:

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 

Das gewünschte Ergebnis: /0/1/2/3/4/5/6/7/8/9

Ich denke, eine Schließung erforderlich ist Aktivieren Sie die Tail-Rekursion. Ich habe das bisher probiert:

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 

Die Geschwister werden nicht richtig durchlaufen. Wie kann das gemacht werden?

Answer 1

Wie @Bergi schrieb, wenn Sie Stapel manuell verwalten, ist die Lösung unkompliziert.

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