Arboles
Un árbol es una estructura no lineal formada por un conjunto de nodos y un conjunto de ramas.
En un árbol existe un nodo especial denominado raíz. Así mismo, un nodo del que sale alguna rama, recibe el nombre de nodo de bifurcación o nodo rama y un nodo que no tiene ramas recibe el nombre de nodo hoja. A continuación se aprecia en la siguiente figura:
Como se aprecia en la figura cada nodo de un árbol es la raíz de algún subárbol contenido en él. El número de ramas de un nodo recibe el nombre de grado del nodo.
El nivel de un nodo respecto al nodo raíz se define diciendo que la raíz tiene el nivel 0 y cualquier otro nodo tiene un nivel igual a la distancia de ese nodo al nodo raíz. El máximo de los niveles se denomina altura del árbol.
Es útil limitar los árboles en el sentido de que cada nodo sea a lo sumo de grado 2. De esta forma cabe distinguir entre subárbol izquierdo y subárbol derecho de un nodo. Los árboles así formados, se llaman árboles binarios.
Árboles binarios
Un árbol binario es un conjunto finito de nodos que consta de un nodo raíz que tiene dos subárboles binarios denominados subárbol izquierdo y subárbol derecho.
El árbol binario es una estructura de datos muy útil cuando el tamaño de la estructura no se conoce, se necesita acceder a sus elementos ordenadamente.
En sí un árbol binario es una colección de objetos, cada uno de los cuales contiene datos o una referncia a su subárbol derecho.
Básicamente se pueden utilizar tres formas para recorrer un árbol binario, preorden, inorden, postorden.
Preorden: R,I,D
Inorden: I,R,D
Postorden: I,D,R
En el orden preorden se recorre de la siguiente manera: raíz, subárbol izquierdo, subárbol derecho.
En el orden inorden se recorre de la siguiente manera: subárbol izquierdo, raíz, subárbol derecho.
En el orden postorden se recorre de la siguiente manera: subárbol izquierdo, subárbol derecho, raíz.
La definición de la clase árbol binario, analizando lo expuesto anteriormente de una variable que simboliza la raíz del árbol y cada nodo del árbol será un objeto de la clase Nodo, por ejemplo:
class arbolbinario
{
public nodo raiz=null; //raíz del árbol
class nodo
{
public double dato;
/*dato es la variable que guarda
el dato contenido en el nodo*/
public nodo izquierdo;
//raíz del subárbol izquierdo
public nodo derecho;
//raíz del subárbol derecho
public nodo(){}
//constructor
}
}
|
Si el árbol está vacío, raíz es igual a null; en otro caso la raíz es una referencia al nodo raíz del árbol y según se puede observar en el ejemplo anterior este nodo tiene 3 atributos: una referencia a los datos, una referencia a su subárbol izquierdo y otra a su subárbol derecho.
Ejemplo:
using System;
namespace ejemplo
{
//definición de la clase NodoArbol
public class NodoArbol
{
// datos miembro de la clase NodoArbol
public NodoArbol nodoIzquierdo;
public NodoArbol nodoDerecho;
public int datos;
//inicializar datos y hacer de este nodo un nodo hoja
public NodoArbol(int datosNodo)
{
datos=datosNodo;
nodoIzquierdo=nodoDerecho=null;
//el nodo no tiene hijos
}
//insertar un nuevo
public void insertar(int valorInsertar)
{
//insertar un subárbolizquierdo
if(valorInsertar < datos)
{
//insertar un nuevo NodoArbol
if(nodoIzquierdo==null)
nodoIzquierdo=new NodoArbol(valorInsertar);
else
//continuar reccorriendo el subárbol izquierdo
nodoIzquierdo.insertar(valorInsertar);
}
//insertar un subárbol derecho
else
if(valorInsertar>datos)
{
//insertar un nuevo NodoArbol
if(nodoDerecho==null)
nodoDerecho=new NodoArbol(valorInsertar);
else
//continuar reccorriendo el subárbol derecho
nodoDerecho.insertar(valorInsertar);
}
}
}
//definición de la clase árbol
public class Arbol:NodoArbol
{
public NodoArbol raiz;
//insertar un nuevo nodo en el árbol de búsqueda binaria
//construir un objeto árbol vacío de enteros
public Arbol()
{
raiz=null;
}
public void insertarNodo(int valorInsertar)
{
if(raiz==null)
raiz=new NodoArbol(valorInsertar);
//se crea el nodo raíz
else
raiz.insertar(valorInsertar);
//llamar al método insertar
}
//empezar el recorrido preorden
public void recorridoPreorden()
{
ayudantePreorden(raiz);
}
//método recursivo para realizar recorrido preorden
public void ayudantePreorden(NodoArbol nodo)
{
if(nodo==null)
return;
Console.WriteLine(nodo.datos +" ");
//mostrar datos del nodo
ayudantePreorden(nodo.nodoIzquierdo);
//recorrer subárbol izquierdo
ayudantePreorden(nodo.nodoDerecho);
//recorrer subárbol derecho
}
//empezar el recorrido inorden
public void recorridoInorden()
{
ayudanteInorden(raiz);
}
//método recursivo para realizar el recorrido inorden
public void ayudanteInorden(NodoArbol nodo)
{
if(nodo==null)
return;
ayudanteInorden(nodoIzquierdo);
//recorrer subárbol izquierdo
Console.WriteLine(nodo.datos+ " ");
//mostrar datos del nodo
ayudanteInorden(nodo.nodoDerecho);
//recorrer subárbol derecho
}
//empezar recorrido postorden
public void recorridoPostorden()
{
ayudantePostorden(raiz);
}
//método recursivo para realizar el recorrido postorden
public void ayudantePostorden(NodoArbol nodo)
{
if(nodo==null)
return;
ayudantePostorden(nodoIzquierdo);
//recorrer subárbol izquierdo
ayudantePostorden(nodo.nodoDerecho);
//recorrer subárbol derecho
Console.WriteLine(nodo.datos+ " ");
//mostrar datos del nodo
}
[STAThread]
static void Main(string[] args)
{
Arbol arbol=new Arbol();
int valor;
Console.WriteLine("Insertar los valores al arbol");
for(int i=0;i<=10;i++)
{
valor=int.Parse(Console.ReadLine());
arbol.insertarNodo(valor);
}
Console.WriteLine("Al recorrer el arbol de manera Preorden es:");
arbol.recorridoPreorden();
Console.WriteLine("Al recorrer el arbol de manera Inorden es:");
arbol.recorridoInorden();
Console.WriteLine("Al recorrer el arbol de manera Postorden es:");
arbol.recorridoPostorden();
}
}
}
Ver Animación de Árboles
|
|