85889


C#でツリー(Tree)構造を再帰検索で作成している途中で、自分の親またはさらに上の要素と同じ値にならないように親と子のIDが一致した場合や親と孫のIDが一致した場合など、子から見て親より上の要素に同じIDがないかをチェックしたいと考えています。  
もし、同じIDが存在したら、その時点でツリー構造を打ち切りにしないと、ずっと繰り返し、下記の例ようにツリー構造が終わらなくなるためです。（例は、親と孫が一致した場合）  
このようなケースを防ぎたいのですが、子から見て親、さらに上の要素を知ることはできるでしょうか？  
Tree1  
|-Tree2  
|-Tree1  
|-Tree2  
|-Tree1  
…以降繰り返し


CC BY-SA 4.0
2022-01-23T13:17:21.423
85879
2022-01-24T04:57:49.753
9228
question
c#
ツリー構造を再帰検索で作成している途中で、自分のより上の階層の要素をしることはできますか？


親への参照を持てばいいです。

[code]

    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;
            }
        }
    }
    
[/code]


CC BY-SA 4.0
2022-01-23T18:28:08.630
85889
2022-01-23T18:28:08.630
50741
85879
answer


別の方法です。  
再帰呼出しするメソッドの、引数を利用すると、望みどおりのチェックができると思います。  
以下にイメージ（考え方を伝えるもの）を示します。  
Tree構造のルート要素から、  
現在の要素の親要素までの要素を、  
Listオブジェクトで渡すと、チェックしやすいかと思います。

[code]

    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); // 再帰呼出し
            }
        }
    }
    
[/code]


CC BY-SA 4.0
2022-01-24T04:57:49.753
85894
2022-01-24T04:57:49.753
48481
85879
answer