Estructuras de Datos y Algoritmos en Java

Un �rbol es un grupo finito de nodos, donde uno de esos nodos sirve como ra�z y el resto de los nodos se organizan debajo de la ra�z de una forma jer�rquica. Un nodo que referencia un nodo debajo suyo es un nodo padre. De forma similar, un nodo referenciado por un nodo encima de �l, es un nodo hijo. Los nodos sin hijos, son nodos hoja. Un nodo podr�a ser un padre e hijo, o un nodo hijo y un nodo hoja.

Un nodo padre podr�a referenciar tantos hijos como sea necesario. En muchas situaciones, los nodos padre s�lo referencian un m�ximo de dos nodos hijos. Los �rboles basados en dichos nodos son conocidos como arboles binarios. La siguiente figura representa un �rbol binario que almacena siete palabras en orden alfab�tico.

Insertar nodos, borrar nodos, y atravesar los nodos en �rboles binarios o de otros tipos se realiza mediante la recursi�n (vea el cap�tulo siguiente). Por brevedad, no entraremos en los algoritmos recursisvos de inserci�n, borrado y movimiento por los nodos. En su lugar, presentar� el c�digo fuente de una aplicaci�n de contaje de palabras para demostrar la inserci�n y el movimiento por los nodos. Este c�digo utiliza inserci�n de nodos para crear un �rbol binario, donde cada nodo contiene una palabra y un contador de ocurrencias de esa palabra, y muestra estas palabras y contadores en orden alfab�tico mediante una variante del algoritmo de movimiento por �rboles move-left-examine-node-move-right:

// WC.java 

import java.io.*; 

class TreeNode { 
     String word;               // Word being stored. 
     int count = 1;             // Count of words seen in text. 
     TreeNode left;             // Left subtree reference. 
     TreeNode right;            // Right subtree reference. 

     public TreeNode (String word) { 
            this.word = word; 
            left = right = null; 
     } 

     public void insert (String word)  { 
            int status = this.word.compareTo (word); 

            if (status > 0) {    // word argument precedes current word 

                    // If left-most leaf node reached, then insert new node as  
                    // its left-most leaf node. Otherwise, keep searching left. 
                    if (left == null) 
                            left = new TreeNode (word); 
                    else 
                            left.insert (word); 
            } 
            else 
                if (status < 0) {    // word argument follows current word      

                    // If right-most leaf node reached, then insert new node as 
                    // its right-most leaf node. Otherwise, keep searching right. 

                    if (right == null) 
                            right = new TreeNode (word); 
                    else 
                            right.insert (word); 
                } 
                else 
                    this.count++; 
     } 
} 

class WC { 
     public static void main (String [] args) throws IOException  { 
            int ch; 

            TreeNode root = null; 

            // Read each character from standard input until a letter 
            // is read. This letter indicates the start of a word. 

            while ((ch = System.in.read ()) != -1) { 
                 // If character is a letter then start of word detected. 

                 if (Character.isLetter ((char) ch)) { 
                         // Create StringBuffer object to hold word letters. 

                         StringBuffer sb = new StringBuffer (); 

                        // Place first letter character into StringBuffer object. 
                         sb.append ((char) ch); 

                         // Place all subsequent letter characters into StringBuffer 
                         // object. 
                         do { 
                                ch = System.in.read (); 
                                if(Character.isLetter ((char) ch)) 
                                        sb.append((char) ch); 
                                else 
                                        break; 
                         } 
                         while (true); 
                         // Insert word into tree. 
                         if (root == null) 
                                root = new TreeNode (sb.toString ()); 
                         else 
                                 root.insert (sb.toString ()); 
                 } 
            } 
            display (root); 
     } 

