La clase Arbol en C#

Nov 28, 2010 Codigos C# Tutoriales C# 20 comentarios

Los árboles son una de las estructuras de datos más comunes en la programación de software para almacenar y procesar datos, gracias a sus innumerables aplicaciones. En este post veremos algunas características de los árboles y las implementaciones de algunos métodos y propiedades usando C#.

Informalmente, un árbol es una colección de objetos llamados nodos, de los cuales uno constituye la raíz. Sobre los nodos se define una relación “ser padre” que garantiza la estructura jerárquica entre los nodos. Como se puede apreciar, un hijo de un nodo de un árbol, es también un árbol, por lo que podemos definir un árbol recursivamente como una estructura formada por un nodo raíz r y un conjunto de árboles cuyas raíces son los hijos de r.

arbol La clase Arbol en C#

Algunas definiciones

Un nodo es hoja si no es padre de ningún nodo.
Un árbol que no tenga ningún nodo es un árbol nulo.
Un árbol es ordenado si existe una relación de orden entre los hijos de un nodo.
Un árbol binario es un árbol donde cada nodo tiene como máximo dos hijos. De igual forma podemos definir un árbol k-ario, donde cada nodo tiene a lo sumo k hijos.
Un árbol binario ordenado es un árbol donde cada nodo tiene un hijo izquierdo y un hijo derecho.
Veamos algunos métodos y propiedades que se pueden tener en un árbol:

public void Add(T x); (agrega un objeto al árbol)
public bool Contains(T x); (dice si el árbol contiene el objeto especificado)
public int Widht(); (devuelve el ancho del árbol, o sea el total de hojas)
public int Height(); (devuelve la altura del árbol, que es la mayor distancia desde la raíz a una de la hojas)
public object Value{get;} (devuelve el valor de la raíz del árbol)

Nota: Si no estás familiarizado con la notación “T x” utilizada para clases genéricas, puedes leer aquí sobre genericidad en C#.

Existen varias formas de recorrer un árbol, en dependencia de cómo estén ordenados, los recorridos más comunes son preorden, entreorden, a lo ancho y postorden.

PreOrden: Este recorrido imprime primero los padres y después los hijos en preorden. El algoritmo sería el siguiente:

public void Preorder(Tree t)
{
   foreach (T key in t.Keys)
     //Imprime la llave i-esima
     Console.WriteLine(key);
   foreach (Tree child in t.Childs)
     //Recorrer en preorden el hijo i-esimo
     Preorder(child);
}

El resultado de este recorrido para el árbol de la figura anterior sería A, B, C, D, E, F.

EntreOrden: Primero se imprime el primer hijo izquierdo con su recorrido EntreOrden, después la raíz, y luego el segundo hijo en EntreOrden, y así sucesivamente los restantes hijos. Si el árbol en cuestión es un árbol binario ordenado (ABB) el recorrido sería exactamente una ordenación de los elementos de dicho árbol, ya que hay un orden establecido entre los hijos, pero luego trataremos un post completo sobre los árboles binarios de búsqueda, que tienen algunas aplicaciones y propiedades importantes.

public static void EntreOrden (Tree t)
{
   if (t.Childs.Length>0)
      // Recorre en simétrico el primer hijo
      EntreOrden(t.Childs[0]);
   for (int i = 1; i < t.Childs.Length; i++)
   {
      // Imprime la llave (i-1)-esima
      Console.WriteLine(t.Keys[i - 1]);
      // Recorre en entreorden el hijo i-esimo
      EntreOrden(t.Childs[i]);
   }
}

Para el ejemplo anterior tendríamos el siguiente recorrido: B, A, D, C, E, F
PostOrden: Se recorren primero los hijos y luego los padres en postorden.

public static void PostOrden(Tree t)
{
   foreach (Tree child in t.Childs)
      // Recorre en postorden el hijo i-esimo
      PostOrden(child);
   foreach (T key in t.Keys)
      // Imprime la llave i-esima
      Console.WriteLine(key);
}

El recorrido postorden para el ejemplo sería B, D, E, F, C, A

Por último, le dejo algunos códigos que hice hace algunos años donde pueden ver otros métodos y funcionalidades de la clase árbol (añadir elementos, eliminar, altura, espejo, ancho, recorridos, dibujar arbol,  etc), también añadí la clase árbol binario, que hereda de la clase árbol, y una aplicación de consola donde se prueban varios métodos de estas clases.

