从树中移除重复项

Question

我有一个类：

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

为了表示树中的一个节点。

现在我想从树中删除重复的节点。例如，考虑以下树：

请注意：绿色 Foo != 紫色 Foo

哪个算法能使我从树中删除重复项以最终得到：

为了确定绿色 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;
            }
        }
    }

如果你想创建和我这里相同的树，请使用以下代码：

---

code:

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

- Tono Nam

---

重复节点但具有不同子节点怎么办？ - saj

重复的父节点是否保证也有完全重复的子树？编辑：哇@saj，我们同时想到了同样的事情 :) - mellamokb

如果你有一个带两个孩子的红色汤姆和一个带三个孩子的红色汤姆，你的算法会输出什么？ - Dan Puzey

我不知道如何处理具有不同子节点的重复节点。我猜即使它们不同，也要将它们删除。 - Tono Nam

@TonoNam：如果你在处理自己的数据和自己的规范时都不知道该如何处理，那么我们又该如何弄清楚呢？你希望结果是什么？ - mellamokb

如果两个节点具有相同的compareId，则它们很可能具有相同的子节点。因此，在我的问题中，我不关心是否具有不同的子节点。尽管有一个能够处理这种情况的实现会很好。 - Tono Nam

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

- Andre Calil

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。

- daryal

---

我认为在这里我们应该删除除1以外的所有内容，改为 i = 1 对于（int i = 0; i < nodesToBeremoved.Count; i++） { root.Children.Remove(nodesToBeremoved[i]); } - karen

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

- Tono Nam