     static void display (TreeNode root) { 
            // If either the root node or the current node is null, 
            // signifying that a leaf node has been reached, return. 
            if (root == null) 
                    return; 

            // Display all left-most nodes (i.e., nodes whose words 
            // precede words in the current node). 
            display (root.left); 

            // Display current node's word and count. 
            System.out.println ("Word = " + root.word + ", Count = " + 
                                                    root.count); 

            // Display all right-most nodes (i.e., nodes whose words 
            // follow words in the current node). 
            display (root.right); 
     } 
} 

Como tiene muchos cometarios no explicar� el c�digo. En su lugar le sugiero que juegue con esta aplicaci�n de esta forma: cuente el n�mero de palabras de un fichero, lance una l�nea de comandos que incluya el s�mbolo de redirecci�n <. Por ejemplo, cuente el n�mero de palabras en WC.java lanzando java WC <WC.java. Abajo puede ver un extracto de la salida de este comando:

Word = Character, Count = 2 
Word = Count, Count = 2 
Word = Create, Count = 1 
Word = Display, Count = 3 
Word = IOException, Count = 1 
Word = If, Count = 4 
Word = Insert, Count = 1 
Word = Left, Count = 1 
Word = Otherwise, Count = 2 
Word = Place, Count = 2 
Word = Read, Count = 1 
Word = Right, Count = 1 
Word = String, Count = 4 
Word = StringBuffer, Count = 5 

�Recursi�n

La ciencia de la computaci�n hace tiempo que descubri� que se puede reemplazar a un m�todo que utiliza un bucle para realizar un c�lculo con un m�todo que se llame repetidamente a s� mismo para realizar el mismo c�lculo. El echo de que un m�todo se llame repetidamente a s� mismo se conoce como recursion.

La recursi�n trabaja dividiendo un problema en subproblemas. Un programa llama a un m�todo con uno o m�s par�metros que describen un problema. Si el m�todo detecta que los valores no representan la forma m�s simple del problema, se llama a s� mismo con valores de par�metros modificados que describen un subproblema cercano a esa forma. Esta actividad contin�a hasta que el m�todo detecta la forma m�s simple del problema, en cuyo caso el m�todo simplemente retorna, posiblemente con un valor, si el tipo de retorno del m�todo no es void. La pila de llamadas a m�todo empieza a desbobinarse como una llamada a m�todo anidada para ayudar a completar una evaluaci�n de expresi�n. En alg�n punto, la llamada el m�todo original se completa, y posiblemente se devuelve un valor.

Para entender la recursi�n, consideremos un m�todo que suma todos los enteros desde 1 hasta alg�n l�mite superior:

static int sum (int limit) {
    int total = 0;
    for (int i = 1; i <= limit; i++)
       total += i;
    return total;
}

Este m�todo es correcto porque consigue el objetivo. Despu�s de crear una variable local total e inicializarla a cero, el m�todo usa un bucle for para sumar repetidamente enteros a total desde 1 hasta el valor del par�metro limit. Cuando la suma se completa, sum(int limit) devuelve el total, mediante return total;, a su llamador.

La recursi�n hace posible realizar est� suma haciendo que sum(int limit) se llame repetidamente a s� mismo, como demuestra el siguiente fragmento de c�digo:

static int sum (int limit) {
   if (limit == 1)
       return 1;
   else
       return limit + sum (limit - 1);
}

Para entender como funciona la recursi�n, considere los siguientes ejemplos:

1. sum (1): El m�todo detecta que limit contiene 1 y vuelve.
2. sum (2): Como limit contiene 2, se ejecuta return limit + sum (limit - 1);. Lo que implica que se ejecute return 2 + sum (1);. La llamada a sum (1) devuelve 1, lo que hace que return 2 + sum (1); devuelva 3.
3. sum (3): Como limit contiene 3, se ejecuta return limit + sum (limit - 1);. Esto implica que se ejecute return 3 + sum (2);. La llamada a sum (2) ejecuta return 2 + sum (1);. Luego, sum (1) devuelve 1, lo que hace que sum (2) devuelva 3, y al final return 3 + sum (2); devuelve 6.