Espero que les sirva de ayuda. Si tienen alguna duda con el código, dejen su comentario.

Descargar Código

Compartir:

Relacionados

algunos artículos que te pueden interesar

20 comentarios

Forma parte de nuestra discusión y síguela de cerca

Gracias. Justamente andaba buscando este tipo de código.
Saludos

Autor: xeer | Fecha: Dic 6, 2010.

Me parece un post muy completo y util. Gracias por toda la información.

Autor: Impulsa tu Web | Fecha: Dic 19, 2010.

Muchas gracias! Vienen muy bien los datos! Gracias!

Autor: crear tienda virtual | Fecha: Ene 6, 2011.

gracias por la ayuda, esta interesante.

Autor: melu | Fecha: Ene 7, 2011.

Nos parecen muy interesantes y muy bien explicados tus artículos, te queremos invitar a formar parte de la red social para profesionales del sector IT: Run IT en donde podrás publicar estas notas y contactarte con otros colegas, enterarte de eventos, participar de sorteos y leer otros artículos relacionados al software.
Saludos!

Autor: Run IT | Fecha: Ene 9, 2011.

Me pareció muy interesante ese sitio (Run IT), gracias por la invitación, ya soy parte de la comunidad ;)

Autor: Tomy | Fecha: Ene 12, 2011.

Si!!! Me ha salido tu ejemplo. Muchas gracias por compartir!

Autor: ocasion arval | Fecha: Ene 22, 2011.

No tuve problemas, me función de maravillas. Gracias.

Autor: mercedes de segunda mano | Fecha: Ene 24, 2011.

[...] completamente, es decir, entre sus hijos no hay prioridad. Como vimos en el post anterior con los arboles binarios de búsquedas, donde el hijo izquierdo tenía que ser menor que el padre y este a su vez, menor que el hijo [...]

Autor: Cola con Prioridad. Heap. Implementación y código en C# | puntopeek | Fecha: Ene 31, 2011.

Amigo , muy buena informacion , pero me surge una duda , para generar los arboles como seria?

Autor: edson | Fecha: Sep 21, 2011.

Muchas gracias por este ejemplo, la verdad me ha servido demasiado, y muchísimas gracias por compartir tus conocimientos con la comunidad, Te felicito.

Autor: Juan Felipe | Fecha: Feb 21, 2012.

Hola, soy nuevo en esto de programacion y pues tengo que hacer exactamente lo que tue tienes publicado hacer un arbo buscar y borar ramas u hojas solo tengo la parte de buscar porque no me sale la de elinar hojas no se si podrias decirme como o pasarme un ejemplo que tengas tu para darme una idea y asi realizarlo. Te lo agradeceria mucho

Autor: Jose | Fecha: Mar 8, 2012.

Tendrán algun ejemplo de la estructura de la base de datos sql para guardar los nodos de los integrantes del sistema de ventas binario? y algùn ejm de cómo dibujar el árbol?
Gracias.
jorge.elizondo@gmail.com

Autor: Jorge Elizondo | Fecha: Oct 6, 2012.

¿Cómo dibujar el árbol en web y que sea interactivo?

Autor: Jorge Elizondo | Fecha: Oct 6, 2012.

mmm… ya eso es más complicado, para hacerlo interactivo necesitas programar mucho con Javascript. Puedes usar ASP. Net para poder tener el arbol en C# y llevarlo a la plataforma web.

Autor: Tomy | Fecha: Oct 22, 2012.

para borrar 2 hijos de un arbol

Autor: pedro | Fecha: Nov 22, 2012.

@pedro, parece que se me olvidó el método Eliminar ;) lo incluiré pronto

Autor: Tomy | Fecha: Ene 1, 2013.

xikos muchas gracias x esa ayuda pero me sale una advertencia con la propiedad RUNPOSTBUILDEVENT

Autor: rosita | Fecha: Jun 24, 2013.

Tendrás el de eliminar?
Necesito un poco el de eliminar eh.

Autor: IIoZoII | Fecha: Jul 17, 2013.

descarge el ejemplo pero a la hora de abrirlo me dice que ‘El archivo de solución %s no se puede migrar porque es de solo lectura en el disco’. Intento cambiar los permisos y no existe la opción en la carpeta del ejemplo.

Autor: Jose Castillo | Fecha: Ago 14, 2014.

Escribe tu comentario

Requerido.

Requerido. No público.

Si tienes alguno.