ツリー構造の比較のアルゴリズムを教えてください

質問

ディレクトリ構造の変更前と変更後の比較を行って、
どのフォルダがどこへ行ったかを判別するプログラムを作成したいのですが、どんなアルゴリズムにすればよいでしょうか？

変更前と変更後でディレクトリは１：１に対応しません。ｎ：ｍや削除、追加など色んなパターンがあります。

ツリー構造（ディレクトリ構造）とは、以下のようなイメージのものです。
C:.
├─Acrobat
│ ├─ActiveX
│ ├─Browser
│ ├─FileInfo
│ ├─HowTo
│ │ ├─ENU
│ │ │ └─Images
│ │ └─JPN
│ │ └─Images
│ ├─Javascripts

回答No.1

machongola · ベストアンサー

考えてみましたが何とも言えません。
取り敢えず回答カウントがゼロなので投稿させていただきます。
但し、これはあくまで個人的なアイデアやイメージである事を前提とします。

☆ツリー構造はGUIコントロールでありマウスで操作するとコールバックされる事を前提(TreeGUIとします)

☆手順はコールバックがかかる度に変化したTreeGUIの状態からデータ構造を生成します

☆データ型
struct TreeData
{
string strDirectory;//ディレクトリの名前 "Actobat"など
int nAction;//このディレクトリに対して行われた操作フラグの記録
//その他TreeDataを連結するポインタなど
};

☆page[?]//TreeData*をしまう為の配列
　page[0]//変更前
　page[1]//変更後

(1)以下のスタートの状態からTreeDataを生成してpage[0]に入れる

├─Acrobat
│ ├─ActiveX
│ ├─Browser
│ ├─FileInfo
│ ├─HowTo
│ │ ├─ENU
│ │ │ └─Images
│ │ └─JPN
│ │ └─Images
│ ├─Javascripts

(2)TreeGUIをマウスで突っついたりディレクトリ操作をする（コールバック発生）TreeGUIの状態かTreeDataを生成してpage[1]に入れる

アルゴリズム等
　1:1やm:nの確認なら再帰等で操作してCTreeDataの連結数を数えて比較すれば出来ます
　oldCount = DoCount(page[0])
　nowCount = DoCount(page[1])

　ディレクトリの位置が違うがカウントは同じ
　if(oldCount == nowCount)//...

　あとはTreeDataの構造を操作しながらその都度処理していくしかなさそうです。当然ながらどのような操作を受けたディレクトリなのかを示すメンバデータも必要になります。

　また変更前と変更後の二つだけしか必要ない場合、TreeGUIに反応するたびpage[1]にTreeData生成しますが、一歩手前を検出する場合は変更以前のものが軌跡を残すように連鎖するので（アンドゥリドゥみたいになる）pageは動的に拡大されます(page[0] ～ page[n])。

　この設問に回答するのは実に困難であります。