0

別のツリーにコピーしたいバイナリツリー T があります。

すべてのノードで評価される visit メソッドがあるとします。

struct visit 
{
 virtual void operator() (node* n)=0;

};

そして私は訪問者アルゴリズムを持っています

void visitor(node* t, visit& v)
{
//do a preorder traversal using stack or recursion
 if (!t) return;
 v(t);
 visitor(t->left, v);
 visitor(t->right, v);

}

2 つの質問があります。

  1. ブーストグラフがこれを行うことがわかったので（頂点訪問者）、ファンクターベースのアプローチを使用することにしました。また、同じコードを繰り返してツリーをトラバースし、各ノードで異なることを行う傾向があります。これは、重複したコードを取り除くための良い設計ですか? 他にどのような代替デザインがありますか?
  2. これを使用して、既存のバイナリ ツリーから新しいバイナリ ツリーを作成するにはどうすればよいですか? 必要に応じて訪問ファンクターにスタックを保持できますが、それは訪問者のアルゴリズムに結び付けられます。
  3. ここにポストオーダートラバーサルを組み込むにはどうすればよいですか? 別のファンクタークラス？
4

2 に答える 2

1

3: 実行するトラバーサルの種類ごとに追加のメソッドを作成し、訪問者の呼び出しを再配置します。

void preorder_visitor(node* t, visit& v)
{
 if (!t) return;
 v(t);
 visitor(t->left, v);
 visitor(t->right, v);
}

void postorder_visitor(node* t, visit& v)
{
 if (!t) return;
 visitor(t->left, v);
 visitor(t->right, v);
 v(t);
}
于 2010-04-05T16:28:10.320 に答える
0
  1. 訪問者をサブクラス化し、個々のタスクごとに異なる訪問者を提供し、同様の (または関連する) タスクを同じ訪問者にマージします。最善のアプローチは、何をしようとしているのかによって大きく異なります。
  2. 訪問者は別のツリーを構築できます。ノードにアクセスすると、新しいノードのコピーが作成され、それらが「正しい」順序でリンクされます。
  3. ノードが訪問される順序を書き換えます。

ビジターはテクニックです。テクニックを特定のソリューションと混同しているようです。ビジターを使用するということは、コールバックによって外部オブジェクト (ビジター) と通信するデータ構造によっていくつかのナビゲーション サービスが提供されることを意味します。

于 2010-04-05T16:24:28.423 に答える