Hủy bỏ bản sao từ cây

Question

Tôi có lớp:

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

Đại diện một nút trong một cái cây.

Bây giờ tôi sẽ xóa các nút trùng lặp khỏi một cây. Lấy ví dụ cây:

Lưu ý: màu xanh lá cây Foo = tím Foo

thuật toán gì sẽ cho phép tôi để loại bỏ các bản sao từ cây để kết thúc với:

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

Để để xác định rằng Foo màu xanh lá cây không bằng nhau (! =) với màu tím Foo Tôi đoán tôi cần phải có một tài sản khác để lưu trữ ight của nút hoặc một số thuộc tính khác sẽ cho phép tôi cho phép tôi so sánh các nút. Đây là tài sản tôi nghĩ rằng tôi cần (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; 
      } 
     } 
    } 

---

Nếu bạn muốn tạo ra các cây cùng tôi có ở đây là các mã:

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

Xin vui lòng, kiểm tra này:

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

Nó có thể không cần phải nói, vẫn còn. Cách sử dụng:

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

} 

Chỉ cần vượt qua root đến hàm đệ quy này; nó sẽ cắt tất cả các bản sao trong cùng một cấp độ. Bạn không cần tạo Id so sánh.

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