Trabalho Estrutura de dados - ArvoreAVL com Interface Gráfica

Estrutura de Dados I

•

UFC

Alison Santos

16.05.2016

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

TrabalhoEdArvoreAVL/.classpath
 
	 
	 
	 
TrabalhoEdArvoreAVL/.project
 
	 TrabalhoEdArvoreAVL
	 
	 
	
	 
		 
			 org.eclipse.jdt.core.javabuilder
			 
			
		
	
	 
		 org.eclipse.jdt.core.javanature
	
TrabalhoEdArvoreAVL/.settings/org.eclipse.jdt.core.prefs
eclipse.preferences.version=1
org.eclipse.jdt.core.compiler.codegen.inlineJsrBytecode=enabled
org.eclipse.jdt.core.compiler.codegen.targetPlatform=1.8
org.eclipse.jdt.core.compiler.codegen.unusedLocal=preserve
org.eclipse.jdt.core.compiler.compliance=1.8
org.eclipse.jdt.core.compiler.debug.lineNumber=generate
org.eclipse.jdt.core.compiler.debug.localVariable=generate
org.eclipse.jdt.core.compiler.debug.sourceFile=generate
org.eclipse.jdt.core.compiler.problem.assertIdentifier=error
org.eclipse.jdt.core.compiler.problem.enumIdentifier=error
org.eclipse.jdt.core.compiler.source=1.8
TrabalhoEdArvoreAVL/bin/Readme
Você primeiro adiciona os valores, e depois clica em exibir todos, mostrará os valores inserido.
Todo vez que inserir terá que clicar em exibir, para mostrar a árvore atual.
DICA - Tente refazer para mostrar a arvore em tempo real!!
TrabalhoEdArvoreAVL/bin/ed/avl/fim/ARVORE.class
TrabalhoEdArvoreAVL/bin/ed/avl/fim/ArvoreAVLv2.class
TrabalhoEdArvoreAVL/bin/ed/avl/fim/Tela$1.class
TrabalhoEdArvoreAVL/bin/ed/avl/fim/Tela$2.class
TrabalhoEdArvoreAVL/bin/ed/avl/fim/Tela$3.class
TrabalhoEdArvoreAVL/bin/ed/avl/fim/Tela.class
TrabalhoEdArvoreAVL/src/Readme
Você primeiro adiciona os valores, e depois clica em exibir todos, mostrará os valores inserido.
Todo vez que inserir terá que clicar em exibir, para mostrar a árvore atual.
DICA - Tente refazer para mostrar a arvore em tempo real!!
TrabalhoEdArvoreAVL/src/ed/avl/fim/ARVORE.java
package ed.avl.fim;
public class ARVORE {
	
 int num, altd, alte; 
 ARVORE noDir, noEsq;
 int pX = 0,pY = 0;
}
TrabalhoEdArvoreAVL/src/ed/avl/fim/ArvoreAVLv2.java
package ed.avl.fim;
import java.awt.Color;
import java.awt.Graphics;
import javax.swing.JPanel;
@SuppressWarnings("serial")
public class ArvoreAVLv2 extends JPanel{
	
	int fat = 40;
	int linha = 1;
	
	
	Graphics g;
	
	
 public ARVORE inserir(ARVORE aux, int num) {
 
 	ARVORE novo;
 if (aux == null) {
 
 novo = new ARVORE();
 novo.num = num;
 novo.altd = 0;
 novo.alte = 0;
 novo.noEsq = null;
 novo.noDir = null;
 aux = novo;
 
 } else if (num < aux.num) {
 	
 aux.noEsq = inserir(aux.noEsq, num);
 if (aux.noEsq.altd > aux.noEsq.alte) {
 aux.alte = aux.noEsq.altd + 1;
 } else {
 aux.alte = aux.noEsq.alte + 1;
 }
 aux = balanceamento(aux);
 
 
 } else {
 aux.noDir = inserir(aux.noDir, num);
 if (aux.noDir.altd > aux.noDir.alte) {
 aux.altd = aux.noDir.altd + 1;
 } else {
 aux.altd = aux.noDir.alte + 1;
 }
 aux = balanceamento(aux);
 
 }
 
 
 return aux;// retorna a raiz
 }
 
