0

I have a list of nodes in a big hierarchy. How do I efficiently determine which of my nodes are descendants of any others in my list?

Specifically this is a list of ASP.NET controls. My code examines each of these nodes and their descendants, so I am trying to eliminate redundancy.

A simple example is this tree:

         Parent
         /    \
    Gladis    Arthur
    /    \
 Jon      Sam

My list contains { Parent, Jon }.

I would like to write an algorithm that reduces the list to just Parent based on the fact that the Parent node contains Jon as a descendant.

Here is code:

    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
        }
    }

I can't think of an efficient algorithm to accomplish this. I cannot control the order in which the nodes are added to the list. It seems like it could be optimized by examining both the tree and the relationships I've already identified in the list as I traverse it.

**EDIT: .parent is available in the Node struct. It's easier to discover ancestral relationship using .parent.

4

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 回答