ARBOLES

1.1. ¿Cómo utilizar árboles?

1.2. ¿Cómo crear un árbol? árbol binario que presenta una estructura de datos en forma de árbol usada en informática.

Podemos utilizar árboles con la clase JTree, se puede mostrar un árbol de datos. JTree realmente no contiene datos, simplemente es un vista de ellos. Aquí tienes una imagen de un árbol.

Como muestra la figura anterior, JTree muestra los datos verticalmente. Cada fila contiene exactamente un ítem de datos (llamado un nodo). Cada árbol tiene un nodo raíz. Los nodos que no pueden tener hijos se llaman nodos leaf (hoja). En la figura anterior, el aspecto-y-comportamiento marca los nodos hojas con una Flecha.

Los nodos que no sean hojas pueden tener cualquier número de hijos, o incluso no tenerlos. En la figura anterior, el aspecto-y-comportamiento marca los nodos que no son hojas con un carpeta. Normalmente el usuario puede expandir y contraer los nodos que no son hojas -- haciendo que sus hijos sean visibles o invisibles -- pulsando sobre él.

• Para crear un árbol se tiene que crear una raíz que es el nodo principal del cual se van a colocar los demás nodos.

  public Arbol() {
         ...
         top = new DefaultMutableTreeNode("Raíz");
         createNodes(top);
           
     

• Crea un árbol que permite una selección a la vez.

  JTree tree = new JTree(treeModel);
       tree.getSelectionModel().setSelectionMode
           (TreeSelectionModel.SINGLE_TREE_SELECTION);
     

• Se incluye para las hojas la imagen "right.gif"

  DefaultTreeCellRenderer renderer = new DefaultTreeCellRenderer();
       renderer.setLeafIcon(new ImageIcon("./right.gif"));
       tree.setCellRenderer(renderer);
     

• Aquí se se crean los nodos del inicio del programa con sus respectivos programas

  private TreeNode createNodes(DefaultMutableTreeNode top) {
         DefaultMutableTreeNode category = null;
         DefaultMutableTreeNode book = null;
         DefaultMutableTreeNode sub = null;
         category = new DefaultMutableTreeNode("Arboles");
         top.add(category);
         book = new DefaultMutableTreeNode("Nodos");
         top.add(book);
         ....
       
     

  En este momento ya tenemos creado el árbol con sus respectivos nodos.

Árbol binario de búsqueda

Un árbol binario de búsqueda es un tipo particular de

Descripciónárbol binario definido de la siguiente forma:

Un árbol binario de búsqueda de tamaño 9 y profundidad 3, con raíz 8 y hojas 1, 4, 7 y 13

lenguaje de programación. De aquí se deduce que puede haber distintos árboles binarios de búsqueda para un mismo conjunto de elementos.recorrido en inorden proporciona los elementos ordenados de forma ascendente y en que la búsqueda de algún elemento suele ser muy eficiente.subrutina, que puede estar predefinida en el lenguaje de programación, que los compare y pueda establecer una relación de orden entre ellos, es decir, que dados dos elementos sea capaz de reconocer cual es mayor y cual menor. Se habla de clave de un elemento porque en la mayoría de los casos el contenido de los nodos será otro tipo de estructura y es necesario que la comparación se haga sobre algún campo al que se denomina clave.

Un árbol binario de búsqueda (ABB) es un

Todo árbol vacío es un árbol binario de búsqueda.

Un árbol binario no vacío, de raíz R, es un árbol binario de búsqueda si:
• En caso de tener subárbol izquierdo, la raíz R debe ser mayor que el valor máximo
 almacenado en el subárbol izquierdo, y que el subárbol izquierdo sea un árbol binario
 de búsqueda.
• En caso de tener subárbol derecho, la raíz R debe ser menor que el valor mínimo
 almacenado en el subárbol derecho, y que el subárbol derecho sea un árbol binario 
 de búsqueda.

Para una fácil comprensión queda resumido en que es un árbol binario que cumple que el subárbol izquierdo de cualquier nodo (si no está vacío) contiene valores menores que el que contiene dicho nodo, y el subárbol derecho (si no está vacío) contiene valores mayores.
Para estas definiciones se considera que hay una relación de orden establecida entre los elementos de los nodos. Que cierta relación esté definida, o no, depende de cada
La altura h en el peor de los casos siempre el mismo tamaño que el número de elementos disponibles. Y en el mejor de los casos viene dada por la expresión h = ceil(log₂(c + 1)), donde ceil indica redondeo por exceso.
El interés de los árboles binarios de búsqueda (ABB) radica en que su
Dependiendo de las necesidades del usuario que trate con una estructura de este tipo se podrá permitir la igualdad estricta en alguno, en ninguno o en ambos de los subárboles que penden de la raíz. Permitir el uso de la igualdad provoca la aparición de valores dobles y hace la búsqueda más compleja.


Operaciones
Todas las operaciones realizadas sobre árboles binarios de búsqueda están basadas en la comparación de los elementos o clave de los mismos, por lo que es necesaria una

 Búsquedafunción logarítmica. El maximo número de comparaciones que necesitaríamos para saber si un elemento se encuentra en un árbol binario de búsqueda estaría entre [log₂(N+1)] y N, siendo N el número de nodos. La búsqueda de un elemento en un ABB (Árbol Binario de Búsqueda) se puede realizar de dos formas, iterativa o recursiva.

La búsqueda consiste acceder a la raíz del árbol, si el elemento a localizar coincide con éste la búsqueda ha concluido con éxito, si el elemento es menor se busca en el subárbol izquierdo y si es mayor en el derecho. Si se alcanza un nodo hoja y el elemento no ha sido encontrado se supone que no existe en el árbol. Cabe destacar que la búsqueda en este tipo de árboles es muy eficiente, representa una


Inserción
La inserción es similar a la búsqueda y se puede dar una solución tanto iterativa como recursiva. Si tenemos inicialmente como parámetro un árbol vacío se crea un nuevo nodo como único contenido el elemento a insertar. Si no lo está, se comprueba si el elemento dado es menor que la raíz del árbol inicial con lo que se inserta en el subárbol izquierdo y si es mayor se inserta en el subárbol derecho. De esta forma las inserciones se hacen en las hojas.

Evolución de la inserción del elemento "5" en un ABB.

Como en el caso de la búsqueda puede haber varias variantes a la hora de implementar la inserción en el TAD (Tipo Abstracto de Datos), y es la decisión a tomar cuando el elemento (o clave del elemento) a insertar ya se encuentra en el árbol, puede que éste sea modificado o que sea ignorada la inserción. Es obvio que esta operación modifica el ABB perdiendo la versión anterior del mismo.


Borrado
La operación de borrado no es tan sencilla como las de búsqueda e inserción. Existen varios casos a tener en consideración:

• Borrar un nodo sin hijos ó nodo hoja: simplemente se borra y se establece a nulo el apuntador de su padre.

Nodo a eliminar 74

• Borrar un nodo con un subárbol hijo: se borra el nodo y se asigna su subárbol hijo como subárbol de su padre.

Nodo a eliminar 70

• Borrar un nodo con dos subárboles hijo: la solución está en reemplazar el valor del nodo por el de su predecesor o por el de su sucesor en inorden y posteriormente borrar este nodo. Su predecesor en inorden será el nodo más a la derecha de su subárbol izquierdo (mayor nodo del subarbol izquierdo), y su sucesor el nodo más a la izquierda de su subárbol derecho (menor nodo del subarbol derecho). En la siguiente figura se muestra cómo existe la posibilidad de realizar cualquiera de ambos reemplazos:

Recorridos
Se puede hacer un recorrido de un árbol en profundidad o en anchura.
Los recorridos en anchura son por niveles, se realiza horizontalmente desde la raíz a todos los hijos antes de pasar a la descendencia de alguno de los hijos.
El recorrido en profundidad lleva al camino desde la raíz hacia el descendiente más lejano del primer hijo y luego continúa con el siguiente hijo. Como recorridos en profundidad tenemos inorden, preorden y postorden.
Una propiedad de los ABB es que al hacer un recorrido en profundidad inorden obtenemos los elementos ordenados de forma ascendente.

Ejemplo árbol binario de búsqueda

Resultado de hacer el recorrido en:
Inorden = [6, 9, 13, 14, 15, 17, 20, 26, 64, 72].
Preorden = [15, 9, 6, 14, 13, 20, 17, 64, 26, 72].
Postorden =[6, 13, 14, 9, 17, 26, 72, 64, 20, 15].

Se llama recorrido de un árbol al proceso que permite acceder una sola vez a cada uno de los nodos del árbol para examinar el conjunto completo de nodos.

Recorrido en Profundidad: el proceso exige alcanzar las profundidades de un camino desde la raíz hacia el descendiente mas lejano del primer hijo, antes de proseguir con el segundo. Recorrido en Anchura: el proceso se realiza horizontalmente desde la raíz a todos su hijos antes de pasar con la descendencia de alguno de ellos.

Primeramente se ven los algorítmos para construir el árbol sintáctico, para la expresión dada en sufijo, prefijo o posfijo y también se presentan algoritmos para reconocer si una expresión está sintácticamente correcta cuando esta dada en prefijo o posfijo.

Recorridos

Al visitar los nodos de un árbol existen algunas maneras útiles en las que se pueden ordenar sistemáticamente los nodos de un árbol.

Los ordenamientos más importantes son llamados: preorden, post-orden y en-orden y se definen recursivamente como sigue:

Si un árbol T es nulo, entonces, la lista vacía es el listado preorden, post-orden y en-orden del árbol T.

Si T consiste de un sólo nodo n, entonces, n es el listado preorden, post-orden y en-orden del árbol T.

Los algoritmos de recorrido de un árbol binario presentan tres tipos de actividades comunes:

• visitar el nodo raíz

• recorrer el subárbol izquierdo

• recorrer el subárbol derecho

Estas tres acciones llevadas a cabo en distinto orden proporcionan los distintos recorridos del árbol.

Recorrido en PRE-ORDEN:

• Visitar el raíz

• Recorrer el subárbol izquierdo en pre-orden

• Recorrer el subárbol derecho en pre-orden

Recorrido EN-ORDEN

• Recorrer el subárbol izquierdo en en-orden• Visitar el raíz• Recorrer el subárbol derecho en en-orden

Recorrido en POST-ORDEN

• Recorrer el subárbol izquierdo en post-orden

• Recorrer el subárbol derecho en post-orden

• Visitar el raíz

Recorridos

Si T es un árbol con raíz n y subárboles T1, T2, . . . , Tk, entonces, El listado pre-orden de los nodos de T es la raíz n, seguida por los nodos de T1 en pre-orden, después los nodos de T2 en preorden, y así, hasta los nodos de Tk en pre-orden.

El listado post-orden de los nodos de T es los nodos de T1 en postorden, seguidos de los nodos de T2 en post-orden, y así hasta los nodos de Tk en post-orden, todos ellos seguidos de n. El listado en-orden de los nodos de T es los nodos de T1 en-orden, seguidos por n, seguidos por los nodos de T2, . . . , Tk, cada grupo.

Recorreremos el Árbol Siguiente:

“

Recorrido Pre Orden (RID)

El recorrido en Pre Orden del árbol es el siguiente: 15, 6, 4, 10, 20, 17, 22

Recorrido En Orden(IRD)

El recorrido en En Orden del árbol es el siguiente: 4, 6, 10, 15, 17, 20, 22

Recorrido Post Orden(IDR)

El recorrido en Post Orden del árbol es el siguiente: 4, 10, 6, 17, 22, 20, 15

Comparemos Otros Recorridos

Pre Orden (RID) 18, 12, 5, 9, 28, 20, 35

En Orden (IRD) 5, 9, 12, 18, 20, 28, 35

Post Orden (IDR) 9, 5, 12, 20, 35, 28, 18

A+B SUFIJO

+AB PREFIJO

AB+ POSFIJO

El arbol normal

(a+b) * c

*       

  A+b        c

     +               

A b

I pre orden

d entre orden

r pos orden

idr posfijo


     rid Prefijo

     ird sufijo

---

3.7.4 Recorridos en un Árbol

En este tema trataremos las diferentes formas de hacer recorridos de un árbol de una expresión algebraica, con el fin de poder cambiar de manera algorítmica una expresión en sufijo a forma de prefijo o posfijo.

Se llama recorrido de un árbol al proceso que permite acceder una sola vez a cada uno de los elementos del árbol para examinar el conjunto completo. Primeramente se ven los algoritmos para construir el árbol, para la expresión dada en sufijo, prefijo o posfijo y también se presentan algoritmos para reconocer si una expresión está correcta cuando esta dada en prefijo o posfijo.

Recorridos

Al visitar los elementos de un árbol existen algunas maneras útiles en las que se pueden ordenar sistemáticamente. Los ordenamientos más importantes son llamados: prefijo, sufijo y posfijo.

Los algoritmos de recorrido de un árbol presentan tres tipos de actividades:

* visitar el nodo raíz

    * recorrer el subárbol izquierdo

    * recorrer el subárbol derecho

Estas tres acciones llevadas a cabo en distinto orden proporcionan los distintos recorridos del árbol.

Recorrido en PREFIJO:

* Visitar la raíz

    * Recorrer el subárbol izquierdo en prefijo

    * Recorrer el subárbol derecho en prefijo

Recorrido SUFIJO:

* Recorrer el subárbol izquierdo en sufijo

    * Visitar la raíz

    * Recorrer el subárbol derecho en sufijo

Recorrido en POSFIJO:

* Recorrer el subárbol izquierdo en postfijo

    * Recorrer el subárbol derecho en postfijo

    * Visitar la raíz

Autor : Cuevas Flores Ricardo

---

Recorridos de un Arbol

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.

Hay tres manera de recorrer un árbol : en inorden, preorden y postorden. Cada una de ellas tiene una secuencia distinta para analizar el árbol como se puede ver a continuación:

1. INORDEN(Sufijo)

Recorrer el subarbol izquierdo en inorden.

 Examinar la raíz. 

 Recorrer el subarbol derecho en inorden. 

2. PREORDEN(Prefijo)

Examinar la raíz. 

 Recorrer el subárbol izquierdo en preorden. 
 recorrer el subárbol derecho en preorden. 

3. POSTORDEN(Posfijo)

Recorrer el subárbol izquierdo en postorden. 

 Recorrer el subárbol derecho en postorden. 

 Examinar la raíz. 

BOSQUES
representa un conjunto normalmente ordenados de uno o mas arboles generales.


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
   }
}

