ツリー構造（階層構造）のオブジェクトから要素を検索する方法

Question

やりたいこと

以下の様な、ツリー構造を想定したクラスが存在します。

public class Person {
  public string PersonId { get; set;}
  public string ParentId { get; set;}
  public string PersonName { get; set;}
  public List<Person> Children { get; set;}
}

親となるPersonがあり、親は複数の子を持ち、子はさらに複数の子供を持ち…
という、よくある階層構造となるクラスです。

ツリー構造のオブジェクトの中からツリー構造を保ったまま要素の「検索」をしたいと思っていますが、スッキリとした方法が思い浮かびません。
（汚く効率の悪いロジックなら書けるのですが…）
このような場合の綺麗なロジックの書き方を教えてください。

※ 上に挙げたプロパティの他に必要なものがあれば、追加しても構いません

補足

このPersonクラスのオブジェクトは、最初は階層構造になっておらず単なる一次元のリストの状態です。
これを最終的に、PersonId(自分自身のID)とParentId(親要素のID)を頼りに階層構造となるように組み立てていきます。

検索について

検索を行う際は、以下のような仕組みを想定しています。

• テキストボックスに入力されたキーワードを元に、PersonNameで検索（部分一致）をする
• 検索の結果、ツリーの枝要素にヒットした場合は、その配下の枝・葉の要素はすべて表示する。ヒットした枝より上位の枝要素もすべて表示する。
• 検索の結果、葉要素にヒットした場合は、それより上位の枝要素はすべて表示する
• 葉要素が一つもヒットしなかった枝要素は画面に表示しない（葉のない枝は表示しない）

というものを考えています。
簡単に言えば、「検索結果に関係のあるものだけ表示をする」という、これまたよくありそうなツリー構造の検索の仕組みです。

検索の結果、「表示しない」と判断された要素はツリー構造のオブジェクトから削除されます。（または、ツリーを組み立てるときにそれを含まないようにします）
決して「非表示フラグを立てる」という方法ではありません。（これは仕様として絶対条件です）

例）
以下のようなツリーを例とします。
例えば「太郎」で検索をかけた場合、「田中太郎」にヒットします。
なので、配下の「田中二郎」「鈴木花子」も残ります。
また「田中太郎」より上の「山田一郎」も残ることになります。

「花子」で検索をかけた場合、ツリーに残るのは「山田一郎」「田中太郎」「鈴木花子」になります。

「一郎」で検索をかけた場合は、最上位の枝要素にヒットしているので、「すべて」の人物がツリーに残ったままになります。

同様に、「二郎」で検索をかけると、「鈴木花子」を除くすべての人物がツリーに残ります。

山田一郎 ┓
＿＿＿＿ ┣ 山田二郎
＿＿＿＿ ┗ 田中太郎 ┓
＿＿＿＿＿＿＿＿＿＿ ┣ 田中二郎
＿＿＿＿＿＿＿＿＿＿ ┗ 鈴木花子

（図中のアンダーバーは、位置ずれを起こさないためのスペースの代わりです）

考えた方法

方法としては複数あるかと思います。

• ツリー状に組み立てる前の一次元リストの状態で「検索」を行い、何かしらの処理をしてから組み立てる
• 完成したツリーから、検索の結果不要となった要素を削除する
• 検索の結果必要と判断された要素だけでツリーを構築する

ただし、どれも実現が難しく困っています。

それは、

• 組み立てる前の一次元リストでは、直接ヒットしなかった要素が最終的に必要となるのかどうか組み立てるまで分からない
• 木構造のリストから不要なものを削除するには非常に手間がかかる（foreachなどでループしながら要素を削除すると、かなり気を使わない要素数が減ったことでとエラーになる）
• 親→子→孫→…の順に検索を行う必要があるため、この順で要素を作っていくことになるが、「孫を入れるための子オブジェクトを作ったが、孫が０人だったので子オブジェクトが不要になってしまった」として葉要素の無い枝オブジェクトが発生してしまう

