Rimuovere i duplicati da un albero

Question

ho la classe:

class Node 
{ 
    public string Name; 
    public string Address; 
    public int Id; 
    public List<Node> Children = new List<Node>; 
    public Node Parent; 
} 

per rappresentare un nodo in un albero.

Ora mi piacerebbe rimuovere i nodi duplicati da un albero. Prendete per esempio l'albero:

Nota: verde Foo = Foo viola

Che algoritmo mi permetterà di rimuovere i duplicati dal albero per finire con:

-------------------------------------------

In ordine per determinare che il Foo verde non è uguale (! =) a Foo viola Immagino di aver bisogno di un'altra proprietà che memorizza il ight del nodo o qualche altra proprietà che mi consenta di permettermi di confrontare i nodi. Questa è la proprietà Penso di aver bisogno (CompareId):

class Node 
    { 
     public string Name;  
     public string Address; 
     public int Id; 
     public List<Node> Children = new List<Node>(); 
     public Node Parent; 

     public string CompareId // <----------------- Property I need to compare 
     { 
      get 
      { 
       var temp = this.Name + this.Address + this.Id; 

       if (this.Parent == null) 
        return temp; 
       else 
        return temp + this.Parent.CompareId; 
      } 
     } 
    } 

---

Se si desidera creare lo stesso albero che ho qui è il codice:

Node root = new Node() { Name = "Root", Id = 12, Address = "0x0A1F12" }; 

Node tom1 = new Node() { Name = "Tom", Id = 15, Address = "0x0F1A17", Parent=root }; 
root.Children.Add(tom1); 
Node tom2 = new Node() { Name = "Tom", Id = 15, Address = "0x0F1A17", Parent = root }; 
root.Children.Add(tom2); 
Node foo = new Node() { Name = "Foo", Id = 99, Address = "0x4C0012", Parent=root };       
root.Children.Add(foo); 


Node foo1 = new Node() { Name = "Foo", Id = 99, Address = "0x4C0012", Parent = tom1 }; 
tom1.Children.Add(foo1); 
Node foo2 = new Node() { Name = "Foo", Id = 99, Address = "0x4C0012", Parent = tom1 }; 
tom1.Children.Add(foo2); 

Node foo3 = new Node() { Name = "Foo", Id = 99, Address = "0x4C0012", Parent = tom2}; 
tom2.Children.Add(foo3); 
Node foo4 = new Node() { Name = "Foo", Id = 99, Address = "0x4C0012", Parent = tom2}; 
tom2.Children.Add(foo4); 

Node joe1 = new Node() { Name = "Joe", Id = 99, Address = "0x605C2C", Parent = foo }; 
foo.Children.Add(joe1); 
Node joe2 = new Node() { Name = "Joe", Id = 99, Address = "0x605C2C", Parent = foo };                
foo.Children.Add(joe2); 

Answer 1

prega, check this out:

public class Node 
{ 
    public string Name; 
    public string Address; 
    public int Id; 
    public List<Node> Children; 
    public Node Parent; 

    public Node() 
    { 
     this.Children = new List<Node>(); 
    } 

    public string CompareId 
    { 
     get 
     { 
      var temp = string.Concat(this.Name, this.Address, this.Id); 

      if (this.Parent == null) 
       return temp; 
      else 
       return string.Concat(temp, this.Parent.CompareId); 
     } 
    } 

    public override bool Equals(object OtherNode) 
    { 
     if (OtherNode is Node) 
      return this.CompareId.Equals(((Node)OtherNode).CompareId); 
     else 
      return false; 
    } 

    public static Node RemoveDuplicatesFromTree(Node RootNode) 
    { 
     if (RootNode.Children.Count > 0) 
     { 
      List<Node> OldChildrenList = new List<Node>(); 
      OldChildrenList.AddRange(RootNode.Children); 

      foreach (Node CurrentChild in OldChildrenList) 
      { 
       if (RootNode.Children.Any<Node>(x => x.Equals(CurrentChild))) 
       { 
        List<Node> Duplicates = RootNode.Children.Where(x => x.Equals(CurrentChild)).ToList<Node>(); 

        Duplicates.ForEach(x => 
         { 
          CurrentChild.Children = CurrentChild.Children.Union<Node>(x.Children).ToList<Node>(); 
          RootNode.Children.Remove(x); 
         }); 

        RootNode.Children.Add(CurrentChild); 
       } 

       Node.RemoveDuplicatesFromTree(CurrentChild); 
      } 
     } 

     return RootNode; 
    } 
} 

Può essere inutile dirlo, ancora. Uso:

Node.RemoveDuplicatesFromTree(root); 

Answer 2

private void RemoveDuplicatesFromTree(Node root) 
{ 
    List<Node> nodesToBeremoved = new List<Node>(); 
    root.Children.ForEach(p => 
     { 
      if (!nodesToBeremoved.Contains(p)) 
      {       
       nodesToBeremoved.AddRange(root.Children.Where(q => q.Name == p.Name && q != p)); 
      } 
     }); 
    for (int i = 0; i < nodesToBeremoved.Count; i++) 
    { 
     root.Children.Remove(nodesToBeremoved[i]); 
    } 
    if (root.Children != null && root.Children.Count > 0) 
    { 
     root.Children.ForEach(t => this.RemoveDuplicatesFromTree(t)); 
    } 

} 

basta passare il radice a questa funzione ricorsiva; taglierà tutti i duplicati allo stesso livello. Non è necessario creare un ID confronto.

Answer 3

static void RemoveDuplicates(ref Node root) 
{ 
     Dictionary<string, Node> nonDuplicates = new Dictionary<string, Node>(); 

     Action<Node> traverseTree = null; 
     traverseTree = (x) => 
     { 
      var compareId = x.CompareId; 

      if (nonDuplicates.ContainsKey(compareId)) // if there is a duplicate 
      { 
       x.Parent.Children.Remove(x); // remove node 
      } 
      else 
      { 
       nonDuplicates.Add(compareId, x);      
      } 

      // cannot use foreach loop because removing a node will result in exception 

      // keep traversing the tree 
      for (var i = x.Children.Count - 1; i >= 0; i--) 
       traverseTree(x.Children[i]); 


     }; 

     traverseTree(root); 
}