Árvore de busca binária em C++[resolvido]

cesarvargas00 · Abril 3, 2010, 8:04pm

Oi pessoal tudo bom?
Será que alguem pode me ajudar com um problema de 0xC0000005: Access violation reading location?
É o seguinte, ele compila no Dev C++, porém da pau no primeiro segundo. O Código é grande e está separado em 3 arquivos : header.h , main.cpp e classes.cpp.

#include "header.h"
int main(){
	Tree teste;
cout << teste.root()->get_valor();

	

	fflush(stdin);
	getchar();
	return 0;
}
//MAIN ACIMA




#include "header.h"
bool Tree::Busca(int x, No* j){
	if(j->get_valor()==x)
		return true;
	else if(j->get_valor()>x && j->get_esq()!=NULL)
		Busca(x,j->get_esq());
		else if(j->get_valor()<x && j->get_dir()!=NULL)
			Busca(x,j->get_dir());
	return false;
}
void Tree::Insere(int x, No* j){
	No *p;
	if(j==NULL){
		p=new No();
		p->set_valor(x);
		j=p;
	}
	else if(j->get_valor()>x)
		Insere(x,j->get_esq());
		else if(j->get_valor()<x)
			Insere(x,j->get_dir());
}
void Tree::Imprime(No* p){
	
	if (p->get_esq()!=NULL)
		Imprime(p->get_esq());
	cout << p->get_valor()<< " ";
		if (p->get_dir()!=NULL)
			Imprime(p->get_dir());
}
 // FUNCOES DAS CLASSES ACIMA



#include <iostream>
#include <cstdlib>
using namespace std;

class No{
private:
	No *esq,*dir;
	
	int valor;
public:
	No(){
		this->valor=0;
		this->esq=NULL;
		this->dir=NULL;
		
		
	}
	void set_esq(No* p){esq=p;}
	void set_dir(No* p){dir=p;}
	No* get_esq(){return esq;}
	No* get_dir(){return dir;}
	int get_valor(){return valor;}
	void set_valor(int x){valor=x;}
};
class Tree{
private:
	No* raiz;
public:
	Tree(){
		raiz=NULL;
	}
	No *root(){return raiz;}
	bool Busca(int,No*);
	void Insere(int,No*);
	void Imprime(No*);
};

Acredito que o erro está no construtor No(), porém não sei onde…
Sou iniciante e desde já agradeço a paciência e a colaboração de vocês.
Obrigado !!

ViniGodoy · Abril 3, 2010, 11:58pm

O seu main pede o valor da raiz. Mas como você nunca inseriu nenhum valor, a raiz ainda é NULL. Quando vc faz getValor() sobre NULL você tem o seu problema.

Algumas dicas:

Não use o devcpp. Além de ser pré-histórico e usar uma versão antiquíssima do MinGW, ele é cheio de bugs. Um deles, o mais irritante, é ocultar parte das mensagens de erro, o que pode deixar o código 300x mais difícil de se corrigir. No lugar, use o Code::Blocks, que é tão pequeno quanto, moderno e já vem com o mesmo compilador numa versão mais nova: http://www.codeblocks.org
Use a lista de inicialização para inicializar variáveis no construtor. Sem ela, o C++ irá inicializa-la duas vezes e isso pode ser especialmente caro se você tiver objetos como seus atributos. Ou seja no lugar de:

No(){ this->valor=0; this->esq=NULL; this->dir=NULL; }

Faça simplesmente:

No() : esq(NULL), dir(NULL), valor(0) { }

Cuidado com a identação. E, lembre-se, se você tiver um return dentro de um if, você não precisa de um else (pois o código vai cair fora mesmo se entrar no if).

Por exemplo, esse método:

bool Tree::Busca(int x, No* j){ if(j->get_valor()==x) return true; else if(j->get_valor()>x && j->get_esq()!=NULL) Busca(x,j->get_esq()); else if(j->get_valor()<x && j->get_dir()!=NULL) Busca(x,j->get_dir()); return false; }

Fica assim:

O seu main pede o valor da raiz. Mas como você nunca inseriu nenhum valor, a raiz ainda é NULL. Quando vc faz getValor() sobre NULL você tem o seu problema.

Algumas dicas:

