Desafio: Árvore Binária

24 de abril de 2005 11 respostas

rodrigo.achilles 24 de abril de 2005

Olá pessoal, estou fazendo um projeto muito legal em JAVA e OpenGL, mais serve apenas para estudo, no momento.
Gostaria desenhar uma Árvore Binária, mais o problema é que não consigo fazer com que ela desenhe dinamicamente, dependendo do seu nível.
Fiz algumas funções:

public void drawNo(double[] cor, double EsfX, double EsfY)
 	{
 		GL gl = canvas.getGL();
 		GLU glu = canvas.getGLU();
 		GLUT glut = new GLUT();
 		
 		gl.glPushMatrix();
			gl.glTranslated(EsfX, EsfY, 0.0); // Transformação da Esfera p/ Localização
			
			gl.glColor3dv(cor); // Define a Cor da Esfera
			glut.glutWireSphere(glu, 0.1, 10, 10);
		gl.glPopMatrix();
 	}
 	public void drawAresta(double[] cor, double tamLig, double LigX, double LigY, double LocX, double LocY)
 	{
 		GL gl = canvas.getGL();
 		GLU glu = canvas.getGLU();
 		GLUquadric gluQuadric = glu.gluNewQuadric();
 		
 		gl.glPushMatrix();
 			gl.glTranslated(LigX, LigY, 0.0); // Transformação da Aresta p/ a Esquerda ou Direita
			gl.glRotated(90.0, LocX, LocY, 0.0); // Transformação para Rotacionar
			
			gl.glColor3dv(cor); // Define a Cor da Aresta
			glu.gluCylinder(gluQuadric, 0.03, 0.03, tamLig, 100, 100);
		gl.glPopMatrix();
 	}

Até aí tudo bem, o problema é passar os parâmetros, gostaria de obter uma lógica para colocar dentro de um FOR, e ir adicionado automaticamente, dependendo da entrada.

Fiz um para vcs terem uma idéia:

// Define a transformacao WINDOW x VIEWPORT
		gl.glViewport(0, 0, width, height); // Define a vizualização da VIEWPORT
		gl.glMatrixMode(GL.GL_PROJECTION);
		gl.glLoadIdentity();
		
		glu.gluPerspective(50, xmax / ymax, 1, 20);
		gl.glMatrixMode(GL.GL_MODELVIEW);
		gl.glLoadIdentity();
		gl.glEnable(GL.GL_DEPTH_TEST);
		gl.glEnable(GL.GL_LIGHTING); // Ativa as luzes
		gl.glEnable(GL.GL_LIGHT0);
		gl.glEnable(GL.GL_COLOR_MATERIAL);
		glu.gluLookAt(0,0,5, 0,-2.2,0, 0,1,0);
		
		// Se estiver vazia não mostrar, senão mostrar.
		this.drawNo(corRaiz, 0.0, 0.0); // Chama o Nó Raiz

		this.drawAresta(corAresta, 0.3, 0.0, 0.0, 1.0, -1.0);
		this.drawNo(corFilho, -0.2, -0.2); // No Esquerdo

		this.drawAresta(corAresta, 0.3, 0.0, 0.0, 1.0, 1.0);
		this.drawNo(corFilho, 0.2, -0.2); // No Direito

Entenderam +/-, em vez de fazer hardcore, gostaria que fosse dinâmico…
Estou a 2 semanas para pegar uma lógica para isso.

Agradeço desde já a atenção.

11 Respostas

Filipe_Silva 24 de abr. de 2005

vc não poderia utilizar um algoritmo recursivo raiz-esquerda-direita?

fmeyer 24 de abr. de 2005

Direto do canal