GRAFOS

Un grafo en el ámbito de las ciencias de la computación es una estructura de datos, en concreto un tipo abstracto de datos (TAD), que consiste en un conjunto de nodos (también llamados vértices) y un conjunto de arcos (aristas) que establecen relaciones entre los nodos. El concepto de grafo TAD desciende directamente del concepto matemático de grafo.
Informalmente se define como G = (V, E), siendo los elementos de V los vértices, y los elementos de E, las aristas (edges en inglés). Formalmente, un grafo, G, se define como un par ordenado, G = (V, E), donde V es un conjunto finito y E es un conjunto que consta de dos elementos de V.


Algunos de los principales tipos de grafos son los que se muestran a continuación:

• Grafo regular: Aquel con el mismo grado en todos los vértices. Si ese grado es k lo llamaremos k-regular.
• 
  

Por ejemplo, el primero de los siguientes grafos es 3-regular, el segundo es 2-regular y el tercero no es regular

• Grafo bipartito: Es aquel con cuyos vértices pueden formarse dos conjuntos disjuntos de modo que no haya adyacencias entre vértices pertenecientes al mismo conjunto
• 
  

Ejemplo.- de los dos grafos siguientes el primero es bipartito y el segundo no lo es

• Grafo completo: Aquel con una arista entre cada par de vértices. Un grafo completo con n vértices se denota Kn.
• Un grafo bipartito regular: se denota Km,n donde m, n es el grado de cada conjunto disjunto de vértices.
• 
  