 public void exibirArvore(ARVORE aux) {
 
 	String c;
 g = (Graphics) this.getGraphics(); 
 try{
 	if (aux != null) {
 	c = String.valueOf(aux.num);
 	//System.out.println("altura direita"+aux.altd);
 	//System.out.println("altura esquerda"+aux.alte);
 	
 	
 	
 	g.drawString(c , aux.pX, aux.pY);
 	g.setColor(Color.BLUE);
 	c.length();
 	
 	
 	g.drawOval(aux.pX-10, aux.pY-15, 20, 20);
 	
 	
 	if(aux.alte > 0 ){
 		
 		if(aux.alte == 1){
 			aux.noEsq.pX = aux.pX - fat;
 			aux.noEsq.pY = aux.pY + fat;
 			
 		}
 		else if(aux.alte>=2){
 			aux.noEsq.pX = aux.pX;
 			aux.noEsq.pY = aux.pY + fat;
 			
 			
 			//caso a altura seja maior que 2, e feito um deslocamento nos nós 
 			for(int i=0;i<aux.alte;i++){
 				aux.noEsq.pX -= fat;
 			}
 			
 		}
 		
 		exibirArvore(aux.noEsq);
 	} 
	
 	if(aux.altd > 0){
 			if(aux.altd == 1){
 				
 				aux.noDir.pX = aux.pX + fat;
 				
 				aux.noDir.pY = aux.pY + fat;
 			}
 			else if(aux.altd>=2){
 				aux.noDir.pX = aux.pX;
 				aux.noDir.pY = aux.pY + fat;
 				
 				for(int i=0;i<aux.altd;i++){
 					aux.noDir.pX += fat;
 				}
 			}
 			exibirArvore(aux.noDir); 			
 	}
 	
 
 	else
 		System.out.println("aqui");
 		aux = null;
 	
 }
 }catch(Exception e){
 	e.printStackTrace();
 }
 		
 }
 public void desenharLinha(ARVORE aux, int posX, int posY, boolean desenhar) {
		//g = this.getGraphics();
		
		if (aux!=null) {
			if(desenhar==true){
				g.drawLine( aux.pX, aux.pY,posX,posY );
				//desenhar = false;
			}
			else {desenhar = true;}
				
				
			desenharLinha(aux.noEsq,aux.pX,aux.pY,desenhar);
			
			desenharLinha(aux.noDir,aux.pX,aux.pY,desenhar);
		}
	}
 
 public ARVORE balanceamento(ARVORE aux) {
 int d, df;
 d = aux.altd - aux.alte;
 if (d == 2) {
 df = aux.noDir.altd - aux.noDir.alte;
 if (df >= 0) {
 aux = rotacao_esquerda(aux);
 } else {
 aux.noDir = rotacao_direita(aux.noDir);
 aux = rotacao_esquerda(aux);
 }
 } else if (d == -2) {
 df = aux.noEsq.altd - aux.noEsq.alte;
 if (df <= 0) {
 aux = rotacao_direita(aux);
 } else {
 aux.noEsq = rotacao_esquerda(aux.noEsq);
 aux = rotacao_direita(aux);
 }
 }
 //repaint();
 return aux;
 }
 public ARVORE rotacao_esquerda(ARVORE aux) {
 ARVORE aux1, aux2;
 aux1 = aux.noDir;
 aux2 = aux1.noEsq;
 aux.noDir = aux2;
 aux1.noEsq = aux;
 if (aux.noDir == null) {
 aux.altd = 0;
 } else if (aux.noDir.alte > aux.noDir.altd) {
 aux.altd = aux.noDir.alte + 1;
 } else {
 aux.altd = aux.noDir.altd + 1;
 }
 
 if (aux1.noEsq.alte > aux1.noEsq.altd) {
 aux1.alte = aux1.noEsq.alte + 1;
 } else {
 aux1.alte = aux1.noEsq.altd + 1;
 }
 return aux1;
 }
 public ARVORE rotacao_direita(ARVORE aux) {
 ARVORE aux1, aux2;
 aux1 = aux.noEsq;
 aux2 = aux1.noDir;
 aux.noEsq = aux2;
 aux1.noDir = aux;
 if (aux.noEsq == null) {
 aux.alte = 0;
 } else if (aux.noEsq.alte > aux.noEsq.altd) {
 aux.alte = aux.noEsq.alte + 1;
 } else {
 aux.alte = aux.noEsq.altd + 1;
 }
 
 if (aux1.noDir.alte > aux1.noDir.altd) {
 aux1.altd = aux1.noDir.alte + 1;
 } else {
 aux1.altd = aux1.noDir.altd + 1;
 }
 return aux1;
 }
 
