La clase Arbol en C#

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.

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