Comment traverser/plier un arbre dans DFS post-ordre

Question

donné est cette structure de données d'arbre:

const tree = {v:"f", c:[ 
    {v:"b", c:[ 
    {v:"a", c:[]}, 
    {v:"d", c:[ 
     {v:"c", c:[]}, 
     {v:"e", c:[]} 
    ]} 
    ]}, 
    {v:"g", c:[ 
    {v:"i", c:[ 
     {v:"h", c:[]} 
    ]} 
    ]} 
]}; 

Jusqu'à présent, je suis parvenu à le traverser en BFS et précommande DFS avec une approche récursive de la queue :

// tree fold 
 

 
const foldl = concat => (valueKey, childKey) => f => acc => tree => { 
 
    const next = (acc, [head, ...tail]) => head === undefined 
 
    ? acc 
 
    : next(
 
    f(acc) (head[valueKey]), 
 
    concat(head[childKey]) (tail) 
 
    ); 
 
    
 
    return next(acc, [tree]); 
 
}; 
 

 

 
// auxilliary functions 
 

 
const flip = f => x => y => f(y) (x); 
 

 
const concat = xs => x => xs.concat(x); 
 

 

 
// data 
 

 
const tree = {v:"f", c:[ 
 
    {v:"b", c:[ 
 
    {v:"a", c:[]}, 
 
    {v:"d", c:[ 
 
     {v:"c", c:[]}, 
 
     {v:"e", c:[]} 
 
    ]} 
 
    ]}, 
 
    {v:"g", c:[ 
 
    {v:"i", c:[ 
 
     {v:"h", c:[]} 
 
    ]} 
 
    ]} 
 
]}; 
 

 

 
// and run... 
 

 
console.log("DFS pre-order", foldl(concat) ("v", "c") (concat) ([]) (tree)); 
 
// yields ["f", "b", "a", "d", "c", "e", "g", "i", "h"] 
 

 
console.log("BFS", foldl(flip(concat)) ("v", "c") (concat) ([]) (tree)); 
 
// yields ["f", "b", "g", "a", "d", "i", "c", "e", "h"]

Malheureusement, je ne suis pas en mesure d'adapter l'approche de manière à pouvoir gérer post-ordre DFS en plus - une approche unifiée, ainsi parler. La sérialisation souhaitée est ["a", "c", "e", "d", "b", "h", "i", "g", "f"]. Toute aide est appréciée!

[EDIT]

j'ai réussi à mettre en œuvre la version post-ordre - mais pas encore une solution unifiée pour tous les trois cas BFS, DFS pré-commande, post-ordre DFS. D'ailleurs, je ne pense pas que mon approche soit particulièrement élégante. Donc, je suis toujours intéressé par les réponses de personnes qui ont une meilleure compréhension de la récursivité que moi.

const foldl = (valueKey, childKey) => f => acc => o => { 
    const next = (acc, [head, ...tail]) => { 
    // base case 
    if (head === undefined) return acc; 

    // branch (children) 
    if (head[childKey].length > 0) { 
     return next(
     acc, 
     concat(head[childKey].concat({v:head[valueKey], c:[]})) (tail) 
    ); 
    } 

    // leaf (no children) 
    return next(f(acc) (head[valueKey]), tail); 
    }; 

    return next(acc, [o]); 
}; 

foldl("v", "c") (concat) ([]) (tree); 
// yields ["a", "c", "e", "d", "b", "h", "i", "g", "f"] 

Answer 1

au lieu de la queue-récursion, vous voulez récursivité dans l'arbre avant d'ajouter les éléments:

function dfsPost(tree) { 
    return tree.c.reduce((arr, el) => arr.concat(dfsPost(el)), []).concat(tree.v); 
} 

dfsPost(tree) // ["a", "c", "e", "d", "b", "h", "i", "g", "f"] 

moins performant, mais récursive queue: Vous pouvez faire un simple DFS, mais lorsque vous parcourez chaque élément, utilisez c.reduceRight(). Puis appelez reverse() sur le tableau résultant.

function dfsPost(tree) { 
    return (function dfs(tree) { 
     return [tree.v].concat(tree.c.reduceRight((arr, el) => arr.concat(dfs(el)), [])) 
    }(tree)).reverse(); 
} 

dfsPost(tree) // ["a", "c", "e", "d", "b", "h", "i", "g", "f"]