Arboles

Un Arbol Tiene:

1.Longitud: Cantidad de aristas; se cuenta desde la raiz a un nodo al q se hace referencia.
2.Tamaño: Cantidad de nodos.
3.Profundidad: Se da desde la raiz al nodo referido.
4.Altura: Se cuenta desde la raiz hasta el ultimo nodo mas profundo.
5.Rrcorridos:

-Preorden ---->raiz, izquierdo, derecho.
-Inorden ---->izquierdo, raiz, derecho.
-Postorden ---->izquierdo, derecho,raiz.

ARBOLES BINARIOS

Conjunto finito que tiene las siguientes caracteristicas:

•grado
•recorrido
•recorrido a lo ancho

ARBOL DE EQUILIBRIO

FE=hijos subderecho-hijos subizquierdo

ARBOL DE BUSQUEDAD

•crear
•insertar
•eliminar
•busquedad
IMPLEMENTACION DE ARBOLES

•Representación basada en cursores a los hijos
–Representación de árboles en base a vectores
•Cada componente del vector guarda un nodo con:
–el elementoque contiene
–Los índices donde se encuentran sus hijos (izqy der)
–Booleano indicando si la componente del vector estáen uso o no
•El árbol estaráformado por el índice donde se encuentra la raíz del árbol, y el vector que almacena los nodos
–Árbol vacíose representarácon valor 0como índice de la raiz

EJEMPLO1:

class NodoArbol{
NodoArbol li,ld;
int dato;
public NodoArbol(int d){
dato=d;
li=ld=null;
}
public synchronized void insertar(int d){
if(dif(li==null){
li=new NodoArbol(d);
}
else{
li.insertar(d);
}
}
if(d>dato){
if(ld==null){
ld=new NodoArbol(d);
}
else{
ld.insertar(d);
}
}
}//fin insertar
public int retornadato(){
return(dato);
}//end retornadato
}
public class Arbol {
private NodoArbol raiz;
public Arbol() {
raiz=null;
}
public NodoArbol retornaraiz(){
return(raiz);
}
public synchronized void insertarNodo(int d){
if(raiz==null){
raiz=new NodoArbol(d);
//primero=raiz;
}
else{
raiz.insertar(d);
}
}//fin insertarNodo
public synchronized String preorden(){
String pre=ayudantepreorden(raiz);
return(pre);
}
private String ayudantepreorden(NodoArbol nodo){
String cadena=new String();
if(nodo!=null){
//return;
//System.out.print(nodo.dato+" ");
cadena=cadena+String.valueOf(nodo.dato+" ");
cadena=cadena+ayudantepreorden(nodo.li);
cadena=cadena+ayudantepreorden(nodo.ld);
}
else{
cadena="";
}
return(cadena);
}
public synchronized String inorden(){
String inor=ayudanteinorden(raiz);
return(inor);
}
private String ayudanteinorden(NodoArbol nodo){
String cadena=new String();
if(nodo!=null){
// return;
cadena=cadena+ayudanteinorden(nodo.li);
cadena=cadena+nodo.dato+" ";
cadena=cadena+ayudanteinorden(nodo.ld);
}
else{cadena="";}
return(cadena);
}
public synchronized String posorden(){
String pos=ayudanteposorden(raiz);
return(pos);
}
private String ayudanteposorden(NodoArbol nodo){
String cadena=new String();
if(nodo!=null){
cadena=cadena+ayudanteposorden(nodo.li);
cadena=cadena+ayudanteposorden(nodo.ld);
cadena=cadena+nodo.dato+" ";
}
else{cadena="";}
return(cadena);
}
public synchronized int altura(NodoArbol R){
NodoArbol p=R;
int altizq=p.li==null ? 1:1+altura(p.li);
int altder=p.ld==null ? 1:1+altura(p.ld);
return(Math.max(altizq,altder));
}//end altura
public synchronized int hojas(NodoArbol R){
NodoArbol p=R;
int hojas=0;
if(p.li==null & p.ld==null){
hojas=1;
}
else{
if(p.li!=null){
hojas=hojas+hojas(p.li);
}
if(p.ld!=null){
hojas=hojas+hojas(p.ld);
}
}
return(hojas);
}//end hojas
public synchronized String ancestros(NodoArbol R,int d){
NodoArbol p=R;
String h=new String();
if (p.dato==d){
return(String.valueOf(" --> "+d));
}//end if
if (d>p.dato){
h=h+" --> "+p.dato+ancestros(p.ld,d);
}
else{
h=h+" --> "+p.dato+ancestros(p.li,d);
}
return(h);
}
}

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="\n\n",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<=nodos;i++){
dato=Integer.parseInt( JOptionPane.showInputDialog(null,"ingrese el dato a insertar en el arbol") );
arbol.insertarNodo(dato);
}
}//end construye
if(e.getSource()==pre){
JOptionPane.showMessageDialog(null,"Preorden : "+arbol.preorden());
}//end preorden
if(e.getSource()==inor){
JOptionPane.showMessageDialog(null,"Inorden : "+arbol.inorden());
}//end inorden
if(e.getSource()==pos){
JOptionPane.showMessageDialog(null,"Posorden : "+arbol.posorden());
}//end posorden
if(e.getSource()==alt){
JOptionPane.showMessageDialog(null,"Altura : "+arbol.altura(arbol.retornaraiz()));
}//end altura
if(e.getSource()==hoj){
JOptionPane.showMessageDialog(null,"Hojas : "+arbol.hojas(arbol.retornaraiz()));
}//end hojas
if(e.getSource()==anc){
int db=Integer.parseInt(JOptionPane.showInputDialog(null,"Ingrese el dato cuyos ancestros desea conocer"));
JOptionPane.showMessageDialog(null,"Ancestro : "+arbol.ancestros(arbol.retornaraiz(),db));
}
if(e.getSource()==mostrar){
mostrarArbol(arbol.retornaraiz(),aux);
c.removeAll();
c.add(most);
c.setBackground(Color.WHITE);
c.repaint();
}//end mostrar
if(e.getSource()==nuevo){
c.removeAll();
arbol=new Arbol();
cadena=new String();
most=new TextArea();
dato=0;nodos=0;
aux="R";fila=" ";columna="\n\n";
c.setBackground(Color.WHITE);
}
if(e.getSource()==creditos){
c.removeAll();
JLabel cred=new JLabel("ESTE PROGRAMA FUE DISEÑADO POR JUAN RICARDO COGOLLO OYOLA");
cred.setBounds(200,200,510,200);
cred.setFont(new Font("EuropeExt", Font.BOLD + Font.ITALIC, 14));
cred.setForeground(Color.DARK_GRAY);
c.setBackground(Color.white);
c.add(cred);
c.repaint();
}
if(e.getSource()==salir){
System.exit(0);
}
}
}
public static void main(String[] args) {
PruebaArbol ventana = new PruebaArbol("ARBOLES BINARIOS DE BUSQUEDA");
ventana.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
}
void pintar(int d,String h){
cadena=cadena+columna+fila+h+" : "+String.valueOf(d);
most = new TextArea("",200,300,0);
most.setBounds(20,200,700,500);
most.append(cadena);
most.setEditable(false);
}
void mostrarArbol(NodoArbol R,String hijo){
String h=hijo;
if(R!=null){
pintar(R.retornadato(),h);
if(R.li!=null){
aux="Izq";
fila=fila+" ";
mostrarArbol(R.li,aux);
int n=fila.length();
fila=fila.substring(10);
}
if(R.ld!=null){
aux="Der";
fila=fila+" ";
mostrarArbol(R.ld,aux);
int n=fila.length();
fila=fila.substring(10);
}
}
}
}