[22:32] &lt;filipesilva&gt; como vc montou a sua árvore? 
[22:32] &lt;Rodrigo_o_imortal&gt; Voltando, o problema que tenho é mesmo 
com o opengl pois percorrer a árvore consigo fazer em outra classe. 
[22:32] &lt;scottys0&gt; assim o red pode ser custoso cada vez que ele for 
mostrar o valor na tela 
[22:32] &lt;filipesilva&gt; cara o red é linear. é um tapa 
[22:33] &lt;scottys0&gt; vc pode criar tb uma classe de controle que gerencie 
um objeto arvore e imprima as coordenadas desse objeto  
[22:33] &lt;filipesilva&gt; ué, mas então não entendi 
[22:33] &lt;filipesilva&gt; é 
[22:33] &lt;Rodrigo_o_imortal&gt; Tipo estou fazendo para ela cheia que não 
terá problema, é só para criar a árvore em OpenGl que estou com dificuldades. 
[22:34] &lt;filipesilva&gt; tipo draw(objetoarvore, Graphics2D g2d) 
[22:34] &lt;scottys0&gt; entao vc nao cria a arvore em gl ... vc cria um controlador 
[22:35] &lt;filipesilva&gt; digamos que vc está no contexto do desenho 
[22:35] &lt;Rodrigo_o_imortal&gt; Isso galera, o problema é pegar as coord. 
certas para que ela faça sem pegar o ramo de outra. 
[22:35] &lt;filipesilva&gt; vc tem que ter alguma forma de acessar a raiz não 
é? 
[22:35] &lt;filipesilva&gt; concorda? 
[22:35] &lt;Rodrigo_o_imortal&gt; A raiz está nas coord. 0,0 
[22:35] &lt;filipesilva&gt; to te entendo 
[22:36] &lt;filipesilva&gt; pq vc não armazena as cordenadas na árvore? 
[22:36] &lt;scottys0&gt; eu fiz isso com grafos :0 
[22:36] &lt;scottys0&gt; :p 
[22:36] &lt;Rodrigo_o_imortal&gt; Depois estou pensando primeiro em 
construir a parte esquerda, pois a direita seria simplesmente a mesmas 
coord. só que como se fosse um espelhamento. 
[22:36] &lt;scottys0&gt; armazenava a coordenada dentro dele pra quando 
imprimisse ficar legal 
[22:36] &lt;filipesilva&gt; é uma solução kra. todo nó tem uma coordenada 
[22:37] &lt;filipesilva&gt; é binária perfeita? 
[22:38] &lt;Rodrigo_o_imortal&gt; gostei, não tinha pensado nisso. Mas uma 
coisa. Gostaria que fosse inserido um nó quando o usuário inserisse em 
um campo texto. 
[22:38] &lt;filipesilva&gt; bom, desenha a árvore toda de novo ^^ 
[22:39] &lt;scottys0&gt; pensa como se fosse um applet ... cria um metodo 
draw ... 
[22:39] &lt;scottys0&gt; hehhe 
[22:39] *** GUJUSER has joined #guj 
[22:39] &lt;filipesilva&gt; na verdade tem uma solução melhor hein 
[22:39] &lt;filipesilva&gt; draw(No) { 
[22:39] &lt;Rodrigo_o_imortal&gt; Tipo dinâmico, vamos supor que ela tem 5 
níveis e o usuário insere mais um e fica 6 níveis, ou seja vai 
aumentando... então guardar, se não sei o número exato... 
[22:39] *** GUJUSER is now known as Douglas 
[22:39] *** Douglas is now known as Guest341972 
[22:39] &lt;filipesilva&gt; desenha(No) 
[22:39] &lt;scottys0&gt; ai quando vc rotacionar vc vai ter q dar refresh no 
quadro 
[22:39] &lt;filipesilva&gt; Draw(No.leftchild); 
[22:40] &lt;filipesilva&gt; Draw(no.rightchild); 
[22:40] &lt;filipesilva&gt; } 
[22:40] *** Guest341972 is now known as dsiviotti 
[22:40] &lt;scottys0&gt; mas filipesilva, se ele rotacionar vai ter q atualizar 
tudo ... :0 
[22:40] &lt;scottys0&gt; se não vai ficar "suja" a tela .. 
[22:40] &lt;filipesilva&gt; isso não resolve. mas se a cada vez que vc entrar na
 função vc utilizar uma variável de controle profundidade ae resolve 
