ejemplo arbolo binario

Iniciado por soytupadre, 25 Julio 2012, 22:07 PM

0 Miembros y 1 Visitante están viendo este tema.

soytupadre

este es un ejemplo de arbol binario de buscada, consta de 3 clases, una principal, nodo y una arbol, espero que les sirva y estudiar, practiquen es facil y divertido aprender.

public class Nodo {
    protected int  info;
    protected Nodo nizq;
    protected Nodo nder;
   
    public Nodo() {}
    public Nodo(int dato) {
        this.info = dato;
        this.nizq = null;
        this.nder = null;
    }}
public class Arbol extends Nodo {
    Nodo raiz;
   
    public Arbol () {
        this.raiz= null;
    }
   
    public void agrega(int dato) {
        Nodo nuevo = new Nodo(dato);
        raiz = agregar(raiz,nuevo);
    }
   
    public Nodo agregar(Nodo r, Nodo n) {
        if(r==null) {
            return n;
        }
        else {
            if(n.info < r.info)     r.nizq = agregar(r.nizq,n);
            else {
                if(n.info > r.info) r.nder = agregar(r.nder,n);
            }
            return r;
        }
    }
   
    public Nodo getRAIZ() {
        return raiz;
    }
   
    public int getINFO(Nodo r) {
        return r.info;
    }
   
    public Nodo getNIZQ(Nodo r) {
        return r.nizq;
    }
        public Nodo getNDER(Nodo r) {
        return r.nder;
    }
        public int hojas(Nodo r){
    if(r!=null){
        if(r.nizq==null && r.nder==null)
            return 1;
        else
            return hojas(r.nizq)+hojas(r.nder);}
    return 0;
    }
   
    public int profundidad(Nodo r){
        if(r==null)
           return 0;
        else{
             int pi = profundidad(r.nizq);
             int pd = profundidad(r.nder);
             if(pd>pi)
                 return 1 + pd;
             else
                 return 1 + pi;}
   }
     
    public int suma(Nodo r){
    if(r==null)
        return 0;
    else
        return r.info + suma(r.nizq) + suma(r.nder);
    }
        public int mayor(Nodo r){
        if(r==null)
           return -1;
        else{
             if(r.nizq==null)
               return r.info;
             else
               return mayor(r.nizq);}
    }
        public int mni(Nodo r){
    if(r!=null)
        return mayor(r.nizq);
    return r.info;
    }
   
    public int menor(Nodo r){
    if(r==null)
        return -1;
    else{
         if(r.nder==null)
            return r.info;
         else
             return menor(r.nder);
    }   }
        public int mnd(Nodo r){
    if(r!=null)
        return menor(r.nder);
    return r.info;
    }}


import java.awt.*;
import java.applet.*;
import java.awt.event.*;

public class ABB extends Applet implements ActionListener {
    Arbol     miArbol  = new Arbol();   
    String    fRID, fIRD, fIDR;
    TextField unDato;
    int       xn [] = new int [31];
    int       yn [] = new int [31];
    int       vn [] = new int [31];
    int       xa [] = new int [31];
    int       ya [] = new int [31];
    int       r     = 30;
    int       n     = -1;
    int       w     = 800;
    int       h     = 600;
   
    int       hojas = -1; //cantidad  nodos hoja
    int       profu = -1; //profundidad del árbol
    int       menor = -1; //valor del nodo  menor
    int       mayor = -1; //valor del nodo  mayor
    int       mayiz = -1; //menor nieto derecho
    int       mende = -1; //mayor nieto izquierdo
    int       total = -1; //suma nodos del  árbol

   
   
    public void init() {
        this.setLayout(null);
        this.setSize(w, h);
        setBackground(Color.orange);
       
        unDato = new TextField();
        unDato.setBounds(380,500,40,20);
        unDato.addActionListener(this);
        add(unDato);       
    }
   
