jueves, 31 de octubre de 2013

Unidad III

Árbol (informática)


Que es?

En ciencias de la informática, un árbol 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.

Mi árbol Genealógico. 


Recorrido de Arboles

Árbol binario
  • Preorden: (raíz, izquierdo, derecho). Para recorrer un árbol binario no vacío en preorden, hay que realizar las siguientes operaciones recursivamente en cada nodo, comenzando con el nodo de raíz:
  1. Visite la raíz
  2. Atraviese el sub-árbol izquierdo
  3. Atraviese el sub-árbol derecho
  • Inorden: (izquierdo, raíz, derecho). Para recorrer un árbol binario no vacío en inorden (simétrico), hay que realizar las siguientes operaciones recursivamente en cada nodo:
  1. Atraviese el sub-árbol izquierdo
  2. Visite la raíz
  3. Atraviese el sub-árbol derecho
  • Postorden: (izquierdo, derecho, raíz). Para recorrer un árbol binario no vacío en postorden, hay que realizar las siguientes operaciones recursivamente en cada nodo:
  1. Atraviese el sub-árbol izquierdo
  2. Atraviese el sub-árbol derecho
  3. Visite la raíz


Programa Ejemplo:


package javaapplication3;

 import java.awt.*;
 import java.awt.event.*;
 import javax.swing.*;
 import javax.swing.tree.*;
 import java.util.*;

/**
 *
 * @author alumno
 */
public class Main {

    /**
     * @param args the command line arguments
     */

   public static void main(String[] args)
    {  JFrame frame = new MainTreeFrame();
       frame.show();
    }
 }
 class MainTreeFrame 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 MainTreeFrame()
    {  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