Recorrido y búsqueda de arboles

Recorrido y búsqueda en arboles

Según el libro de T. Parajan nos dice que:

El recorrido de un árbol es el proceso para recorrer (desplazarse a lo largo) un árbol de manera sistemática a fin de que cada vértice se visite y procese exactamente una vez .Hay tres métodos para recorrer un árbol binario a saber recorridos de preorden , de inorden y de posorden.

Según el libro de JOHNSONBAUGH Richard pag. 415 nos dice que :

La búsqueda a lo ancho y la búsqueda a profundidad proporcionan formas de recorrer un arbol , es decir de recorrerlo de manera sistemática de modo que cada vértice sea visitado exactamente una vez.

Recorrido preorden :

Para recorrer un árbol binario no vació en preorden, hay que realizar las siguientes operaciones recursivamente en cada nodo, comenzando con el nodo de raiz:

1.Visite la raíz

2.Atraviese el sub-arbol izquierdo

3.Atraviese el sub-arbol derecho

Preorden: ABDGEHICFJK

Recorrido inorden :

Para recorrer un arbol binario no vació en inorden (simétrico), hay que realizar las siguientes operaciones recursivamente en cada nodo:

1.Atraviese el sub-arbol izquierdo

2.Visite la raíz

3.Atraviese el sub-arbol derecho

Inorden: GDBHEIACJKF

Recorrido posorden :

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

1.Atraviese el sub-arbol izquierdo

2.Atraviese el sub-arbol derecho

3.Visite la raíz

Postorden: GDHIEBKJFCA

Búsqueda en Arboles

Esto implica examinar cada parte del árbol hasta que el vértice o la arista deseada sea encontrada. Podríamos profundizar moviéndonos a un vértice siempre que sea posible o podríamos des plegarnos comprobando todos los vertices en un nivel antes de pasar al siguiente.

Búsqueda en profundidad:

La idea básica de la búsqueda en profundidad es penetrar tan profundamente como sea posible antes de desplegarse a otros vértices .Esto se consigue al tomar el nuevo vértice adyacente al ultimo de los posibles vértices anteriores.

Búsqueda en anchura:

La idea básica de la búsqueda en anchura es desplegarse a tantos vértices como sea posible antes de penetrar en profundidad dentro de un árbol. Esto significa que visitaremos todos los vértices adyacentes a uno dado antes de cambiar de nivel.

Algoritmos de recorridos preorden, inorden y postorden

Arboles en Java: Recorrido Preorden, Inorden y Postorden

El recorrido de árboles refiere al proceso de visitar de una manera sistemática, exactamente una vez, cada nodo en una estructura de datos de árbol (examinando y/o actualizando los datos en los nodos).

Preorden: (raíz, izquierdo, derecho). 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

Inorden: (izquierdo, raíz, derecho). 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

Postorden: (izquierdo, derecho, raíz). 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

En general, la diferencia entre preorden, inorden y postorden es cuándo se recorre la raíz. En los tres, se recorre primero el sub-árbol izquierdo y luego el derecho.

• En preorden, la raíz se recorre antes que los recorridos de los subárboles izquierdo y derecho
• En inorden, la raíz se recorre entre los recorridos de los árboles izquierdo y derecho, y
• En postorden, la raíz se recorre después de los recorridos por el subárbol izquierdo y el derecho

public class NodoArbol
{
    //miembros de acceso
    NodoArbol nodoizquierdo;
    int datos;
    NodoArbol nododerecho;
    
    //iniciar dato y hacer de este nodo un nodo hoja
    public NodoArbol(int datosNodo)
    {
        datos = datosNodo;
        nodoizquierdo = nododerecho = null; //el nodo no tiene hijos
    }
    
    //buscar punto de insercion e inserter nodo nuevo
    public synchronized void insertar(int valorInsertar)
    {
        //insertar en subarbol izquierdo
        if(valorInsertar < datos)
        {
            //insertar en subarbol izquierdo
            if(nodoizquierdo == null)
                nodoizquierdo = new NodoArbol(valorInsertar);
            else    //continua recorriendo subarbol izquierdo
                nodoizquierdo.insertar(valorInsertar);
        }
        
        //insertar nodo derecho
        else if(valorInsertar > datos)
        {
            //insertar nuevo nodoArbol
            if(nododerecho == null)
                nododerecho = new NodoArbol(valorInsertar);
            else
                nododerecho.insertar(valorInsertar);
        }
    } // fin del metodo insertar
}

class Arbol
{
    private NodoArbol raiz;
    
    //construir un arbol vacio
    public Arbol()
    {
        raiz = null;
    }
    
    //insertar un nuevo ndo en el arbol de busqueda binaria
    public synchronized void insertarNodo(int valorInsertar)
    {
        if(raiz == null)
            raiz = new NodoArbol(valorInsertar); //crea nodo raiz
        else
            raiz.insertar(valorInsertar); //llama al metodo insertar        
    }
    
    // EMPIEZA EL RECORRIDO EN PREORDEN
    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
    }
    
    //EMPEZAR RECORRIDO INORDEN
    public synchronized void recorridoInorden()
    {
        ayudanteInorden(raiz);
    }
    
    //meoto recursivo para recorrido inorden
    private void ayudanteInorden( NodoArbol nodo)
    {
        if(nodo == null)
            return;
        
        ayudanteInorden(nodo.nodoizquierdo);
        System.out.print(nodo.datos + " ");
        ayudanteInorden(nodo.nododerecho);
    }
    
    //EMPEZAR RECORRIDO PORORDEN
    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 + " ");
    }
}