Es una estructura de datos ampliamente usada que imita la forma de un árbol (un conjunto de nodos conectados). Un nodo es la unidad sobre la que se construye el árbol y puede tener cero o más nodos hijos conectados a él. Se dice que un nodo a es padre de un nodo b si existe un enlace desde a hasta b (en ese caso, también decimos que b es hijo de a). Sólo puede haber un único nodo sin padres, que llamaremos raíz. Un nodo que no tiene hijos se conoce como hoja. Los demás nodos (tienen padre y uno o varios hijos) se les conoce como rama.
Formalmente, podemos definir un árbol de la siguiente forma:
- Caso base: un árbol con sólo un nodo (es a la vez raíz del árbol y hoja).
- Un nuevo árbol a partir de un nodo nr y k árboles de raíces con elementos cada uno, puede construirse estableciendo una relación padre-hijo entre nr y cada una de las raíces de los k árboles. El árbol resultante de nodos tiene como raíz el nodo nr, los nodos son los hijos de nr y el conjunto de nodos hoja está formado por la unión de los k conjuntos hojas iniciales. A cada uno de los árboles Ai se les denota ahora subárboles de la raíz.
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 A1, 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 conexoy acíclico (ver también teoría de grafos y Glosario en teoría de grafos).
Arboles Binarios
-Enlazar los hijos de cada nodo en forma horizontal(los hermanos=.
-Relacionar en forma vertical el nodo padre con el lujo que se encuentre con el hijo que se encuentra mas a la izquierda. Ademas, se debe eliminar el vinculo de ese padre con el resto de los hijos.
-Respetar el diagrama resultante aproximadamente 45grados a la izquierda y así se obtendrá un árbol binario correspondiente
Bosque
Representa un conjunto normalmente ordenado de uno o mas arboles generales
Conversión al árbol binario
-Enlazar en forma horizontal las raíces de los distraídos árboles generales.
-Relacionar los lujos de cada nodo(los hermanos) en forma horizontal.
-Enlazar en forma vertical el nodo padre con el hijo que se encuentra más a la izquierda. Además se debe eliminar el vinculo del padre con el resto de los hijos.
-Restar el diagrama resultante aproximadamente 45 grados hacia la izquierda y así obtendrá el árbol binario correspondiente.
package treeframe;
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import javax.swing.tree.*;
import java.util.*;
/**
*
* @author pc132-43
*/
public class NewClass
{
public static void main(String[] args)
{ JFrame NewClass = new SimpleTreeFrame();
NewClass.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