質問: やりたいこと ------- 以下の様な、ツリー構造を想定したクラスが存在します。 ``` public class Person { public string PersonId { get; set;} public string ParentId { get; set;} public string PersonName { get; set;} public List Children { get; set;} } ``` 親となるPersonがあり、親は複数の子を持ち、子はさらに複数の子供を持ち... という、よくある階層構造となるクラスです。 ツリー構造のオブジェクトの中からツリー構造を保ったまま要素の「検索」をしたいと思っていますが、スッキリとした方法が思い浮かびません。 (汚く効率の悪いロジックなら書けるのですが...) このような場合の綺麗なロジックの書き方を教えてください。 **※ 上に挙げたプロパティの他に必要なものがあれば、追加しても構いません** 補足 --- このPersonクラスのオブジェクトは、最初は階層構造になっておらず単なる一次元のリストの状態です。 これを最終的に、`PersonId(自分自身のID)`と`ParentId(親要素のID)`を頼りに階層構造となるように組み立てていきます。 検索について ------- 検索を行う際は、以下のような仕組みを想定しています。 * テキストボックスに入力されたキーワードを元に、`PersonName`で検索(部分一致)をする * 検索の結果、ツリーの枝要素にヒットした場合は、その配下の枝・葉の要素はすべて表示する。ヒットした枝より上位の枝要素もすべて表示する。 * 検索の結果、葉要素にヒットした場合は、それより上位の枝要素はすべて表示する * 葉要素が一つもヒットしなかった枝要素は画面に表示しない(葉のない枝は表示しない) というものを考えています。 簡単に言えば、「検索結果に関係のあるものだけ表示をする」という、これまたよくありそうなツリー構造の検索の仕組みです。 検索の結果、「表示しない」と判断された要素はツリー構造のオブジェクトから削除されます。(または、ツリーを組み立てるときにそれを含まないようにします) 決して「非表示フラグを立てる」という方法ではありません。(これは仕様として絶対条件です) 例) 以下のようなツリーを例とします。 例えば「太郎」で検索をかけた場合、「田中太郎」にヒットします。 なので、配下の「田中二郎」「鈴木花子」も残ります。 また「田中太郎」より上の「山田一郎」も残ることになります。 「花子」で検索をかけた場合、ツリーに残るのは「山田一郎」「田中太郎」「鈴木花子」になります。 「一郎」で検索をかけた場合は、最上位の枝要素にヒットしているので、「すべて」の人物がツリーに残ったままになります。 同様に、「二郎」で検索をかけると、「鈴木花子」を除くすべての人物がツリーに残ります。 ``` 山田一郎 ┓ ____ ┣ 山田二郎 ____ ┗ 田中太郎 ┓ __________ ┣ 田中二郎 __________ ┗ 鈴木花子 ``` (図中のアンダーバーは、位置ずれを起こさないためのスペースの代わりです) 考えた方法 ------ 方法としては複数あるかと思います。 * ツリー状に組み立てる前の一次元リストの状態で「検索」を行い、何かしらの処理をしてから組み立てる * 完成したツリーから、検索の結果不要となった要素を削除する * 検索の結果必要と判断された要素だけでツリーを構築する ただし、どれも実現が難しく困っています。 それは、 * 組み立てる前の一次元リストでは、直接ヒットしなかった要素が最終的に必要となるのかどうか組み立てるまで分からない * 木構造のリストから不要なものを削除するには非常に手間がかかる(foreachなどでループしながら要素を削除すると、かなり気を使わない要素数が減ったことでとエラーになる) * 親→子→孫→...の順に検索を行う必要があるため、この順で要素を作っていくことになるが、「孫を入れるための子オブジェクトを作ったが、孫が0人だったので子オブジェクトが不要になってしまった」として葉要素の無い枝オブジェクトが発生してしまう といった問題となるからです。 さいごに ----- このように、「ツリーに対して検索をかけ、マッチした要素と関連するものだけ表示する」ように実装をする方法が分かりません。 どうにか綺麗に実装をする方法を教えてください。 なるべく外部のライブラリを使用したり(.NETに初めから含まれているものならOK)、巨大なツリー用のクラスを作ったり...ということは避けたいと思っています。 (前者は絶対に認められません。後者は簡易なものであれば良さそうですが。) よろしくお願いします。
回答: こんにちは。 > > 完成したツリーから、検索の結果不要となった要素を削除する > > > これが一番簡単と思います。 深さ優先探索(Depth First Search)で良いと思いますよ。 分岐点をスタックに積みながら、探索を進めるイメージです。 ルートAから子をたどる時、ルートをスタックに積みます。 その最初の子Bが葉ならば、スタック先頭の分岐点へ戻り、次の子Cをたどります。 次の子Cが更に子Dを持つなら、Cをスタックに積んでDを辿ります。Cの子全てを検索したらスタックの先頭要素をポップして破棄し、現在のスタック先頭要素の指す分岐へ戻るという感じですね。 意外にスマートに書けますよ。 上記のスタックの代わりにキューを使えば、幅優先探索(Width First Search)も実装できます。 幅優先探索はメモリを多量に消費するので必要ない限りは使わない方が良いです。