Arbol Binario

public class ARBOL_BINARIO
{

public Object ELIMINAR(int Clave)
{
boolean Busqueda = false;
NODOA CAMBIO;
NODOA PADRE;
NODOA SALE;
NODOA ANTES;

PADRE=RAIZ;
SALE=RAIZ;

if (Status == CONT_VACIO)
{
System.out.println("ERROR. El arbol esta vacio");
return(null);
}
else
{
while ((SALE != null) && (!Busqueda))
{
if(SALE.Clave == Clave)
{
Busqueda = true;
}
else
{
PADRE=SALE;
if(SALE.Clave > Clave)
{
SALE=PADRE.IENLACE;
}
else
{
SALE=PADRE.DENLACE;
}
}
}
if (!Busqueda)
{
System.out.println("ERROR. el dato no se encuentra");
return(null);
}
else
{
if((SALE.IENLACE == null) && (SALE.DENLACE == null))
{
CAMBIO = null;
}
else
{
if(SALE.IENLACE == null)
{
CAMBIO = SALE.IENLACE
}
else
{
if(SALE.DENLACE == null)
{
CAMBIO = SALE.DENLACE;
}
else
{
CAMBIO = SALE.IENLACE;
ANTES = CAMBIO;
while(CAMBIO.DENLACE != null)
{
ANTES=CAMBIO;
CAMBIO=CAMBIO.DENLACE;
}
if (ANTES==CAMBIO)
{
CAMBIO.DENLACE=SALE.DENLACE;
}
else
{
ANTES.DENLACE=CAMBIO.IENLACE;
CAMBIO.DENLACE=SALE.DENLACE;
CAMBIO.IENLACE=SALE.IENLACE;
}
}
if (RAIZ==SALE)
{
RAIZ=CAMBIO;
}
else
{
if(PADRE.Clave > SALE.Clave)
{
PADRE.IENLACE = CAMBIO;
}
else
{
PADRE.DENLACE = CAMBIO;
}
}
}
}
}
}
return(SALE.Informacion);
}
*/

public NODOA CONSULTAR(int Clave)
{
NODOA BUSCA;
BUSCA = RAIZ;
if (Status == CONT_VACIO)
{
System.out.println("ERROR el arbol esta vacio");
return(null);
}
else
{
while (BUSCA != null)
{
if (BUSCA.Clave == Clave)
{
return(BUSCA);
}
else if (BUSCA.Clave > Clave)
{
BUSCA=BUSCA.IENLACE;
}
else
{
BUSCA=BUSCA.DENLACE;
}
}
}
System.out.println("El elemento con clave "+ Clave +"no se encontro");
return(null);
}

public int ESTADO()
{
return(Status);
}

public String RECORRE_PREORDEN()
{
PILA_ENCADENADA PILA= new PILA_ENCADENADA();
NODOA P;
String Recorrido = "RECORRIDO PRE ORDEN \n ================== \n";
String Padre = " ";

P=RAIZ;

while ((P != null) || (PILA.ESTADO() != CONT_VACIO))
{
if(P != null)
{
if (P != RAIZ)
{
Recorrido = Recorrido + "Clave: " + P.Clave + " Informacion: " + P.Informacion.toString() +" Hijo " + Padre + "\n";
}
else
{
Recorrido = "--- Nodo RAIZ --- \n";
Recorrido = Recorrido + "Clave: " + P.Clave + " Informacion: " + P.Informacion.toString() +"\n";
}

PILA.INSERTAR(P);
Padre = "Izquierdo de " + P.Clave;
P=(NODOA)P.IENLACE;

}
else
{
P=(NODOA)PILA.ELIMINAR();
Padre = "Derecho de " + P.Clave;
P=P.DENLACE;
}
}
return (Recorrido);
}

public String RECORRE_INORDEN()
{
PILA_ENCADENADA PILA = new PILA_ENCADENADA();
NODOA P;
String Recorrido = "RECORRIDO IN ORDEN \n ================== \n";

P=RAIZ;

while ((P != null) || (PILA.ESTADO() != CONT_VACIO))
{
if(P != null)
{
PILA.INSERTAR(P);
P=P.IENLACE;
}
else
{
P=(NODOA)PILA.ELIMINAR();
Recorrido = Recorrido + "Clave: " + P.Clave + " Informacion: " + P.Informacion.toString() +"\n";
P=P.DENLACE;
}
}
return (Recorrido);
}

}

