tengo la clase:eliminar duplicados de árbol
class Node
{
public string Name;
public string Address;
public int Id;
public List<Node> Children = new List<Node>;
public Node Parent;
}
para representar un nodo en un árbol.
Ahora me gustaría eliminar los nodos duplicados de un árbol. Tomemos por ejemplo el árbol:
Nota: verde Foo = Foo púrpura
Qué algoritmo me permitirá eliminar los duplicados del árbol con el fin de terminar con:
-------------------------------------------
En orden para determinar que el Foo verde no es igual (! =) al Foo púrpura, supongo que necesito tener otra propiedad que almacene el del nodo u otra propiedad que me permita habilitar la comparación de nodos. Esta es la propiedad Creo que necesito (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;
}
}
}
Si se desea crear el mismo árbol que tengo aquí es el código:
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);
¿qué pasa con los nodos duplicados con diferentes niños? – saj
¿Está garantizado que los nodos padres duplicados también tienen subárboles totalmente duplicados? Edit: Wow @saj pensamos lo mismo al mismo tiempo :) – mellamokb
Si tuviera un Tom rojo con dos hijos y un Tom rojo con tres hijos, ¿cuál sería el resultado de su algoritmo? –