Não use o devcpp. Além de ser pré-histórico e usar uma versão antiquíssima do MinGW, ele é cheio de bugs. Um deles, o mais irritante, é ocultar parte das mensagens de erro, o que pode deixar o código 300x mais difícil de se corrigir. No lugar, use o Code::Blocks, que é tão pequeno quanto, moderno e já vem com o mesmo compilador numa versão mais nova: http://www.codeblocks.org
Use a lista de inicialização para inicializar variáveis no construtor. Sem ela, o C++ irá inicializa-la duas vezes e isso pode ser especialmente caro se você tiver objetos como seus atributos. Ou seja no lugar de:

No(){ this->valor=0; this->esq=NULL; this->dir=NULL; }

Faça simplesmente:

No() : valor(0), esq(NULL), dir(NULL) { }

Cuidado com a identação. E, lembre-se, se você tiver um return dentro de um if, você não precisa de um else (pois o código vai cair fora mesmo se entrar no if).

Por exemplo, esse método:

[code]
bool Tree::Busca(int x, No* j){
if(j->get_valor()==x)
return true;

if(j->get_valor()>x && j->get_esq()!=NULL)  
    Busca(x,j->get_esq());  
else if(j->get_valor()<x && j->get_dir()!=NULL)  
    Busca(x,j->get_dir());  
return false;

} [/code]

cesarvargas00 · Abril 4, 2010, 10:36am

Então, eu continuo com o problema… Mas agora acho que sei onde fica ele :
A função Insere(int,No*) não altera o nó raiz da classe Tree. Eu tenho dificuldades com ponteiro, mas se eu fizesse essa função de modo iterativo eu até conseguiria numa boa…
O problema é que Insere é uma função recursiva o que dificulta o meu aprendizado… Realizei as mudanças que você me pediu, mas continuo com problemas. A seguir o código:

//MAIN.cpp
#include "header.h"
int main(){
	Tree teste;
	teste.Insere(10,teste.root());
	teste.Insere(9,teste.root());
	teste.Imprime(teste.root());
	

	fflush(stdin);
	getchar();
	return 0;
}
//Header.h
#include <iostream>
#include <cstdlib>
using namespace std;

class No{
private:
	No *esq,*dir;
	
	int valor;
public:
	No():valor(0),esq(NULL),dir(NULL){
	}
	void set_esq(No* p){esq=p;}
	void set_dir(No* p){dir=p;}
	No* get_esq(){return esq;}
	No* get_dir(){return dir;}
	int get_valor(){return valor;}
	void set_valor(int x){valor=x;}
};
class Tree{
private:
	No* raiz;
public:
	Tree(){
		raiz=NULL;
	}
	No *root(){return raiz;}
	bool Busca(int,No*);
	void Insere(int,No*);
	void Imprime(No*);
};

//Classes.cpp

#include "header.h"
bool Tree::Busca(int x, No* j){
	if(j->get_valor()==x)
		return true;
		if(j->get_valor()>x && j->get_esq()!=NULL)
			Busca(x,j->get_esq());
			else if(j->get_valor()<x && j->get_dir()!=NULL)
				Busca(x,j->get_dir());
	return false;
}
void Tree::Insere(int x, No* j){
	No *p;
	if(j==NULL){
		p=new No();
		p->set_valor(x);
		j=p;
	}
	else if(j->get_valor()>x)
		Insere(x,j->get_esq());
		else if(j->get_valor()<x)
			Insere(x,j->get_dir());
}
void Tree::Imprime(No* p){
	
	if (p->get_esq()!=NULL)
		Imprime(p->get_esq());
	cout << p->get_valor()<< " ";
		if (p->get_dir()!=NULL)
			Imprime(p->get_dir());
}

Obrigado! Agradeço desde já a resposta que foi me dada quase que imediatamente e espero ansiosamente por outra. Grato!!

cesarvargas00 · Abril 4, 2010, 11:56am

Ahh, estou usando o Visual C++ 2008 Express Edition… Foi nele que descobri que não estava alterando o No raiz. Obrigado!
by the way, o visual c++ é bom?

ViniGodoy · Abril 4, 2010, 12:51pm

