Arbol (informatica)

Arboles Binarios

    El árbol es una estructura de datos fundamental en la informática, muy utilizada en todos sus campos, por que se adapta a la representación natural de informaciones homogéneas organizadas y de una gran comodidad y rapidez de manipulación.

   

    Las estructuras tipo árbol se usan principalmente para representar datos con una relación jerárquica entre sus elementos, como son árboles genealógicos, tablas, etc.

   La definición de un árbol implica una estructura recursiva. Esto es, la definición del árbol se refiere a otros árboles. Un árbol con ningún nodo es un árbol nulo; no tiene raíz.

TERMINOLOGÍA Y REPRESENTACIÓN DE UN ÁRBOL GENERAL
La representación y terminología de los arboles se realiza con las típicas notaciones de las relaciones familiares en los árboles genealógicos: padre, hijo, hermano, ascendente, descendiente, etc. 


RAIZ: Todos loa árboles que no esta vacíos tienen un único nodo raíz. Todos los demás elementos o nodos derivan o descienden de el. El nodo Raíz no tiene Padre es decir no es hijo de ningún elemento


PADRE: X es padre de Y sí y solo sí el nodo X apunta a Y. También se dice que X es antecesor de Y.

HIJO: X es hijo de Y, sí y solo sí el nodo X es apuntado por Y. También se dice que X es descendiente directo de Y.

HERMANO: Dos nodos serán hermanos si son descendientes directos de un mismo nodo.

HOJA. Se le llama hoja o Terminal a aquellos nodos que no tienen ramificaciones (hijos).

NODO. Son los Vértices o elementos del Árbol.

NODO INTERIOR. Es un nodo que no es raíz ni Terminal.

GRADO. Es el número de descendientes directos de un determinado nodo.

GRADO DEL ARBOL Es el máximo grado de todos los nodos del árbol.

NIVEL. Es el número de arcos que deben ser recorridos para llegar a un determinado nodo. Por definición la raíz tiene nivel 1.

ALTURA. Es el máximo número de niveles de todos los nodos del árbol. Equivale al nivel más alto de los nodos más 1.

PESO. Es el número de nodos terminales del árbol

LONGITUD DE CAMINO. Es el número de arcos que deben ser recorridos para llegar desde la raíz al nodo X. Por definición la raíz tiene longitud de camino 1, y sus descendientes directos longitud de camino 2 y así sucesivamente.

Operaciones de los Arboles Binarios

Una sucesión de nodos del árbol, de forma que entre cada dos nodos consecutivos de la sucesión haya una relación de parentesco, decimos que es un recorrido árbol. Existen dos recorridos típicos para listar los nodos de un árbol: primero en profundidad y primero en anchura. En el primer caso, se listan los nodos expandiendo el hijo actual de cada nodo hasta llegar a una hoja, donde se vuelve al nodo anterior probando por el siguiente hijo y así sucesivamente. En el segundo, por su parte, antes de listar los nodos de nivel n + 1 (a distancia n + 1 aristas de la raíz), se deben haber listado todos los de nivel n. Otros recorridos típicos del árbol son preorden, postorden e inorden:

• El recorrido en preorden, también llamado orden previo consiste en recorrer en primer lugar la raíz y luego cada uno de los hijos en orden previo.
• El recorrido en inorden, también llamado orden simétrico (aunque este nombre sólo cobra significado en los árboles binarios) consiste en recorrer en primer lugar A₁, luego la raíz y luego cada uno de los hijos en orden simétrico.
• El recorrido en postorden, también llamado orden posterior consiste en recorrer en primer lugar cada uno de los hijos en orden posterior y por último la raíz.

Finalmente, puede decirse que esta estructura es una representación del concepto de árbol en teoría de grafos. Un árbol es un grafo conexo y acíclico (ver también teoría de grafos y Glosario en teoría de grafos).


Codigo de Arbol
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);
     }
}

Sintaxis de un arbol en Java