Los árboles-B es que los nodos internos deben tener un número variable de nodos hijo dentro de un rango predefinido. Cuando se inserta o se elimina un dato de la estructura, la cantidad de nodos hijo varía dentro de un nodo. Para que siga manteniéndose el número de nodos dentro del rango predefinido, los nodos internos se juntan o se parten. Dado que se permite un rango variable de nodos hijo, los árboles-B no necesitan rebalancearse tan frecuentemente como los árboles binarios de búsqueda auto-balanceables, pero por otro lado pueden desperdiciar memoria, porque los nodos no permanecen totalmente ocupados. Los límites superior e inferior en el número de nodos hijo son definidos para cada implementación en particular.
Estructura de los nodos
Cada elemento de un nodo interno actúa como un valor separador, que lo divide en subárboles. Por ejemplo, si un nodo interno tiene tres nodos hijo, debe tener dos valores separadores o elementos a1 y a2. Todos los valores del subárbol izquierdo deben ser menores a a1, todos los valores del subárbol del centro deben estar entre a1 y a2, y todos los valores del subárbol derecho deben ser mayores a a2.
Los nodos internos de un árbol B, es decir los nodos que no son hoja, usualmente se representan como un conjunto ordenado de elementos y punteros a los hijos. Cada nodo interno contiene un máximo de U hijos y, con excepción del nodo raíz, un mínimo de L hijos. Para todos los nodos internos exceptuando la raíz, el número de elementos es uno menos que el número de punteros a nodos. El número de elementos se encuentra entre L-1 y U-1. El número U debe ser 2L o 2L-1, es decir, cada nodo interno está por lo menos a medio llenar. Esta relación entre U y L implica que dos nodos que están a medio llenar pueden juntarse para formar un nodo legal, y un nodo lleno puede dividirse en dos nodos legales (si es que hay lugar para subir un elemento al nodo padre). Estas propiedades hacen posible que el árbol B se ajuste para preservar sus propiedades ante la inserción y eliminación de elementos.
Operaciones
Búsqueda
La búsqueda es similar a la de los árboles binarios. Se empieza en la raíz, y se recorre el árbol hacia abajo, escogiendo el sub-nodo de acuerdo a la posición relativa del valor buscado respecto a los valores de cada nodo. Típicamente se utiliza la búsqueda binaria para determinar esta posición relativa.
Procedimiento
1 Situarse en el nodo raíz.
2 Comprobar si contiene la clave a buscar.
1. . Encontrada fin de procedimiento .
2. . No encontrada:
---------1. . La clave a buscar k <> ki y k < style="font-weight: bold;">Inserción
Todas las inserciones se hacen en los nodos hoja.
1. Realizando una búsqueda en el árbol, se halla el nodo hoja en el cual debería ubicarse el nuevo elemento.
2. Si el nodo hoja tiene menos elementos que el máximo número de elementos legales, entonces hay lugar para uno más. Inserte el nuevo elemento en el nodo, respetando el orden de los elementos.
3. De otra forma, el nodo debe ser dividido en dos nodos. La división se realiza de la siguiente manera:
---1. Se escoge el valor medio entre los elementos del nodo y el nuevo elemento.
---2. Los valores menores que el valor medio se colocan en el nuevo nodo izquierdo, y los valores mayores que el valor medio se colocan en el nuevo nodo derecho; el valor medio actúa como valor separador.
--3. El valor separador se debe colocar en el nodo padre, lo que puede provocar que el padre sea dividido en dos, y así sucesivamente.
Si las divisiones de nodos suben hasta la raíz, se crea una nueva raíz con un único elemento como valor separador, y dos hijos. Es por esto por lo que la cota inferior del tamaño de los nodos no se aplica a la raíz. El máximo número de elementos por nodo es U-1. Así que debe ser posible dividir el número máximo de elementos U-1 en dos nodos legales. Si este número fuera impar, entonces U=2L, y cada uno de los nuevos nodos tendrían (U-2)/2 = L-1 elementos, y por lo tanto serían nodos legales. Si U-1 fuera par, U=2L-1, así que habría 2L-2 elementos en el nodo. La mitad de este número es L-1, que es el número mínimo de elementos permitidos por nodo.
Un algoritmo mejorado admite una sola pasada por el árbol desde la raiz,hasta el nodo donde la inserción tenga lugar,dividiendo todos los nodos que estén llenos encontrados a su paso.Esto evita la necesidad de volver a cargar en memoria los nodos padres,que pueden ser caros si los nodos se encuentran en una memoria secundaria.Sin embargo,para usar este algoritmo mejorado, debemos ser capaces de enviar un elemento al nodo padre y dividir el resto U-2 elementos en 2 nodos legales,sin añadir un nuevo elemento.Esto requiere que U=2L en lugar de U=L-1,lo que explica por qué algunos libros de texto imponen este requisito en la definicion de árboles-B.
Eliminación
La eliminación de un elemento es directa si no se requiere corrección para garantizar sus propiedades. Hay dos estrategias populares para eliminar un nodo de un árbol B.
*localizar y eliminar el elemento, y luego corregir.
*hacer una única pasada de arriba a abajo por el árbol, pero cada vez que se visita un nodo, reestructurar el árbol para que cuando se encuentre el elemento a ser borrado, pueda eliminarse sin necesidad de continuar reestructurando.
Se pueden dar dos problemas al eliminar elementos: primero, el elemento puede ser un separador de un nodo interno. Segundo, puede suceder que al borrar el elemento número de elementos del nodo quede debajo de la cota mínima. Estos problemas se tratan a continuación en orden.
Eliminación en un nodo hoja
* Busque el valor a eliminar.
* Si el valor se encuentra en un nodo hoja, se elimina directamente la clave, posiblemente dejándolo con muy pocos elementos; por lo que se requerirán cambios adicionales en el árbol.
Eliminación en un nodo interno
ada elemento de un nodo interno actúa como valor separador para dos subárboles, y cuando ese elemento es eliminado, pueden suceder dos casos. En el primero, tanto el hijo izquierdo como el derecho tienen el número mínimo de elementos, L-1. Pueden entonces fundirse en un único nodo con 2L-2 elementos, que es un número que no excede U-1 y por lo tanto es un nodo legal. A menos que se sepa que este árbol B en particular no tiene datos duplicados, también se debe eliminar el elemento en cuestión (recursivamente) del nuevo nodillo.
En el segundo caso, uno de los dos nodos hijos tienen un número de elementos mayor que el mínimo. Entonces se debe hallar un nuevo separador para estos dos subárboles. Note que el mayor elemento del árbol izquierdo es el mayor elemento que es menor que el separador. De la misma forma, el menor elemento del subárbol derecho es el menor elemento que es mayor que el separador. Ambos elementos se encuentran en nodos hoja, y cualquiera de los dos puede ser el nuevo separador.
* Si el valor se encuentra en un nodo interno, escoja un nuevo separador (puede ser el mayor elemento del subárbol izquierdo o el menor elemento del subárbol derecho), elimínelo del nodo hoja en que se encuentra, y reemplace el elemento a eliminar por el nuevo separador.
* Como se ha eliminado un elemento de un nodo hoja, se debe tratar este caso de manera equivalente.
Rebalanceo después de la eliminación
Si al eliminar un elemento de un nodo hoja el nodo se ha quedado con menos elementos que el mínimo permitido, algunos elementos se deben redistribuir. En algunos casos el cambio lleva la deficiencia al nodo padre, y la redistribución se debe aplicar iterativamente hacia arriba del árbol, quizá incluso hasta a la raíz. Dado que la cota mínima en el número de elementos no se aplica a la raíz, el problema desaparece cuando llega a ésta.
La estrategia consiste en hallar un hermano para el nodo deficiente que tenga más del mínimo número de elementos y redistribuir los elementos entre los hermanos para que todos tengan más del mínimo. Esto también cambia los separadores del nodo padre.
* Si el nodo hermano inmediato de la derecha del nodo deficiente tiene más del mínimo número de elementos, escoja el valor medio entre el separador y ambos hermanos como nuevo separador y colóquelo en el padre.
* Redistribuya los elementos restantes en los nodos hijo derecho e izquierdo.
* Redistribuya los subárboles de los dos nodos . Los subárboles son trasplantados por completo, y no se alteran si se mueven a un otro nodo padre, y esto puede hacerse mientras los elementos se redistribuyen.
* Si el nodo hemano inmediato de la derecha del nodo deficiente tiene el mínimo número de elementos, examine el nodo hermano inmediato de la izquierda.
* Si los dos nodos hemanos inmediatos tienen el mínimo número de elementos, cree un nuevo nodo con todos los elementos del nodo deficiente, todos los elementos de uno de sus hermanos, colocando el separador del padre entre los elementos de los dos nodos hermanos fundidos.
* Elimine el separador del padre, y reemplace los dos hijos que separaba por el nuevo nodo fundido.
* Si esa acción deja al número de elementos del padre por debajo del mínimo, repita estos pasos en el nuevo nodo deficiente, a menos que sea la raíz, ya que no tiene cota mínima en el número de elementos.
-----------------
Estructura de los nodos
Cada elemento de un nodo interno actúa como un valor separador, que lo divide en subárboles. Por ejemplo, si un nodo interno tiene tres nodos hijo, debe tener dos valores separadores o elementos a1 y a2. Todos los valores del subárbol izquierdo deben ser menores a a1, todos los valores del subárbol del centro deben estar entre a1 y a2, y todos los valores del subárbol derecho deben ser mayores a a2.
Los nodos internos de un árbol B, es decir los nodos que no son hoja, usualmente se representan como un conjunto ordenado de elementos y punteros a los hijos. Cada nodo interno contiene un máximo de U hijos y, con excepción del nodo raíz, un mínimo de L hijos. Para todos los nodos internos exceptuando la raíz, el número de elementos es uno menos que el número de punteros a nodos. El número de elementos se encuentra entre L-1 y U-1. El número U debe ser 2L o 2L-1, es decir, cada nodo interno está por lo menos a medio llenar. Esta relación entre U y L implica que dos nodos que están a medio llenar pueden juntarse para formar un nodo legal, y un nodo lleno puede dividirse en dos nodos legales (si es que hay lugar para subir un elemento al nodo padre). Estas propiedades hacen posible que el árbol B se ajuste para preservar sus propiedades ante la inserción y eliminación de elementos.
Operaciones
Búsqueda
La búsqueda es similar a la de los árboles binarios. Se empieza en la raíz, y se recorre el árbol hacia abajo, escogiendo el sub-nodo de acuerdo a la posición relativa del valor buscado respecto a los valores de cada nodo. Típicamente se utiliza la búsqueda binaria para determinar esta posición relativa.
Procedimiento
1 Situarse en el nodo raíz.
2 Comprobar si contiene la clave a buscar.
1. . Encontrada fin de procedimiento .
2. . No encontrada:
---------1. . La clave a buscar k <> ki y k < style="font-weight: bold;">Inserción
Todas las inserciones se hacen en los nodos hoja.
1. Realizando una búsqueda en el árbol, se halla el nodo hoja en el cual debería ubicarse el nuevo elemento.
2. Si el nodo hoja tiene menos elementos que el máximo número de elementos legales, entonces hay lugar para uno más. Inserte el nuevo elemento en el nodo, respetando el orden de los elementos.
3. De otra forma, el nodo debe ser dividido en dos nodos. La división se realiza de la siguiente manera:
---1. Se escoge el valor medio entre los elementos del nodo y el nuevo elemento.
---2. Los valores menores que el valor medio se colocan en el nuevo nodo izquierdo, y los valores mayores que el valor medio se colocan en el nuevo nodo derecho; el valor medio actúa como valor separador.
--3. El valor separador se debe colocar en el nodo padre, lo que puede provocar que el padre sea dividido en dos, y así sucesivamente.
Si las divisiones de nodos suben hasta la raíz, se crea una nueva raíz con un único elemento como valor separador, y dos hijos. Es por esto por lo que la cota inferior del tamaño de los nodos no se aplica a la raíz. El máximo número de elementos por nodo es U-1. Así que debe ser posible dividir el número máximo de elementos U-1 en dos nodos legales. Si este número fuera impar, entonces U=2L, y cada uno de los nuevos nodos tendrían (U-2)/2 = L-1 elementos, y por lo tanto serían nodos legales. Si U-1 fuera par, U=2L-1, así que habría 2L-2 elementos en el nodo. La mitad de este número es L-1, que es el número mínimo de elementos permitidos por nodo.
Un algoritmo mejorado admite una sola pasada por el árbol desde la raiz,hasta el nodo donde la inserción tenga lugar,dividiendo todos los nodos que estén llenos encontrados a su paso.Esto evita la necesidad de volver a cargar en memoria los nodos padres,que pueden ser caros si los nodos se encuentran en una memoria secundaria.Sin embargo,para usar este algoritmo mejorado, debemos ser capaces de enviar un elemento al nodo padre y dividir el resto U-2 elementos en 2 nodos legales,sin añadir un nuevo elemento.Esto requiere que U=2L en lugar de U=L-1,lo que explica por qué algunos libros de texto imponen este requisito en la definicion de árboles-B.
Eliminación
La eliminación de un elemento es directa si no se requiere corrección para garantizar sus propiedades. Hay dos estrategias populares para eliminar un nodo de un árbol B.
*localizar y eliminar el elemento, y luego corregir.
*hacer una única pasada de arriba a abajo por el árbol, pero cada vez que se visita un nodo, reestructurar el árbol para que cuando se encuentre el elemento a ser borrado, pueda eliminarse sin necesidad de continuar reestructurando.
Se pueden dar dos problemas al eliminar elementos: primero, el elemento puede ser un separador de un nodo interno. Segundo, puede suceder que al borrar el elemento número de elementos del nodo quede debajo de la cota mínima. Estos problemas se tratan a continuación en orden.
Eliminación en un nodo hoja
* Busque el valor a eliminar.
* Si el valor se encuentra en un nodo hoja, se elimina directamente la clave, posiblemente dejándolo con muy pocos elementos; por lo que se requerirán cambios adicionales en el árbol.
Eliminación en un nodo interno
ada elemento de un nodo interno actúa como valor separador para dos subárboles, y cuando ese elemento es eliminado, pueden suceder dos casos. En el primero, tanto el hijo izquierdo como el derecho tienen el número mínimo de elementos, L-1. Pueden entonces fundirse en un único nodo con 2L-2 elementos, que es un número que no excede U-1 y por lo tanto es un nodo legal. A menos que se sepa que este árbol B en particular no tiene datos duplicados, también se debe eliminar el elemento en cuestión (recursivamente) del nuevo nodillo.
En el segundo caso, uno de los dos nodos hijos tienen un número de elementos mayor que el mínimo. Entonces se debe hallar un nuevo separador para estos dos subárboles. Note que el mayor elemento del árbol izquierdo es el mayor elemento que es menor que el separador. De la misma forma, el menor elemento del subárbol derecho es el menor elemento que es mayor que el separador. Ambos elementos se encuentran en nodos hoja, y cualquiera de los dos puede ser el nuevo separador.
* Si el valor se encuentra en un nodo interno, escoja un nuevo separador (puede ser el mayor elemento del subárbol izquierdo o el menor elemento del subárbol derecho), elimínelo del nodo hoja en que se encuentra, y reemplace el elemento a eliminar por el nuevo separador.
* Como se ha eliminado un elemento de un nodo hoja, se debe tratar este caso de manera equivalente.
Rebalanceo después de la eliminación
Si al eliminar un elemento de un nodo hoja el nodo se ha quedado con menos elementos que el mínimo permitido, algunos elementos se deben redistribuir. En algunos casos el cambio lleva la deficiencia al nodo padre, y la redistribución se debe aplicar iterativamente hacia arriba del árbol, quizá incluso hasta a la raíz. Dado que la cota mínima en el número de elementos no se aplica a la raíz, el problema desaparece cuando llega a ésta.
La estrategia consiste en hallar un hermano para el nodo deficiente que tenga más del mínimo número de elementos y redistribuir los elementos entre los hermanos para que todos tengan más del mínimo. Esto también cambia los separadores del nodo padre.
* Si el nodo hermano inmediato de la derecha del nodo deficiente tiene más del mínimo número de elementos, escoja el valor medio entre el separador y ambos hermanos como nuevo separador y colóquelo en el padre.
* Redistribuya los elementos restantes en los nodos hijo derecho e izquierdo.
* Redistribuya los subárboles de los dos nodos . Los subárboles son trasplantados por completo, y no se alteran si se mueven a un otro nodo padre, y esto puede hacerse mientras los elementos se redistribuyen.
* Si el nodo hemano inmediato de la derecha del nodo deficiente tiene el mínimo número de elementos, examine el nodo hermano inmediato de la izquierda.
* Si los dos nodos hemanos inmediatos tienen el mínimo número de elementos, cree un nuevo nodo con todos los elementos del nodo deficiente, todos los elementos de uno de sus hermanos, colocando el separador del padre entre los elementos de los dos nodos hermanos fundidos.
* Elimine el separador del padre, y reemplace los dos hijos que separaba por el nuevo nodo fundido.
* Si esa acción deja al número de elementos del padre por debajo del mínimo, repita estos pasos en el nuevo nodo deficiente, a menos que sea la raíz, ya que no tiene cota mínima en el número de elementos.
-----------------
PROGRAMA1. CONTRUCCION, RECORRIDO, ALTURA
import java.awt.Color;
import java.awt.Container;
import java.awt.FlowLayout;
import java.awt.Font;
import java.awt.TextArea;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import javax.swing.*;
public class PruebaArbol extends JFrame {Container c=getContentPane();private JMenuBar menu;private JMenu i1,i2;
private JMenuItem construye,mostrar,alt,hoj,anc,salir,creditos,nuevo,inor,pos,pre;
private int dato=0,nodos=0;
Arbol arbol;
String aux="R",fila=" ",columna="nn",cadena=new String();
private TextArea most;
public PruebaArbol(String cogollo){super(cogollo);c.setLayout(new FlowLayout());
menu = new JMenuBar();
i1 = new JMenu("ARCHIVO");
i2 = new JMenu("PROCESOS");
nuevo=new JMenuItem("NUEVO PROYECTO");
salir=new JMenuItem("SALIR");
construye=new JMenuItem("CONSTRUIR ARBOL");
mostrar=new JMenuItem("MOSTRAR ARBOL");
alt=new JMenuItem("ALTURA DEL ARBOL");
hoj=new JMenuItem("HOJAS DEL ARBOL");
anc=new JMenuItem("ANCESTROS DEL ARBOL");
inor=new JMenuItem("INORDEN");pre=new JMenuItem("PREORDEN");
pos=new JMenuItem("POSORDEN");
creditos=new JMenuItem("CREDITOS");
i1.add(nuevo);
i1.add(construye);
i1.add(mostrar);
i1.add(creditos);
i1.add(salir);
i2.add(alt);i2.add(hoj);
i2.add(anc);i2.add(inor);
i2.add(pos);i2.add(pre);
nuevo.addActionListener(new manejaEventos());
salir.addActionListener(new manejaEventos());
mostrar.addActionListener(new manejaEventos());
construye.addActionListener(new manejaEventos())
;alt.addActionListener(new manejaEventos());
anc.addActionListener(new manejaEventos());
hoj.addActionListener(new manejaEventos());
inor.addActionListener(new manejaEventos());
pre.addActionListener(new manejaEventos());
pos.addActionListener(new manejaEventos());
creditos.addActionListener(new manejaEventos());
menu.add(i1);
menu.add(i2);
c.setBackground(new Color(128,0,255));
setJMenuBar(menu);
setSize( 1024 , 768 );
setVisible( true );
}class manejaEventos implements ActionListener{public void actionPerformed(ActionEvent e){ if(e.getSource()==construye){arbol=new Arbol();
int valor=0;
nodos=Integer.parseInt( JOptionPane.showInputDialog(null,"ingrese el numero de nodos para el arbol") );for (int i=1;i
------------
PROGRAMA2 ARBOL GENERICO
public Arboles() {
System.out.println("Un árbol genérico");
}
public Arboles(String tipo) {
System.out.println("Un árbol tipo " + tipo);
}
public Arboles(int altura) {
System.out.println("Un árbol de " + altura + " metros");
}
public Arboles(int altura,String tipo) {
System.out.println("Un " + tipo + " de " + altura + " metros");
}
public static void main(String args[]) {
Arboles arbol1 = new Arboles(4);
Arboles arbol2 = new Arboles("Roble");
Arboles arbol3 = new Arboles();
Arboles arbol4 = new Arboles(5,"Pino");
}
}
----------
PROGRAMA
package pfc15;
import java.util.*;
import java.awt.*;
import javax.swing.*;
import java.awt.event.*;
import javax.swing.tree.*;
public class Arboles extends JPanel{
//elementos para crear el entorno grafico
private static JSplitPane oJSP1, oJSP2;
private static JTree arbol1,arbol2;
static int i=0;
DefaultMutableTreeNode raiz,raiz2,rama,seleccion;
DefaultTreeModel modelo,modelo2;
/////////////////////////////////////////
/** Creates a new instance of arboles */
public Arboles() {
//creamos el entorno grafico
oJSP1 = new JSplitPane(JSplitPane.HORIZONTAL_SPLIT);
oJSP2 = new JSplitPane(JSplitPane.HORIZONTAL_SPLIT);
raiz = new DefaultMutableTreeNode( "raiz" );
arbol1 = new JTree(raiz);
//////////////////////////////////////////////////////////////////
//codigo necesario en los arboles para controlar las acciones
// Se obtiene el modelo del árbol
modelo =(DefaultTreeModel)arbol1.getModel();
modelo.addTreeModelListener(new MiTreeModelListener());
arbol1.addTreeSelectionListener(new MiTreeSelectionListener());
arbol1.addTreeExpansionListener(new MiTreeExpansionListener());
////////////////////////////////////////////////////////////////
oJSP2.setRightComponent(new JScrollPane( arbol1));
oJSP2.setLeftComponent(new JScrollPane());
oJSP1.setRightComponent(oJSP2);
raiz2 = new DefaultMutableTreeNode( "raiz2" );
arbol2 = new JTree(raiz2);
//////////////////////////////////////////////////////////////////
//codigo necesario en los arboles para controlar las acciones
// Se obtiene el modelo del árbol
modelo2 =(DefaultTreeModel)arbol2.getModel();
modelo2.addTreeModelListener(new MiTreeModelListener());
arbol2.addTreeSelectionListener(new MiTreeSelectionListener());
arbol2.addTreeExpansionListener(new MiTreeExpansionListener());
////////////////////////////////////////////////////////////////
oJSP1.setLeftComponent(new JScrollPane(arbol2));
Dimension minimumSize = new Dimension(100, 540);
oJSP1.setDividerLocation(150);
oJSP1.setDividerSize(10);
oJSP1.setPreferredSize(new Dimension(500, 450));
this.add(oJSP1);
//creamos las tablas para almacenar las acciones
//
}
//anhade una nueva rama al nodo seleccionado
void nueva_rama(){
Estructura est;
String datos[][] = {
{ "Colores","Rojo","Verde","Azul" },
{ "Sabores","Salado","Dulce","Amargo" },
{ "Longitud","Corta","Media","Larga" },
{ "Intensidad","Alta","Media","Baja" },
{ "Temperatura","Alta","Media","Baja" },
{ "Volumen","Alto","Medio","Bajo" },
};
if( i == datos.length ) i = 0;
rama = new Rama( datos[i++] ).node();
// Control de la útlima selección realizada
if (MiTreeSelectionListener.oEstructura.getTree() == null) return;
seleccion = (DefaultMutableTreeNode)MiTreeSelectionListener.oEstructura.getTree().getLastSelectedPathComponent();
if( seleccion == null ) {
System.out.println("AKI LA CAGO!!!!!!!!!!");
seleccion = raiz;
}
// El modelo creará el evento adecuado, y en respuesta
// a él, el árbol se actualizará automáticamente
MiTreeSelectionListener.oEstructura.getModelo().insertNodeInto( rama,seleccion,0 );
}
//elimina la rama seleccionada
void elimina_rama(){
Estructura est;
//buscamos la rama seleccionada
rama = (DefaultMutableTreeNode) MiTreeSelectionListener.oEstructura.getTree().getLastSelectedPathComponent();
//comprobamos q la rama no sea nula
if (rama == null) return;
//comprobamos q no sea la rama raiz y la borramos
if ((rama !=raiz)&&(rama !=raiz2)) MiTreeSelectionListener.oEstructura.getModelo().removeNodeFromParent(rama);
}
}
import java.util.*;
import java.awt.*;
import javax.swing.*;
import java.awt.event.*;
import javax.swing.tree.*;
public class Arboles extends JPanel{
//elementos para crear el entorno grafico
private static JSplitPane oJSP1, oJSP2;
private static JTree arbol1,arbol2;
static int i=0;
DefaultMutableTreeNode raiz,raiz2,rama,seleccion;
DefaultTreeModel modelo,modelo2;
/////////////////////////////////////////
/** Creates a new instance of arboles */
public Arboles() {
//creamos el entorno grafico
oJSP1 = new JSplitPane(JSplitPane.HORIZONTAL_SPLIT);
oJSP2 = new JSplitPane(JSplitPane.HORIZONTAL_SPLIT);
raiz = new DefaultMutableTreeNode( "raiz" );
arbol1 = new JTree(raiz);
//////////////////////////////////////////////////////////////////
//codigo necesario en los arboles para controlar las acciones
// Se obtiene el modelo del árbol
modelo =(DefaultTreeModel)arbol1.getModel();
modelo.addTreeModelListener(new MiTreeModelListener());
arbol1.addTreeSelectionListener(new MiTreeSelectionListener());
arbol1.addTreeExpansionListener(new MiTreeExpansionListener());
////////////////////////////////////////////////////////////////
oJSP2.setRightComponent(new JScrollPane( arbol1));
oJSP2.setLeftComponent(new JScrollPane());
oJSP1.setRightComponent(oJSP2);
raiz2 = new DefaultMutableTreeNode( "raiz2" );
arbol2 = new JTree(raiz2);
//////////////////////////////////////////////////////////////////
//codigo necesario en los arboles para controlar las acciones
// Se obtiene el modelo del árbol
modelo2 =(DefaultTreeModel)arbol2.getModel();
modelo2.addTreeModelListener(new MiTreeModelListener());
arbol2.addTreeSelectionListener(new MiTreeSelectionListener());
arbol2.addTreeExpansionListener(new MiTreeExpansionListener());
////////////////////////////////////////////////////////////////
oJSP1.setLeftComponent(new JScrollPane(arbol2));
Dimension minimumSize = new Dimension(100, 540);
oJSP1.setDividerLocation(150);
oJSP1.setDividerSize(10);
oJSP1.setPreferredSize(new Dimension(500, 450));
this.add(oJSP1);
//creamos las tablas para almacenar las acciones
//
}
//anhade una nueva rama al nodo seleccionado
void nueva_rama(){
Estructura est;
String datos[][] = {
{ "Colores","Rojo","Verde","Azul" },
{ "Sabores","Salado","Dulce","Amargo" },
{ "Longitud","Corta","Media","Larga" },
{ "Intensidad","Alta","Media","Baja" },
{ "Temperatura","Alta","Media","Baja" },
{ "Volumen","Alto","Medio","Bajo" },
};
if( i == datos.length ) i = 0;
rama = new Rama( datos[i++] ).node();
// Control de la útlima selección realizada
if (MiTreeSelectionListener.oEstructura.getTree() == null) return;
seleccion = (DefaultMutableTreeNode)MiTreeSelectionListener.oEstructura.getTree().getLastSelectedPathComponent();
if( seleccion == null ) {
System.out.println("AKI LA CAGO!!!!!!!!!!");
seleccion = raiz;
}
// El modelo creará el evento adecuado, y en respuesta
// a él, el árbol se actualizará automáticamente
MiTreeSelectionListener.oEstructura.getModelo().insertNodeInto( rama,seleccion,0 );
}
//elimina la rama seleccionada
void elimina_rama(){
Estructura est;
//buscamos la rama seleccionada
rama = (DefaultMutableTreeNode) MiTreeSelectionListener.oEstructura.getTree().getLastSelectedPathComponent();
//comprobamos q la rama no sea nula
if (rama == null) return;
//comprobamos q no sea la rama raiz y la borramos
if ((rama !=raiz)&&(rama !=raiz2)) MiTreeSelectionListener.oEstructura.getModelo().removeNodeFromParent(rama);
}
}
--------
PROGRAMA ARBOL BINARIO
public class CArbolBinarioDeBusqueda extends CArbolBinB
{
public int comparar(Object obj1, Object obj2)
{
String str1=new String(((CDatos)obj1).obtenerNombre());
String str2=new String(((CDatos)obj2).obtenerNombre());
return str1.compareTo(str2);
}
public void procesar(Object obj)
{
String nombre=new String(((CDatos)obj).obtenerNombre());
Double nota=((CDatos)obj).obtenerNota();
System.out.println(nombre+" "+nota);
}
public void visitarInorden()
{
inorden(null, true);
}
public void visitarPosorden()
{
posorden(null, true);
}
public void visitarPreorden()
{
preorden(null, true);
}
}
-----------
PROGRAMA A. BINARIO
public abstract class CArbolBinB{
protected CNodo raiz=null;
private class CNodo{
private Object datos;
private CNodo izquierdo;
private CNodo derecho;
public CNodo(){
}
}
public static final int CORRECTO=000;
public static final int NO_DATOS=100;
public static final int YA_EXISTE=101;
public static final int NO_EXISTE=102;
public CArbolBinB(){
}
public abstract int comparar(Object obj1, Object obj2);
public abstract void procesar(Object obj);
public abstract void visitarInorden();
public abstract void visitarPosorden();
public abstract void visitarPreorden();
public Object buscar(Object obj){
CNodo actual=raiz;
int nComp=0;
while(actual!=null){
if((nComp=comparar(obj,actual.datos))==0)
return(actual.datos);
else if(nComp<0) actual="actual.izquierdo;" actual="actual.derecho;" ultimo="null," actual="raiz;" ncomp="0;" obj="=" ncomp="comparar(obj," ultimo="actual;" actual="actual.izquierdo;" actual="actual.derecho;" actual="=" nuevonodo="new" datos="obj;" izquierdo="nuevoNodo.derecho=" ultimo="=" raiz="nuevoNodo;" izquierdo="nuevoNodo;" derecho="nuevoNodo;" ultimo="null," actual="raiz;" marcado="null," sucesor="null;" nanteriorcomp="0," ncomp="0;" obj="=" nanteriorcomp="nComp;" ncomp="comparar(obj,actual.datos))=" ultimo="actual;" actual="actual.izquierdo;" actual="actual.derecho;" marcado="actual;" izquierdo="=" derecho="=" sucesor="null;" izquierdo="=" sucesor="actual.derecho;" derecho="=" sucesor="actual.izquierdo;" sucesor="actual=" actual="actual.izquierdo;" izquierdo="marcado.izquierdo;" izquierdo="sucesor;" derecho="sucesor;" raiz="sucesor;" actual="null;" actual="raiz;" actual="r;" actual="null;" actual="raiz;" actual="r;" actual="null;" actual="raiz;" actual="r;">
PROGRAMA7
public class CDatos
{
private String nombre;
private double nota;
public CDatos(){}
public CDatos(String nom, double n)
{
nombre=nom;
nota=n;
}
public void asignarNombre(String nom)
{
nombre=nom;
}
public String obtenerNombre()
{
return nombre;
}
public void asignarNota(double n)
{
nota=n;
}
public double obtenerNota()
{
return nota;
}
}
--------------
PROGRMA8A
import java.io.*;
public class Leer{
public static String dato(){
String sdato = "";
try{
InputStreamReader isr =
new InputStreamReader(System.in);
BufferedReader flujoE=
new BufferedReader(isr);
sdato = flujoE.readLine();
}
catch(IOException e){
System.err.println("Error: " + e.getMessage());
}
return sdato;
}
public static short datoShort(){
try{
return Short.parseShort(dato());
}
catch(NumberFormatException e){
return Short.MIN_VALUE;
}
}
public static int datoInt(){
try{
return Integer.parseInt(dato());
}
catch(NumberFormatException e){
return Integer.MIN_VALUE;
}
}
public static long datoLong(){
try{
return Long.parseLong(dato());
}
catch(NumberFormatException e){
return Long.MIN_VALUE;
}
}
public static float datoFloat(){
try{
Float f = new Float(dato());
return f.floatValue();
}
catch(NumberFormatException e){
return Float.NaN;
}
}
public static double datoDouble(){
try{
Double d = new Double(dato());
return d.doubleValue();
}
catch(NumberFormatException e){
return Double.NaN;
}
}
public static String datoString(){
return dato();
}
public static char datoChar(){
int c=0;
try{
InputStreamReader isr =
new InputStreamReader(System.in);
BufferedReader flujoE=
new BufferedReader(isr);
c=flujoE.read();
char car;
car=(char) c;
return car;
}
catch(IOException e){
return '\0';
}
}
}
---------
B I N A R I O S
PROGRAMADEARBOLESBINARIOS
import java.util.NoSuchElementException;
public class BinarySearchTree
implements SortedMap
{
private Branch root = null;
private int length = 0;
private Comparator comparator = null;
public BinarySearchTree( Comparator c )
{ comparator = c; }
public BinarySearchTree()
{ this( null ); }
public void clear()
{
root = null;
length = 0;
}
public boolean isEmpty()
{
return ( root == null );
}
public int size() // devuelve el número de elementos del mapa
{
return length;
}
public Object firstKey() // devuelve la clave del primer elemento;
// es null si el mapa está vacío
{
if ( root == null )
return null;
else
return root.first().key;
}
public Object lastKey() // devuelve la clave del último elemento;
// es null si el mapa está vacío
{
if ( root == null )
return null;
else
return root.last().key;
}
public Object get( Object k ) // devuelve el valor correspondiente a la clave k
// si ésta está en el árbol; de lo contrario, es null
{
Branch b = find( k );
return ( b == null ) ? null : b.value;
}
public Object put(Object k, Object v) // si ya hay un nodo correspondiente a
// k devuelve su valor y los sustituye por v;
// de lo contrario, inserta un nuevo nodo(k, v)
{
Branch p = null;
Branch b = root;
int c = 0;
// encuentra el nodo con clave k y conserva la referencia p al padre
while ( b != null )
{
p = b;
c = compare( k, b.key );
if ( c == 0 )
{
// lo ha encontrado; inserta el nuevo valor y devuelve el antiguo
Object oldValue = b.value;
b.value = v;
return oldValue;
}
------
import java.util.NoSuchElementException;
public class BinarySearchTree
implements SortedMap
{
private Branch root = null;
private int length = 0;
private Comparator comparator = null;
public BinarySearchTree( Comparator c )
{ comparator = c; }
public BinarySearchTree()
{ this( null ); }
public void clear()
{
root = null;
length = 0;
}
public boolean isEmpty()
{
return ( root == null );
}
public int size() // devuelve el número de elementos del mapa
{
return length;
}
public Object firstKey() // devuelve la clave del primer elemento;
// es null si el mapa está vacío
{
if ( root == null )
return null;
else
return root.first().key;
}
public Object lastKey() // devuelve la clave del último elemento;
// es null si el mapa está vacío
{
if ( root == null )
return null;
else
return root.last().key;
}
public Object get( Object k ) // devuelve el valor correspondiente a la clave k
// si ésta está en el árbol; de lo contrario, es null
{
Branch b = find( k );
return ( b == null ) ? null : b.value;
}
public Object put(Object k, Object v) // si ya hay un nodo correspondiente a
// k devuelve su valor y los sustituye por v;
// de lo contrario, inserta un nuevo nodo(k, v)
{
Branch p = null;
Branch b = root;
int c = 0;
// encuentra el nodo con clave k y conserva la referencia p al padre
while ( b != null )
{
p = b;
c = compare( k, b.key );
if ( c == 0 )
{
// lo ha encontrado; inserta el nuevo valor y devuelve el antiguo
Object oldValue = b.value;
b.value = v;
return oldValue;
}
------
B I N A R I O S 2
PROGRAMARBOLBANARIO2
import javax.swing.*;
import java.awt.event.*;
import java.awt.BorderLayout;
import java.awt.Color;
import java.util.NoSuchElementException;
public class BinarySearchTreeView
extends JPanel
implements ActionListener
{
private BinarySearchTree btree = new BinarySearchTree( );
private JLabel count;
private JTextField keyField;
private JTextField valueField;
public BinarySearchTreeView()
{
super();
setLayout( new BorderLayout() );
setBorder( BorderFactory.createLineBorder( Color.black, 2 ) );
JPanel buttons = new JPanel();
JButton clearBtn = new JButton( "clear" );
buttons.add( clearBtn );
clearBtn.addActionListener( this );
JButton firstBtn = new JButton( "first" );
buttons.add( firstBtn );
firstBtn.addActionListener( this );
JButton lastBtn = new JButton( "last" );
buttons.add( lastBtn );
lastBtn.addActionListener( this );
JButton getBtn = new JButton( "get" );
buttons.add( getBtn );
getBtn.addActionListener( this );
JButton putBtn = new JButton( "put" );
buttons.add( putBtn );
putBtn.addActionListener( this );
JButton removeBtn = new JButton( "remove" );
buttons.add( removeBtn );
removeBtn.addActionListener( this );
JButton iteratorBtn = new JButton( "iterator" );
buttons.add( iteratorBtn );
iteratorBtn.addActionListener( this );
add( buttons, BorderLayout.NORTH );
JPanel dataPanel = new JPanel( new BorderLayout() );
JPanel countPanel = new JPanel();
JLabel countLabel = new JLabel( "Count:" );
countPanel.add( countLabel, BorderLayout.WEST );
count = new JLabel( "0", JLabel.LEFT );
countPanel.add( count, BorderLayout.WEST );
dataPanel.add( countPanel, BorderLayout.WEST );
JPanel keyPanel = new JPanel( );
JLabel keyLabel = new JLabel( "Key:" );
keyPanel.add( keyLabel );
keyField = new JTextField( 12 );
keyPanel.add( keyField );
dataPanel.add( keyPanel, BorderLayout.CENTER );
JPanel valuePanel = new JPanel( );
JLabel valueLabel = new JLabel( "Value:" );
valuePanel.add( valueLabel );
valueField = new JTextField( 12 );
valuePanel.add( valueField, BorderLayout.EAST );
dataPanel.add( valuePanel, BorderLayout.EAST );
add( dataPanel, BorderLayout.CENTER );
}
public void actionPerformed( ActionEvent e )
{
String command = e.getActionCommand();
if ( command.equals( "clear" ) )
doClear();
else if ( command.equals( "first" ) )
doFirst();
else if ( command.equals( "last" ) )
doLast();
else if ( command.equals( "get" ) )
doGet();
else if ( command.equals( "put" ) )
doPut();
else if ( command.equals( "remove" ) )
doRemove();
else if ( command.equals( "iterator" ) )
doIterator();
updateView();
}
private void doClear()
{
btree.clear();
keyField.setText( null );
valueField.setText( null );
}
private void doFirst()
{
String key = (String) btree.firstKey();
keyField.setText( key );
valueField.setText( (String) btree.get( key ));
}
private void doLast()
{
String key = (String) btree.lastKey();
keyField.setText( key );
valueField.setText( (String) btree.get( key ));
}
private void doPut()
{
valueField.setText((String) btree.put( keyField.getText(),
valueField.getText()));
}
private void doGet()
{
valueField.setText( (String) btree.get( keyField.getText() ) );
}
private void doRemove()
{
valueField.setText( (String) btree.remove( keyField.getText() ) );
}
private void doIterator()
{
MapIterator iter = btree.iterator();
MapIteratorView iterView = new MapIteratorView( iter );
iterView.setVisible( true );
}
private void updateView()
{
count.setText( String.valueOf( btree.size() ));
}
}
--------------
import javax.swing.*;
import java.awt.event.*;
import java.awt.BorderLayout;
import java.awt.Color;
import java.util.NoSuchElementException;
public class BinarySearchTreeView
extends JPanel
implements ActionListener
{
private BinarySearchTree btree = new BinarySearchTree( );
private JLabel count;
private JTextField keyField;
private JTextField valueField;
public BinarySearchTreeView()
{
super();
setLayout( new BorderLayout() );
setBorder( BorderFactory.createLineBorder( Color.black, 2 ) );
JPanel buttons = new JPanel();
JButton clearBtn = new JButton( "clear" );
buttons.add( clearBtn );
clearBtn.addActionListener( this );
JButton firstBtn = new JButton( "first" );
buttons.add( firstBtn );
firstBtn.addActionListener( this );
JButton lastBtn = new JButton( "last" );
buttons.add( lastBtn );
lastBtn.addActionListener( this );
JButton getBtn = new JButton( "get" );
buttons.add( getBtn );
getBtn.addActionListener( this );
JButton putBtn = new JButton( "put" );
buttons.add( putBtn );
putBtn.addActionListener( this );
JButton removeBtn = new JButton( "remove" );
buttons.add( removeBtn );
removeBtn.addActionListener( this );
JButton iteratorBtn = new JButton( "iterator" );
buttons.add( iteratorBtn );
iteratorBtn.addActionListener( this );
add( buttons, BorderLayout.NORTH );
JPanel dataPanel = new JPanel( new BorderLayout() );
JPanel countPanel = new JPanel();
JLabel countLabel = new JLabel( "Count:" );
countPanel.add( countLabel, BorderLayout.WEST );
count = new JLabel( "0", JLabel.LEFT );
countPanel.add( count, BorderLayout.WEST );
dataPanel.add( countPanel, BorderLayout.WEST );
JPanel keyPanel = new JPanel( );
JLabel keyLabel = new JLabel( "Key:" );
keyPanel.add( keyLabel );
keyField = new JTextField( 12 );
keyPanel.add( keyField );
dataPanel.add( keyPanel, BorderLayout.CENTER );
JPanel valuePanel = new JPanel( );
JLabel valueLabel = new JLabel( "Value:" );
valuePanel.add( valueLabel );
valueField = new JTextField( 12 );
valuePanel.add( valueField, BorderLayout.EAST );
dataPanel.add( valuePanel, BorderLayout.EAST );
add( dataPanel, BorderLayout.CENTER );
}
public void actionPerformed( ActionEvent e )
{
String command = e.getActionCommand();
if ( command.equals( "clear" ) )
doClear();
else if ( command.equals( "first" ) )
doFirst();
else if ( command.equals( "last" ) )
doLast();
else if ( command.equals( "get" ) )
doGet();
else if ( command.equals( "put" ) )
doPut();
else if ( command.equals( "remove" ) )
doRemove();
else if ( command.equals( "iterator" ) )
doIterator();
updateView();
}
private void doClear()
{
btree.clear();
keyField.setText( null );
valueField.setText( null );
}
private void doFirst()
{
String key = (String) btree.firstKey();
keyField.setText( key );
valueField.setText( (String) btree.get( key ));
}
private void doLast()
{
String key = (String) btree.lastKey();
keyField.setText( key );
valueField.setText( (String) btree.get( key ));
}
private void doPut()
{
valueField.setText((String) btree.put( keyField.getText(),
valueField.getText()));
}
private void doGet()
{
valueField.setText( (String) btree.get( keyField.getText() ) );
}
private void doRemove()
{
valueField.setText( (String) btree.remove( keyField.getText() ) );
}
private void doIterator()
{
MapIterator iter = btree.iterator();
MapIteratorView iterView = new MapIteratorView( iter );
iterView.setVisible( true );
}
private void updateView()
{
count.setText( String.valueOf( btree.size() ));
}
}
--------------
PROGRAMA ARBOL BINARIO BUSQUEDA
public class CArbolBinarioDeBusqueda extends CArbolBinB
{
public int comparar(Object obj1, Object obj2)
{
String str1=new String(((CDatos)obj1).obtenerNombre());
String str2=new String(((CDatos)obj2).obtenerNombre());
return str1.compareTo(str2);
}
public void procesar(Object obj)
{
String nombre=new String(((CDatos)obj).obtenerNombre());
Double nota=((CDatos)obj).obtenerNota();
System.out.println(nombre+" "+nota);
}
public void visitarInorden()
{
inorden(null, true);
}
public void visitarPosorden()
{
posorden(null, true);
}
public void visitarPreorden()
{
preorden(null, true);
}
}
---------
ejemplo: recorrido en preorden de un arbol binario
// "raiz" es la referencia a la raiz del arbol
// llamado inicial: preorden(raiz)
// version recursiva
void preorden(Nodo nodo)
{
if (nodo!=null)
{
System.out.print(nodo.elemento);
preorden(nodo.izq);
preorden(nodo.der);
}
}
// primera version iterativa
void preorden(Nodo nodo)
{
Nodo aux;
Pila pila=new Pila(); // pila de nodos
pila.apilar(nodo);
while(!pila.estaVacia()) // mientras la pila no este vacia
{
aux=pila.desapilar();
if (aux!=null)
{
System.out.print(aux.elemento);
// primero se apila el nodo derecho y luego el izquierdo
// para mantener el orden correcto del recorrido
// al desapilar los nodos
pila.apilar(aux.der);
pila.apilar(aux.izq);
}
}
}
// segunda version iterativa
// dado que siempre el ultimo nodo apilado dentro del bloque if es
// aux.izq podemos asignarlo directamente a aux hasta que éste sea
// null, es decir, el bloque if se convierte en un bloque while
// y se cambia el segundo apilar por una asignacion de la referencia
void preorden(Nodo nodo)
{
Nodo aux;
Pila pila=new Pila(); // pila de nodos
pila.apilar(nodo);
while(!pila.estaVacia()) // mientras la pila no este vacia
{
aux=pila.desapilar();
while (aux!=null)
{
System.out.print(aux.elemento);
pila.apilar(aux.der);
aux=aux.izq;
}
}
}
--------
P R O G R A M A A R B O L L I S T A
import java.io.*;
public class Leer{
public static String dato(){
String sdato = "";
try{
InputStreamReader isr =
new InputStreamReader(System.in);
BufferedReader flujoE=
new BufferedReader(isr);
sdato = flujoE.readLine();
}
catch(IOException e){
System.err.println("Error: " + e.getMessage());
}
return sdato;
}
public static short datoShort(){
try{
return Short.parseShort(dato());
}
catch(NumberFormatException e){
return Short.MIN_VALUE;
}
}
public static int datoInt(){
try{
return Integer.parseInt(dato());
}
catch(NumberFormatException e){
return Integer.MIN_VALUE;
}
}
public static long datoLong(){
try{
return Long.parseLong(dato());
}
catch(NumberFormatException e){
return Long.MIN_VALUE;
}
}
public static float datoFloat(){
try{
Float f = new Float(dato());
return f.floatValue();
}
catch(NumberFormatException e){
return Float.NaN;
}
}
public static double datoDouble(){
try{
Double d = new Double(dato());
return d.doubleValue();
}
catch(NumberFormatException e){
return Double.NaN;
}
}
public static String datoString(){
return dato();
}
public static char datoChar(){
int c=0;
try{
InputStreamReader isr =
new InputStreamReader(System.in);
BufferedReader flujoE=
new BufferedReader(isr);
c=flujoE.read();
char car;
car=(char) c;
return car;
}
catch(IOException e){
return '\0';
}
}
}
-----------
public class Leer{
public static String dato(){
String sdato = "";
try{
InputStreamReader isr =
new InputStreamReader(System.in);
BufferedReader flujoE=
new BufferedReader(isr);
sdato = flujoE.readLine();
}
catch(IOException e){
System.err.println("Error: " + e.getMessage());
}
return sdato;
}
public static short datoShort(){
try{
return Short.parseShort(dato());
}
catch(NumberFormatException e){
return Short.MIN_VALUE;
}
}
public static int datoInt(){
try{
return Integer.parseInt(dato());
}
catch(NumberFormatException e){
return Integer.MIN_VALUE;
}
}
public static long datoLong(){
try{
return Long.parseLong(dato());
}
catch(NumberFormatException e){
return Long.MIN_VALUE;
}
}
public static float datoFloat(){
try{
Float f = new Float(dato());
return f.floatValue();
}
catch(NumberFormatException e){
return Float.NaN;
}
}
public static double datoDouble(){
try{
Double d = new Double(dato());
return d.doubleValue();
}
catch(NumberFormatException e){
return Double.NaN;
}
}
public static String datoString(){
return dato();
}
public static char datoChar(){
int c=0;
try{
InputStreamReader isr =
new InputStreamReader(System.in);
BufferedReader flujoE=
new BufferedReader(isr);
c=flujoE.read();
char car;
car=(char) c;
return car;
}
catch(IOException e){
return '\0';
}
}
}
-----------
PROGRAMAARBOLESB
package org.neos.arboles.binarios.dinamicos;
import java.util.ArrayList;
import org.neos.arboles.binarios.dinamicos.beans.Informacion;
import org.neos.arboles.binarios.dinamicos.beans.Nodo;
import org.neos.arboles.binarios.dinamicos.exceptions.ExceptionElementoDuplicado;
import org.neos.arboles.binarios.dinamicos.exceptions.ExceptionNoEncontrado;
/**
* @version 1.0
* @author Eugenio Flores
* Para cambiar la plantilla para este comentario de tipo generado vaya a
* Ventana>Preferencias>Java>Generación de código>Código y comentarios
*/
public class ArbolBinario {
private Nodo raiz;
private ArrayList recorrido;
/**
* Constructor que permite crear un árbol contenido en un vector de un
* tamaño definido por el parámetro recibido.
* @param num_elementos Número de elementos que podrá contener el vector.
* @throws ExceptionDimensionInvalida En caso de que el tamaño del vector
* no sea valido.
*/
public ArbolBinario() {
this.raiz = null;
this.recorrido = null;
}
/**
* Método útil para preguntar es nuestro árbol esta vacío o no.
* @return
*
*/
public boolean esArbolVacio() {
return (null == raiz) ? true : false;
}
/**
* Obtener la posición del nodo raíz.
* @return Posición del elemento que representa al nodo raíz. Se obtiene -1
* si el árbol esta vacío.
*/
public Nodo obtenerPosicionRaiz() {
return raiz;
}
/**
* Obtener respuesta a la pregunta ¿Existe el elemento en el árbol?
* @param info información a buscar dentro del árbol.
* @return
* la información especificada.
*
* contiene la información especificada.
public boolean existeElemento(Object info) {
Nodo nodo = obtenerElemento(info, raiz);
if(null != nodo) {
return true;
} else {
return false;
}
}
/**
* Obtener el elemento (Nodo) que contiene la información indicada.
* @param info Información que se busca dentro del árbol.
* @return
* la información existe dentro del árbol.
*
existe dentro del árbol.
*/
public Nodo obtenerElemento(Object info, Nodo raiz) {
if(null == raiz) {
return raiz;
} else {
Informacion obj_info = new Informacion(info);
Informacion obj_info_pa = new Informacion( raiz.getInformacion() );
if( obj_info_pa.equals(obj_info) ) {
return raiz;
} else if( obj_info.compareTo(obj_info_pa) < num_elems =" 0;" peso =" 0;" num_h_izq =" 0;" num_h_der =" 0;" num_h_izq =" obtenerNumeroElementos(nodo.getIzquierdo());" num_h_der =" obtenerNumeroElementos(nodo.getDerecho());" peso =" num_h_izq" altura =" 0;" altura_r_izq =" 0;" altura_r_der =" 0;" altura =" 1;" ref_h_izq =" nodo.getIzquierdo();" ref_h_der =" nodo.getDerecho();" altura_r_izq =" obtenerAltura(ref_h_izq);" altura_r_der =" obtenerAltura(ref_h_der);">= altura_r_der) { // tomar en cuenta solo la rama de mayor altura
altura += altura_r_izq;
} else {
altura += altura_r_der;
}
} else if( (ref_h_izq != null) && (ref_h_der == null) ) { // si solo tiene rama izquierda
altura += obtenerAltura(ref_h_izq);
} else if( (ref_h_izq == null) && (ref_h_der != null) ) { // si solo tiene rama derecha
altura += obtenerAltura(ref_h_der);
} else if( (ref_h_izq == null) && (ref_h_der == null) ) { // si el nodo es una hoja
altura -= 1;
}
}
return altura;
}
/**
* Método de apoyo a InsertarElemento(int). Este método se encarga de
* agregar el elemento dentro del vector que representa el árbol.
* @param info Información que contendrá el nuevo nodo.
* @param nodo Nodo contra el que se compara la información.
* @return La respuesta a la pregunta ¿Se inserto el elemento?
*/
private boolean insertarElemento(Object info, Nodo nodo) {
Nodo nuevo_nodo = null;
Informacion obj_info = new Informacion(info);
Informacion obj_info_pa = new Informacion( nodo.getInformacion() );
if( obj_info.compareTo(obj_info_pa) < nuevo_nodo =" new" nuevo_nodo =" new" se_inserto =" false;" raiz =" new" se_inserto =" true;" se_inserto =" insertarElemento(info," nodo =" null;" se_borro =" false;" nodo =" obtenerElemento(info," se_borro =" borrarNodoInterior(nodo);" se_borro =" borrarNodoHoja(nodo);" se_borro =" borrarNodoRaiz(nodo);" respuesta =" false;" nodo_padre =" nodo.getPadre();" nodo_izq =" nodo.getIzquierdo();" nodo_der =" nodo.getDerecho();" nodo_c =" null;" nodo_c =" new" nodo =" null;" nodo_izq =" null;" respuesta =" true;" nodo =" null;" respuesta =" true;" nodo =" null;" respuesta =" true;" se_borro =" false;" nodo_padre =" nodo.getPadre();" nodo =" null;" se_borro =" true;" se_borro =" false;" nodo_izq =" nodo.getIzquierdo();" nodo_der =" nodo.getDerecho();" nodo_c =" null;" raiz =" nodo_der;" nodo_c =" new" nodo =" null;" nodo_izq =" null;" se_borro =" true;" raiz =" nodo_izq;" nodo =" null;" se_borro =" true;" raiz =" nodo_der;" nodo =" null;" se_borro =" true;" raiz =" null;" se_borro =" true;" nodo ="="" recorrido =" new" nodo ="="" recorrido =" new" nodo ="="" recorrido =" new">
*/
public Nodo obtenerElemento(Object info, Nodo raiz) {
if(null == raiz) {
return raiz;
} else {
Informacion obj_info = new Informacion(info);
Informacion obj_info_pa = new Informacion( raiz.getInformacion() );
if( obj_info_pa.equals(obj_info) ) {
return raiz;
} else if( obj_info.compareTo(obj_info_pa) < num_elems =" 0;" peso =" 0;" num_h_izq =" 0;" num_h_der =" 0;" num_h_izq =" obtenerNumeroElementos(nodo.getIzquierdo());" num_h_der =" obtenerNumeroElementos(nodo.getDerecho());" peso =" num_h_izq" altura =" 0;" altura_r_izq =" 0;" altura_r_der =" 0;" altura =" 1;" ref_h_izq =" nodo.getIzquierdo();" ref_h_der =" nodo.getDerecho();" altura_r_izq =" obtenerAltura(ref_h_izq);" altura_r_der =" obtenerAltura(ref_h_der);">= altura_r_der) { // tomar en cuenta solo la rama de mayor altura
altura += altura_r_izq;
} else {
altura += altura_r_der;
}
} else if( (ref_h_izq != null) && (ref_h_der == null) ) { // si solo tiene rama izquierda
altura += obtenerAltura(ref_h_izq);
} else if( (ref_h_izq == null) && (ref_h_der != null) ) { // si solo tiene rama derecha
altura += obtenerAltura(ref_h_der);
} else if( (ref_h_izq == null) && (ref_h_der == null) ) { // si el nodo es una hoja
altura -= 1;
}
}
return altura;
}
/**
* Método de apoyo a InsertarElemento(int). Este método se encarga de
* agregar el elemento dentro del vector que representa el árbol.
* @param info Información que contendrá el nuevo nodo.
* @param nodo Nodo contra el que se compara la información.
* @return La respuesta a la pregunta ¿Se inserto el elemento?
*/
private boolean insertarElemento(Object info, Nodo nodo) {
Nodo nuevo_nodo = null;
Informacion obj_info = new Informacion(info);
Informacion obj_info_pa = new Informacion( nodo.getInformacion() );
if( obj_info.compareTo(obj_info_pa) < nuevo_nodo =" new" nuevo_nodo =" new" se_inserto =" false;" raiz =" new" se_inserto =" true;" se_inserto =" insertarElemento(info," nodo =" null;" se_borro =" false;" nodo =" obtenerElemento(info," se_borro =" borrarNodoInterior(nodo);" se_borro =" borrarNodoHoja(nodo);" se_borro =" borrarNodoRaiz(nodo);" respuesta =" false;" nodo_padre =" nodo.getPadre();" nodo_izq =" nodo.getIzquierdo();" nodo_der =" nodo.getDerecho();" nodo_c =" null;" nodo_c =" new" nodo =" null;" nodo_izq =" null;" respuesta =" true;" nodo =" null;" respuesta =" true;" nodo =" null;" respuesta =" true;" se_borro =" false;" nodo_padre =" nodo.getPadre();" nodo =" null;" se_borro =" true;" se_borro =" false;" nodo_izq =" nodo.getIzquierdo();" nodo_der =" nodo.getDerecho();" nodo_c =" null;" raiz =" nodo_der;" nodo_c =" new" nodo =" null;" nodo_izq =" null;" se_borro =" true;" raiz =" nodo_izq;" nodo =" null;" se_borro =" true;" raiz =" nodo_der;" nodo =" null;" se_borro =" true;" raiz =" null;" se_borro =" true;" nodo ="="" recorrido =" new" nodo ="="" recorrido =" new" nodo ="="" recorrido =" new">
Entradas
0 comentarios:
Publicar un comentario