elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Trabajando con las ramas de git (tercera parte)


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación General
| | |-+  Java
| | | |-+  Arbol AVL
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Arbol AVL  (Leído 19,220 veces)
arkaos

Desconectado Desconectado

Mensajes: 4


Ver Perfil
Arbol AVL
« en: 6 Mayo 2009, 01:58 am »

Hola, necesito por favor ayuda con el codigo en java de un arbol AVL, tengo las funciones de insertado y necesito las funciones de borrado de nodos y alguna forma de visualizarlo. Muchas gracias  :huh:


En línea

juancho77


Desconectado Desconectado

Mensajes: 455


rie con demencia


Ver Perfil
Re: Arbol AVL
« Respuesta #1 en: 8 Mayo 2009, 01:34 am »

Tengo que hacer eso mismo en estos dias, cuando lo termine te lo subo si aun te hace falta


En línea

arkaos

Desconectado Desconectado

Mensajes: 4


Ver Perfil
Re: Arbol AVL
« Respuesta #2 en: 10 Mayo 2009, 15:18 pm »

bueno, muchas gracias
En línea

Amerikano|Cls


Desconectado Desconectado

Mensajes: 789


[Beyond This Life]


Ver Perfil WWW
Re: Arbol AVL
« Respuesta #3 en: 11 Mayo 2009, 01:53 am »

Yo ya lo tengo hecho,luego lo pongo  ;D
En línea





Mi blog:
http://amerikanocls.blogspot.com
juancho77


Desconectado Desconectado

Mensajes: 455


rie con demencia


Ver Perfil
Re: Arbol AVL
« Respuesta #4 en: 12 Mayo 2009, 05:05 am »

Para borrar nodos yo hice esto (siempre con arboles generales, binarios o no):

Código
  1. ListaDeHijos = nodo.obtenerHijos();
  2. padreDeNodo=nodo.obtenerPadre();
  3. posicionDeNodo=nodo.obtenerPosicionEnLista();
  4. //borrar el nodo
  5. nodo.establecerHijos(null);
  6. nodo.establecerPadre(null);
  7. //opcion1: un hijo (el primero) toma el lugar del padre
  8. if (listaDeHijos.isEmpty()==false)
  9. {
  10. nuevoHijo=listaDeHijos.obtenerPrimero();
  11. listaDeHijos.eliminarNodo(listaDeHijos.obtenerPrimero());
  12. nuevoHijo.establecerHijos(listaDeHijos);
  13. Para cada nodo de listaDeHijos hacer
  14.    nodo.establecerPadre(nuevoHijo);
  15. padreDeNodo.obtenerHijos().insertarNodoEnPosicion(posicionDeNodo,nuevoHijo);
  16. //opcion2: todos los hijos pasan a ser hijos del padre del eliminado
  17. /*
  18. * padreDeNodo.obtenerHijos().concatenarListas(listaDeHijos); //agrega los nodos hijos a los del padre del eliminado
  19. * Para cada nodo de listaDeHijos hacer
  20. *   nodo.establecerPadre(nuevoHijo);
  21. */
  22.  
  23.  

Para visualizarlo existe un algoritmo muy conocido llamado recorridoEnOrden. Es asi  (para arboles binarios, pero se puede expandir, solo hay que pensar un cachin) :
Código:
recorridoEnOrden(nodo v)
 if v tiene un hijo izquierdo
    recorridoEnOrden(v.hijoIzquierdo());
 hacer algo en v
 if v tiene un hijo derecho
    recorridoEnOrden(v.hijoDerecho());

Para dibujarlo, crea un arreglo con todos los nodos visitados en el orden obtenido por recorridoEnOrden. Si lo haces bien, el orden sera de izquierda a derecha en la coordenada x. Luego, modifica el paintComponent de algun elemento (un panel, por ejemplo) y pinta ovalos: la coordenada x del ovalo sera la ubicacion en el arreglo (+1 para ser exactos), y la coordenada y sera el resultado de obtenerAltura(nodo), función recursiva que retorna la altura de un nodo y se define:
Código:
obtenerAltura(Nodo v)
 si isRoot(v)
   retornar 0
 sino retornar 1 + obtenerAltura(v.parent());



Entendeme que te paso idea y algoritmos y no codigo para ser mas claro en la explicacion y ademas porque seguramente tu implementacion requiere datos precisos distintos a los mios (o no, pero es probable que si). Si lo que quieres es algo hecho puedes buscar en internet, o bueno, si insistes te lo paso.   :-*
En línea

Amerikano|Cls


Desconectado Desconectado

Mensajes: 789


[Beyond This Life]


Ver Perfil WWW
Re: Arbol AVL
« Respuesta #5 en: 12 Mayo 2009, 06:26 am »

Pero el que pusiste de AVL te lo equilibra?, porque no veo donde  ;), luego que me desocupe de todas estas tareas lo organizo y lo pongo que ando liado en estos momentos  :).

