Recorrido por niveles del árbol de búsqueda binaria

El recorrido por niveles del árbol de búsqueda binaria consiste en recorrer nivel por nivel, almacenando los nodos de cada nivel en una cola, y luego realizar operaciones de sacar de la cola (extraer nodos) y poner en la cola (almacenar los nodos del siguiente nivel), logrando así el propósito del recorrido.

Para soportar el recorrido por niveles, se introduce una cola:

  • Si el nodo raíz está vacío, no hay nada que recorrer;

  • Si el nodo raíz no está vacío:

    • Primero, poner el nodo raíz en la cola;

    • Mientras la cola no esté vacía:

      • Extraer el nodo al frente de la cola y recorrerlo;
      • Si el nodo al frente de la cola tiene hijo izquierdo, poner el hijo izquierdo en la cola;
      • Si el nodo al frente de la cola tiene hijo derecho, poner el hijo derecho en la cola;

A continuación se muestran los pasos en orden:

(1)Primero se extrae el nodo raíz y se coloca en la cola

(2)Se extrae 29, los nodos hijos izquierdo y derecho entran en la cola

(3)El 17, que está al frente de la cola, sale de la cola; los nodos hijos 14 y 23 entran en la cola.

(4)31 sale de la cola; los nodos hijos 30 y 43 entran en la cola

(5)Finalmente, todos salen de la cola

Ejemplo de código central:
...
// Recorrido por niveles del árbol de búsqueda binaria
public void levelOrder(){

    // Usamos LinkedList como nuestra cola
    LinkedList<Node> q = new LinkedList<Node>();
    q.add(root);
    while( !q.isEmpty() ){

        Node node = q.remove();

        System.out.println(node.key);

        if( node.left != null )
            q.add( node.left );
        if( node.right != null )
            q.add( node.right );
    }
}
...

Código de ejemplo en Java

Descargar el paquete de código fuente:Download

Código del archivo src/ejemplo/binary/LevelTraverse.java:

package ejemplo.binary;

import java.util.LinkedList;

/**
* Recorrido por niveles
 */

public class LevelTraverse<Key extends Comparable<Key>, Value>{

    // Los nodos del árbol son una clase privada; el mundo exterior no necesita conocer la implementación específica de los nodos del árbol de búsqueda binaria
    private class Node {
        private Key key;
        private Value value;
        private Node left, right;

        public Node(Key key, Value value) {
            this.key = key;
            this.value = value;
            left = right = null;
        }
    }

    private Node root;  // Nodo raíz
    private int count;  // Número de nodos del árbol

    // Constructor, por defecto construye un árbol de búsqueda binaria vacío
    public LevelTraverse() {
        root = null;
        count = 0;
    }

    // Devuelve el número de nodos del árbol de búsqueda binaria
    public int size() {
        return count;
    }

    // Devuelve si el árbol de búsqueda binaria está vacío
    public boolean isEmpty() {
        return count == 0;
    }

    // Inserta un nuevo par de datos (key, value) en el árbol de búsqueda binaria
    public void insert(Key key, Value value){
        root = insert(root, key, value);
    }

    // Comprueba si existe la clave key en el árbol de búsqueda binaria
    public boolean contain(Key key){
        return contain(root, key);
    }

    // Busca en el árbol de búsqueda binaria el valor correspondiente a la clave key. Si este valor no existe, devuelve null
    public Value search(Key key){
        return search( root , key );
    }

    // Recorrido preorden del árbol de búsqueda binaria
    public void preOrder(){
        preOrder(root);
    }

    // Recorrido inorden del árbol de búsqueda binaria
    public void inOrder(){
        inOrder(root);
    }

    // Recorrido postorden del árbol de búsqueda binaria
    public void postOrder(){
        postOrder(root);
    }

    // Recorrido por niveles del árbol de búsqueda binaria
    public void levelOrder(){

        // Usamos LinkedList como nuestra cola
        LinkedList<Node> q = new LinkedList<Node>();
        q.add(root);
        while( !q.isEmpty() ){

            Node node = q.remove();

            System.out.println(node.key);

            if( node.left != null )
                q.add( node.left );
            if( node.right != null )
                q.add( node.right );
        }
    }

    //********************
    //* Funciones auxiliares del árbol de búsqueda binaria
    //********************

    // Inserta el nodo (key, value) en el árbol de búsqueda binaria con raíz node, usando un algoritmo recursivo
    // Devuelve la raíz del árbol de búsqueda binaria después de insertar el nuevo nodo
    private Node insert(Node node, Key key, Value value){

        if( node == null ){
            count ++;
            return new Node(key, value);
        }

        if( key.compareTo(node.key) == 0 )
            node.value = value;
        else if( key.compareTo(node.key) < 0 )
            node.left = insert( node.left , key, value);
        else    // key > node->key
            node.right = insert( node.right, key, value);

        return node;
    }

    // Comprueba si el árbol de búsqueda binaria con raíz node contiene un nodo con clave key, usando un algoritmo recursivo
    private boolean contain(Node node, Key key){

        if( node == null )
            return false;

        if( key.compareTo(node.key) == 0 )
            return true;
        else if( key.compareTo(node.key) < 0 )
            return contain( node.left , key );
        else // key > node->key
            return contain( node.right , key );
    }

    // Busca el value correspondiente a key en el árbol de búsqueda binaria con raíz node, algoritmo recursivo
    // Si el value no existe, devuelve NULL
    private Value search(Node node, Key key){

        if( node == null )
            return null;

        if( key.compareTo(node.key) == 0 )
            return node.value;
        else if( key.compareTo(node.key) < 0 )
            return search( node.left , key );
        else // key > node->key
            return search( node.right, key );
    }

    // Realiza un recorrido preorden en el árbol de búsqueda binaria con raíz node, algoritmo recursivo
    private void preOrder(Node node){

        if( node != null ){
            System.out.println(node.key);
            preOrder(node.left);
            preOrder(node.right);
        }
    }

    // Realiza un recorrido inorden en el árbol de búsqueda binaria con raíz node, algoritmo recursivo
    private void inOrder(Node node){

        if( node != null ){
            inOrder(node.left);
            System.out.println(node.key);
            inOrder(node.right);
        }
    }

    // Realiza un recorrido postorden en el árbol de búsqueda binaria con raíz node, algoritmo recursivo
    private void postOrder(Node node){

        if( node != null ){
            postOrder(node.left);
            postOrder(node.right);
            System.out.println(node.key);
        }
    }
   
}
Otras extensiones