[22:40] &lt;scottys0&gt; fala dsiviotti 
[22:41] &lt;dsiviotti&gt; tá ficando legal isso aqui! 
[22:41] &lt;dsiviotti&gt; fala 
[22:41] &lt;Rodrigo_o_imortal&gt; Blz, as funções para fazer é tranq. o 
problema é acertá-las na corrdenadas exatas, pois tem também as arestar 
[22:41] &lt;Rodrigo_o_imortal&gt; blz dsiviotii. OpenGL na mente... 
[22:41] &lt;scottys0&gt; por isso que voce tem que sentar e definir padroes de
 coordenada no papel ... antes de sentar pra desenvolver 
[22:42] &lt;filipesilva&gt; hum. mas em suma é isso ae

louds 24 de abr. de 2005

Para desenhar facilmente uma árvore binaria, você tem que desenhar ela de baixo para cima.

Carlos_Martins 25 de abr. de 2005

Cara eu fiz hah algum tempo uma calculadora, pra trab facu, com aquele esquema de infixa, posfixa e prefixa usei uma arvore binaria.Mas se vc tiver trabalhando com int vc pode utilizar este codigo abaixo dentro do for que vc insere corretamente.A questao pra desenhar eh meio complicada tentarei ajudar.

public ArvoreBin insereArv(ArvoreBin arvBin,int info)
    {
        
        if(arvBin ==null)
        {
            arvBin = new ArvoreBin(); 
            arvBin.setInfo(Integer.toString(info));
         }
        else
        {
            if(info < Integer.parseInt(arvBin.getInfo())) // info eh uma string portanto deve ser passado para int     
               arvBin.setEsq(insereArv(arvBin.getEsq(),info));
            else
               arvBin.setDir(insereArv(arvBin.getDir(),info));
        }
        return arvBin;
     }

Nunca usei este opeGl quando desenhei foi sem esta biblioteca.Fiz assim:

contrua a arvore binaria;
crie uma estrutura q identifique quem esta ligago com quem;
tipo: info=1 tem esq =4 e dir=8;
crie uma string com valores da arvore em percuso posfixo;
pegue os valores de traz pra frente(string item 3) e coloque dentro de um Vector isso ira possibilitar vc desenhar a arvore de cima para baixo(raiz pra folhas).
crie uma matriz nxn onde n eh o tam de string criada no item 3;
com a estrutura montada no item 2 monte a matriz (item 4) de forma q se i tah ligado a j coloque um(1) nesta posicao;
passe a matriz(item 5) e o vetor do item 4 para a classe abaixo:

import java.awt.*;
import javax.swing.*;
import java.awt.event.*;
import java.util.*;
import java.lang.String.*;
public class Teste extends JPanel implements MouseListener
{
   
    protected int tam;
    private Vector vetPonto;
    private Vector vetPosFixa;
    public Teste(matriz [][] mat,Vector vetPosFixa)
    {
        this.setBackground(Color.yellow);
        addMouseListener(this);
        vetPonto = new Vector();
        this.vetPosFixa = vetPosFixa;
        tam=mat.length;
    }
    public int getTam()
    {
        return this.tam;
    }
    public void setTam(int tam)
    {
        this.tam = tam;
    }
   
