Arboles Binarios

Un árbol binario es un grafo conexo, acíclico y no dirigido tal que el grado de cada vértice no es mayor a 3″, eso significa que tenemos un grafo donde cada nodo puede tener máximo 2 hijos ( o hojas ) y estas hojas no pueden tener como hijos a cualquier otra hoja anterior como podemos ver en la siguiente imagen:

Podemos ver en la imagen como “Raíz” es padre de “Hoja 1″ y “Hoja 2″ y estas a su vez también son la raíz de las “Sub hojas” y se vuelve un proceso recursivo hasta ncantidad de hojas.

¿Para que sirve un árbol binario?

Como todos sabemos un árbol binario es una estructura de datos, y como todas, este sirve para organizar datos para facilitar su manipulación, ya sea el ingreso, borrado o búsqueda de datos, y precisamente una de las principales ventajas de los árboles binarios es la búsqueda, ya que como en muchos algoritmos de búsqueda necesitamos tener la información ordenada y en nuestros árboles binarios precisamente los datos van ingresando de forma ordenada.

Recorridos con los conocidos métodos recursivos:

Inorden

 Para recorrer un árbol binario no vacío en inorden (simétrico), hay que realizar las siguientes operaciones recursivamente en cada nodo:

1.       Atraviese el sub-árbol izquierdo

2.      Visite la raíz

3.      Atraviese el sub-árbol derecho

Codigo:

public synchronized void recorridoInorden()

    {

        ayudanteInorden(raiz);

    }

     

    //metodo recursivo para recorrido inorden

    private void ayudanteInorden( NodoArbol nodo)

    {

        if(nodo == null)

            return;

         

        ayudanteInorden(nodo.nodoizquierdo);

        System.out.print(nodo.datos + " ");

        ayudanteInorden(nodo.nododerecho);

    }

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -  

     

Postorden

Para recorrer un árbol binario no vacío en postorden, hay que realizar las siguientes operaciones recursivamente en cada nodo:

1.       Atraviese el sub-árbol izquierdo

2.      Atraviese el sub-árbol derecho

3.      Visite la raíz

public synchronized void recorridoPosorden()

    {

        ayudantePosorden(raiz);       

    }

     

    //meotod recursivo para recorrido posorden

    private void ayudantePosorden(NodoArbol nodo)

    {

        if( nodo == null )

            return;

         

        ayudantePosorden(nodo.nodoizquierdo);

        ayudantePosorden(nodo.nododerecho);

        System.out.print(nodo.datos + " ");

    }

}

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 

Preorden

Para recorrer un árbol binario no vacío en preorden, hay que realizar las siguientes operaciones recursivamente en cada nodo, comenzando con el nodo de raíz:

1.       Visite la raíz

2.      Atraviese el sub-árbol izquierdo

3.      Atraviese el sub-árbol derecho

Codigo:

public synchronized void recorridoPreorden()

    {

        ayudantePreorden(raiz);

    }

    //meoto recursivo para recorrido en preorden

     

    private void ayudantePreorden(NodoArbol nodo)

    {

        if(nodo == null)

            return;

         

    System.out.print(nodo.datos + " ");     //mostrar datos del nodo

    ayudantePreorden(nodo.nodoizquierdo);   //recorre subarbol izquierdo

    ayudantePreorden(nodo.nododerecho);     //recorre subarbol derecho

    }

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 

Programa de arboles Binarios

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -