Árbol binario

Introducción

El recorrido de árboles binarios incluye principalmente el recorrido en profundidad y el recorrido en amplitud. El recorrido en profundidad prioriza la visita a todos los nodos de un subárbol, teniendo una característica vertical, mientras que el recorrido en amplitud prioriza la visita a todos los nodos de un mismo nivel, teniendo una característica horizontal.

Recorrido en profundidad

El recorrido en profundidad tiene tres órdenes principales:

• Preorden —— raíz, izquierda, derecha
• Inorden —— izquiedra, raíz, derecha
• Postorden —— izquierda, derecha, raíz

Estos tres órdenes se puedan implementar fácilmente con recursión, pero aquí se enfoca en la implementación no recursiva. Para realizar el recorrido iterativo, se utiliza la característica de pila.

Preorden (C++ no recursivo)

Algoritmo:

1. Insertar el nodo raíz en la pila
2. Visitar el elemento superior de la pila y eliminarlo de la pila
3. Insertar los hijos derecho e izquierdo en la pila, ya que el orden de visita es "raíz, izquierda, derecha", y debido al uso de pila, primero se inserta el hijo derecho y luego el hijo izquierdo
4. Repetir los pasos 2 y 3 hasta que la pila esté vacía

void preOrder(NodoArbol* raiz) {
    stack<NodoArbol*> pila;
    NodoArbol* actual = NULL;
    if(raiz == NULL)
        return;
    pila.push(raiz);   //Insertar la raíz en la pila
    while(!pila.empty()) {
        //Orden de visita "raíz, izquierda, derecha"
        actual = pila.top();
        cout<<""<<actual->dato<<"\n";
        //Eliminar el nodo visitado
        pila.pop();
        //Insertar primero el hijo derecho para visitar primero el hijo izquierdo
        if(actual->hijoDerecho != NULL)
            pila.push(actual->hijoDerecho);
        if(actual->hijoIzquierdo != NULL)
            pila.push(actual->hijoIzquierdo);
    }
}

Inorden (C++ no recursivo)

Algoritmo:

1. Insertar el nodo raíz en la pila
2. Recorrer los hijos izquierdos, insertándolos en la pila hasta que el hijo izquierdo sea nulo
3. Visitar el elemento superior de la pila y eliminarlo de la pila
4. Realizar los pasos 2 y 3 en el subárbol derecho
5. Repetir los pasos 2, 3 y 4 hasta que la pila esté vacía

void inOrder(NodoArbol* raiz) {
    stack<NodoArbol*> pila;
    NodoArbol* actual = NULL;
    if(raiz == NULL)
        return;
    pila.push(raiz);   //Insertar la raíz en la pila
    actual = raiz;
    while(!pila.empty()) {
        //Orden de visita "izquierda, raíz, derecha"
        while(actual) {    //Insertar los hijos izquierdos en la pila
            pila.push(actual);
            actual = actual->hijoIzquierdo;
        }
        //Visitar el nodo más a la izquierda
        actual = pila.top();
        cout<<""<<actual->dato<<"\n";
        pila.pop();
        //Realizar el mismo proceso con el subárbol derecho
        actual = actual->hijoDerecho;
    }
}

Recorrido por niveles

El recorrido por niveles es el mismo que el recorrido en amplitud, requiriendo la característica FIFO de la cola.

Algoritmo:

1. Insertar el nodo raíz en la cola
2. Si la cola no está vacía, extraer un elemento y visitarlo, luego insertar sus hijos izquierdo y derecho en la cola
3. Repetir el paso 2 hasta que la cola esté vacía

void levelOrder(NodoArbol* raiz) {
queue cola;
if(raiz == NULL)
return;
NodoArbol* actual = raiz;
cola.push(raiz);
while(!cola.empty()) {
//Visitar el primer elemento de la cola
actual = cola.front();
cout<dato<<"\n";
cola.pop();
/*Insertar los hijos en la cola*/
if(actual->hijoIzquierdo != NULL)
cola.push(actual->hijoIzquierdo);
if(actual->hijoDerecho != NULL)
cola.push(actual->hijoDerecho);
}
}