Suche nach toten Knoten aus übergeordneten Kind Knoten Sammlung

Ich habe eine Sammlung von benutzerdefinierten Knoten, die eine übergeordnete Kind-Beziehung hat. Jeder Knoten kann ein zusammengesetzter Typ sein (der ein anderes Kind hat) oder ein einfacher Typ (Knoten auf Blattebene)Suche nach toten Knoten aus übergeordneten Kind Knoten Sammlung

Ich möchte eine Funktion schreiben, die mir eine Liste aller toten Knoten geben wird. Zum Beispiel hier ist die Knoten Sammlung

enter image description here

auf dem obigen Fall Basierend, P2, P3, P8, P9, P10, p6, c1 sind tot Knoten (da unten ihre Hierarchie sie haben keine einfachen Knoten in ihnen)

brauche ich eine Funktion als

private List<NodeEntity> GetDeadNodes(List<NodeEntity> originalList)

Hier kann die Funktion ist für die ursprüngliche Liste hat

private List<NodeEntity> GetOriginalList() 
{ 
    var list = new List<NodeEntity>() 
    { 
     new NodeEntity() {Code = "P1", ParentCode = "001", Type = NodeType.Composite}, 
     new NodeEntity() {Code = "C1", ParentCode = "001", Type = NodeType.Composite}, 
     new NodeEntity() {Code = "P2", ParentCode = "P1", Type = NodeType.Composite}, 
     new NodeEntity() {Code = "P3", ParentCode = "P2", Type = NodeType.Composite}, 
     new NodeEntity() {Code = "P8", ParentCode = "P3", Type = NodeType.Composite}, 
     new NodeEntity() {Code = "P9", ParentCode = "P3", Type = NodeType.Composite}, 
     new NodeEntity() {Code = "P4", ParentCode = "P1", Type = NodeType.Composite}, 
     new NodeEntity() {Code = "L3", ParentCode = "P1", Type = NodeType.Simple}, 
     new NodeEntity() {Code = "P6", ParentCode = "P1", Type = NodeType.Composite}, 
     new NodeEntity() {Code = "P10", ParentCode = "P4", Type = NodeType.Composite}, 
     new NodeEntity() {Code = "L2", ParentCode = "P4", Type = NodeType.Simple}, 
     new NodeEntity() {Code = "P5", ParentCode = "P4", Type = NodeType.Composite}, 
     new NodeEntity() {Code = "L1", ParentCode = "P5", Type = NodeType.Simple} 
    }; 
    return list; 
}

Quelle

2017-08-21 dev1

Sind p1, p4, p6, L3, c1 auf gleichem Niveau? – displayName

Was hast du probiert? Baum plus rekursive Tiefe zuerst suchen? Warteschlange der zu besuchenden Knoten beginnend mit Simple? Etwas? –

sehe meinen Bildanhang. p6, p4, L3 sind Kinder von p1. c1 und p1 sind auf der gleichen Ebene, die Kinder von 001 – dev1

Sie so etwas versuchen.

private List<NodeEntity> GetDeadNodes(List<NodeEntity> originalList) 
    { 
     var rest = originalList.ToList(); 

     // Remove simple nodes and their ascendants. 
     // The rest will be dead nodes. 
     var simpleNodes = originalList.Where(n => n.Type == NodeType.Simple); 
     foreach (var simpleNode in simpleNodes) 
     { 
      rest.Remove(simpleNode); 
      RemoveAscendants(rest, simpleNode); 
     } 

     return rest; 
    } 

    private void RemoveAscendants(List<NodeEntity> rest, NodeEntity node) 
    { 
     var parent = rest.SingleOrDefault(n => n.Code == node.ParentCode); 

     // We have reached the root node. 
     if (parent == null) 
     { 
      return; 
     } 
     rest.Remove(parent); 
     RemoveAscendants(rest, parent); 
    }

Quelle

2017-08-22 10:10:58 polkduran

(i) Warum Rekursion für was ist eine einfache 'while' Schleife verwenden? 'while node! = null {Knoten entfernen; Knoten = Elternknoten finden;} ' (ii) der Kommentar sollte lauten:" Wir haben den Wurzelknoten erreicht ODER der Elternknoten wurde bereits entfernt " –

Sie können einen einfachen scannen den Baum von jedem einfachen Knoten führen alle Knoten zu sammeln zu halten (in Pseudocode):

put Simple nodes in a Set 

while node in Set 
    add node to a 'seen' list 
    add parent to Set 

dead nodes = all nodes except 'seen' nodes

Quelle

2017-08-21 17:01:04

Suche nach toten Knoten aus übergeordneten Kind Knoten Sammlung

Antwort

Verwandte Themen