回答編集履歴
1
深さ優先探索について言及
test
CHANGED
|
@@ -1,4 +1,4 @@
|
|
|
1
|
-
このような場合はリストのまま検索しようとせずTreeを最初に構築してから、Treeを
|
|
1
|
+
このような場合はリストのまま検索しようとせず、Treeを最初に構築してから、Treeを深さ優先探索で走査するように検索していくと綺麗に実装できると思います。
|
|
2
2
|
|
|
3
3
|
|
|
4
4
|
|
|
@@ -16,21 +16,29 @@
|
|
|
16
16
|
|
|
17
17
|
|
|
18
18
|
|
|
19
|
-
public class SearchTree
|
|
19
|
+
public class SearchTree
|
|
20
|
+
|
|
20
|
-
|
|
21
|
+
{
|
|
22
|
+
|
|
21
|
-
public static void Main()
|
|
23
|
+
public static void Main()
|
|
24
|
+
|
|
22
|
-
|
|
25
|
+
{
|
|
26
|
+
|
|
23
|
-
var persons = new List<Person>()
|
|
27
|
+
var persons = new List<Person>()
|
|
28
|
+
|
|
24
|
-
|
|
29
|
+
{
|
|
30
|
+
|
|
25
|
-
|
|
31
|
+
new Person("1", null, "山田一郎"),
|
|
26
|
-
|
|
32
|
+
|
|
27
|
-
|
|
33
|
+
new Person("2", "1", "山田二郎"),
|
|
28
|
-
|
|
34
|
+
|
|
29
|
-
|
|
35
|
+
new Person("3", "1", "田中太郎"),
|
|
30
|
-
|
|
36
|
+
|
|
31
|
-
|
|
37
|
+
new Person("4", "3", "田中二郎"),
|
|
32
|
-
|
|
38
|
+
|
|
33
|
-
|
|
39
|
+
new Person("5", "3", "鈴木花子"),
|
|
40
|
+
|
|
41
|
+
};
|
|
34
42
|
|
|
35
43
|
var searcher = new PersonSearcher(persons);
|
|
36
44
|
|
|
@@ -42,13 +50,19 @@
|
|
|
42
50
|
|
|
43
51
|
|
|
44
52
|
|
|
45
|
-
static void ShowPersons(List<Person> persons, string indent = "")
|
|
53
|
+
static void ShowPersons(List<Person> persons, string indent = "")
|
|
54
|
+
|
|
46
|
-
|
|
55
|
+
{
|
|
56
|
+
|
|
47
|
-
foreach (var person in persons)
|
|
57
|
+
foreach (var person in persons)
|
|
58
|
+
|
|
59
|
+
{
|
|
48
60
|
|
|
49
61
|
Console.WriteLine(indent + "- " + person.Name);
|
|
50
62
|
|
|
51
|
-
if (person.Children != null)
|
|
63
|
+
if (person.Children != null)
|
|
64
|
+
|
|
65
|
+
{
|
|
52
66
|
|
|
53
67
|
ShowPersons(person.Children, indent + " ");
|
|
54
68
|
|
|
@@ -62,7 +76,9 @@
|
|
|
62
76
|
|
|
63
77
|
|
|
64
78
|
|
|
65
|
-
class PersonSearcher
|
|
79
|
+
class PersonSearcher
|
|
80
|
+
|
|
81
|
+
{
|
|
66
82
|
|
|
67
83
|
// 親のいないPersonのリスト
|
|
68
84
|
|
|
@@ -74,13 +90,19 @@
|
|
|
74
90
|
|
|
75
91
|
|
|
76
92
|
|
|
77
|
-
public PersonSearcher(List<Person> persons)
|
|
93
|
+
public PersonSearcher(List<Person> persons)
|
|
94
|
+
|
|
95
|
+
{
|
|
78
96
|
|
|
79
97
|
// PersonDictionaryとFoundersの構築
|
|
80
98
|
|
|
81
|
-
foreach (var person in persons)
|
|
99
|
+
foreach (var person in persons)
|
|
100
|
+
|
|
82
|
-
|
|
101
|
+
{
|
|
102
|
+
|
|
83
|
-
if (person.ParentId == null)
|
|
103
|
+
if (person.ParentId == null)
|
|
104
|
+
|
|
105
|
+
{
|
|
84
106
|
|
|
85
107
|
Founders.Add(person);
|
|
86
108
|
|
|
@@ -94,13 +116,19 @@
|
|
|
94
116
|
|
|
95
117
|
// Personのツリーを構築
|
|
96
118
|
|
|
97
|
-
foreach (var person in persons)
|
|
119
|
+
foreach (var person in persons)
|
|
120
|
+
|
|
98
|
-
|
|
121
|
+
{
|
|
122
|
+
|
|
99
|
-
if (person.ParentId != null)
|
|
123
|
+
if (person.ParentId != null)
|
|
124
|
+
|
|
125
|
+
{
|
|
100
126
|
|
|
101
127
|
var parent = PersonDictionary[person.ParentId];
|
|
102
128
|
|
|
103
|
-
if (parent.Children == null)
|
|
129
|
+
if (parent.Children == null)
|
|
130
|
+
|
|
131
|
+
{
|
|
104
132
|
|
|
105
133
|
parent.Children = new List<Person>();
|
|
106
134
|
|
|
@@ -116,7 +144,9 @@
|
|
|
116
144
|
|
|
117
145
|
|
|
118
146
|
|
|
119
|
-
public List<Person> Search(string query)
|
|
147
|
+
public List<Person> Search(string query)
|
|
148
|
+
|
|
149
|
+
{
|
|
120
150
|
|
|
121
151
|
// 親のいないPersonから検索を始める
|
|
122
152
|
|
|
@@ -126,13 +156,19 @@
|
|
|
126
156
|
|
|
127
157
|
|
|
128
158
|
|
|
129
|
-
private List<Person> SearchInternal(List<Person> persons, string query)
|
|
159
|
+
private List<Person> SearchInternal(List<Person> persons, string query)
|
|
160
|
+
|
|
130
|
-
|
|
161
|
+
{
|
|
162
|
+
|
|
131
|
-
return persons.Select(person =>
|
|
163
|
+
return persons.Select(person =>
|
|
164
|
+
|
|
165
|
+
{
|
|
132
166
|
|
|
133
167
|
// 名前に含まれている場合はツリーをそのまま返す
|
|
134
168
|
|
|
135
|
-
if (person.Name.Contains(query))
|
|
169
|
+
if (person.Name.Contains(query))
|
|
170
|
+
|
|
171
|
+
{
|
|
136
172
|
|
|
137
173
|
return person;
|
|
138
174
|
|
|
@@ -140,13 +176,17 @@
|
|
|
140
176
|
|
|
141
177
|
// 子供がいる場合はそれも検索する
|
|
142
178
|
|
|
143
|
-
if (person.Children != null)
|
|
179
|
+
if (person.Children != null)
|
|
180
|
+
|
|
181
|
+
{
|
|
144
182
|
|
|
145
183
|
var newChildren = SearchInternal(person.Children, query);
|
|
146
184
|
|
|
147
185
|
// 検索結果が0ではなければその検索結果を含んだPersonを新規に作る
|
|
148
186
|
|
|
149
|
-
if (newChildren.Count() > 0)
|
|
187
|
+
if (newChildren.Count() > 0)
|
|
188
|
+
|
|
189
|
+
{
|
|
150
190
|
|
|
151
191
|
var newPerson = new Person(person);
|
|
152
192
|
|
|
@@ -180,7 +220,9 @@
|
|
|
180
220
|
|
|
181
221
|
|
|
182
222
|
|
|
183
|
-
public Person(string id, string parentId, string name)
|
|
223
|
+
public Person(string id, string parentId, string name)
|
|
224
|
+
|
|
225
|
+
{
|
|
184
226
|
|
|
185
227
|
Id = id;
|
|
186
228
|
|
|
@@ -192,7 +234,9 @@
|
|
|
192
234
|
|
|
193
235
|
|
|
194
236
|
|
|
195
|
-
public Person(Person person)
|
|
237
|
+
public Person(Person person)
|
|
238
|
+
|
|
239
|
+
{
|
|
196
240
|
|
|
197
241
|
Id = person.Id;
|
|
198
242
|
|