पेड़

Question

से डुप्लिकेट निकालें मैं कक्षा की है।

अब मैं एक पेड़ से डुप्लिकेट नोड्स को हटाना चाहता हूं। उदाहरण के लिए पेड़:

नोट:! हरी फू = बैंगनी फू

क्या एल्गोरिथ्म मुझे क्रम में पेड़ से डुप्लिकेट निकालने के लिए सक्षम हो जाएगा के साथ समाप्त करने के लिए:

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

क्रम में यह निर्धारित करने के लिए कि हरा फू बैंगनी फू के बराबर नहीं है (! =) मुझे लगता है कि मुझे एक और संपत्ति की आवश्यकता है जो उसे स्टोर करे नोड या कुछ अन्य संपत्ति की दृष्टि जो मुझे नोड्स की तुलना करने में सक्षम बनाती है। यह गुण मुझे लगता है कि मैं जरूरत (CompareId) है:

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

कृपया इस बाहर की जाँच:

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

यह अभी भी, कहने की हो सकती है। उपयोग:

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

} 

बस पारित:

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

---

आप एक ही पेड़ मैं यहाँ है बनाना चाहते हैं कोड है इस पुनरावर्ती समारोह के लिए जड़; यह सभी स्तरों पर एक ही स्तर पर ट्रिम कर देगा। आपको तुलना आईडी बनाने की आवश्यकता नहीं है।

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