0

大きな階層にノードのリストがあります。どのノードがリスト内の他のノードの子孫であるかを効率的に判断するにはどうすればよいですか?

具体的には、これは ASP.NET コントロールのリストです。私のコードはこれらのノードとその子孫のそれぞれを調べるので、冗長性を排除しようとしています。

簡単な例は、次のツリーです。

         Parent
         /    \
    Gladis    Arthur
    /    \
 Jon      Sam

私のリストには が含まれています{ Parent, Jon }。

ノードが子孫として含まれてParentいるという事実に基づいて、リストを削減するアルゴリズムを書きたいと思います。ParentJon

コードは次のとおりです。

    public class Node
    {
        public Node(string name_, params Node[] children_)
        {
            this.children = children_;
        }
        public string name;
        public Node[] children;
    }

    public class NodeAnalysis
    {
        public Node node;
        public Node containingAncestor = null;
    }

    static void Main(string[] args)
    {
        Node jon = new Node("jon");
        Node parent = new Node("parent",
            new Node("Gladis",
                jon,
                new Node("Sam")),
            new Node("Arthur")
        );

        List<NodeAnalysis> results = new List<NodeAnalysis>();
        results.Add(new NodeAnalysis{ node = parent });
        results.Add(new NodeAnalysis{ node = jon });

        foreach (NodeAnalysis item in results)
        {
            // ??? populate item.containingAncestor
        }
    }

これを達成するための効率的なアルゴリズムは思いつきません。ノードがリストに追加される順序を制御できません。ツリーと、リストをたどる際にリストで既に特定した関係の両方を調べることで、最適化できるようです。

**編集:構造体.parentで利用できますNode。を使用すると、祖先の関係を発見しやすくなり.parentます。

4

1 に答える 1

1

1 つのアプローチを次に示します。

public static void RemoveDescendants(IList<Node> list)
{
    for (int index = 0; index < list.Count; index++)
        RemoveDescendants(list[index], list);
}
private static void RemoveDescendants(Node node, IList<Node> list)
{
    foreach (var child in node.children)
    {
        list.Remove(child);
        RemoveDescendants(child, list);
    }
}
于 2012-08-31T19:29:22.113 に答える