Já não sei mais o quer fazer estou tentando implementar esse metodo a 2 semanas e nada.
Segundo que eu sei é assim se o nó a ser removido é folha aponto o nó anterior para null e altero o fator de balanceamento.
agora se o nó a ser removido não é folha tem que verificar se possui sub-arvore esquerda se sim verificar qual é o maior desta sub-arvore,caso não tenha sub-arvore esquerda verificar o menor da direita.após saber qual mais ser o "notroca" eu aponto o pai do notroca para null(verificando se o "notroca" estava na direita ou esq) e depois substituo o no pelo notroca depois eu verifico o fator de balanceamento.
code:
Main:
package arvoreavl;
import java.awt.event.WindowAdapter;
import java.awt.event.WindowEvent;
import java.io.IOException;
import javax.swing.JFrame;
public class ArvoreMain {
static ArAVL teste = new ArAVL();
static int[] vetor = new int[10];
private static int count = 0;
public static int getCount() {
return count;
}
public static void setCount(int i) {
count = i;
}
public static void main(String[] args) throws IOException {
vetor[0] = 34;
vetor[1] = 22;
vetor[2] = 48;
vetor[3] = 65;
vetor[4] = 39;
vetor[5] = 36;
vetor[6] = 69;
vetor[7] = 20;
vetor[8] = 60;
vetor[9] = 62;
for (int i = 0; i < args.length; i++) {
teste.insere(Integer.parseInt(args[i]));
}
JFrame f = new JFrame("BinaryTree");
f.getContentPane().add(new BinaryTreeView(teste));
// create and add an event handler for window closing event
f.addWindowListener(new WindowAdapter() {
public void windowClosing(WindowEvent e) {
System.exit(0);
}
});
f.setBounds(50, 50, 500, 400);
f.setResizable(false);
f.show();
}
}
ArAvl:
package arvoreavl;
import javax.swing.JOptionPane;
public class ArAVL {
private No raiz;
private int height;
public ArAVL() {
raiz = null;
}
private void setH(int h) {
height = h;
}
private int getH() {
return height;
}
public void insere(int valor) {
//vetor.add(valor);
setH(0);
raiz = insere(raiz, valor, getH()); // adicionar referencia
}
private No insere(No p, int valor, int h) {//adicionar referencia
if (p == null) {
p = new No(valor);
setH(1);
} else if (valor < p.dado) { // esquerda
p.esq = insere(p.esq, valor, getH());
if (getH() == 1) {
switch (p.bal) {
case 1:
p.bal = 0;
setH(0);
break;
case 0:
p.bal = -1;
break;
case -1:
p = caso1(p);
setH(0);
break;
}
}
} else if (valor > p.dado) { // direita
p.dir = insere(p.dir, valor, h);
if (getH() == 1) {
switch (p.bal) {
case -1:
p.bal = 0;
setH(0);
break;
case 0:
p.bal = 1;
break;
case 1:
p = caso2(p);
setH(0);
break;
}
}
}
return p;
}
private No caso1(No p) {
No u, v;
u = p.esq;
// caso 1.1 : rotação direita1
if(u != null){
if (u.bal == -1) {
System.out.println("Rotação Direita");
p.esq = u.dir;
u.dir = p;
p.bal = 0; // ajustar o balanceamento de p
p = u;
} else { // caso 1.2 : rotação dupla direita
System.out.println("Rotação Dupla Direita");
v = u.dir;
u.dir = v.esq;
p.esq = v.dir;
v.esq = u;
v.dir = p;
if (v.bal == -1) {
p.bal = 1;
} else {
p.bal = 0;
}
if (v.bal == 1) {
u.bal = -1;
} else {
u.bal = 0;
}
p = v;
}
p.bal = 0;
return p;
}
else
return p;
}
private No caso2(No p) {
No z, y;
z = p.dir;
//caso 2.1: Rotação esquerda
if (z.bal == 1) {
System.out.println("Rotação Esquerda");
p.dir = z.esq;
z.esq = p;
p.bal = 0;
p = z;
} //caso 2.2: Rotação esquerda dupla
else {
System.out.println("Rotação Dupla Esquerda");
y = z.esq;
z.esq = y.dir;
p.dir = y.esq;
y.esq = p;
y.dir = z;
if (y.bal == 1) {
p.bal = -1;
} else {
p.bal = 0;
}
if (y.bal == -1) {
z.bal = 1;
} else {
z.bal = 0;
}
p = y;
}
p.bal = 0;
return p;
}
public void preOrdem() {
preOrdem(raiz);
}
private void preOrdem(No no) {
if (no == null) {
return;
}
System.out.println(no.dado + "");
preOrdem(no.esq);
preOrdem(no.dir);
}
No getRoot() {
return raiz;
}
public void Remove(int dado) {
No r = raiz;
No pai = getPai(dado, r); //pai do no a ser deletado
No veNo = getNo(dado, r); //no a ser deletado
No troca;
No trocaPai;
if (veNo == r) { // se o nó a ser removido é a raiz manipulo diretamente a raiz
if (veNo.esq != null) {//possui sub-arvore esquerda
troca = verMaiorEsquerda(veNo.esq);//mando a sub esquerda
trocaPai = getPai(troca.dado, r);//acho o pai do nó a ser trocado
if (veNo.esq == troca) { // verifico se o primeiro elemento a esquerda é o que vou trocar
No nodir = veNo.dir;
veNo.esq = null;
troca.dir = nodir;
if(troca.bal == -1)
raiz = troca;
} else {//caso não seja o primeiro a esquerda
trocaPai.dir = null;
No nodir = veNo.dir;//sub-arvore direita
No noesq = veNo.esq;//sub arvore esquerda
veNo = troca;
veNo.dir = nodir;//atribuo as sub arvores
veNo.esq = noesq;
raiz = veNo; // altero a raiz
}/*
switch (trocaPai.esq.bal) {
case 1:
trocaPai.bal = 0;
setH(0);
break;
case 0:
trocaPai.bal = -1;
break;
case -1:
trocaPai = caso1(trocaPai);
setH(0);
break;
}*/
} else {
troca = verMenorDireita(veNo.dir);//mando a sub direita
trocaPai = getPai(troca.dado, r);
if (veNo.dir == troca) {
veNo.dir = null;
veNo = troca;
} else {
No nodir = veNo.dir;
No noesq = veNo.esq;
veNo = troca;
veNo.dir = nodir;
veNo.esq = noesq;
trocaPai.esq = null;
}
switch (trocaPai.dir.bal) {
case -1:
trocaPai.bal = 0;
setH(0);
break;
case 0:
trocaPai.bal = 1;
break;
case 1:
trocaPai = caso2(trocaPai);
setH(0);
break;
}
}
} else {
if (veNo == null) {
JOptionPane.showMessageDialog(null, "Não ha elementos a serem removidos");
} else {
if (veNo.esq == null && veNo.dir == null) {//No a ser removido é folha
if (pai.esq == veNo) {//No a ser removido é folha esquerda aponto para null
pai.esq = null;
pai.bal = 0;
if (pai.esq != null || pai.dir != null) {
switch (pai.dir.bal) {
case 1:
pai.dir.bal = 0;
setH(0);
break;
case 0:
pai.dir.bal = -1;
break;
case -1:
pai = caso1(pai.dir);
setH(0);
break;
}
}
}
if (pai.dir == veNo) {//No a ser removido é folha direita aponto para null
pai.dir = null;
pai.bal = 0;
if(pai.esq != null){
pai.bal = -1;
}
/*if (pai.esq != null || pai.dir != null) {
switch (pai.bal) {
case -1:
pai.bal = 0;
setH(0);
break;
case 0:
pai.bal = 1;
break;
case 1:
pai = caso2(pai);
setH(0);
break;
}
}*/
}
} else {//No a ser removido não é folha,verificar se tem sub-arvore esquerda se sim pegar o maior elemento dela,se não o menor da direita
if (veNo.esq != null) {//possui sub-arvore esquerda
troca = verMaiorEsquerda(veNo.esq);//mando a sub esquerda
trocaPai = getPai(troca.dado, r);
if (veNo.esq == troca) {
if(veNo.dir != null){
troca.bal = 1;
}
else{
troca.bal = -1;
}
No nodir = veNo.dir;
veNo.esq = null;
veNo = troca;
veNo.dir = nodir;
pai.dir = veNo;
} else {
if(veNo.esq != null){
trocaPai.bal = -1;
}
else{
trocaPai.bal = 1;
}
No nodir = veNo.dir;
No noesq = veNo.esq;
veNo = troca;
veNo.dir = nodir;
veNo.esq = noesq;
trocaPai.dir = null;
}
if(trocaPai.esq != null){
switch (trocaPai.esq.bal) {
case 1:
trocaPai.esq.bal = 0;
setH(0);
break;
case 0:
trocaPai.esq.bal = -1;
break;
case -1:
trocaPai = caso1(trocaPai.esq);
setH(0);
break;
}
}} else {
troca = verMenorDireita(veNo.dir);//mando a sub direita
trocaPai = getPai(troca.dado, r);
if (veNo.dir == troca) {
No noesq = veNo.esq;
veNo.dir = null;
veNo = troca;
veNo.esq = noesq;
pai.esq = veNo;
} else {
No nodir = veNo.dir;
No noesq = veNo.esq;
veNo = troca;
veNo.dir = nodir;
veNo.esq = noesq;
trocaPai.esq = null;
}
if (trocaPai.dir != null) {
switch (trocaPai.dir.bal) {
case -1:
trocaPai.dir.bal = 0;
setH(0);
break;
case 0:
trocaPai.dir.bal = 1;
break;
case 1:
trocaPai = caso2(trocaPai.dir);
setH(0);
break;
}
}
}
}
}
}
}
private No getPai(int dado, No r) {
boolean achou = false;
boolean avanco = false;
No volta = null;
if (r.dado == dado) {
achou = true;
}
while (r != null && !achou) {
No aux = r;
if (aux.dir != null) {
if (aux.dir.dado == dado) {//dado é filho direito de r
volta = r;
achou = true;
}
}
if (r.esq != null) {
if (r.esq.dado == dado) {
volta = r;
achou = true;
}
}
if (dado > r.dado) {
r = r.dir;
avanco = true;
}
if (!avanco) {
if (dado < r.dado) {
r = r.esq;
}
}
avanco = false;
}
return volta;
}
private No getNo(int dado, No r) {
boolean achou = false;
No volta = null;
while (r != null && !achou) {
if (dado > r.dado) {
r = r.dir;
}
if (dado < r.dado) {
r = r.esq;
}
if (dado == r.dado) {
volta = r;
achou = true;
}
}
return volta;
}
private No verMaiorEsquerda(No subEsq) {//verifico o maior da esquerda
No aux = subEsq;
No volta = null;
if (aux.dir == null) {
volta = aux;
}
while (aux != null) {
if (aux.dir != null) {
volta = aux.dir;
}
aux = aux.dir;
}
return volta;
}
private No verMenorDireita(No subDir) {
No aux = subDir;
No volta = null;
if (aux.esq == null) {
volta = aux;
}
while (aux != null) {
if (aux.esq != null) {
volta = aux.esq;
}
aux = aux.esq;
}
return volta;
}
}
binarytreeviewer:
package arvoreavl;
/*
* Programming graphical user interfaces
* Example: BinaryTreeView.java
* Jarkko Leponiemi 2003
*/
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import java.util.*;
/**
* A class representing a graphical view of a binary tree.
*/
public class BinaryTreeView extends JPanel implements ActionListener {
// the binary tree
private ArAVL tree = null;
// the node location of the tree
private HashMap nodeLocations = null;
// the sizes of the subtrees
private HashMap subtreeSizes = null;
// do we need to calculate locations
private boolean dirty = true;
// space between nodes
private int parent2child = 20, child2child = 30;
// helpers
private Dimension empty = new Dimension(0, 0);
private FontMetrics fm = null;
public BinaryTreeView(ArAVL tree) {
this.tree = tree;
nodeLocations = new HashMap();
subtreeSizes = new HashMap();
registerKeyboardAction(this, "add", KeyStroke.getKeyStroke(KeyEvent.VK_A, 0), WHEN_IN_FOCUSED_WINDOW);
registerKeyboardAction(this, "delete", KeyStroke.getKeyStroke(KeyEvent.VK_D, 0), WHEN_IN_FOCUSED_WINDOW);
}
// event handler for pressing "A"
public void actionPerformed(ActionEvent e) {
if (e.getActionCommand().equals("add")) {
if (ArvoreMain.getCount() != 10) {
int i = ArvoreMain.getCount();
tree.insere(ArvoreMain.vetor[i]);
ArvoreMain.setCount(i + 1);
dirty = true;
repaint();
}
//}
}
if (e.getActionCommand().equals("delete")) {
int i = ArvoreMain.getCount();
if (i > 9) {
i--;
}
if (i > 0 && i < 10) {
tree.Remove(ArvoreMain.vetor[i]);
ArvoreMain.setCount(i - 1);
dirty = true;
repaint();
}
}
}
// calculate node locations
private void calculateLocations() {
nodeLocations.clear();
subtreeSizes.clear();
No root = ArvoreMain.teste.getRoot();
if (root != null) {
calculateSubtreeSize(root);
calculateLocation(root, Integer.MAX_VALUE, Integer.MAX_VALUE, 0);
}
}
// calculate the size of a subtree rooted at n
private Dimension calculateSubtreeSize(No n) {
if (n == null) {
return new Dimension(0, 0);
}
int i = n.dado;
Dimension ld = calculateSubtreeSize(n.esq);
Dimension rd = calculateSubtreeSize(n.dir);
int h = fm.getHeight() + parent2child + Math.max(ld.height, rd.height);
int w = ld.width + child2child + rd.width;
Dimension d = new Dimension(w, h);
subtreeSizes.put(n, d);
return d;
}
// calculate the location of the nodes in the subtree rooted at n
private void calculateLocation(No n, int left, int right, int top) {
if (n == null) {
return;
}
Dimension ld = (Dimension) subtreeSizes.get(n.esq);
if (ld == null) {
ld = empty;
}
Dimension rd = (Dimension) subtreeSizes.get(n.dir);
if (rd == null) {
rd = empty;
}
int center = 0;
if (right != Integer.MAX_VALUE) {
center = right - rd.width - child2child / 2;
} else if (left != Integer.MAX_VALUE) {
center = left + ld.width + child2child / 2;
}
int i = n.dado;
String s = String.valueOf(i);
int width = fm.stringWidth(s);
Rectangle r = new Rectangle(center - width / 2 - 3, top, width + 6, fm.getHeight());
nodeLocations.put(n, r);
calculateLocation(n.esq, Integer.MAX_VALUE, center - child2child / 2, top + fm.getHeight() + parent2child);
calculateLocation(n.dir, center + child2child / 2, Integer.MAX_VALUE, top + fm.getHeight() + parent2child);
}
// draw the tree using the pre-calculated locations
private void drawTree(Graphics2D g, No n, int px, int py, int yoffs) {
if (n == null || n.dado == 0) {
return;
}
Rectangle r = (Rectangle) nodeLocations.get(n);
g.draw(r);
int i = n.dado;
String s = String.valueOf(i);
g.drawString(s.toString(), r.x + 3, r.y + yoffs);
if (px != Integer.MAX_VALUE) {
g.drawLine(px, py, r.x + r.width / 2, r.y);
}
drawTree(g, n.esq, r.x + r.width / 2, r.y + r.height, yoffs);
drawTree(g, n.dir, r.x + r.width / 2, r.y + r.height, yoffs);
}
public void paint(Graphics g) {
super.paint(g);
fm = g.getFontMetrics();
// if node locations not calculated
if (dirty) {
calculateLocations();
dirty = false;
}
Graphics2D g2d = (Graphics2D) g;
g2d.translate(getWidth() / 2, parent2child);
drawTree(g2d, tree.getRoot(), Integer.MAX_VALUE, Integer.MAX_VALUE, fm.getLeading() + fm.getAscent());
fm = null;
}
public static void main(String[] args) {
ArAVL tree = new ArAVL();
for (int i = 0; i < args.length; i++) {
tree.insere(Integer.parseInt(args[i]));
}
JFrame f = new JFrame("BinaryTree");
f.getContentPane().add(new BinaryTreeView(tree));
// create and add an event handler for window closing event
f.addWindowListener(new WindowAdapter() {
public void windowClosing(WindowEvent e) {
System.exit(0);
}
});
f.setBounds(50, 50, 300, 300);
f.show();
}
}
No:
package arvoreavl;
public class No {
int dado;
No esq;
No dir;
No pai;
int bal;
public No(int valor){
dado = valor;
esq = null;
dir = null;
bal = 0;
}
}
alguem pode me dar alguma ajuda para fazer esse método de remoção?