Ele é excelente. Mas o compilador dele é o MSCPP. Não creio que para o caso dos exercícios da faculdade vá haver algum problema de compatibilidade, até pq a versão 2008 é bem mais próxima do standard que as anteriores.

No caso do Code::Blocks o compilador é o MinGW, o mesmo do Dev, mas numa versão muitíssimo mais nova.
Se você não tem problemas em usar o Visual, continue usando, ele é incomparavelmente melhor que essas outras duas IDES.

cesarvargas00 · Abril 4, 2010, 1:18pm

Certo, então vou usar o Visual a partir de agora…

Mas confesso que ainda não consegui achar o erro… esse último código que eu passei, mudei a Main e mesmo assim continua o erro:

[code]
#include "header.h"
int main(){
Tree teste;
teste.Insere(10,teste.root());
teste.Insere(9,teste.root());
teste.Imprime(teste.root());

fflush(stdin);
getchar();
return 0;

}[/code]

Parece-me que o erro se encontra na função-membro da classe Tree::Insere que é a seguinte:

void Tree::Insere(int x, No* j){ No *p; if(j==NULL){ p=new No(); p->set_valor(x); j=p; } else if(j->get_valor()>x) Insere(x,j->get_esq()); else if(j->get_valor()<x) Insere(x,j->get_dir()); }
Onde que estou errando? Você tem uma dica?
Obrigado, agradeço mais uma vez a resposta!

ViniGodoy · Abril 4, 2010, 3:43pm

O seu método insere deve atualizar a raiz, caso ela seja vazia. Note que nele vc insere um nó, mas se a raiz tiver nula, esse nó não passa a ser a raiz.

Insira um if lá, antes de terminar o método:

if (raiz == NULL) raiz = j;

cesarvargas00 · Abril 4, 2010, 4:53pm

Certo, eu fiz isso. Mas quando eu vou imprimir, só aparece a raíz na tela…
Será que fiz algo de errado?

[code]void Tree::Insere(int x, No* j){
No p;
if(j==NULL){
p=new No();
p->set_valor(x);
j=p;
}
else if(j->get_valor()>x)
Insere(x,j->get_esq());
else if(j->get_valor()<x)
Insere(x,j->get_dir());
if(raiz==NULL)
raiz=j;
}
void Tree::Imprime(No p){

if (p->get_esq()!=NULL)
	Imprime(p->get_esq());
cout << p->get_valor()<< " ";
	if (p->get_dir()!=NULL)
		Imprime(p->get_dir());

}
[/code]
e a main :[code]
#include "header.h"
int main(){
Tree teste;
teste.Insere(10,teste.root());
teste.Insere(9,teste.root());
teste.Insere(2,teste.root());
teste.Imprime(teste.root()); // Soh imprime o 10 na tela… O 9 e o 2 são ignorados.

fflush(stdin);
getchar();
return 0;

}[/code]

Obrigado novamente!

ViniGodoy · Abril 4, 2010, 5:55pm

Há um problema no seu método de inserção. Você não define o novo nó como esquerda ou direita do último nó encontrado.

Revise aquela linha que diz
j = p;

Ela deveria ser um pouco diferente. Em algum local, você terá que ter um

j->set_dir§;

ou

j->set_esq§;

Não vou passar o código corrigido pra que vc tente achar o problema.

cesarvargas00 · Abril 4, 2010, 6:12pm

Nossa… Que cabeça a minha… Eu me perdi nos detalhes e não me toquei que estava me esquecendo de dizer pra onde aponta esq ou dir… Deve ser muito chocolate!! Hhehe obrigado, chegando em casa eu farei as alterações e volto para postar o resultado.

cesarvargas00 · Abril 10, 2010, 12:32am

Então, na verdade meu código é recursivo, entao não precisa mudar o esq ou o dir, já que não importa pois os dois sào ponteiros… O meu erro estava em passar um valor NULL como parâmetro da função.

Segue o código corrigido:

