पूंछ रिकर्सिव ट्री Traversal

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

जैसा कि @ बर्गि ने लिखा है कि यदि आप मैन्युअल रूप से स्टैक को बनाए रखते हैं तो समाधान सरल है।

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