salu2
En línea





Mi blog:
http://amerikanocls.blogspot.com
arkaos

Desconectado Desconectado

Mensajes: 4


Ver Perfil
Re: Arbol AVL
« Respuesta #6 en: 31 Mayo 2009, 05:33 am »

gracias por las ideas, tengo un arbol pero no lo equilibra, es un arbol binario balanceado, pero no avl, ingresa los nodos por JoptionPane, el primero dato es el numero de nodos, luego el primer dato es la raiz y luego los nodos, el problema es que no me equilibra por altura, no tengo implementado las roteciones. 

Esta es la clase Arbol.java

class NodoArbol{
        NodoArbol li,ld;
        int dato;

        public NodoArbol(int d){
                dato=d;
                li=ld=null;
        }

        public synchronized void insertar(int d){

                if(d<dato){
                        if(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);
        }

}


Esta es la clase Main.java

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


public class Main extends JFrame implements ActionListener {

        Container c;
        JMenuBar menu;
        JMenu menuArc,menuMet;
        JMenuItem construye,alt,hoj,anc,salir,nuevo,inor,pos,pre;
        int dato,nodos;
        Arbol arbol;
        String aux, fila, columna, cadena;
        JTextArea most;
        JScrollPane scroll;
        BorderLayout borde;
        GridLayout gridCentro, gridSur;       
        JPanel panelCentro;

        public Main()
        {
                super("Arbol AVL");
                borde= new BorderLayout();
                c=getContentPane();
                c.setLayout(borde);
                gridCentro= new GridLayout(1,1);
                most = new JTextArea(20,20);
                most.setFont(new Font("Arial", Font.BOLD, 12));
                scroll=new JScrollPane(most);
                panelCentro= new JPanel();
                panelCentro.setLayout(gridCentro);
                panelCentro.add(scroll);
                c.add(panelCentro, borde.CENTER);

                nuevo=new JMenuItem("Nuevo");
                nuevo.addActionListener(this);

                construye=new JMenuItem("Crear AVL");
                construye.addActionListener(this);

                salir=new JMenuItem("Salir");
                salir.addActionListener(this);

                alt=new JMenuItem("Altura AVL");
                alt.addActionListener(this);

                hoj=new JMenuItem("Hojas AVL");
                hoj.addActionListener(this);

                inor=new JMenuItem("InRoden");
                inor.addActionListener(this);

                pre=new JMenuItem("PreOrden");
                pre.addActionListener(this);

                pos=new JMenuItem("PosOrden");
                pos.addActionListener(this);

                menuArc = new JMenu("Archivo");
                menuArc.add(nuevo);
                menuArc.add(construye);
                menuArc.add(salir);

                menuMet = new JMenu("Metodos");
                menuMet.add(alt);
                menuMet.add(hoj);
                menuMet.add(inor);
                menuMet.add(pos);
                menuMet.add(pre);

                menu = new JMenuBar();
                menu.add(menuArc);
                menu.add(menuMet);
                setJMenuBar(menu);
                dato=nodos=0;
                aux="R"; fila=""; columna="\n\n"; cadena="";
        }


        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);
                        }
                        mostrar();
                }//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));
                }//end ancestros


                if(e.getSource()==nuevo){
                        arbol=new Arbol();
                        cadena=new String();
                        most.setText("");
                        dato=0; nodos=0;
                        aux="R";fila="          ";columna="\n\n";
                }//end nuevo

                if(e.getSource()==salir){
                        System.exit(0);
                }//end salir


        }


        public static void main(String[] args) {
                Main ventana = new Main();
                Point ubica= new Point(200, 100);
                ventana.setLocation(ubica);
                ventana.setVisible(true);
                ventana.setSize(800, 800);
        }


        void pintar(int d,String h){
                most.setEditable(true);
                cadena=cadena+columna+fila+h+" : "+String.valueOf(d);
                most.append(cadena);
        }

        void mostrar(){        mostrarArbol(arbol.retornaraiz(),aux); }

        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);
                        } 
                }
               
               
        }//end windows


}

En línea

Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Arbol multinivel con una sola consulta
PHP
Alex_bro 6 10,313 Último mensaje 15 Agosto 2011, 22:22 pm
por Alex_bro
Error en arbol
Programación C/C++
Lateseles 2 2,451 Último mensaje 4 Noviembre 2011, 06:01 am
por do-while
Árbol de Busqueda
Programación C/C++
Chicha88 0 1,568 Último mensaje 11 Noviembre 2012, 13:53 pm
por Chicha88
arbol avl c++
Programación C/C++
jovanny12 2 4,644 Último mensaje 13 Abril 2014, 15:54 pm
por d91
duda con recorridos en arbol
Programación C/C++
andoporto 0 1,691 Último mensaje 26 Febrero 2015, 01:49 am
por andoporto
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines