Boa tarde, estou querendo tirar uma dúvida de dois trabalhos que fiz, e não tive sucesso, no caso eles apresentavam erros, e eu acabei não conseguindo identificar.
Mais isso já passou, e estou querendo só tirar essa dúvida o do por que acontece isso, no caso, vou colocar até as alterações que mexi por esses dias, pra ver se conseguia algo, mais, me deu muito trabalho.
Então o primeiro que estarei passando é a Árvore AVL, no caso, do jeito que fiz ele, de primeiro, ele roda de boa, se eu colocar as variáveis fixas, mais, passou da 7 inserção ele acusa um erro, mesmo eu colocando o vetor de 256 posições. Porque acontece esse tipo de coisa, e quando eu coloco pra poder fazer a chamada, pra ir inserindo um por vez, pra fazer o tamanho do vetor e perguntando as variáveis está boa, mais o importante que é o balanceamento, nem sinal. Por favor, dá uma olhada nessas implementações, eu tenho que pegar esses macetes logo… só dou trabalho mesmo… rsrs
[code]public class AvlNode {
protected int height;
protected int key;
protected AvlNode left, right;
public AvlNode ( int Elemento ) {
this( Elemento, null, null );
}
public AvlNode ( int theElement, AvlNode lt, AvlNode rt ) {
key = theElement;
left = lt;
right = rt;
height = 0;
}
}[/code]
[code]public class AvlTree {
/private static Object arvore;/
private static Object t;
private AvlNode root = null;
public AvlTree( ) {
root = null;
}
public void clear() {
root = null;
}
public boolean isEmpty() {
return root == null;
}
public AvlNode getRootNode (){
return root;
}
/** Retorna a altura da árvore */
private static int height( AvlNode t ) {
return t == null ? -1 : t.height;
}
/**
* Retorna o maior valor ente lhs e rhs.
*/
private static int max( int lhs, int rhs ) {
return lhs > rhs ? lhs : rhs;
}
/** Retorna o fator de balanceamento da árvore com raiz t */
private int getFactor (AvlNode t) {
return height( t.left ) - height( t.right );
}
public boolean insert (int x) {
root = inserirNo (x, root);
return true;
}
private AvlNode inserirNo (int x, AvlNode t) {
if( t == null )
t = new AvlNode( x, null, null );
else if( x<t.key ) t.left = inserirNo( x, t.left );
else if( x>t.key) t.right = inserirNo( x, t.right );
t = balance (t);
return t;
}
/** Faz a chamada da rotação dupla direita e esquerda*/
public AvlNode balance (AvlNode t) {
if ( getFactor(t) == 2 ) {
if (getFactor (t.left)>0) t = doRightRotation( t );
else t = doDoubleRightRotation( t );
}
else if ( getFactor(t) == -2 ) {
if ( getFactor(t.right)<0 ) t = doLeftRotation( t );
else t = doDoubleLeftRotation( t );
}
t.height = max( height( t.left ), height( t.right ) ) + 1;
return t;
}
/** Faz a rotação simples a direita */
private static AvlNode doRightRotation( AvlNode r2 ) {
AvlNode r1 = r2.left;
r2.left = r1.right;
r1.right = r2;
r2.height = max( height( r2.left ), height( r2.right ) ) + 1;
r1.height = max( height( r1.left ), r2.height ) + 1;
return r1;
}
/** Faz a rotação simples à esquerda */
private static AvlNode doLeftRotation( AvlNode r1 ) {
AvlNode r2 = r1.right;
r1.right = r2.left;
r2.left = r1;
r1.height = max( height( r1.left ), height( r1.right ) ) + 1;
r2.height = max( height( r2.right ), r1.height ) + 1;
return r2;
}
public AvlNode search(int el) {
return search(root,el);
}
protected AvlNode search(AvlNode p, int el) {
while (p != null) {
/* se valor procurado == chave do nó retorna referência ao nó */
if (el==p.key) return p;
/* se valor procurado < chave do nó, procurar na sub-árvore esquerda deste nó */
else if (el<p.key) p = p.left;
/* se valor procurado > chave do nó, procurar na sub-árvore direita deste nó */
else p = p.right;
}
// caso chave não foi achada, retorna null
return null;
}
public void inorder() {
inorder(root);
}
protected void inorder(AvlNode p) {
if (p != null) {
inorder(p.left);
System.out.print(p.key+" - ");
inorder(p.right);
}
}
public void preorder() {
preorder(root);
}
protected void preorder(AvlNode p) {
if (p != null) {
System.out.print(p.key + " ");
preorder(p.left);
preorder(p.right);
}
}
public void postorder() {
postorder(root);
}
protected void postorder(AvlNode p) {
if (p != null) {
postorder(p.left);
postorder(p.right);
System.out.print(p.key + " ");
}
}
protected AvlNode searchFather (int el) {
AvlNode p = root;
AvlNode prev = null;
while (p != null && !(p.key==el)) { // acha o nó p com a chave el
prev = p;
if (p.key<el)
p = p.right;
else p = p.left;
}
if (p!=null && p.key==el) return prev;
return null;
}
public void displayTree() {
if (isEmpty()){
System.out.println("Árvore vazia!");
return;
}
String separator = String.valueOf(" |____ ");
System.out.println(this.root.key+"("+root.height+")");
displaySubTree(root.left, separator);
displaySubTree(root.right, separator);
}
private void displaySubTree(AvlNode node, String separator) {
if (node != null) {
AvlNode father = this.searchFather(node.key);
if (node.equals(father.left) == true) {
System.out.println(separator+node.key+"("+node.height+")"+" (ESQ)");
}else{
System.out.println(separator+node.key+"("+node.height+")"+" (DIR)");
}
displaySubTree(node.left, " "+separator);
displaySubTree(node.right, " "+separator);
}
}
public static void main (String args[]){
//AvlTree inserirNo = new AvlTree();
//ArvoreAVL arvore = new ArvoreAVL();
Scanner leia = new Scanner (System.in);
int n;
int valor;
int bal;
System.out.println("\n Digite a qtdade de posições:");
n=leia.nextInt();
System.out.println("\n Digite os valores as serem inseridos:");
for(int i =1;i<=n;i++){
valor=leia.nextInt();
t.inserirNo( valor );
}
/*
t.insert(65);
t.insert(98);
t.insert(100);
t.insert(27);
t.insert(76);
t.insert(28);
t.insert(10);
t.displayTree();*/
}
private AvlNode doDoubleRightRotation(AvlNode t) {
throw new UnsupportedOperationException("Not yet implemented");
}
private AvlNode doDoubleLeftRotation(AvlNode t) {
throw new UnsupportedOperationException("Not yet implemented");
}
}[/code]
Agora na minha árvore B é questão de implementação, tipo, na classe BSTNode tem o erro, e o netbeans pede pra criar um contrutor BSTNode(int) dentro do meu pacote. Mais ai que está, eu já tentei criar alguns construtor, mais saia desse erro e criava outro… será que minha implementação está errada?? Só queria que alguém pudesse me ajudar a entender essa minha implementação de árvore B.
[code]class BSTNode {
private BSTNode root;
private BSTNode left;
private int key;
private BSTNode right;
public boolean insert(int el) {
BSTNode p = root, prev = null;
// caso o valor já exista na árvore, não inserir e retornar false
if (search(el)!=null) return false;
// procurando um lugar para colocar o novo nó
while (p != null) {
prev = p;
if (el<p.key) p = p.left;
else p = p.right;
}
// se árvore vazia
if (root == null) root = new BSTNode(el);
else if (prev.key<el) prev.right = new BSTNode(el);
else prev.left = new BSTNode(el);
return true;
}
public BSTNode search(int el) {
return search(root,el);
}
protected BSTNode search(BSTNode p, int el) {
while (p != null) {
/* se valor procurado == chave do nó retorna referência ao nó */
if (el==p.key) return p;
/* se valor procurado < chave do nó, procurar na sub-árvore esquerda deste nó */
else if (el<p.key) p = p.left;
/* se valor procurado > chave do nó, procurar na sub-árvore direita deste nó */
else p = p.right;
}
// caso chave não foi achada, retorna null
return null;
}
/* métodos de busca recursivos */
public BSTNode searchR (int el) {
return searchR(root,el);
}
protected BSTNode searchR(BSTNode p, int el) {
if (p==null || el==p.key) return p;
else if (el<p.key) return searchR (p.left, el);
else return searchR (p.right, el);
}
protected BSTNode searchFather (int el) {
BSTNode p = root;
BSTNode prev = null;
while (p != null && !(p.key==el)) { // acha o nó p com a chave el
prev = p;
if (p.key<el)
p = p.right;
else p = p.left;
}
if (p!=null && p.key==el) return prev;
return null;
}
public void inorder() {
inorder(root);
}
protected void inorder(BSTNode p) {
if (p != null) {
inorder(p.left);
System.out.print(p.key + " ");
inorder(p.right);
}
}
public void preorder() {
preorder(root);
}
protected void preorder(BSTNode p) {
if (p != null) {
System.out.print(p.key + " ");
preorder(p.left);
preorder(p.right);
}
}
public void postorder() {
postorder(root);
}
protected void postorder(BSTNode p) {
if (p != null) {
postorder(p.left);
postorder(p.right);
System.out.print(p.key + " ");
}
}
public void deleteByCopying(int el) {
BSTNode node = null, father = null;
node = search (el) ; // procura nó a ser deletado
if (node != null && node.key==el) {
if (node!=root) father = searchFather (el); // procura pai do nó a ser deletado
if (node.right == null){ // nó não tem filho direito (segundo caso);
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) { // nó não tem filho esquerdo (segundo caso)
if (node==root) root= node.right;
else if (father.left == node) father.left = node.right;
else father.right = node.right;
}
else { // nó tem ambos os filhos: fazer remoção por cópia
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-árvore esquerda do nó
}
deleteByCopying (tmp.key); // remove por copia o nó que possui o maior valor
// da sub-arvore esquerda do nó a ser deletado
node.key = tmp.key; // copia o valor da chave do maior nó
// da subárvore 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(int el) {
BSTNode tmp = null, node = null,father = null;
node = search (el) ; // procura nó a ser deletado
if (node != null && node.key==el) {
if (node!=root) father = searchFather (el); // procura pai do nó a ser deletado
if (node.right == null){ // nó não tem filho direito (segundo caso);
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) { // nó não tem filho esquerdo (segundo caso)
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 deleção por fusão
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 nó 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 max (int i, int j){
return i>j?i:j;
}
/*void inserirNo(int valor, Object raiz) {
//public void inserirNo( int valor ){
if( raiz == null )
{
raiz = new No( valor );
}
else
{
raiz.insert( valor );
}
// }
}*/
}[/code]
[code]public class Main {
public static void main(String args[]){
// (vermelho) leitura e inserção de elementos
BSTNode arvore = new BSTNode();
Scanner leia = new Scanner (System.in);
int n;
int valor;
int bal;
System.out.println("\n Digite a qtdade de posições:");
n=leia.nextInt();
System.out.println("\n Digite os valores as serem inseridos:");
for(int i =1;i<=n;i++)
{
valor=leia.nextInt();
arvore.insert( valor );
}
/*BST b = new BST();
b.insert(5);
b.displayTree();
System.out.print("\n\nEM-ORDEM: ");
b.inorder();
System.out.print("\nPOS-ORDEM: ");
b.postorder();
System.out.print("\nPRE-ORDERM: ");
b.preorder();
System.out.println("\n");*/
}
}
public class BST {
protected BSTNode root = null;
private Object raiz;
public BST() {
}
public void clear() {
root = null;
}
public boolean isEmpty() {
return root == null;
}
public BSTNode getRootNode (){
return root;
}
}
/*//Criando metodos pelo main, pela duvida peguei pela correcao do programa
void displayTree() {
throw new UnsupportedOperationException("Not yet implemented");
}
void inorder() {
throw new UnsupportedOperationException("Not yet implemented");
}
void postorder() {
throw new UnsupportedOperationException("Not yet implemented");
}
void preorder() {
throw new UnsupportedOperationException("Not yet implemented");
}
void insert(int i) {
// if( raiz == null ){
// raiz = new No(valor);
//}else{
// raiz.inserir(valor);
//}
//}
throw new UnsupportedOperationException("Not yet implemented");
}
}*/[/code]
Muito obrigado pela paciência por lerem meus erros e tentar me ajudar!
Inté mais Ficam com DEUS!!