A Arvore Binaria
Por: Caio Romulo • 25/5/2021 • Trabalho acadêmico • 510 Palavras (3 Páginas) • 178 Visualizações
package arvorebinaria;
import java.io.*;
import java.util.*;
public class No {
public long item;
public No dir;
public No esq;
}
----------------------------------------
package arvorebinaria;
public class Tree {
private No root;
public Tree() {
root = null;
}
public void inserir(long v) {
No novo = new No();
novo.item = v;
novo.dir = null;
novo.esq = null;
if (root == null)
root = novo;
else {
No atual = root;
No anterior;
while (true) {
anterior = atual;
if (v <= atual.item) {
atual = atual.esq;
if (atual == null) {
anterior.esq = novo;
return;
}
} else {
atual = atual.dir;
if (atual == null) {
anterior.dir = novo;
return;
}
}
}
}
}
public No buscar(long chave) {
if (root == null)
return null;
No atual = root;
while (atual.item != chave) {
if (chave < atual.item)
atual = atual.esq;
else
atual = atual.dir;
if (atual == null)
return null;
}
return atual;
}
public boolean remover(long v) {
if (root == null)
return false;
No atual = root;
No pai = root;
boolean filho_esq = true;
while (atual.item != v) {
pai = atual;
if (v < atual.item) {
atual = atual.esq;
filho_esq = true;
} else {
atual = atual.dir;
filho_esq = false;
}
if (atual == null)
return false;
}
if (atual.esq == null && atual.dir == null) {
if (atual == root)
root = null;
else if (filho_esq)
pai.esq = null;
else
pai.dir = null;
} else if (atual.dir == null) {
if (atual == root)
root = atual.esq;
else if (filho_esq)
pai.esq = atual.esq;
else
pai.dir = atual.esq;
} else if (atual.esq == null) {
if (atual == root)
root = atual.dir;
else if (filho_esq)
pai.esq = atual.dir;
else
pai.dir = atual.dir;
} else {
No sucessor = no_sucessor(atual);
if (atual == root)
root = sucessor;
else if (filho_esq)
pai.esq = sucessor;
else
pai.dir = sucessor;
sucessor.esq = atual.esq;
}
return true;
}
public No no_sucessor(No apaga) {
No paidosucessor = apaga;
No sucessor = apaga;
No atual = apaga.dir;
while (atual != null) {
paidosucessor = sucessor;
sucessor = atual;
atual = atual.esq;
}
if (sucessor != apaga.dir) {
paidosucessor.esq = sucessor.dir;
sucessor.dir = apaga.dir;
}
...