    public void setVetPonto()
    {
        vetPonto.removeAllElements();
    }
    public void paint(Graphics g)
    {
       super.paint(g);
       if(vetPonto.size()>0)
       {
           
           tam--;
           if(tam > 0)
           {
               for (int i = 0; i < vetPonto.size(); i++)
               {
                  Point ptX  = (Point)vetPonto.get(i);
                  String s = (String)vetPosFixa.get(i);
                  g.setColor(Color.black);
                  g.fillOval((int)ptX.getX(),(int)ptX.getY(), 15,15);
                  g.setColor(Color.white);
                  g.drawString(s,(int)ptX.getX() + (15/2 - 5), 
                         (int)ptX.getY() + (15/2 + 5));
                }
            }
            else
            {
                for(int i=0;i&lt;vetPonto.size();i++)
                {
                    Point ptX = (Point)vetPonto.get(i);
                    for(int j=0;j&lt;vetPonto.size();j++)
                    {
                       
                         if(mat[i][j]==1)
                         {
                             Point ptY = (Point)vetPonto.get(j);
                             g.setColor(Color.blue);
                            g.drawLine((int)ptX.getX() + (15/2), 
                                  (int)ptX.getY() + (15/2),
                                  (int)ptY.getX() + (15/2), 
                                  (int)ptY.getY() + (15/2));
                          }     
                    }
                }
           }  
           for (int i = 0; i &gt;< vetPonto.size(); i++)
           {
                    Point ptX  = (Point)vetPonto.get(i);
                    String s = (String)vetPosFixa.get(i);
                    g.setColor(Color.black);
                    g.fillOval((int)ptX.getX(),(int)ptX.getY(), 15,15);
                    g.setColor(Color.white);
                    g.drawString(""+ i,(int)ptX.getX() + (15/2 - 5), 
                         (int)ptX.getY() + (15/2 + 5));
           }
      }
    }  
    public void mouseClicked(MouseEvent e)
    {
         if(tam > 0)
         {
            vetPonto.add(e.getPoint());
            repaint();
         }
         else
            JOptionPane.showMessageDialog(null,"Número de vértices alcançado: "+ vetPonto.size()); 
    } 
    public void mouseEntered(MouseEvent e)
    {
    }
    public  void mouseExited(MouseEvent e)
    {
    }
    public  void mousePressed(MouseEvent e)
    {
    }
    public  void mouseReleased(MouseEvent e)
    {
    }
//main soh para teste
/*
    public static void main()
    {
        JFrame frame = new JFrame();
        frame.setSize(500,400);
        frame.getContentPane().add(new Teste(5));
        frame.show();
    }
*/
    
}

Eh isto ai qq coisa dah um toque!!!

rodrigo.achilles 25 de abr. de 2005

Olá pessoal,
Bom, primeiramente, obrigado a todos.

Segundo, valeu Carlos dei uma olhada e vi que vc fazia com pontos fixos, e esse era meu problema pois gostaria de fazer dinamicamente, iria colocando em pontos diferentes para que se encaixe na tela conforme a quantidade de níveis da minha árvore. Obrigao mesmo.

Terceiro, valeu fillipe, scottys0, a galera ajudou pra caramba. Muito agradecido.

E por fim e desanimadora linha… DESISTO! :x Fui vencido pelo cansaço. quase uma semana e consegui colocar até o nível 3, depois disse ele desanda… Vou fazer com pontos Fixos, até um nível pré determinado.
Quando quiser colocar um Nó a mais do nível, vai acusar erro. É melhor.
Minha cabeça vai espludir, pensando em uma árvore com um número N de níveis.

agradeço a todos e com tristeza vou desistir.

Abraços.

escordeiro 25 de abr. de 2005

Primeiro: fiquei com preguiça de ler as respostas imensas acima, por isso ignore qualquer coisa que eu dizer que já tenha sido citada ou entre em conflito com as respostas do pessoal, ok?

Segundo: não basta você, a cada nível, diminuir a distância horizontal entre os nós do mesmo nível???

Terceiro: desiste não…você só cresce se apanhar e se levantar; desistir é muito fácil

rodrigo.achilles 25 de abr. de 2005

Olá pessoal,

Valeu Eduardo, pela força. Vou tentar...

Eu consegui como eu disse, apenas os níveis 1, 2 e 3, acima disso fica ruim.