/*
* ESTRUCTURAS DE DATOS Y ALGORITMOS
*
* Capitulo 8 Estructuras en Arbol
* Ejercicio Clase ARBOL_BINARIO
*
* Lenguaje: Java 2 - SDK 1.3
*
*/

import javax.swing.*;
import java.awt.*;
import java.awt.event.*;
import java.text.*;

public class EJERCICIO_ARBOL_BINARIO extends JApplet
{
private ARBOL_BINARIO AB = new ARBOL_BINARIO();
private ValidadorTipo ValidadorDato = new ValidadorTipo();
private ValidadorTipo ValidadorClave = new ValidadorTipo();

public void init()
{
setContentPane(ConstruirGUI());
}

JPanel ConstruirGUI()
{

final JLabel lblClave = new JLabel("Clave");
final JTextField txtClave = new JTextField(30);

final JLabel lblDato = new JLabel("Dato");
final JTextField txtDato = new JTextField(30);

final JLabel lblRecorrido = new JLabel("Recorrido");
final JTextArea txtRecorrido = new JTextArea(10,30);
txtRecorrido.setLineWrap(true);
txtRecorrido.setWrapStyleWord(true);

final JLabel lblPadre = new JLabel("PADRE");
final JTextField txtPadre = new JTextField(10);
final JLabel lblInfoPadre = new JLabel("Informacion");

final JLabel lblHI = new JLabel("HIJO IZQUIERDO");
final JTextField txtHI = new JTextField(10);
final JLabel lblInfoHI = new JLabel("Informacion");

final JLabel lblHD = new JLabel("HIJO DERECHO");
final JTextField txtHD = new JTextField(10);
final JLabel lblInfoHD = new JLabel("Informacion");

final JScrollPane scrollRecorrido = new JScrollPane(txtRecorrido);
scrollRecorrido.setVerticalScrollBarPolicy(JScrollPane.VERTICAL_SCROLLBAR_ALWAYS);

final JComboBox comboTipo = ValidadorDato.ConstruirCombo();
ValidadorClave.EstablecerTipo(ValidadorClave.ENTERO);
ValidadorDato.EstablecerTipo(ValidadorDato.CARACTER);

JButton btnEliminar = new JButton("Eliminar");
btnEliminar.setMnemonic(KeyEvent.VK_E);

JButton btnBuscar = new JButton("Buscar");
btnBuscar.setMnemonic(KeyEvent.VK_B);
btnBuscar.addActionListener(new ActionListener()
{
public void actionPerformed(ActionEvent e)
{
if (ValidadorClave.Validar(txtPadre.getText()))
{
int cod = Integer.parseInt(txtPadre.getText());

NODOA PAPA = AB.CONSULTAR(cod);
if (PAPA != null)
{
Toolkit.getDefaultToolkit().beep();
lblInfoPadre.setText(PAPA.Informacion.toString());

if (PAPA.IENLACE != null)
{
txtHI.setText(""+PAPA.IENLACE.Clave);
lblInfoHI.setText(PAPA.IENLACE.Informacion.toString());
}
else
{
txtHI.setText("Nulo");
lblInfoHI.setText("Nulo");
}

if (PAPA.DENLACE != null)
{
txtHD.setText(""+PAPA.DENLACE.Clave);
lblInfoHD.setText(PAPA.DENLACE.Informacion.toString());
}
else
{
txtHD.setText("Nulo");
lblInfoHD.setText("Nulo");
}
}
else
{
Toolkit.getDefaultToolkit().beep();
JOptionPane.showMessageDialog(getContentPane(),"El nodo con codigo " + cod +" \n No se encontro en el ARBOL BINARIO","Error",JOptionPane.ERROR_MESSAGE);
}
}
else
{
Toolkit.getDefaultToolkit().beep();
System.out.println("-- Error en la CLAVE: "+ValidadorClave.Mensaje);
JOptionPane.showMessageDialog(getContentPane(),"Error en la CLAVE: "+ValidadorClave.Mensaje,"Error",JOptionPane.ERROR_MESSAGE);
}
}
});

JButton btnInsertar = new JButton("Adicionar");
btnInsertar.setMnemonic(KeyEvent.VK_A);
btnInsertar.addActionListener(new ActionListener()
{
public void actionPerformed(ActionEvent e)
{
if (ValidadorClave.Validar(txtClave.getText()))
{
int cod=0;

cod= Integer.parseInt(txtClave.getText());

if(ValidadorDato.Validar(txtDato.getText()))
{
boolean resultado=false;

switch(ValidadorDato.Tipo())
{
case 0:resultado = AB.INSERTAR(new Integer(txtDato.getText()),cod);break;
case 1:resultado = AB.INSERTAR(new Double(txtDato.getText()),cod);break;
case 2:resultado = AB.INSERTAR(new String(txtDato.getText()),cod);break;
}

if(resultado)
{
Toolkit.getDefaultToolkit().beep();
System.out.println("El elemento ha sido insertado en el ARBOL BINARIO");
txtClave.setText("");
txtDato.setText("");

}
else
{
Toolkit.getDefaultToolkit().beep();
if (AB.ESTADO() == AB.CONT_LLENO)
JOptionPane.showMessageDialog(getContentPane(),"El elemento no pudo ser insertado. \n El ARBOL BINARIO esta LLENO \n Por favor cierre algunas aplicaciones y vuelva a intentarlo","Error",JOptionPane.ERROR_MESSAGE);
else
JOptionPane.showMessageDialog(getContentPane(),"El elemento no pudo ser insertado. \n El elemento que quiere insertar ya se encuentera en el ARBOL BINARIO","Error",JOptionPane.ERROR_MESSAGE);
}
}
else
{
Toolkit.getDefaultToolkit().beep();
System.out.println("-- El elemento no pudo ser insertado: "+ValidadorDato.Mensaje);
JOptionPane.showMessageDialog(getContentPane(),ValidadorDato.Mensaje,"Error",JOptionPane.ERROR_MESSAGE);
}
}
else
{
Toolkit.getDefaultToolkit().beep();
System.out.println("-- Error en la CLAVE: "+ValidadorClave.Mensaje);
JOptionPane.showMessageDialog(getContentPane(),"Error en la CLAVE: "+ValidadorClave.Mensaje,"Error",JOptionPane.ERROR_MESSAGE);
}
}
});

JButton btnInorden = new JButton("Recorrer INORDEN");
btnInorden.setMnemonic(KeyEvent.VK_I);
btnInorden.addActionListener(new ActionListener()
{
public void actionPerformed(ActionEvent e)
{
txtRecorrido.setText("");
txtRecorrido.setText(AB.RECORRE_INORDEN());
}
});

JButton btnPreorden = new JButton("Recorrer PREORDEN");
btnPreorden.setMnemonic(KeyEvent.VK_P);
btnPreorden.addActionListener(new ActionListener()
{
public void actionPerformed(ActionEvent e)
{
txtRecorrido.setText("");
txtRecorrido.setText(AB.RECORRE_PREORDEN());
}
});

/***********************CREACION DE PANELES*****************************/
GridBagLayout gridbag = new GridBagLayout();
GridBagConstraints c = new GridBagConstraints();
c.fill = GridBagConstraints.HORIZONTAL;

/*********************** PANEL 1*****************************/

JPanel panel1 = new JPanel();

panel1.setAlignmentX(LEFT_ALIGNMENT);
panel1.setLayout(gridbag);

lblClave.setAlignmentX(RIGHT_ALIGNMENT);
lblDato.setAlignmentX(RIGHT_ALIGNMENT);

c.insets = new Insets(10,3,3,3);

c.gridwidth=1; c.gridheight=1;
c.gridx=2; c.gridy=1; gridbag.setConstraints(lblClave, c); panel1.add(lblClave);

c.gridwidth=3; c.gridheight=2;
c.gridx=3; c.gridy=1; gridbag.setConstraints(txtClave, c); panel1.add(txtClave);

c.gridwidth=1;c.gridheight=1;
c.gridx=2; c.gridy=3; gridbag.setConstraints(lblDato, c); panel1.add(lblDato);

c.gridwidth=3;c.gridheight=2;
c.gridx=3; c.gridy=3; gridbag.setConstraints(txtDato, c); panel1.add(txtDato);

c.gridwidth=1; c.gridheight=1;
c.gridx=2; c.gridy= 10; gridbag.setConstraints(btnInsertar, c); panel1.add(btnInsertar);
c.gridx=3; c.gridy= 10; gridbag.setConstraints(btnEliminar, c); panel1.add(btnEliminar);

/*********************** PANEL 2*****************************/

JPanel panel2 = new JPanel();

panel2.setAlignmentX(LEFT_ALIGNMENT);
panel2.setLayout(gridbag);

lblRecorrido.setAlignmentX(LEFT_ALIGNMENT);

c.insets = new Insets(10,3,3,3);

c.gridwidth =1; c.gridheight=1;
c.gridx=2; c.gridy=1; gridbag.setConstraints(lblRecorrido, c); panel2.add(lblRecorrido);

c.gridwidth =4; c.gridheight=4;
c.gridx=2; c.gridy=3; gridbag.setConstraints(scrollRecorrido, c); panel2.add(scrollRecorrido);

c.gridwidth =2; c.gridheight=1;
c.gridx=1; c.gridy=8; gridbag.setConstraints(btnInorden, c); panel2.add(btnInorden);
c.gridx=3; c.gridy=8; gridbag.setConstraints(btnPreorden, c); panel2.add(btnPreorden);

/*********************** PANEL 3*****************************/

JPanel panel3 = new JPanel();

panel3.setAlignmentX(LEFT_ALIGNMENT);
panel3.setLayout(gridbag);

c.fill = GridBagConstraints.NONE;
c.insets = new Insets(3,3,3,3);

c.gridwidth =3; c.gridheight=1;
c.gridx=1; c.gridy=1;
JLabel lblVer = new JLabel("Digite en el cuadro superior el nodo a ser buscado");
gridbag.setConstraints(lblVer, c); panel3.add(lblVer);

c.gridwidth =1; c.gridheight=1;
c.gridx=4; c.gridy=1; gridbag.setConstraints(btnBuscar, c); panel3.add(btnBuscar);
c.gridx=2; c.gridy=3; gridbag.setConstraints(lblPadre, c); panel3.add(lblPadre);
c.gridx=2; c.gridy=4; gridbag.setConstraints(txtPadre, c); panel3.add(txtPadre);
c.gridx=2; c.gridy=5; gridbag.setConstraints(lblInfoPadre, c); panel3.add(lblInfoPadre);

c.gridx=1; c.gridy=7; gridbag.setConstraints(lblHI, c); panel3.add(lblHI);
c.gridx=1; c.gridy=8; gridbag.setConstraints(txtHI, c); panel3.add(txtHI);
c.gridx=1; c.gridy=9; gridbag.setConstraints(lblInfoHI, c); panel3.add(lblInfoHI);

c.gridx=3; c.gridy=7; gridbag.setConstraints(lblHD, c); panel3.add(lblHD);
c.gridx=3; c.gridy=8; gridbag.setConstraints(txtHD, c); panel3.add(txtHD);
c.gridx=3; c.gridy=9; gridbag.setConstraints(lblInfoHD, c); panel3.add(lblInfoHD);

/*********************** PANELES *****************************/

JTabbedPane Paneles = new JTabbedPane();
Paneles.addTab("Adicionar",null, panel1, "Permite ingresar un nuevo nodo al ARBOL BINARIO");
Paneles.addTab("Recorrer",null, panel2, "Recorra el ARBOL BINARIO en Inorden o Preorden");
Paneles.addTab("Buscar",null, panel3, "Seleccione un nodo del ARBOL BINARIO y vea sus hijos");

Paneles.setSelectedIndex(0);
JPanel PanelPrincipal = new JPanel();
PanelPrincipal.setLayout(new GridLayout(1, 1));
PanelPrincipal.add(Paneles);
/*PanelPrincipal.setPreferredSize(new Dimension(,200));*/
return PanelPrincipal;
}

public static void main(String[] args)
{
/*try {UIManager.setLookAndFeel("com.sun.java.swing.plaf.windows.WindowsLookAndFeel");} catch (Exception e) { }*/

JFrame frame = new JFrame("Ejercicio ARBOL BINARIO");
frame.addWindowListener(new WindowAdapter()
{public void windowClosing(WindowEvent e) {System.exit(0); } });

EJERCICIO_ARBOL_BINARIO eab = new EJERCICIO_ARBOL_BINARIO();
frame.setContentPane(eab.ConstruirGUI());
frame.pack();
frame.setVisible(true);
}

}
//Grafo
import java.io.*;

