質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

87.93%

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

解決済

回答 3

投稿 編集

  • 評価
  • クリップ 1
  • VIEW 11K+

score 12

 やりたいこと

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

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などでループしながら要素を削除すると、かなり気を使わない要素数が減ったことでとエラーになる)
  • 親→子→孫→…の順に検索を行う必要があるため、この順で要素を作っていくことになるが、「孫を入れるための子オブジェクトを作ったが、孫が0人だったので子オブジェクトが不要になってしまった」として葉要素の無い枝オブジェクトが発生してしまう

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

 さいごに

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

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

よろしくお願いします。

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 3

checkベストアンサー

0

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

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: 二郎
山田一郎
    山田二郎
    田中太郎
        田中二郎

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

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

このような場合はリストのまま検索しようとせず、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;
  }
}

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

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

こんにちは。

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

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

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

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

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 87.93%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る