int nivel = 4;
		double posX = 0.0, posY = 0.0, novoPosX = 0.0, antPosX = 0.0, antPosY = 0.0, numFilhos = 0.1, disNo = 0.4;
		double tamLig = 0.3;
		
		// Atribuições das variáveis
		for ( int i = 2; i <= nivel; i++ )
			numFilhos *= 2;
		
		for ( int i = 3; i <= nivel; i++ )
			tamLig *= 2;
		
		posX = numFilhos;
		posY = numFilhos;
		
		// Se estiver vazia não mostrar, senão mostrar.
		if ( nivel != 0 )
		{
			if ( nivel >= 2 )
			{
				this.drawAresta(corAresta, tamLig, 0.0, 0.0, 1.0, -1.0);
				this.drawNo(corFilho, -posX, -posY); // Nó Esquerdo
				this.drawText(-posX, -posY, 0.2, 1.0, 1.0, 1.0, "2");
				
				this.drawAresta(corAresta, tamLig, 0.0, 0.0, 1.0, 1.0);
				this.drawNo(corFilho, posX, -posY); // Nó Direito
				this.drawText(posX, -posY, 0.2, 1.0, 1.0, 1.0, "3");
			}
			if ( nivel >= 3 )
			{
				tamLig /= 2;
				antPosX = posX;
				antPosY = posY;
				posX = 0.2;
				posY += 0.2;
				
				for ( int i = 3; i <= nivel; i++ )
				{
					novoPosX = posX + disNo;
					for ( int j = 0; j < numFilhos; j++ )
					{
						antPosX = (posX + novoPosX) / 2;
						this.drawAresta(corAresta, tamLig, -antPosX, -antPosY, 1.0, 1.0);
						this.drawNo(corFilho, -posX, -posY); // Nó Direito
						this.drawText(-posX, -posY, 0.2, 1.0, 1.0, 1.0, "4");
						
						this.drawAresta(corAresta, tamLig, -antPosX, -antPosY, 1.0, -1.0);
						this.drawNo(corFilho, -novoPosX, -posY); // Nó Esquerdo
						this.drawText(-(posX + disNo), -posY, 0.2, 1.0, 1.0, 1.0, "5");
						
						this.drawAresta(corAresta, tamLig, antPosX, -antPosY, 1.0, -1.0);
						this.drawNo(corFilho, novoPosX, -posY); // Nó Esquerdo
						this.drawText((posX + disNo), -posY, 0.2, 1.0, 1.0, 1.0, "7");
						
						this.drawAresta(corAresta, tamLig, antPosX, -antPosY, 1.0, 1.0);
						this.drawNo(corFilho, posX, -posY); // Nó Direito
						this.drawText(posX, -posY, 0.2, 1.0, 1.0, 1.0, "6");
						antPosX = posX;
						antPosY = posY;
						novoPosX = posX + disNo;
						posX += disNo;
					}
					antPosX = posX;
					antPosY = posY;
					disNo += disNo;
					posX += disNo;
					posY += 0.2;
					tamLig /= 2;
					numFilhos /=2;
				}
			}
			// Desenha o Nó Raiz
			this.drawNo(corRaiz, 0.0, 0.0);
			this.drawText(0.0, 0.0, 0.2, 1.0, 1.0, 1.0, "1");
		}

Com as funções que eu mostrei na 1ª msn. acima usei no código acima para gerar os gráficos.

E deêm uma olhada como ficou:
Nível 2:
[img]http://www.rodrigoachilles.kit.net/nivel2.gif[/img]
Nível 3:
[img]http://www.rodrigoachilles.kit.net/nivel3.gif[/img]
Nível 4:
[img]http://www.rodrigoachilles.kit.net/nivel4.gif[/img]

Tá muito difícil. Se alguém puder me ajudar. Pois o conceito de todos, estão corretos porém na prática tá difícil de fazer.
Falta pouco, mais ao mesmo tempo falta muuuiito.

Abraços galera. :?

Davi_Campos 25 de abr. de 2005

Rodrigo, isso é complicado mesmo. Eu fiz isso em delphi numa arvore desbalanceada, dá um trabalho enorme para você pensar, tive que colocar no papel e começar a desenhar… fiz tudo no milimetrado mas funcionou.

Não lembro muito bem o que fiz mas se quiser posso te enviar o código.