A continuación ponemos los dibujos de K1,2, K3,3, y K2,5

• Grafo nulo: Se dice que un grafo es nulo cuando los vértices que lo componen no están conectados, esto es, que son vértices aislados.
• 
  
• Grafos Isomorfos: Dos grafos son isomorfos cuando existe una correspondencia biunívoca (uno a uno), entre sus vértices de tal forma que dos de estos quedan unidos por una arista en común.
• 
  
• Grafos Platónicos: Son los Grafos formados por los vértices y aristas de los cinco sólidos regulares (Sólidos Platónicos), a saber, el tetraedro, el cubo, el octaedro, el dodecaedro y el icosaedro.
• 
  

Grafos Eulerianos.

Para definir un camino euleriano es importante definir un camino euleriano primero. Un camino euleriano se define de la manera más sencilla como un camino que contiene todos los arcos del grafo.
Teniendo esto definido podemos hablar de los grafos eulerianos describiéndolos simplemente como aquel grafo que contiene un camino euleriano.
El primer grafo de ellos no contiene caminos eulerianos mientras el segundo contiene al menos uno.

Grafos Conexos.

Un grafo se puede definir como conexo si cualquier vértice V pertenece al conjunto de vértices y es alcanzable por algún otro. Otra definición que dejaría esto más claro sería: "un grafo conexo es un grafo no dirigido de modo que para cualquier par de nodos existe al menos un camino que los une".