//MAIN
#include "header.h"
int main(){
	Tree teste;
	teste.Insere(10);
	teste.Insere(5);
	teste.Insere(9);
	teste.Insere(1);
	teste.Insere(2);
	teste.Insere(15);
	teste.Insere(14);
	teste.Insere(13);
	teste.Insere(32);
	teste.Insere(113);
	teste.Insere(11);
	teste.Imprime();
	if (teste.Busca(32))
		cout << "\n\n32 dentro. TAM= "<< teste.get_tam();
	teste.Lumberjacker();// apaga todos os elementos da arvore (lumberjack eh lenhador em ingles)
	teste.Insere(13);
	teste.Insere(32);
	teste.Insere(113);
	teste.Insere(11);
	teste.Imprime();// Testa se apagou os elementos.
	
	

	fflush(stdin);
	getchar();
	return 0;
}
//HEADER.h
#include <iostream>
#include <cstdlib>
using namespace std;

class No{
private:
	No *esq,*dir;
	int valor;
public:
	No():valor(0),esq(NULL),dir(NULL){
	}
	void set_esq(No* p){esq=p;}
	void set_dir(No* p){dir=p;}
	No* get_esq(){return esq;}
	No* get_dir(){return dir;}
	int get_valor(){return valor;}
	void set_valor(int x){valor=x;}
};
class Tree{
private:
	No* raiz;
	unsigned tam;
	void Insere_d(int,No*);
	bool Busca_d(int,No*);
	void Imprime_d(No*);
	void Tamanho(unsigned x,No* p){
		x++;
		if(tam < x)
			tam=x;
		if(p->get_esq()!=NULL)
			Tamanho(x,p->get_esq());
		if(p->get_dir()!=NULL)
			Tamanho(x,p->get_dir());
	}
	void Lumberjacker_d(No*);
public:
	Tree():raiz(NULL),tam(0){	
	}
	~Tree(){
		if (raiz!=NULL)
			Lumberjacker();
	}
	unsigned get_tam(){
		return tam;
	}
	bool Busca(int x){
		if(Busca_d(x,raiz)==true)
			return true;
		return false;
	}
	void Imprime(){
		if (raiz!=NULL)
		Imprime_d(raiz);
	}
	void Insere(int);
	void Lumberjacker(){
		Lumberjacker_d(raiz);
		raiz=NULL;
	}
};
//classes.cpp
#include "header.h"
bool Tree::Busca_d(int x, No* j){
	if(j->get_valor()==x)
		return true;
		if(j->get_valor()>x && j->get_esq()!=NULL)
			Busca_d(x,j->get_esq());
			else if(j->get_valor()<x && j->get_dir()!=NULL)
				Busca_d(x,j->get_dir());
				else
					return false;
}
void Tree::Insere_d(int x, No* j){
	No *p;
	if (x < j->get_valor() && j->get_esq() == NULL){
		p=new No;
		j->set_esq(p);
		p->set_valor(x);
	}
		else if (x < j->get_valor() && j->get_esq() != NULL)
			Insere_d(x,j->get_esq());
	
	if (x > j->get_valor() && j->get_dir() == NULL){
		p=new No;
		j->set_dir(p);
		p->set_valor(x);
	}
		else if (x > j->get_valor() && j->get_dir() != NULL)
			Insere_d(x,j->get_dir());
}
void Tree::Imprime_d(No* p){
	
	if (p->get_esq()!=NULL)
		Imprime_d(p->get_esq());
	cout << p->get_valor()<< " ";
		if (p->get_dir()!=NULL)
			Imprime_d(p->get_dir());
}
void Tree::Insere(int x){
	No *p;
	if (raiz==NULL){
		p=new No;
		raiz=p;
		raiz->set_valor(x);
	}
		else
			Insere_d(x,raiz);
	Tamanho(0,raiz);
}
void Tree::Lumberjacker_d(No* p){
	if(p->get_esq()!=NULL)
		Lumberjacker_d(p->get_esq());
	if(p->get_dir()!=NULL)
		Lumberjacker_d(p->get_dir());
	delete p;
}

Eu adicionei uma funcao chamada Lumberjacker que apaga os elementos da arvore. E tambem adicionei um destrutor da classe Tree.
Obrigado! Agora vou pensar em um modo de remover os elementos ( na verdade ja tenho em mente o algoritmo , so falta implementa-lo recursivamente).

system · Janeiro 5, 2016, 8:24pm

Árvore de busca binária em C++[resolvido]

Cursos de Mobile

Cursos de Programação

Cursos de Front-end

Cursos de DevOps

Cursos de Design & UX

Cursos de Business

Cursos de Data & BI