Estructura de Árbol – Fundamentos de Programación Orientada a Objetos

Son estructuras de datos jerarquizadas, organizadas y dinámicas. Formada por un conjunto de nodos y de punteros que conectan pares de nodos.

Estructura-de-arbol

Definición de Árbol

Los árboles son estructuras de datos jerarquizadas, organizadas y dinámicas. Formada por un conjunto de nodos y un conjunto de punteros que conectan pares de nodos.  

  • Jerárquica porque los componentes están a  distinto nivel.
  • Organizada porque importa la forma en que esté dispuesto el contenido.
  • Dinámica porque su forma, tamaño y contenido pueden variar durante la ejecución.

Al primer nodo se le conoce con el nombre de RAÍZ.

Representación de un Árbol

Características

  • Todo árbol tiene un único nodo raíz. 
  • Todo nodo, excepto la raíz está conectado por medio de un puntero o arista a un único nodo, conocido como nodo padre, que le(s) antecede. 
  • Hay un único camino desde la raíz a cada nodo. El número de punteros que atraviesa es la longitud del camino. 
  • Todo nodo que no tiene más ramificaciones se le conoce como nodo terminal u hoja.
  •  Padre es el antecesor inmediato de un nodo
  •  Hijo, es cualquiera de sus descendientes inmediatos.
  •  Hermano de un nodo, es otro nodo con el mismo padre.
  •  El grado de un nodo cualquiera, es el número de descendientes directos que tenga.
  •  Grado de un Árbol, es el máximo grado de todos los nodos.
  •  Nivel, es el número de punteros o aristas o arcos que deben ser recorridos para llegar a un determinado nodo.
  •  Altura de un árbol, es el máximo número de niveles de todos los nodos del árbol.

Aplicaciones de Árboles

  •  Representación de un árbol genealógico.
  •  Representación de operaciones algebraicas.
  •  Para realizar la administración de directorios como para UNIX, Linux, Windows.
  •  Crear directorio de ficheros, etc.

Árboles Binarios

Son los árboles cuyo grado es 2 como máximo.

Es decir,  un árbol es binario si tiene 0, 1 o 2 hijos

  • (a) es un nodo binario de un solo nodo, por lo tanto A es la raíz en el nivel 0.
  • (b) Árbol binario de 3 nodos. A es la raíz de grado 2 por tener 2 hijos.
  • (c) Árbol binario de 3 nodos. A es la raíz de grado 1, B es de grado 1 por tener 1 hijo. El árbol solo tiene hijos derechos y ningún hijo izquierdo.
  • (d) Árbol binario de 2 nodos. A es la raíz de grado 1, B es de grado 0 por no tener hijos. El árbol solo tiene hijos izquierdos y ningún hijo derecho.
  • (e) Árbol binario de 5 nodos, de longitud 3 con E y D como hojas.

Ejemplo:

Tipo de Árboles Binarios

Los árboles binarios completos o llenos. Cada nodo tiene 2 hijos, así en el nivel 0 (nodo raíz) :

En el nivel cero (2^0) existe un nodo, luego …
En el nivel uno  (2^1) existen dos nodos
En el nivel dos  (2^2) existen cuatro nodos, etc.   
Así por inducción : En el nivel k  hay 2^k  nodos.

Recorrido de un Árbol Binario

Los árboles binarios se pueden recorrer de la siguiente manera:

Pre-Orden (Prefijo):  RID

  • Visitar la raiz    
  • Recorrer todo el sub-arbol izquierdo.    
  • Recorrer todo el sub-arbol derecho.    

En-Orden (Infijo): IRD    

  • Recorrer todo el sub-arbol izquierdo.    
  • Visitar la raiz.    
  • Recorrer todo el sub-arbol derecho.    

Post-Orden (Postfijo): IDR    

  • Recorrer todo el sub-arbol izquierdo.    
  • Recorrer todo el sub-arbol derecho.    
  • Visitar la raíz.

Árboles Binarios de Búsqueda

Un árbol binario de búsqueda también llamado árbol ordenado es aquel donde se cumple que nodos menores que la raíz van a la izquierda y los que son mayores que la raíz van a la derecha. Los nodos insertados en árboles de búsqueda binarios se insertan como hojas.  

Representación de un Árbol Ordenado

Tipos de Árboles Binarios de Búsqueda

Árboles AVL

Un árbol AVL (Adelson-Velskii & Landis) es un árbol binario de búsqueda en el que la altura de los subárboles izquierdo y derecho difiere como máximo en 1.

