DFSポスト順に倍/ツリーを走査する方法

Question

は、このツリーデータ構造である：

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:[]} 
    ]} 
    ]} 
]}; 

は、これまでのところ私は末尾再帰的なアプローチでBFSとDFSの前順で、それを横断するために管理してきました：

// 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"]

残念ながら、私は「それがほかにDFSポスト順序を扱うことができるようにアプローチを適応することができませんm - で統一されたアプローチにそう話す。必要なシリアル化は["a", "c", "e", "d", "b", "h", "i", "g", "f"]です。どんな助けもありがとう！

[EDIT]

私はポストオーダーのバージョンを実装するために管理 - しかし、すべての3例のBFS、DFSのプリオーダー、DFSポストオーダーのため、それはまだない統合ソリューション。しかも、私のアプローチは特に優雅だとは思わない。だから私はまだ私よりも再帰をよく理解している人の回答に興味があります。繰り返し処理を行う場合、あなたは簡単なDFSを行うことができますが、：

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"] 

あまりパフォーマンスが、尾の再帰：

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

は、代わりに末尾再帰の、あなたは要素を追加する前に、ツリーを下に再帰したいです各要素は、c.reduceRight（）を使用します。その後、結果の配列に対してreverse（）を呼び出します。

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"]