如何在樹木

Question

我有一個樹狀結構列表數不同的樹如下：

public class TAGNode 
{ 
    public string Val; 
    public string Type = ""; 
    private List<TAGNode> childs; 
    public IList<TAGNode> Childs 
    { 
     get { return childs.AsReadOnly(); } 
    } 

    public TAGNode AddChild(string val) 
    { 
     TAGNode tree = new TAGNode(val); 
     tree.Parent = this; 
     childs.Add(tree); 
     return tree; 
    } 
    public override bool Equals(object obj) 
    { 
     var t = obj as TAGNode; 
     bool eq = Val == t.Val && childs.Count == t.Childs.Count; 
     if (eq) 
     { 
      for (int i = 0; i < childs.Count; i++) 
      { 
       eq &= childs[i].Equals(t.childs[i]); 
      } 
     } 
     return eq; 
    } 

}

我有這樣的樹可以包含重複樹的列表，通過重複我的意思它們具有相同標籤的相同結構。現在我想從這個列表中選擇不同的樹。我試過

 etrees = new List<TAGNode>(); 
     TAGNode test1 = new TAGNode("S"); 
     test1.AddChild("A").AddChild("B"); 
     test1.AddChild("C"); 

     TAGNode test2 = new TAGNode("S"); 
     test2.AddChild("A").AddChild("B"); 
     test2.AddChild("C"); 

     TAGNode test3 = new TAGNode("S"); 
     test3.AddChild("A"); 
     test3.AddChild("B"); 

     etrees.Add(test1); 
     etrees.Add(test2); 
     etrees.Add(test3); 

     var results = etrees.Distinct(); 

     label1.Text = results.Count() + " unique trees"; 

這會返回所有樹的數量（3），而我期望2棵不同的樹！我想也許我應該爲它實施一個合適的Equals函數，但是正如我測試的那樣，它並不關心Equals返回什麼！

Answer 1

我想，也許我應該實現一個合適的Equals函數爲其

正確的。

但正如我測試它不關心什麼Equals返回！

因爲您必須實施匹配GetHashCode！它不需要包含Equals內使用的所有項目，在您的情況下Val可能就足夠了。請記住，您需要的僅僅是返回一個相同的散列碼，以便等於。具有不同哈希碼的項目被認爲是不相等的，並且從未使用Equals進行檢查。

所以這樣的事情應該工作：

public bool Equals(TAGNode other) 
{ 
    if ((object)this == (object)other) return true; 
    if ((object)other == null) return false; 
    return Val == other.Val && childs.SequenceEqual(other.childs); 
} 

public override bool Equals(object obj) => Equals(obj as TAGNode); 

public override int GetHashCode() => Val?.GetHashCode() ?? 0; 

一旦你這樣做，你也可以「標記」您TAGNode爲IEquatable<TAGNode>，讓默認的相等比較直接調用Equals(TAGNode other)超載。

Answer 2

看到https://msdn.microsoft.com/en-us/library/bb348436(v=vs.100).aspx

如果你想返回一些自定義的數據類型的對象序列不同的元素，你必須實現在類的IEquatable泛型接口。下面的代碼示例演示如何在自定義數據類型中實現此接口並提供GetHashCode和Equals方法。

需要impliment IEquatable爲TagNode

Answer 3

請嘗試下面的GetHashCode。我更新了下面的方法以使其更健壯。害怕原創答案可能無法創造獨特的價值。

 private int GetHashCode(TAGNode node) 
     { 
      string hash = node.Val; 
      foreach(TAGNode child in node.childs) 
      { 
       hash += GetHashStr(child); 
      } 
      return hash.GetHashCode();  
     } 
     private string GetHashStr(TAGNode node) 
     { 
      string hash = node.Val; 
      foreach (TAGNode child in node.childs) 
      { 
       hash += ":" + GetHashStr(child); 
      } 
      return hash; 
     }