ツリー構造の一般的なトラバーサル

Question

私のツリー（まあ、それはバイナリトライです）をトラバースする方が一般的です。

私は辞書的なinorderで木を歩いています。 私は普遍的なツリートラバーサルによって抽象化することができると思う機能の例としては、（擬似コードで）、次のとおりです。

items(node*, key, list&) { 
    if(node->value) 
     list.push({node->value, key}) 
    if(node->left) 
     items(node->value, key + "0") 
    if(node->right) 
     items(node->value, key + "1") 
} 

draw(node*, id, ostream&) { 
    drawNode(node, id) 
    if (node->left) 
     drawLine(node, node->left, "0", ostream&) 
     draw(node->left, ++id, ostream&) 
    if (node->right) 
     drawLine(node, node->right, "1", ostream&) 
     draw(node->right, ++id, ostream&) 

私は、コード、右方向に押すだけの機能を求めていませんよ。関数を引数とするテンプレートを使って行うべきでしょうか？トラバーサルが単一の左/右ノードの存在によって単に調整されていないより複雑なケースはどうでしょうか（2つのトライのマージはこの抽象の候補にあまりにも似ているようです）。

Answer 1

トラバーサルの一般的な抽象化は、イテレータの適切な形式です。トラバーサルが一直線に並んだ位置になると、通常のイテレーターの1つを使って定式化します。最も一般的には、BidirectionalIteratorをモデリングします。ツリーのトラバーサル（またはより一般的なグラフ）を一般化するとき、反復操作が異なる方向に動くことがあります。