といった問題となるからです。

さいごに

このように、「ツリーに対して検索をかけ、マッチした要素と関連するものだけ表示する」ように実装をする方法が分かりません。
どうにか綺麗に実装をする方法を教えてください。

なるべく外部のライブラリを使用したり（.NETに初めから含まれているものならOK）、巨大なツリー用のクラスを作ったり…ということは避けたいと思っています。
（前者は絶対に認められません。後者は簡易なものであれば良さそうですが。）

よろしくお願いします。

Answer 1

元のリストは壊れてよいようなので試しに書いてみました。
ただのバックトラックです。

Personは提示のまま。探索・ツリー再作成はSearchメソッドの20行くらい。あとは木を質問の形に初期化したり結果出したりしてるだけです。
Childrenを作り直してるので元のPersonは維持されません（結果のPersonだけ残る）
なにもマッチしないとき、nullで表示のところで落ちるかもしれません。

namespace tt46294 {
    class Program {
        public class Person {
            public string PersonId { get; set; }
            public string ParentId { get; set; }
            public string PersonName { get; set; }
            public List<Person> Children { get; set; }
        }


        static void Main(string[] args) {

            var tree = null as Person;
            var result = null as Person;

            tree = InitTree();
            PrintPerson(Search(tree, "花子"), 0, "花子");
            Console.WriteLine();

            tree = InitTree();
            PrintPerson(Search(tree, "一郎"), 0, "一郎");
            Console.WriteLine();


            tree = InitTree();
            PrintPerson(Search(tree, "二郎"), 0, "二郎");
            Console.WriteLine();

            Console.ReadKey();
        }


        private static void PrintPerson(Person p, int depth = 0, string word="") {
            if (depth == 0) Console.WriteLine("Search Word: " + word);
            Console.WriteLine(new String(' ', depth * 4) + p.PersonName);
            foreach(var c in (p.Children??new List<Person>())) {
                PrintPerson(c, depth + 1);
            }
        }

        private static Person InitTree() {
            var root = new Person {
                PersonName = "山田一郎",
                Children = new List<Person> {
                    new Person {
                        PersonName = "山田二郎"
                    },
                    new Person {
                        PersonName = "田中太郎",
                        Children = new List<Person> {
                            new Person {
                                PersonName = "田中二郎"
                            },
                            new Person {
                                PersonName = "鈴木花子"
                            }
                        }
                    }
                }

            };
            return root;
        }


        private static Person Search(Person current, string v) {
            if (current.PersonName.Contains(v)) return current; // 自分がマッチしたら自分と配下はすべて必要
            if (current.Children == null || current.Children.Count ==0) {
                // 自分もマッチしないし、子もいないのでこのインスタンスはいらない
                return null;
            }else {
                // 子を作り直すので自身をコピー。
                var result = new Person();
                result.PersonName = current.PersonName;
                result.PersonId = current.PersonId;
                result.ParentId = current.ParentId;
                result.Children = new List<Person>();
                // 子について探索
                foreach( var c in current.Children) {
                    var childResult = Search(c, v);
                    // 子が返ってきたらそれは必要。
                    if (childResult != null) result.Children.Add(childResult);
                }
                if (result.Children.Count > 0) return result; // 子に必要なものがあった
                return null; // 子も自分も不要
            }
        }
    }
}

結果：

Search Word: 花子
山田一郎
    田中太郎
        鈴木花子

Search Word: 一郎
山田一郎
    山田二郎
    田中太郎
        田中二郎
        鈴木花子

Search Word: 二郎
山田一郎
    山田二郎
    田中太郎
        田中二郎

答えは書かない方針なんだけど、勢いで書いてしまった。

Answer 2

こんにちは。

完成したツリーから、検索の結果不要となった要素を削除する

これが一番簡単と思います。
深さ優先探索(Depth First Search)で良いと思いますよ。