 public ARVORE excluir(ARVORE aux, int num) {
 ARVORE p, p2;
 
 if (aux.num == num) {
 if (aux.noEsq == aux.noDir) {
 	System.out.println("1");
 return null;
 } else if (aux.noEsq == null) {
 	System.out.println("2");
 return aux.noDir;
 } else if (aux.noDir == null) {
 	System.out.println("3");
 	return aux.noEsq;
 } else {
 	System.out.println("4");
p2 = aux.noDir;
 p = aux.noDir;
 while (p.noEsq != null) {
 p = p.noEsq;
 }
 System.out.println("5");
 p.noEsq = aux.noEsq;
 
 return p2;
 }
 } else if (num > aux.num) {
 	System.out.println("6");
 aux.noDir = excluir(aux.noDir, num);
 } else if(num< aux.num){
 	System.out.println("7");
 aux.noEsq = excluir(aux.noEsq, num);
 }
 
 
 return aux;// é retornado a raiz
 }
 public ARVORE atualizar(ARVORE aux) {
 if (aux != null) {
 	aux.noEsq = atualizar(aux.noEsq);
 if (aux.noEsq == null) {
 aux.alte = 0;
 } else if (aux.noEsq.alte > aux.noEsq.altd) {
 aux.alte = aux.noEsq.alte + 1;
 } else {
 aux.alte = aux.noEsq.altd + 1;
 }
 
 aux.noDir = atualizar(aux.noDir);
 if (aux.noDir == null) {
 aux.altd = 0;
 } else if (aux.noDir.alte > aux.noDir.altd) {
 aux.altd = aux.noDir.alte + 1;
 } else {
 aux.altd = aux.noDir.altd + 1;
 }
 aux = balanceamento(aux);
 }
 return aux;
 }
 public boolean consultar(ARVORE aux, int num, boolean loc) {
 if (aux != null && loc == false) {
 if (aux.num == num) {
 loc = true;
 } else if (num < aux.num) {
 loc = consultar(aux.noEsq, num, loc);
 } else {
 loc = consultar(aux.noDir, num, loc);
 }
 }
 return loc;
 }
 
