如何计算树木列表中的不同树木

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

}

我有一个这样的树的列表，其中可以包含重复的树，重复的意思是它们具有相同的结构和相同的标签。现在我想从这个列表中 select 不同的树。我试过了

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

这是 returns 所有树的数量 (3)，而我希望有 2 棵不同的树！我想也许我应该为它实现一个合适的 Equals 函数，但正如我测试的那样，它并不关心什么 Equals returns!

Answer 1

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

如果您想 return 区分某些自定义数据类型的对象序列中的元素，您必须在 class 中实现 IEquatable 通用接口。以下代码示例显示如何在自定义数据类型中实现此接口并提供 GetHashCode 和 Equals 方法。

你需要为 TagNode 实现 IEquatable

Answer 2

I think maybe I should implement a suitable Equals function for it

正确。

but as I tested it doesn't care what Equals returns!

因为你要实现一个匹配GetHashCode！它不需要包括 Equals 中使用的所有项目，在您的情况下 Val 就足够了。请记住，您所需要的只是 return 一个相同的哈希码可能相同的项目。具有不同哈希码的项目被认为是不相等的，并且永远不会用 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;

一旦你这样做了，你也可以 "mark" 你的 TAGNode 作为 IEquatable<TAGNode>，让默认的相等比较器直接调用 Equals(TAGNode other) 重载。

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

如何计算树木列表中的不同树木

How to count distinct trees in a list of trees

c#

linq

tree

equals