2

これまたはこれのような一般的な k-ary ツリーがあるとします。

ここで後者を繰り返します：

template <typename T>
struct TreeNode
{
  T* DATA ; // data of type T to be stored at this TreeNode

  vector< TreeNode<T>* > children ;

  void insert( T* newData ) ;

  // runs f on this and all children of this
  void preorder( function<void (T*)> f )
  {
    f( this->DATA ) ; // exec f on this
    for( int i = 0 ; i < children.size(); i++ )
      children[i]->preorder( f ) ; // exec f on each child
  }

} ;

template <typename T>
struct Tree
{
  TreeNode<T>* root;

  // TREE LEVEL functions
  void clear() { delete root ; root=0; }

  void insert( T* data ) { if(root)root->insert(data); } 
} ;

TreeNode通常、上記 のように の再帰メンバー関数として、事前注文と事後注文のトラバーサルがあります。しかし、関数を渡したくない場合は、ツリー内の各ノードにクラスの外からアクセスしたいとします(つまり、Treeオブジェクトを指定しただけです)。

どうすればできますか？

4

2 に答える 2

3

PreorderIteratorトラバーサルのどこにあったかについての状態を維持するクラスを定義することで、これにアプローチします。現在のノードを返し、トラバーサルを 1 ステップ進めるためのメソッドがあります。

イテレータの存続期間中にツリー構造が変化する可能性がある場合は注意が必要です。おそらく、ツリーは変更カウントを維持できます。イテレータは、開始時にカウントを取得し、アクセスごとに変更をチェックできます (変更が見つかった場合は例外をスローします)。

于 2013-03-05T22:08:20.920 に答える
2

簡単な方法の1つは、ツリーをリストにロードし、必要に応じてリストをウォークすることです。このリストはポインタのリストにすぎないため、それほど高価ではありません。これを行うには、トライトラバーサルアルゴリズムの修正バージョンを使用します。

void traverse(Node n){
  if(null == n) return;

  for( Node c: n.children){
    visit( c );
    traverse( c );
  }
}

を使用してvisit、実際にリストをロードします。だから何かのような

List<Node> getListToIterate(Node n){
   List<Node> result = new ArrayList<Node>();
   traverse(n,resutl);
   return result;
}

void traverse(Node n, List list){
  if(null == n) return;

  for( Node c: n.children){
    list.add( c );
    traverse( c );
  }

}

TreeIteratorまた、必要に応じて、リスト内のどこにいるかを追跡するクラスでこのアルゴリズムをラップすることもできます。

于 2013-03-06T00:29:48.433 に答える