8

私はクラスを持っています：

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

3 に答える 3

2

これをチェックしてください：

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);
于 2012-08-28T15:02:19.997 に答える
0 
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を作成する必要はありません。

于 2012-08-28T15:01:50.047 に答える
0 
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);
}
于 2012-08-28T15:25:00.540 に答える