class Grafo
{
File file;
FileReader inFile;
FileOutputStream fo;
PrintStream out;
String line;
double time=0;
final int INFINITO=999;
double num=0;
int ren=0;
int col=0;
int Matriz[][]=new int[70][70];
int P[][]=new int[70][70];

public static void main(String[] args)
{

/*if(args.length>=1)
{
try
{
Grafo g=new Grafo(args[0]);
}
catch(IOException e)
{}
}
else */
System.out.println("De el archivo de entrada");
}

public Grafo(String fileName)throws IOException
{
file=new File(fileName);
inFile=new FileReader(file);
Reader r=new BufferedReader(inFile);
StreamTokenizer st= new StreamTokenizer(r);

st.parseNumbers();//lee numeros
// st.eollsSignificant(true);//toma en cuenta/n
int token=0;
int aux=0;

try
{
while(true)
{
token=st.nextToken();

if(token==st.TT_EOF)
break;

num=st.nval;

if(token!=st.TT_EOL)//mientras no acabe el archivo
{
col=aux;
Matriz[ren][col]=(new Double(num)).intValue();
aux++;
}
else
{
ren++;
aux=0;
}
}
col++;//el archivo debe terminar en '\n'
file = new File("R_"+fileName);
fo = new FileOutputStream(file);
out = new PrintStream(fo,true);

time = new Long(System.currentTimeMillis()).doubleValue();
out.println("Algoritmo de Floyd");
out.println();
Despliega(Matriz,"La matriz del archivo es:");
System.out.println("Wrinting R_"+fileName+"...");
Floyd();
out.println();
Despliega(Matriz,"La matriz del camino mas corto es:");
DespliegaCaminos();
time = (new Long(System.currentTimeMillis()).doubleValue()-time)/1000;
out.println();
out.println("Tiempo de ejecucion="+time+"segundos");
out.close();
}
catch(EOFException e)
{}
}
public void Floyd()
{
for(int k=0;k<col;k++)
for(int i=0;i<ren;i++)
for(int j=0;j<col;j++)
if((Matriz[i][k]+Matriz[k][j])<Matriz[i][j])
{
P[i][j]=k;
Matriz[i][j]=Matriz[i][k]+Matriz[k][j];
}
}
void camino(int inicio,int fin)
{
if(P[inicio][fin]!=0)
{
camino(inicio,P[inicio][fin]);
out.print(getPath(P[inicio][fin]));
camino(P[inicio][fin],fin);
}
}
String getPath(int x)
{
char to = inc('A',x);
return"->["+to+"]";
}
char inc(char x,int max)
{
for(int i=0;i<max;i++)
x++;
return x;
}
void Despliega(int [][]M, String men)
{
out.println(men);
for(int i=0;i<ren;i++)
{
for (int j=0;j<col;j++)
if(M[i][j] < INFINITO)//se considera oo a cualquiera >=INFINITo
out.print(M[i][j]+"\t");
else
out.print("oo"+'\t');//oo=infinito
out.println();
}
out.println("Renglones="+ren);
out.println("Columnas="+col);
}

void DespliegaCaminos()
{
out.println();
out.println("Los caminos mas cortos son:");
char A='A';//Se denotan los nodos por letras iniciando en A
char X=A;
char Y=A;

for(int i=0;i<ren;i++)
{
for(int j=0;j<col;j++)
{
if(i!=j)
{
out.print("El camino mas corto del nodo("+X+")al nodo("+Y+")es:");
out.print("["+X+"]");
camino(i,j);
out.print("->["+Y+"]");
out.print("y tiene un costo de:"+Matriz[i][j]);
out.println();
}
Y++;
}
X++;
Y=A;
}
}
}