Recorrido en profundidad del árbol de búsqueda binaria

El recorrido del árbol de búsqueda binaria se divide en dos categorías: recorrido en profundidad y recorrido por niveles.

El recorrido en profundidad se divide en tres tipos: recorrido preorden (preorder tree walk), recorrido en orden (inorder tree walk) y recorrido postorden (postorder tree walk), respectivamente:

  • 1. Recorrido preorden:Primero se visita el nodo actual y luego se recorren recursivamente los subárboles izquierdo y derecho.
  • 2. Recorrido en orden: Primero se recorre recursivamente el subárbol izquierdo, luego se visita el propio nodo y, finalmente, se recorre recursivamente el subárbol derecho.
  • 3. Recorrido postorden: Primero se recorren recursivamente los subárboles izquierdo y derecho, y luego se visita el propio nodo.

Diagrama del resultado del recorrido preorden:

Ejemplo de código correspondiente:

...
// Recorrido preorden del árbol de búsqueda binaria con raíz en node, algoritmo recursivo
private void preOrder(Node node){

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

Diagrama del resultado del recorrido en orden:

Ejemplo de código correspondiente:

...
// Recorrido en orden del árbol de búsqueda binaria con raíz en node, algoritmo recursivo
private void inOrder(Node node){

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

Diagrama del resultado del recorrido postorden:

Ejemplo de código correspondiente:

...
// Recorrido postorden del árbol de búsqueda binaria con raíz en node, algoritmo recursivo
private void postOrder(Node node){

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

Código de ejemplo Java

Descarga del paquete de código fuente:Download

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

package ejemplo.binary;

/**
* Recorrido prioritario
 */

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

    // Los nodos del árbol son clases privadas; 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 Traverse() {
        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);
    }

    // Verifica si la clave key existe 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 en orden del árbol de búsqueda binaria
    public void inOrder(){
        inOrder(root);
    }

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

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

    // Inserta el nodo (key, value) en el árbol de búsqueda binaria con raíz en 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;
    }

    // Verifica si el árbol de búsqueda binaria con raíz en 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 en 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 );
    }

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

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

    // Recorrido en orden del árbol de búsqueda binaria con raíz en node, algoritmo recursivo
    private void inOrder(Node node){

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

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

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