C#でツリー(Tree)構造を再帰検索で作成している途中で、自分の親またはさらに上の要素と同じ値にならないように親と子のIDが一致した場合や親と孫のIDが一致した場合など、子から見て親より上の要素に同じIDがないかをチェックしたいと考えています。
もし、同じIDが存在したら、その時点でツリー構造を打ち切りにしないと、ずっと繰り返し、下記の例ようにツリー構造が終わらなくなるためです。(例は、親と孫が一致した場合)
このようなケースを防ぎたいのですが、子から見て親、さらに上の要素を知ることはできるでしょうか?
Tree1
|-Tree2
|-Tree1
|-Tree2
|-Tree1
…以降繰り返し
コメントを追加
|
2 件の回答
親への参照を持てばいいです。
static void Main(string[] args) {
Tree root = new Tree(0);
root.Add(new Tree(1));
root[0].Add(new Tree(2));
root[0][0].Add(new Tree(1)); // エラーになる
}
public class Tree
{
public int Id { get; }
public Tree Parent { get; private set; }
public List<Tree> children = new List<Tree>();
public Tree(int id) {
Id = id;
}
public void Add(Tree tree) {
Tree p = this;
while (p != null) {
if (p.Id == tree.Id) {
throw new Exception();
}
p = p.Parent;
}
tree.Parent = this;
children.Add(tree);
}
public Tree this [int index] {
get {
return children[index];
}
}
public int Count {
get {
return children.Count;
}
}
}
別の方法です。
再帰呼出しするメソッドの、引数を利用すると、望みどおりのチェックができると思います。
以下にイメージ(考え方を伝えるもの)を示します。
Tree構造のルート要素から、
現在の要素の親要素までの要素を、
Listオブジェクトで渡すと、チェックしやすいかと思います。
public class HogeHoge
void recursiveMethod(Element currentElement, List<Element> path = []) {
if(!currentElement.hasChild()) { // 再帰終了判定
return;
}
// ここで循環参照など、pathを利用してチェックする。
path = path.copy();
path.append(currentElement); // pathを追加
for(childElement in currentElement.iterator()) {
this.recursiveMethod(childElement, path); // 再帰呼出し
}
}
}