Un árbol es una estructura no lineal en la que cada nodo puede apuntar a uno o varios nodos.
También se suele dar una definición recursiva: un árbol es una estructura en compuesta por un dato y varios árboles.
Esto son definiciones simples. Pero las características que implican no lo son tanto.
- Nodo hijo: cualquiera de los nodos apuntados por uno de los nodos del árbol. En el ejemplo, 'L' y 'M' son hijos de 'G'.
- Nodo padre: nodo que contiene un puntero al nodo actual. En el ejemplo, el nodo 'A' es padre de 'B', 'C' y 'D'.
En cuanto a la posición dentro del árbol:
- Nodo raíz: nodo que no tiene padre. Este es el nodo que usaremos para referirnos al árbol. En el ejemplo, ese nodo es el 'A'.
- Nodo hoja: nodo que no tiene hijos. En el ejemplo hay varios: 'F', 'H', 'I', 'K', 'L', 'M', 'N' y 'O'.
- Nodo rama: aunque esta definición apenas la usaremos, estos son los nodos que no pertenecen a ninguna de las dos categorías anteriores. En el ejemplo: 'B', 'C', 'D', 'E', 'G' y 'J'.
Tampoco es necesario que todos los nodos hijos de un nodo concreto existan. Es decir, que pueden usarse todos, algunos o ninguno de los punteros de cada nodo.
Un árbol en el que en cada nodo o bien todos o ninguno de los hijos existe, se llama árbol completo.
En una cosa, los árboles se parecen al resto de las estructuras que hemos visto: dado un nodo cualquiera de la estructura, podemos considerarlo como una estructura independiente. Es decir, un nodo cualquiera puede ser considerado como la raíz de un árbol completo.
Existen otros conceptos que definen las características del árbol, en relación a su tamaño:
- Orden: es el número potencial de hijos que puede tener cada elemento de árbol. De este modo, diremos que un árbol en el que cada nodo puede apuntar a otros dos es de orden dos, si puede apuntar a tres será de orden tres, etc.
- Grado: el número de hijos que tiene el elemento con más hijos dentro del árbol. En el árbol del ejemplo, el grado es tres, ya que tanto 'A' como 'D' tienen tres hijos, y no existen elementos con más de tres hijos.
- Nivel: se define para cada elemento del árbol como la distancia a la raíz, medida en nodos. El nivel de la raíz es cero y el de sus hijos uno. Así sucesivamente. En el ejemplo, el nodo 'D' tiene nivel 1, el nodo 'G' tiene nivel 2, y el nodo 'N', nivel 3.
- Altura: la altura de un árbol se define como el nivel del nodo de mayor nivel. Como cada nodo de un árbol puede considerarse a su vez como la raíz de un árbol, también podemos hablar de altura de ramas. El árbol del ejemplo tiene altura 3, la rama 'B' tiene altura 2, la rama 'G' tiene altura 1, la 'H' cero, etc.
Frecuentemente, aunque tampoco es estrictamente necesario, para hacer más fácil moverse a través del árbol, añadiremos un puntero a cada nodo que apunte al nodo padre. De este modo podremos avanzar en dirección a la raíz, y no sólo hacia las hojas.
Es importante conservar siempre el nodo raíz ya que es el nodo a partir del cual se desarrolla el árbol, si perdemos este nodo, perderemos el acceso a todo el árbol.
RECORRIDOS
Esos recorridos dependen en gran medida del tipo y propósito del árbol, pero hay ciertos recorridos que usaremos frecuentemente. Se trata de aquellos recorridos que incluyen todo el árbol.
Hay tres formas de recorrer un árbol completo, y las tres se suelen implementar mediante recursividad. En los tres casos se sigue siempre a partir de cada nodo todas las ramas una por una.
Supongamos que tenemos un árbol de orden tres, y queremos recorrerlo por completo.
Partiremos del nodo raíz:
RecorrerArbol(raiz);
La función RecorrerArbol, aplicando recursividad, será tan sencilla como invocar de nuevo a la función RecorrerArbol para cada una de las ramas:void RecorrerArbol(Arbol a) \{
if(a == NULL) return;
RecorrerArbol(a->rama[0]);
RecorrerArbol(a->rama[1]);
RecorrerArbol(a->rama[2]);
}
Lo que diferencia los distintos métodos de recorrer el árbol no es el sistema de hacerlo, sino el momento que elegimos para procesar el valor de cada nodo con relación a los recorridos de cada una de las ramas.Árbol
Pre-orden
En este tipo de recorrido, el valor del nodo se procesa antes de recorrer las ramas:void PreOrden(Arbol a) \{
if(a == NULL) return;
Procesar(dato);
RecorrerArbol(a->rama[0]);
RecorrerArbol(a->rama[1]);
RecorrerArbol(a->rama[2]);
}
Si seguimos el árbol del ejemplo en pre-orden, y el proceso de los datos es sencillamente mostrarlos por pantalla, obtendremos algo así:A B E K F C G L M D H I J N O
In-orden
En este tipo de recorrido, el valor del nodo se procesa después de recorrer la primera rama y antes de recorrer la última. Esto tiene más sentido en el caso de árboles binarios, y también cuando existen ORDEN-1 datos, en cuyo caso procesaremos cada dato entre el recorrido de cada dos ramas (este es el caso de los árboles-b):void InOrden(Arbol a) \{
if(a == NULL) return;
RecorrerArbol(a->rama[0]);
Procesar(dato);
RecorrerArbol(a->rama[1]);
RecorrerArbol(a->rama[2]);
}
Si seguimos el árbol del ejemplo en in-orden, y el proceso de los datos es sencillamente mostrarlos por pantalla, obtendremos algo así:K E B F A L G M C H D I N J O
Post-orden
En este tipo de recorrido, el valor del nodo se procesa después de recorrer todas las ramas:void PostOrden(Arbol a) \{
if(a == NULL) return;
RecorrerArbol(a->rama[0]);
RecorrerArbol(a->rama[1]);
RecorrerArbol(a->rama[2]);
Procesar(dato);
}
Si seguimos el árbol del ejemplo en post-orden, y el proceso de los datos es sencillamente mostrarlos por pantalla, obtendremos algo así:K E F B L M G C H I N O J D A
ELIMINAR NODOS
El proceso general es muy sencillo en este caso, pero con una importante limitación, sólo podemos borrar nodos hoja:El proceso sería el siguiente:
- Buscar el nodo padre del que queremos eliminar.
- Buscar el puntero del nodo padre que apunta al nodo que queremos borrar.
- Liberar el nodo.
- padre->nodo[i] = NULL;.
El procedimiento es similar al de borrado de un nodo:
- Buscar el nodo padre del que queremos eliminar.
- Buscar el puntero del nodo padre que apunta al nodo que queremos borrar.
- Podar el árbol cuyo padre es nodo.
- padre->nodo[i] = NULL;.
De modo que el orden en que se borrarán los nodos será:
K E F y B
PROGRAMA:
package javaapplication3; import java.awt.*; import java.awt.event.*; import javax.swing.*; import javax.swing.tree.*; import java.util.*; public class SimpleTree { public static void main(String[] args) { JFrame frame = new SimpleTreeFrame(); frame.show(); } } class SimpleTreeFrame extends JFrame { DefaultMutableTreeNode root = new DefaultMutableTreeNode("Mundo"); DefaultMutableTreeNode arge = new DefaultMutableTreeNode("Argentina"); DefaultMutableTreeNode sant = new DefaultMutableTreeNode("Santa Fe"); DefaultMutableTreeNode rafa = new DefaultMutableTreeNode("Rafaela"); DefaultMutableTreeNode rosa = new DefaultMutableTreeNode("Rosario"); DefaultMutableTreeNode safe = new DefaultMutableTreeNode("Santa Fe"); DefaultMutableTreeNode vena = new DefaultMutableTreeNode("Venado Tuerto"); DefaultMutableTreeNode vill = new DefaultMutableTreeNode("Villa Constitucion"); DefaultMutableTreeNode cord = new DefaultMutableTreeNode("Cordoba"); DefaultMutableTreeNode codo = new DefaultMutableTreeNode("Cordoba"); DefaultMutableTreeNode cbro = new DefaultMutableTreeNode("Cura Brochero"); DefaultMutableTreeNode rcua = new DefaultMutableTreeNode("Rio Cuarto"); DefaultMutableTreeNode chac = new DefaultMutableTreeNode("Chaco"); DefaultMutableTreeNode resi = new DefaultMutableTreeNode("Resistencia"); DefaultMutableTreeNode vang = new DefaultMutableTreeNode("Villa Angela"); DefaultMutableTreeNode chil = new DefaultMutableTreeNode("Chile"); DefaultMutableTreeNode regi = new DefaultMutableTreeNode("Region Metropolitana"); DefaultMutableTreeNode schi = new DefaultMutableTreeNode("Santiago de Chile"); public SimpleTreeFrame() { setTitle("SimpleTree"); setSize(300, 200); addWindowListener(new WindowAdapter() { public void windowClosing(WindowEvent e) { System.exit(0); } } ); root.add(arge); // Enlazado de nodos arge.add(sant); // Enlazado de nodos sant.add(rafa); // Enlazado de nodos sant.add(rosa); // Enlazado de nodos sant.add(safe); // Enlazado de nodos sant.add(vena); // Enlazado de nodos sant.add(vill); // Enlazado de nodos arge.add(cord); // Enlazado de nodos cord.add(codo); // Enlazado de nodos cord.add(cbro); // Enlazado de nodos cord.add(rcua); // Enlazado de nodos arge.add(chac); // Enlazado de nodos chac.add(resi); // Enlazado de nodos chac.add(vang); // Enlazado de nodos root.add(chil); // Enlazado de nodos chil.add(regi); // Enlazado de nodos regi.add(schi); // Enlazado de nodos JTree tree = new JTree(root); Container contentPane = getContentPane(); contentPane.add(new JScrollPane(tree)); Enumeration hijos = sant.children(); // Enumeracion de hijos while ( hijos.hasMoreElements() ) // Enumeracion de hijos { // Enumeracion de hijos System.err.println("Hijos de Santa Fe : "+hijos.nextElement()); // Enumeracion de hijos } // Enumeracion de hijos boolean hoja = vena.isLeaf(); // Consulta Hoja System.err.println("Es Venado Tuerto hoja : "+hoja); // Consulta Hoja Enumeration breadth = root.breadthFirstEnumeration(); // Enumeracion Nodos while ( breadth.hasMoreElements() ) // Enumeracion Nodos { // Enumeracion Nodos System.err.println("Breadth First : "+breadth.nextElement()); // Enumeracion Nodos } // Enumeracion Nodos Enumeration depth = root.depthFirstEnumeration(); // Enumeracion Nodos while ( depth.hasMoreElements() ) // Enumeracion Nodos { // Enumeracion Nodos System.err.println("Depth First : "+depth.nextElement()); // Enumeracion Nodos } // Enumeracion Nodos Enumeration preorder = root.preorderEnumeration(); // Enumeracion Nodos while ( preorder.hasMoreElements() ) // Enumeracion Nodos { // Enumeracion Nodos System.err.println("Pre Order : "+preorder.nextElement()); // Enumeracion Nodos } // Enumeracion Nodos Enumeration postorder = root.postorderEnumeration(); // Enumeracion Nodos while ( postorder.hasMoreElements() ) // Enumeracion Nodos { // Enumeracion Nodos System.err.println("Post Order : "+postorder.nextElement()); // Enumeracion Nodos } // Enumeracion Nodos } }
No hay comentarios:
Publicar un comentario