分岐点をスタックに積みながら、探索を進めるイメージです。
ルートAから子をたどる時、ルートをスタックに積みます。
その最初の子Bが葉ならば、スタック先頭の分岐点へ戻り、次の子Cをたどります。
次の子Cが更に子Dを持つなら、Cをスタックに積んでDを辿ります。Cの子全てを検索したらスタックの先頭要素をポップして破棄し、現在のスタック先頭要素の指す分岐へ戻るという感じですね。
意外にスマートに書けますよ。

上記のスタックの代わりにキューを使えば、幅優先探索(Width First Search)も実装できます。
幅優先探索はメモリを多量に消費するので必要ない限りは使わない方が良いです。

Answer 3

このような場合はリストのまま検索しようとせず、Treeを最初に構築してから、Treeを深さ優先探索で走査するように検索していくと綺麗に実装できると思います。

それっぽいサンプルコードを書いてみました。質問にあるコードとPersonのプロパティ名が違うのはPersonクラスのプロパティにPersonと付いているのは冗長だからです。それとPersonにコンストラクタとコピーコンストラクタを追加しています。

using System;
using System.Collections.Generic;
using System.Linq;

public class SearchTree
{
  public static void Main()
  {
    var persons = new List<Person>()
    {
      new Person("1", null, "山田一郎"),
      new Person("2",  "1", "山田二郎"),
      new Person("3",  "1", "田中太郎"),
      new Person("4",  "3", "田中二郎"),
      new Person("5",  "3", "鈴木花子"),
    };
    var searcher = new PersonSearcher(persons);
    var searched = searcher.Search("二郎");
    ShowPersons(searched, "");
  }

  static void ShowPersons(List<Person> persons, string indent = "")
  {
    foreach (var person in persons)
    {
      Console.WriteLine(indent + "- " + person.Name);
      if (person.Children != null)
      {
        ShowPersons(person.Children, indent + "  ");
      }
    }
  }
}

class PersonSearcher
{
  // 親のいないPersonのリスト
  private List<Person> Founders = new List<Person>();
  // Person.IdからPersonを参照するためのディクショナリ
  private Dictionary<String, Person> PersonDictionary = new Dictionary<String, Person>();

  public PersonSearcher(List<Person> persons)
  {
    // PersonDictionaryとFoundersの構築
    foreach (var person in persons)
    {
      if (person.ParentId == null)
      {
        Founders.Add(person);
      }
      PersonDictionary.Add(person.Id, person);
    }

    // Personのツリーを構築
    foreach (var person in persons)
    {
      if (person.ParentId != null)
      {
        var parent = PersonDictionary[person.ParentId];
        if (parent.Children == null)
        {
          parent.Children = new List<Person>();
        }
        parent.Children.Add(person);
      }
    }
  }

  public List<Person> Search(string query)
  {
    // 親のいないPersonから検索を始める
    return SearchInternal(Founders, query);
  }

  private List<Person> SearchInternal(List<Person> persons, string query)
  {
    return persons.Select(person =>
    {
      // 名前に含まれている場合はツリーをそのまま返す
      if (person.Name.Contains(query))
      {
        return person;
      }
      // 子供がいる場合はそれも検索する
      if (person.Children != null)
      {
        var newChildren = SearchInternal(person.Children, query);
        // 検索結果が0ではなければその検索結果を含んだPersonを新規に作る
        if (newChildren.Count() > 0)
        {
          var newPerson = new Person(person);
          newPerson.Children = newChildren;
          return newPerson;
        }
      }
      return null;
    }).Where(person => person != null).ToList();
  }
}

class Person {
  public string Id { get; set;}
  public string ParentId { get; set;}
  public string Name { get; set;}
  public List<Person> Children { get; set;}

  public Person(string id, string parentId, string name)
  {
    Id = id;
    ParentId = parentId;
    Name = name;
  }

  public Person(Person person)
  {
    Id = person.Id;
    ParentId = person.ParentId;
    Name = person.Name;
  }
}

何かコードについて分からないところがあったらコメントしてください。