Montículos

Un árbol binario es un montículo si es completo y cualquier nodo es mayor que sus sucesores (monton  : ‘max’), o menor (montón :‘min’). Sirve para implementar colas con prioridad.

Operaciones Básicas

Las operaciones básicas son:

  1. Inserción de un nuevo nodo al árbol binario (agregar).
  2. Recorrer un árbol binario.
  3. Búsqueda de un Nodo del árbol binario.
  4. Eliminar un Nodo del árbol binario.

Inserción de un Nodo a un Árbol (Agregar)

Se crea un nuevo Nodo Si la raíz está vacía entonces raíz será el nuevo Nodo Si la raíz tiene datos, comparamos, si es menor se va a la izquierda y si es mayor a la derecha siempre y cuando sea una hoja

Recorrido de un Árbol Binario

Para visualizar o consultar los datos almacenados en un árbol se necesita «recorrer» el árbol o «visitar» los nodos del mismo
1) En el «recorrido en profundidad”, tenemos los siguientes métodos:
Pre-Orden (Prefijo) a RID
In-Orden (Infijo) a IRD
Post-Orden (Postfijo) a IDR

2) En el «recorrido en anchura», el proceso se realiza horizontalmente desde la raíz a todos sus hijos, a continuación a los hijos de sus hijos y así sucesivamente hasta que todos los nodos han sido procesados.

Búsqueda de un Árbol Binario

El proceso de búsqueda se hace recorriendo el árbol.

  1. Primero ver si el dato está en la raíz 
  2. Si el dato no está en la raíz, comparar si es menor que la raíz y buscar en la izquierda, sino buscar en la derecha.

Implementación de un Árbol Binario

Implementación de la Clase Nodo

public class Nodo  
{
public String  codigo;
public String  nombre;
public String sueldo ;


public Nodo  izq;
public Nodo  der;


public Nodo(String cod, String nom, String suel) 
        {
codigo  = cod;
nombre = nom;
sueldo  = suel;


Izq = null;
der = null;
       }
}

Implementación de la Clase Árbol


public class Arbol  
{
Nodo raiz ;


public Arbol()  
     {
raiz = null ;
}
}

Algunos Métodos Importantes

public class Arbol  
{
Nodo raiz ;
public int tamaño(Nodo p)  
      {
if(p==null)
return 0;
else
return 1+ tamaño(p.izq) +  tamaño(p.der);
}
public int altura(Nodo p)  
      {
if(p==null)
return -1;
else
return 1+ Math.max( tamaño(p.izq), tamaño(p.der) );
}
}

Método Agregar no Recursivo

Permite agregar un nuevo nodo al árbol

Insertar (Agregar)

public void agregar(String cod, String nom, String suel)  
   {
Nodo aux= null, back = null;
Nodo nuevo = new Nodo(cod, nom, suel);
if(raiz == null)
      raiz = nuevo;
else
     {
          aux = raiz;
          while(aux != null)
             {
  back = aux;
            if(cod.compareTo(aux.codigo)<0)
                 aux = aux.izq;
                  else
                 aux = aux.der;
      }


      if(cod.compareTo(back.codigo)<0)
             back.izq =nuevo;
      else
             back.der= nuevo;
}
}

Método Agregar Recursivo

Permite agregar un nuevo nodo al árbol

Insertar (Agregar)

public Nodo agregar (Nodo p,   String cod, String nom, String suel)
{
     if(p == null)
       p = new Nodo(cod, nom, suel);
     else
       if(cod.compareTo(p.codigo)>0)
  p.der = agregar(p.der, cod, nom, suel);
         else
  p.izq = agregar(p.izq,  cod, nom, suel);
  return p;
}

Implementación de la Clase Árbol: Recorrido de un Árbol ( En Profundidad)

public String enOrden( Nodo p)
   {
       if(p != null)
           return enOrden(p.izq) + info + "n" + enOrden(p.der);
        return "";
   }
   public String preOrden( Nodo p)
   {
       if(p != null)
            return info + "n" + preOrden(p.izq) + preOrden(p.der);
        return "";
   }
   public String postOrden( Nodo p)
   {
       if(p != null)
           return postOrden(p.izq) +  postOrden(p.der)+ info + "n";
        return "";
   }

Contenido relacionado:

Te puede interesar

Deja una respuesta

Tu dirección de correo electrónico no será publicada.