    public void actionPerformed(ActionEvent e){
        if(n < 31) {
            int dato = Integer.parseInt(unDato.getText());
            unDato.setText("");
            miArbol.agrega(dato);
            prepara();
            fRID = "RID";
            RID(miArbol.getRAIZ());
            fIRD = "IRD";
            IRD(miArbol.getRAIZ());
            fIDR = "IDR";
            IDR(miArbol.getRAIZ());
            profu = miArbol.profundidad(miArbol.getRAIZ());
            hojas = miArbol.hojas(miArbol.getRAIZ());
            menor = miArbol.menor(miArbol.getRAIZ());
            mayor = miArbol.mayor(miArbol.getRAIZ());
            mayiz = miArbol.mni(miArbol.getRAIZ());
            mende = miArbol.mnd(miArbol.getRAIZ());
            repaint();
        }
    }
   
    public void paint(Graphics g) {
        g.setColor(Color.blue);
        g.drawString("cantidad  nodos hoja",10, 10);
        g.drawString("profundidad del árbol",10, 25);
        g.drawString("valor del nodo  menor",10, 40);
        g.drawString("valor del nodo  mayor",10, 55);
        g.drawString("menor nieto derecho",10, 70);
        g.drawString("mayor nieto izquierdo",10, 85);
        g.drawString("suma nodos del  árbol",10,100);
        g.drawString("=",140, 10);
        g.drawString("=",140, 25);
        g.drawString("=",140, 40);
        g.drawString("=",140, 55);
        g.drawString("=",140, 70);
        g.drawString("=",140, 85);
        g.drawString("=",140,100);

        g.drawString(Integer.toString( hojas ),149, 10);
        g.drawString(Integer.toString( profu ),149, 25);
        g.drawString(Integer.toString( mayor ),149, 40);
        g.drawString(Integer.toString( menor ),149, 55);
        g.drawString(Integer.toString( mayiz ),149, 70);
        g.drawString(Integer.toString( mende ),149, 85);
        g.drawString(Integer.toString( total ),149,100);

       
        g.drawString("RAIZ",385,10);
        if(n!=-1) {
            int i, x, y;
            for(i=0;i<=n;i++) {
                x = xn;
                y = yn;
                g.setColor(Color.cyan);
                g.fillOval(x, y, r, r);
                g.setColor(Color.blue);
                g.drawOval(x, y, r, r);
                g.drawString(Integer.toString(vn), x+ r/3, y + 3*r/5);
                g.setColor(Color.black);
                g.drawLine(xa, ya, x + r/2, y);
            }
            g.drawString(fRID, 10, 550);
            g.drawString(fIRD, 10, 570);
            g.drawString(fIDR, 10, 590);
        }
    }
   
    public void prepara() {
        n = -1;
       
        //          raiz            posición    posición   cambio    x        y
        //        del arbol        x del nodo  y del nodo   en x   anterior anterior
        recorre(miArbol.getRAIZ(),  w/2-r/2,      80,       w/4,     w/2,     15  );
    }
   
    public void recorre(Nodo rz, int x, int y, int d, int ax, int ay) {
        if(rz!=null) {
            n++;
            vn[n] = miArbol.getINFO(rz);
            xn[n] = x;
            yn[n] = y;
            xa[n] = ax;
            ya[n] = ay;
           
            recorre(miArbol.getNIZQ(rz), x - d, y+80, d/2, x +   r/8, y + 3*r/4);
            recorre(miArbol.getNDER(rz), x + d, y+80, d/2, x + 7*r/8, y + 3*r/4);
        }
    }
   
    public void RID(Nodo rz) {
        if(rz!=null) {
            fRID = fRID + " - " + Integer.toString(miArbol.getINFO(rz));
            RID(miArbol.getNIZQ(rz));
            RID(miArbol.getNDER(rz));
        }
    }

    public void IRD(Nodo rz) {
        if(rz!=null) {
            IRD(miArbol.getNIZQ(rz));
            fIRD = fIRD + " - " + Integer.toString(miArbol.getINFO(rz));
            IRD(miArbol.getNDER(rz));
        }
    }

    public void IDR(Nodo rz) {
        if(rz!=null) {
            fIDR = fIDR + " - " + Integer.toString(miArbol.getINFO(rz));
            IDR(miArbol.getNIZQ(rz));
            IDR(miArbol.getNDER(rz));
        }
    }
   
   
}