Aristas

Son las líneas con las que se unen las aristas de un grafo y con la que se construyen también caminos.
Si la arista carece de dirección se denota indistintamente {a, b} o {b, a}, siendo a y b los vértices que une.
Si {a ,b} es una arista, a los vértices a y b se les llama sus extremos.

• Aristas Adyacentes: Se dice que dos aristas son adyacentes si convergen en el mismo vértice.
• Aristas Paralelas: Se dice que dos aristas son paralelas si vértice inicial y el final son el mismo.
• Aristas Cíclicas: Arista que parte de un vértice para entrar en el mismo.
• Cruce: Son dos aristas que cruzan en un punto.
• 
  
  

Vértices

Son los puntos o nodos con los que esta conformado un grafo. Llamaremos grado de un vértice al número de aristas de las que es extremo. Se dice que un vértice es `par' o `impar' según lo sea su grado.

• Vértices Adyacentes: si tenemos un par de vértices de un grafo (U, V) y si tenemos un arista que los une, entonces U y V son vértices adyacentes y se dice que U es el vértice inicial y V el vértice adyacente.
• Vértice Aislado: Es un vértice de grado cero.
• Vértice Terminal: Es un vértice de grado 1.
• 
  
  

Caminos

Sean x, y " V, se dice que hay un camino en G de x a y si existe una sucesión finita no vacía de aristas {x,v1}, {v1,v2},..., {vn,y}. En este caso

• x e y se llaman los extremos del camino
• El número de aristas del camino se llama la longitud del camino.
• Si los vértices no se repiten el camino se dice propio o simple.
• Si hay un camino no simple entre 2 vértices, también habrá un camino simple entre ellos.
• Cuando los dos extremos de un camino son iguales, el camino se llama circuito o camino cerrado.
• Llamaremos ciclo a un circuito simple
• Un vértice a se dice accesible desde el vértice b si existe un camino entre ellos. Todo vértice es accesible respecto a si mismo