 /* public static void main(String[] args) {
 	Scanner s;
 ARVORE a = null;
 ArvoreAVLv2 minhaArvore = new ArvoreAVLv2();
 int op;
 
 s = new Scanner(System.in);
 
 
 do {
 	System.out.println("Digite 1 para inserir ");
 	System.out.println("Digite 2 para excluir ");
 	System.out.println("Digite 3 exibir esquerda");
 	System.out.println("Digite 0 para encerrar ");
 	op = s.nextInt();
 switch (op) {
 case 0:
 	System.out.println("fim");
 	break;
		case 1:
			System.out.println("Digite o valor para ser inserido"); 
			a = minhaArvore.inserir(a, s.nextInt());
			break;
		case 2:
			System.out.println("Digite o valor a ser removido");
			int num = s.nextInt();
			if (minhaArvore.consultar(a, num, false)) {
	 a = minhaArvore.excluir(a, num);
	 a = minhaArvore.atualizar(a);
	 }
			else 
				System.out.println("valor nao encontrado");
			break;
		case 3:
			minhaArvore.exibirEsquerda(a);
			break;
		case 4:
			minhaArvore.exibirDireita(a);
		default:
			break;
		}
 }while(op!=0);
 }
}*/
	
}
TrabalhoEdArvoreAVL/src/ed/avl/fim/Tela.java
package ed.avl.fim;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JOptionPane;
import javax.swing.JTextField;
@SuppressWarnings("serial")
public class Tela extends JFrame {
	ARVORE no;
	ArvoreAVLv2 arvore;
	int valor;
	public Tela(String nome) {
		super(nome);
		no = null;
		arvore = new ArvoreAVLv2();
		// arvore.setSize(300,200);
		JButton btADD = new JButton("Adicionar");
		JButton btExibir = new JButton("Exibir todos");
		JButton btExc = new JButton("Excluir valor");
		JTextField entrada = new JTextField(10);
		setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
		setResizable(false);
		btADD.addActionListener(new ActionListener() {
			@Override
			public void actionPerformed(ActionEvent arg0) {
				if (entrada.getText().equals("")) {
					JOptionPane.showMessageDialog(null, "Campo vazio");
				} else {
					try {
						String v = entrada.getText();
						valor = Integer.parseInt(v);
					} catch (NumberFormatException e) {
						e.printStackTrace();
					}
					entrada.setText("");
					if (arvore.consultar(no, valor, false) == true) {
						JOptionPane.showMessageDialog(null,
								"O valor já existe na arvore");
					} else {
						funcoes(1);
					}
				}
			}
		});
		btExibir.addActionListener(new ActionListener() {
			@Override
			public void actionPerformed(ActionEvent arg0) {
				if (no == null) {
					JOptionPane.showMessageDialog(null,
							"Nao há elementos na arvore");
				} else {
					funcoes(2);
				}
			}
		});
		btExc.addActionListener(new ActionListener() {
			@Override
			public void actionPerformed(ActionEvent arg0) {
				if (entrada.getText().equals("")) {
					JOptionPane.showMessageDialog(null, "Campo vazio");
				} else if (no == null) {
					JOptionPane.showMessageDialog(null,
							"Nao há elementos na arvore");
				} else {
					try {
						String v = entrada.getText();
						valor = Integer.parseInt(v);
					} catch (NumberFormatException e) {
						e.printStackTrace();
					}
					entrada.setText("");
					funcoes(3);
				}
			}
		});
		setSize(800, 600);
		arvore.add(btADD);
		arvore.add(entrada);
		arvore.add(btExibir);
		arvore.add(btExc);
		// arvore.setLargura(getWidth());
		// arvore.setAltura(getHeight());
		add(arvore);
		setVisible(true);
	}
	public void funcoes(int op) {
		switch (op) {
		case 0:
			System.out.println("fim");
			break;
		case 1:
			arvore.repaint();
			no = arvore.inserir(no, valor);
			System.out.println("valor inserido");
			break;
		case 2:
			no.pX = getWidth() / 2;
			no.pY = getHeight() / 3;
			arvore.exibirArvore(no);
			arvore.desenharLinha(no, no.pX, no.pY, false);
			// arvore.desenharLinha(no);
			System.out.println("");
			break;
		case 3:
			// aqui é feito primeiro uma busca na arvore para verificar se o
			// valor existe
			if (arvore.consultar(no, valor, false)) {// caso o valor retornado
														// seja true
				no = arvore.excluir(no, valor);
				no = arvore.atualizar(no);
				arvore.repaint();
			} else
				JOptionPane.showMessageDialog(null,
						"Valor não existe na arvore");
		default:
			break;
		}
	}
	@SuppressWarnings("unused")
	public static void main(String[] args) {
		Tela f = new Tela("Arvore AVL");
	}
}