Bah… to com um problema na hora de inserir objetos do tipo Pessoa na minha arvore binaria (classe BST), não insere elementos, estou com uma duvida quanto a isso, penso que deve ter algum erro, mais não estou achando
public class Pessoa {
private String nome;
private String endereco;
private String telefone;
private String cep;
private String cidade;
private String estado;
public Pessoa(String nome, String endereco, String telefone, String cep,
String cidade, String estado) {
this.nome = nome;
this.endereco = endereco;
this.telefone = telefone;
this.cep = cep;
this.cidade = cidade;
this.estado = estado;
}
public String getNome() {
return nome;
}
public String getEndereco() {
return endereco;
}
public String getCep() {
return cep;
}
public String getCidade() {
return cidade;
}
public String getEstado() {
return estado;
}
public void setNome(String nome) {
this.nome = nome;
}
public void setEndereco(String endereco) {
this.endereco = endereco;
}
public void setCep(String cep) {
this.cep = cep;
}
public void setCidade(String cidade) {
this.cidade = cidade;
}
public void setEstado(String estado) {
this.estado = estado;
}
public String getTelefone() {
return telefone;
}
public void setTelefone(String telefone) {
this.telefone = telefone;
}
public void print(){
System.out.println("Nome: "+nome);
System.out.println("Telefone: "+telefone);
System.out.println("Endereço: "+endereco);
System.out.println("CEP: "+cep);
System.out.println("Cidade: "+cidade);
System.out.println("Estado: "+estado);
}
}
E a classe da arvore binaria
import java.io.Serializable;
public class BST implements Serializable{
private BSTNode root = null;
public BST() {
}
public void clear() {
root = null;
}
public boolean isEmpty() {
return root == null;
}
public BSTNode getRootNode() {
return root;
}
public boolean insert(Pessoa a) { // nesse método esta dando erro
BSTNode p = root, prev = null;
// caso o valor ja exista na arvore, nao inserir e retornar false
if (search(a.getNome()) == null)
return false;
// procurando um lugar para colocar o novo noh
while (p != null) {
prev = p;
if (a.getNome().compareToIgnoreCase(prev.key.getNome()) < 0)
prev = prev.left;
else
prev = prev.right;
}
// se arvore vazia
if (root == null)
root = new BSTNode(a);
else if (prev.key.getNome().compareToIgnoreCase(a.getNome()) > 0)
prev.right = new BSTNode(a);
else
prev.left = new BSTNode(a);
return true;
}
public void insereArray(Pessoa[] array){
for(int i = 0; i < array.length; i++){
this.insert(array[i]);
}
}
public boolean isCheia(){
int nivel = this.altura(root);
int valor = (int) (Math.pow(2, nivel) - 1);
if(contaNos() == valor)
return true;
else
return false;
}
public BSTNode search(String nome) {
return search(root, nome);
}
private BSTNode search(BSTNode p, String el) {
while (p != null) {
/* se valor procurado == chave do noh retorna referencia ao noh */
if (el.equalsIgnoreCase(p.key.getNome()))
return p;
/*
* se valor procurado < chave do noh, procurar na sub-arvore esquerda
* deste noh
*/
else if (el.compareToIgnoreCase(p.key.getNome()) < 0)
p = p.left;
/*
* se valor procurado > chave do noh, procurar na sub-arvore direita
* deste noh
*/
else
p = p.right;
}
// caso chave nao foi achada, retorna null
return null;
}
public BSTNode searchR(String el) {
return searchR(root, el);
}
private BSTNode searchR(BSTNode p, String el) {
if (p == null || el.equalsIgnoreCase(p.key.getNome()))
return p;
else if (el.compareToIgnoreCase(p.key.getNome()) < 0)
return searchR(p.left, el);
else
return searchR(p.right, el);
}
protected BSTNode searchFather(String el) {
BSTNode p = root;
BSTNode prev = null;
while (p != null && !(p.key.getNome().equalsIgnoreCase(el))) { // acha o noh p com a chave el
prev = p;
if (p.key.getNome().compareToIgnoreCase(el) > 0)
p = p.right;
else
p = p.left;
}
if (p != null && p.key.getNome().equalsIgnoreCase(el))
return prev;
return null;
}
public void deleteByCopying(String el) {
BSTNode node, father = null;
node = search(el); // procura noh a ser deletado
if (node != null && node.key.getNome().equalsIgnoreCase(el)) {
if (node != root)
father = searchFather(el); // procura pai do noh a ser deletado
if (node.right == null) { // noh nao tem filho direito (caso 2);
if (node == root)
root = node.left;
else if (father.left == node)
father.left = node.left;
else
father.right = node.left;
} else if (node.left == null) { // noh nao tem filho esquerdo (caso
// 2)
if (node == root)
root = node.right;
else if (father.left == node)
father.left = node.right;
else
father.right = node.right;
} else { // noh tem ambos os filhos: fazer remocao por copia
BSTNode tmp = node.left; // 1. pegando sub-arvore esquerda
while (tmp.right != null) { // 2. acha a posicao mais a direita
tmp = tmp.right; // da sub-arvore esquerda do noh
}
deleteByCopying(tmp.key.getNome()); // remove por copia o noh que possui
// o maior valor
// da sub-arvore esquerda do noh a ser deletado
node.key = tmp.key; // copia o valor da chave do maior noh
// da sub-arvore esquerda
}
} else if (root != null)
System.out.println("el " + el + " is not in the tree");
else
System.out.println("the tree is empty");
}
public void deleteByMerging(String el) {
BSTNode tmp, node, father = null;
node = search(el); // procura noh a ser deletado
if (node != null && node.key.getNome().equalsIgnoreCase(el)) {
if (node != root)
father = searchFather(el); // procura pai do noh a ser deletado
if (node.right == null) { // noh nao tem filho direito (caso 2);
if (root == node)
root = node.left;
else if (father.left == node)
father.left = node.left;
else
father.right = node.left;
} else if (node.left == null) { // noh nao tem filho esquerdo (caso
// 2)
if (root == node)
root = node.right;
else if (father.left == node)
father.left = node.right;
else
father.right = node.right;
} else { // se tem dois filhos, faz delecao por fusao
tmp = node.left; // pega sub-arvore esquerda
while (tmp.right != null)
// pega filho mais a direita da sub-arvore esquerda
tmp = tmp.right;
tmp.right = node.right; // o filho mais a direita da sub-arvore
// esquerda passa a ter
// como filho direito o filho direito do noh a ser deletado
if (root == node)
root = node.left;
else if (father.left == node)
father.left = node.left;
else
father.right = node.left;
}
} else if (root != null)
System.out.println("el " + el + " is not in the tree");
else
System.out.println("the tree is empty");
}
public int contaNos() {
int cont = 0;
cont = contaNos(root, cont);
return cont;
}
private int contaNos(BSTNode p, int cont) {
if (p != null) {
cont++;
cont = contaNos(p.left, cont);
cont = contaNos(p.right, cont);
}
return cont;
}
public int qtFolha() {
return contaFolha(root);
}
private int contaFolha(BSTNode p) {
if (p == null)
return 0;
else if(p != null)
if(p.getLeft() == null && p.getRight() == null)
return 1;
return contaFolha(p.left) + contaFolha(p.right);
}
public int altura() {
return altura(root);
}
private int altura(BSTNode p) {
if (p == null)
return 0;
return max(altura(p.left), altura(p.right)) + 1;
}
private int max(int i, int j) {
return i > j ? i : j;
}
public void inorder() {
inorder(root);
}
private void inorder(BSTNode p) {
if (p != null) {
inorder(p.left);
System.out.println("Nome: "+p.key.getNome());
System.out.println("Endereco: "+p.key.getEndereco());
System.out.println("CEP: "+p.key.getCep());
System.out.println("Cidade: "+p.key.getCidade());
System.out.println("Estado: "+p.key.getEstado());
inorder(p.right);
}
}
public void preorder() {
preorder(root);
}
private void preorder(BSTNode p) {
if (p != null) {
System.out.print(p.key.getNome() + " ");
preorder(p.left);
preorder(p.right);
}
}
public void postorder() {
postorder(root);
}
private void postorder(BSTNode p) {
if (p != null) {
postorder(p.left);
postorder(p.right);
System.out.print(p.key.getNome() + " - ");
}
}
protected int getNivel(BSTNode p, String chave, int h) {
if (p == null)
return -1;
else if (p.key.getNome().equalsIgnoreCase(chave))
return h + 1;
else if (chave.compareToIgnoreCase(p.key.getNome()) < 0)
return getNivel(p.left, chave, h + 1);
else
return getNivel(p.right, chave, h + 1);
}
public int getDescendentes(String el){
BSTNode p = this.search(el);
return numDescendentes(p);
}
private int numDescendentes(BSTNode p){
if(p != root)
return this.contaNos(p, -1);
else
return -1;
}
public String imprimeChar(int n) {
String s = "";
if (n / 100 > 0)
s = n + "";
else if (n / 10 > 0)
s = " " + n;
else
s = " " + n + " ";
return s;
}
public int getNroEspacos(int nivel, int h) {
int nro = (getNroNosNivel(h) * 2 - getNroNosNivel(nivel))
/ getNroNosNivel(nivel);
return nro;
}
public int getNroNosNivel(int nivel) {
double n = Math.pow(2, nivel - 1);
return (int) n;
}
public void imprimeNroEspacos(int n) {
for (int i = 1; i <= n; i++)
System.out.print(" ");
}
/* metodo de autoria de Leonardo Zandona - 2006/2 */
public void displayTree() {
if (isEmpty()) {
System.out.println("Arvore vazia!");
return;
}
String separator = String.valueOf(" |__");
System.out.println(this.root.key);
displaySubTree(root.left, separator);
displaySubTree(root.right, separator);
}
private void displaySubTree(BSTNode node, String separator) {
if (node != null) {
BSTNode father = this.searchFather(node.key.getNome());
if (node.equals(father.left) == true) {
System.out.println(separator + node.key.getNome() + " (ESQ)");
} else {
System.out.println(separator + node.key.getNome() + " (DIR)");
}
displaySubTree(node.left, " " + separator);
displaySubTree(node.right, " " + separator);
}
}
public static void main(String[] args){
Pessoa a = new Pessoa("Al", "A", "12345", "989", "T", "a");
Pessoa a1 = new Pessoa("E", "A", "12345", "989", "T", "a");
Pessoa a2 = new Pessoa("B", "A", "12345", "989", "T", "a");
Pessoa a3 = new Pessoa("R", "A", "12345", "989", "T", "a");
Pessoa a4 = new Pessoa("An", "A", "12345", "989", "T", "a");
Pessoa a5 = new Pessoa("Aa", "A", "12345", "989", "T", "a");
BST b = new BST();
b.insert(a);
b.insert(a1);
b.insert(a2);
b.insert(a3);
b.insert(a4);
b.insert(a5);
b.displayTree();
}
}
alguem pode me ajudar ?
