从树中删除重复项

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

---

如果你想创建相同的树我在这里是代码:

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