回答編集履歴
1
深さ優先探索について言及
answer
CHANGED
|
@@ -1,4 +1,4 @@
|
|
|
1
|
-
このような場合はリストのまま検索しようとせずTreeを最初に構築してから、Treeを
|
|
1
|
+
このような場合はリストのまま検索しようとせず、Treeを最初に構築してから、Treeを深さ優先探索で走査するように検索していくと綺麗に実装できると思います。
|
|
2
2
|
|
|
3
3
|
それっぽいサンプルコードを書いてみました。質問にあるコードと`Person`のプロパティ名が違うのは`Person`クラスのプロパティに`Person`と付いているのは冗長だからです。それと`Person`にコンストラクタとコピーコンストラクタを追加しています。
|
|
4
4
|
|
|
@@ -7,49 +7,63 @@
|
|
|
7
7
|
using System.Collections.Generic;
|
|
8
8
|
using System.Linq;
|
|
9
9
|
|
|
10
|
-
public class SearchTree
|
|
10
|
+
public class SearchTree
|
|
11
|
+
{
|
|
11
|
-
public static void Main()
|
|
12
|
+
public static void Main()
|
|
13
|
+
{
|
|
12
|
-
var persons = new List<Person>()
|
|
14
|
+
var persons = new List<Person>()
|
|
15
|
+
{
|
|
13
|
-
|
|
16
|
+
new Person("1", null, "山田一郎"),
|
|
14
|
-
|
|
17
|
+
new Person("2", "1", "山田二郎"),
|
|
15
|
-
|
|
18
|
+
new Person("3", "1", "田中太郎"),
|
|
16
|
-
|
|
19
|
+
new Person("4", "3", "田中二郎"),
|
|
17
|
-
|
|
20
|
+
new Person("5", "3", "鈴木花子"),
|
|
21
|
+
};
|
|
18
22
|
var searcher = new PersonSearcher(persons);
|
|
19
23
|
var searched = searcher.Search("二郎");
|
|
20
24
|
ShowPersons(searched, "");
|
|
21
25
|
}
|
|
22
26
|
|
|
23
|
-
static void ShowPersons(List<Person> persons, string indent = "")
|
|
27
|
+
static void ShowPersons(List<Person> persons, string indent = "")
|
|
28
|
+
{
|
|
24
|
-
foreach (var person in persons)
|
|
29
|
+
foreach (var person in persons)
|
|
30
|
+
{
|
|
25
31
|
Console.WriteLine(indent + "- " + person.Name);
|
|
26
|
-
if (person.Children != null)
|
|
32
|
+
if (person.Children != null)
|
|
33
|
+
{
|
|
27
34
|
ShowPersons(person.Children, indent + " ");
|
|
28
35
|
}
|
|
29
36
|
}
|
|
30
37
|
}
|
|
31
38
|
}
|
|
32
39
|
|
|
33
|
-
class PersonSearcher
|
|
40
|
+
class PersonSearcher
|
|
41
|
+
{
|
|
34
42
|
// 親のいないPersonのリスト
|
|
35
43
|
private List<Person> Founders = new List<Person>();
|
|
36
44
|
// Person.IdからPersonを参照するためのディクショナリ
|
|
37
45
|
private Dictionary<String, Person> PersonDictionary = new Dictionary<String, Person>();
|
|
38
46
|
|
|
39
|
-
public PersonSearcher(List<Person> persons)
|
|
47
|
+
public PersonSearcher(List<Person> persons)
|
|
48
|
+
{
|
|
40
49
|
// PersonDictionaryとFoundersの構築
|
|
41
|
-
foreach (var person in persons)
|
|
50
|
+
foreach (var person in persons)
|
|
51
|
+
{
|
|
42
|
-
if (person.ParentId == null)
|
|
52
|
+
if (person.ParentId == null)
|
|
53
|
+
{
|
|
43
54
|
Founders.Add(person);
|
|
44
55
|
}
|
|
45
56
|
PersonDictionary.Add(person.Id, person);
|
|
46
57
|
}
|
|
47
58
|
|
|
48
59
|
// Personのツリーを構築
|
|
49
|
-
foreach (var person in persons)
|
|
60
|
+
foreach (var person in persons)
|
|
61
|
+
{
|
|
50
|
-
if (person.ParentId != null)
|
|
62
|
+
if (person.ParentId != null)
|
|
63
|
+
{
|
|
51
64
|
var parent = PersonDictionary[person.ParentId];
|
|
52
|
-
if (parent.Children == null)
|
|
65
|
+
if (parent.Children == null)
|
|
66
|
+
{
|
|
53
67
|
parent.Children = new List<Person>();
|
|
54
68
|
}
|
|
55
69
|
parent.Children.Add(person);
|
|
@@ -57,22 +71,28 @@
|
|
|
57
71
|
}
|
|
58
72
|
}
|
|
59
73
|
|
|
60
|
-
public List<Person> Search(string query)
|
|
74
|
+
public List<Person> Search(string query)
|
|
75
|
+
{
|
|
61
76
|
// 親のいないPersonから検索を始める
|
|
62
77
|
return SearchInternal(Founders, query);
|
|
63
78
|
}
|
|
64
79
|
|
|
65
|
-
private List<Person> SearchInternal(List<Person> persons, string query)
|
|
80
|
+
private List<Person> SearchInternal(List<Person> persons, string query)
|
|
81
|
+
{
|
|
66
|
-
return persons.Select(person =>
|
|
82
|
+
return persons.Select(person =>
|
|
83
|
+
{
|
|
67
84
|
// 名前に含まれている場合はツリーをそのまま返す
|
|
68
|
-
if (person.Name.Contains(query))
|
|
85
|
+
if (person.Name.Contains(query))
|
|
86
|
+
{
|
|
69
87
|
return person;
|
|
70
88
|
}
|
|
71
89
|
// 子供がいる場合はそれも検索する
|
|
72
|
-
if (person.Children != null)
|
|
90
|
+
if (person.Children != null)
|
|
91
|
+
{
|
|
73
92
|
var newChildren = SearchInternal(person.Children, query);
|
|
74
93
|
// 検索結果が0ではなければその検索結果を含んだPersonを新規に作る
|
|
75
|
-
if (newChildren.Count() > 0)
|
|
94
|
+
if (newChildren.Count() > 0)
|
|
95
|
+
{
|
|
76
96
|
var newPerson = new Person(person);
|
|
77
97
|
newPerson.Children = newChildren;
|
|
78
98
|
return newPerson;
|
|
@@ -89,13 +109,15 @@
|
|
|
89
109
|
public string Name { get; set;}
|
|
90
110
|
public List<Person> Children { get; set;}
|
|
91
111
|
|
|
92
|
-
public Person(string id, string parentId, string name)
|
|
112
|
+
public Person(string id, string parentId, string name)
|
|
113
|
+
{
|
|
93
114
|
Id = id;
|
|
94
115
|
ParentId = parentId;
|
|
95
116
|
Name = name;
|
|
96
117
|
}
|
|
97
118
|
|
|
98
|
-
public Person(Person person)
|
|
119
|
+
public Person(Person person)
|
|
120
|
+
{
|
|
99
121
|
Id = person.Id;
|
|
100
122
|
ParentId = person.ParentId;
|
|
101
123
|
Name = person.Name;
|