Eu sei que você tem que utilizar o ultimo nivel da arvore para desenha logo o segundo nivel porque as linhas terão que sair mais abertas dependendo dos níveis.

Então um parametro importantíssimo para encontrar a posição horizontal do nó é o nível que aquela ramificação desce, o meu ainda tem um complicador a mais ela não é binária cada nó pode ter mais ou menos 40 descidas e o programa desenha direitinho, se quiser te mando.

louds 25 de abr. de 2005

Você leu minha sugestão? Desenhe de baixo para cima, fica mais facil se você fizer assim.

No primeiro passo você desenha todas folhas de maior profundidade, depois disso é só interpolar a posição dos demais nós usando a posição dos filhos. Ou seja:

desenhaTodasFolhas()
for(Nó n in nósNãoFolha())
  desenhaNó((n.esquerda.x + n.direita.x) / 2, n.profundidade)

Isso para uma árvore perfeitamente balanceada, senão dá um pouco mais de trabalho, a dica nesse caso é fingir que a árvore é perfeitamente balanceada na hora de calcular as posições.

Com isso em mãos você consegue deduzir uma fórmula de posicionamento dado o índice do nó na numeração canônica (cima para baixo, esquerda para direita).

Carlos_Martins 25 de abr. de 2005

rodrigo.achilles tente associar a forma q vc desenha com o com a busca em largura na sua arvore.Assim, o desenho serah por nivel dah direita pra esquerda(implementaçao padrao)

public void  buscaEmLargura(Arvore arv)
    {
       Fila fila = new Fila();
       fila.insereFila(arv);
       while(!fila.ehVazia())
       {
            Arvore aux = fila.removeFila();
            Arvore esq = aux.getEsq();
            Arvore dir = aux.getDir();
            if(esq==null && dir!= null)
            {
               if(vertice direito nao foi visistado)
                {
                     marque o vertice como visitado
                     fila.insereFila(dir);
                 } 
                 //chama seu metodo q desenha  para dir
            }
            else if(esq!=null && dir==null)
            {
                if(vertice esq nao foi visitado)
                {
                      marca vertice como visitado 
                      fila.insereFila(esq);
                    
                } 
                // chama seu metodo q desenha para o esq 
            }
            else if(esq!=null && dir !=null)
            {
                   if(vertice esq nao foi visitado)
                   {
                      marque vertice como visitado 
                      fila.insereFila(esq);
                    
                   }
                   if(vertice dir nao foi visitado)
                   {
                          marque vertice com visitado
                          fila.insereFila(dir)
                    } 
                    //chama metoddo q desenha os dois 

            }

no final tera sua arvore desenhada.Cara nao desiste nao o trem eh feio mesmo.Tente associar este percurso com o q vc esta usando acho q sai.Nao sei se este percurso tah certo qq coisa pegue o algoritmo na net e implemente.

rodrigo.achilles 26 de abr. de 2005

Galera, Show consegui fazer de uma maneira meio diferente. Mas consegui…

To feliz, quero agradecer a ajuda de vcs, foi muito importante, Carlos, scottys0, louds, escordeiro, Davi, Filipe, enfim… valeu mesmo.

Eu consegui fazer da esquerda para direita de baixo pra cima… meio louco de baixo para cima, mais ficou certinho, qq nível fica certo, é dinâmico, ficou perfeito.

Só falta uma coisa agora, fiz o percurso em in ordem, blz.

Queria fazer o seguinte, queria guardar os nós de cada nível.Por exemplo:

No nível 1 = 3 -> só existe o nó raiz;

No nível 2 = 4 / 5 -> nó da esquerda e da direita;

No nível 3 = 2 / 5 . 7 -> os nós netos, que contém 4, mais no caso só tem 3.

E assim por diante.
Só isso que queria.

Estou pensando, acho que vou usar pilha para cada nível.
Vamos ver…

Abraços e muito obrigado!

Criado 24 de abril de 2005

Ultima resposta 26 de abr. de 2005

Respostas 11

Participantes 7

11 Respostas

Topicos relacionados