Estructuras no Lineales - Arboles Binarios

Árboles Binarios

Ilustración 1

 

Introducción: 

El árbol es una estructura de datos muy importante en informática y en ciencias de la computación. Los árboles son estructuras no lineales, al contrario que los arrays y las listas enlazadas, que constituyen estructuras lineales. Los árboles se utilizan para representar fórmulas algebraicas, para organizar objetos en orden de tal forma que las búsquedas sean muy eficientes y en aplicaciones diversas tales como inteligencia artificial o algoritmos de cifrado.

 Casi todos los sistemas operativos almacenan sus archivos en árboles o estructuras similares a árboles. Además de las aplicaciones citadas, los árboles se utilizan en diseño de compiladores, procesado de texto y algoritmos de búsqueda.

 Definición:

Un árbol consta de un conjunto finito de elementos, denominados nodos y de un conjunto finito de líneas dirigidas, denominadas ramas, que conectan los nodos. El número de ramas asociado con un nodo es el grado del nodo.

2da Definición:

Un árbol es un conjunto de uno o más nodos tales que: 1. Hay un nodo diseñado especialmente llamado raíz. 2. Los nodos restantes se dividen en n ≥ 0 conjuntos disjuntos, T1 ... Tn, tal que cada uno de estos conjuntos es un árbol. A T1 ... Tn se les denomina subárboles del raíz.

Representación gráfica de un árbol

 Las formas más frecuentes de representar en papel un árbol son como árbol invertido y como una lista. Representación como árbol invertido Es el diagrama o carta de organización utilizado hasta ahora en las diferentes figuras. El nodo raíz se encuentra en la parte más alta de una jerarquía, de la que descienden ramas que van a parar a los nodos hijos, y así sucesivamente.

Ilustración 2

  Árboles Binarios Complejos

Un árbol binario completo de profundidad n es un árbol en el que para cada nivel, del 0 al nivel n-1, tiene un conjunto lleno de nodos, y todos los nodos hoja a nivel n ocupan las posiciones más a la izquierda del árbol. 


Un árbol binario completo que contiene 2n nodos a nivel n es un árbol lleno. Un árbol lleno es un árbol binario que tiene el máximo número de entradas para su altura. Esto sucede cuando el último nivel está lleno.

Ejemplo : Suponiendo que se tiene n = 10.000 elementos que van a ser los nodos de un árbol binario completo. Determinar la profundidad del árbol.

En el árbol binario completo con n nodos, la profundidad del árbol es el valor entero de log2 n + 1, que es a su vez la distancia del camino más largo desde la raíz a un nodo más uno. 

Profundidad = int (log2 10000) + 1 = int (13.28) + 1 = 14 

Operaciones en árboles binarios 

Algunas de las operaciones típicas que se realizan en árboles binarios son las siguientes:

• Determinar su altura.
  
• Determinar su número de elementos.
  
• Hacer una copia.
  
• Visualizar el árbol binario en pantalla o en impresora.
  
• Determinar si dos árboles binarios son idénticos.
  
• Borrar (eliminar el árbol).
  
• Si es un árbol de expresión, evaluar la expresión. 
  
  Todas estas operaciones se pueden realizar recorriendo el árbol binario de un modo sistemático. El recorrido es la operación de visita al árbol, la visita a cada nodo del árbol una vez y sólo una. La visita de un árbol es necesaria en muchas ocasiones; por ejemplo, si se desea imprimir la información contenida en cada nodo. 
    

Creación de un árbol binario

A partir del nodo raíz de un árbol se puede acceder a los demás nodos del árbol, por ello se mantiene la referencia a la raíz del árbol. Las ramas izquierda y derecha son, a su vez, árboles binarios que tienen su raíz, y así recursivamente hasta llegar a las hojas del árbol. La clase ArbolBinario tiene el campo raiz, un constructor que inicializa raiz y métodos para implementar las operaciones.

Ejemplo de la clase arbol Binario :

Ilustración 3 -Árbol Binario de Cadenas

Un ejemplo de este  tipo de  árboles  se  encuentra  a continuación  con sus capturas  correspondientes  a la compilación y su código fuente:

Impresión de  la  ejecución del programa utilizando el ide Netbeans para ejecutarlo: donde  se  puede  encontrar  todos los  recorridos posibles de un árbol:
 

 

A continuación se  demuestra el código fuente:

public class ArbolBinarioOrdenado {
    class Nodo
      {
        int info;
        Nodo izq, der;
      }
      Nodo raiz;

      public ArbolBinarioOrdenado() {
          raiz=null;
      }
      
      public void insertar (int info)
      {
          Nodo nuevo;
          nuevo = new Nodo ();
          nuevo.info = info;
          nuevo.izq = null;
          nuevo.der = null;
          if (raiz == null)
              raiz = nuevo;
          else
          {
              Nodo anterior = null, reco;
              reco = raiz;
              while (reco != null)
              {
                  anterior = reco;
                  if (info < reco.info)
                      reco = reco.izq;
                  else
                      reco = reco.der;
              }
              if (info < anterior.info)
                  anterior.izq = nuevo;
              else
                  anterior.der = nuevo;
          }
      }


      private void imprimirPre (Nodo reco)
      {
          if (reco != null)
          {
              System.out.print(reco.info + " ");
              imprimirPre (reco.izq);
              imprimirPre (reco.der);
          }
      }

      public void imprimirPre ()
      {
          imprimirPre (raiz);
          System.out.println();
      }

      private void imprimirEntre (Nodo reco)
      {
          if (reco != null)
          {    
              imprimirEntre (reco.izq);
              System.out.print(reco.info + " ");
              imprimirEntre (reco.der);
          }
      }

      public void imprimirEntre ()
      {
          imprimirEntre (raiz);
          System.out.println();
      }


      private void imprimirPost (Nodo reco)
      {
          if (reco != null)
          {
              imprimirPost (reco.izq);
              imprimirPost (reco.der);
              System.out.print(reco.info + " ");
          }
      }


      public void imprimirPost ()
      {
          imprimirPost (raiz);
          System.out.println();
      }

      public static void main (String [] ar)
      {
          ArbolBinarioOrdenado abo = new ArbolBinarioOrdenado ();
          abo.insertar (100);
          abo.insertar (50);
          abo.insertar (25);
          abo.insertar (75);
          abo.insertar (150);
          System.out.println ("Impresion preorden: ");
          abo.imprimirPre ();
          System.out.println ("Impresion entreorden: ");
          abo.imprimirEntre ();
          System.out.println ("Impresion postorden: ");
          abo.imprimirPost ();        
      }      
}