從樹

Question

刪除重複我有類：

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

爲了表示在樹上的一個節點。

現在我想從樹中刪除重複的節點。就拿樹：

注：綠富=紫色富

什麼算法將使我爲了去除從樹中重複直到結束：

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

按順序以確定綠色Foo不等於（！=）到紫色Foo我想我需要有另一個屬性來存儲他這個節點或其他一些屬性可以讓我能夠比較節點。這是我想我需要的屬性（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; 
      } 
     } 
    } 

---

如果你想創建同一棵樹我這裏是代碼：

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

} 

只要傳遞根源於這個遞歸函數;它會修剪同一級別的所有副本。您不需要創建比較ID。

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