Problema com árvores em C.

claudio.g.chepa · 25 de fevereiro de 2013

Boa noite, pessoal.

Estou tentando fazer uma função que remove um nó de uma árvore binária e está dando um erro muito estranho.

Vejam, por favor, o código abaixo:

Quando eu chamo a função "arv_remove", ela reconhece o ponteiro que passo para ela como NULL. Isso é estranho porque ele não é NULL, tanto que a função "preOrdem" que eu chamo antes e depois dela funciona perfeitamente.

Alguém pode me dizer o que está errado?

#include<stdio.h>
#include<stdlib.h>

//===============================================================================================
typedef struct arvore 
{
	int val;
	struct arvore *dir, *esq;
}Arvore;

//===============================================================================================
//Cria um único nó.
Arvore* cria_no( int x )
{
	Arvore *no = ( Arvore* )malloc( sizeof( Arvore ));
	no->val = x;
	return no;
}

//===============================================================================================
//Coloca o nó na árvore, "novo" é um nó já criado por uma outra função, aí é só colocar ele na árvore.
//Essa função precisa ser deste jeito, para mim funcinou perfeitamente.
Arvore* inserir( Arvore *raiz, Arvore *novo )
{
	if( raiz == NULL )
	{
		raiz = novo;
		raiz->esq = NULL;
		raiz->dir = NULL;
	}
	else
	{
		if( novo->val <= raiz->val )
		{
			if( raiz->dir == NULL )
			{
				raiz->dir = novo;
			}
			else
			{
				inserir( raiz->dir, novo );
			}
		}
		else 
		{
			if( raiz->esq == NULL )
			{
				raiz->esq = novo;
			}
			else
			{
				inserir( raiz->esq, novo );
			}
		}
	}

	return raiz;
}

//===============================================================================================
//Mostra todos os valores dos nós da árvore.
void preOrdem( Arvore *raiz )
{
	if( raiz != NULL )
	{
		printf("( %d ) ",raiz->val);
		preOrdem( raiz->esq );
		preOrdem( raiz->dir );
	}
}

//===============================================================================================
//Remove um nó da árvore.
void arv_remove( Arvore *raiz, int id )
{
	Arvore *aux;
	if( raiz == NULL )
	{
		printf("\nArvore nula, nao ha o que remover.\n");
		return;
	}
	if( raiz->val < id )
	{
		arv_remove( raiz->dir, id );
	}
	else if( raiz->val > id )
		{
			arv_remove( raiz->esq, id );
		}
		else
		{	
			if( raiz->esq != NULL && raiz->dir != NULL )
			{
				aux = minimo( raiz->dir ); //Se não forem null, buscamos o menor nó a partir do nó da direita.
				raiz->val = aux->val;
				arv_remove( raiz->dir, raiz->val );
			}
			else
			{
				aux = raiz;
				if( raiz->esq == NULL )
				{
					raiz = raiz->dir;
				}
				else
				{
					raiz = raiz->esq;
				}
				free(aux);
			}
		}
}

//===============================================================================================
Arvore* minimo( Arvore *raiz ){// procura o nó com valor mínimo
    if( raiz == NULL ){
       return NULL;
    }else{
          if( raiz->esq == NULL ){
              return raiz;
          }else{
              return minimo(raiz->esq);
          }
    }
}

//===============================================================================================
Arvore* maximo( Arvore *raiz ){// procura o nó com valor máximo
     if( raiz != NULL ){
       while( raiz->dir != NULL ){
          raiz = raiz->dir;
       }
     }
       return raiz;
}

//===============================================================================================
#include "avl.h"

int main()
{
	int i, val, quant;
	Arvore *inv = NULL;
	printf("Digite quantos valores voce que por na arvore:\n");
	scanf("%d", &quant);
	printf("Digite os valores dos nos da arvore;\n");
	for(i=0; i<quant; i++)
	{
		scanf("%d", &val);
		inv = inserir( inv, cria_no( val ) );
	}
	printf("\nA arvore é:\n");
	preOrdem( inv );
	printf("\nDigite um numero da arvore para remover:\n");
	scanf("%d", &val);
	arv_remove( inv, val );
	printf("\nAgora a arvore é:\n");
	preOrdem( inv );
	printf("\n");
	return 1;
}

ScreenBlack · 26 de fevereiro de 2013

Quando passamos um ponteiro, a função que recebe, cria uma cópia do ponteiro, logo, se você associar uma nova estrutura para esse ponteiro, será perdida quando a função retornar o valor.

Nesses casos, precisamos trabalhar com ponteiro para ponteiro.

Corrigi o seu código:


#include<stdio.h>
#include<stdlib.h>

//#include "avl.h"

//===============================================================================================
typedef struct arvore
{
	int val;
	struct arvore *dir, *esq;
}Arvore;

//===============================================================================================
//Cria um único nó.
Arvore* cria_no( int x )
{
	Arvore *no = ( Arvore* )malloc( sizeof( Arvore ));
	no->val = x;
	no->dir = NULL;
	no->esq = NULL;
	return no;
}

//===============================================================================================
//Coloca o nó na árvore, "novo" é um nó já criado por uma outra função, aí é só colocar ele na árvore.
//Essa função precisa ser deste jeito, para mim funcinou perfeitamente.
Arvore* inserir( Arvore **raiz, Arvore *novo )
{
	if( *raiz == NULL )
	{
		*raiz = novo;
	}
	else
	{
		if( novo->val <= (*raiz)->val )
		{
			if( (*raiz)->dir == NULL )
			{
				(*raiz)->dir = novo;
			}
			else
			{
				inserir( &(*raiz)->dir, novo );
			}
		}
		else
		{
			if( (*raiz)->esq == NULL )
			{
				(*raiz)->esq = novo;
			}
			else
			{
				inserir( &(*raiz)->esq, novo );
			}
		}
	}

	return *raiz;
}

//===============================================================================================
//Mostra todos os valores dos nós da árvore.
void preOrdem( Arvore *raiz )
{
	if( raiz != NULL )
	{
		printf("( %d ) ",raiz->val);
		preOrdem( raiz->esq );
		preOrdem( raiz->dir );
	}
}

//===============================================================================================
Arvore* minimo( Arvore *raiz ){// procura o nó com valor mínimo
    if( raiz == NULL ){
       return NULL;
    }else{
          if( raiz->esq == NULL ){
              return raiz;
          }else{
              return minimo(raiz->esq);
          }
    }
}

//===============================================================================================
Arvore* maximo( Arvore *raiz ){// procura o nó com valor máximo
     if( raiz != NULL ){
       while( raiz->dir != NULL ){
          raiz = raiz->dir;
       }
     }
       return raiz;
}

//===============================================================================================
//Remove um nó da árvore.
void arv_remove( Arvore **raiz, int id )
{
	Arvore *aux;
	if( *raiz == NULL )
	{
		printf("\nArvore nula, não ha o que remover.\n");
		return;
	}
	if( (*raiz)->val > id )
	{
		arv_remove( &(*raiz)->dir, id );
	}
	else if( (*raiz)->val < id )
		{
			arv_remove( &(*raiz)->esq, id );
		}
		else
		{
			if( (*raiz)->esq != NULL && (*raiz)->dir != NULL )
			{
				aux = minimo( (*raiz)->dir ); //Se não forem null, buscamos o menor nó a partir do nó da direita.
				(*raiz)->val = aux->val;
				arv_remove( &(*raiz)->dir, (*raiz)->val );
			}
			else
			{
				aux = *raiz;
				if( (*raiz)->esq == NULL )
				{
					*raiz = (*raiz)->dir;
				}
				else
				{
					*raiz = (*raiz)->esq;
				}
				free(aux);
			}
		}
}

//===============================================================================================
int main()
{
	int i = 0;
	int val = 0;
	int quant = 0;
	Arvore *inv = NULL;

	printf("Digite quantos valores voce que por na arvore:\n");
	scanf("%d", &quant);

	printf("Digite os valores dos nos da arvore;\n");
	for ( i = 0; i < quant; i++ )
	{
		scanf("%d", &val);
		inv = inserir( &inv, cria_no( val ) );
	}

	printf("\nA arvore é:\n");
	preOrdem( inv );
	printf("\nDigite um numero da arvore para remover:\n");
	scanf("%d", &val);
	arv_remove( &inv, val );
	printf("\nAgora a arvore é:\n");
	preOrdem( inv );
	printf("\n");
	return 1;
}

As únicas modificações que fiz, foram:

1) Mudar os parâmetros quando a função "main()" chama a função "inserir()" e "arv_remove()", para passar o ponteiro do ponteiro;

2) Modifiquei as funções "inserir()" e "arv_remove()" para tratar os ponteiros;

3) Correção na função "arv_remove()" para percorrer o lado correto da árvore, pois estava invertido.

No mais, o código está certo, removendo corretamente o nó da árvore.

ChrislleyAlves · 26 de fevereiro de 2013

O problema sempre é no uso do ponteiro.

Uso de ponteiro sem alocação de memória, ponteiro apontando para um retorno de função, ponteiro NULL e assim vai.

claudio.g.chepa · 26 de fevereiro de 2013

Quando passamos um ponteiro, a função que recebe, cria uma cópia do ponteiro, logo, se você associar uma nova estrutura para esse ponteiro, será perdida quando a função retornar o valor.
Nesses casos, precisamos trabalhar com ponteiro para ponteiro.

O problema sempre é no uso do ponteiro.
Uso de ponteiro sem alocação de memória, ponteiro apontando para um retorno de função, ponteiro NULL e assim vai.

É que quando eu passo o ponteio da raíz, é da raíz, é do início da árvore, o que tem abaixo dela ainda não foi lido, e se mudou alguma coisa lá embaixo eu achei que não importava. Na verdade, não entendi muito bem isso que vocês tentaram me exeplicar, se puderem dar uma explicação mais clara, eu agradeço muito.

ScreenBlack · 26 de fevereiro de 2013

Por exemplo: Quando você passa um valor 5 por parâmetro, a função fará uma cópia desse valor pra usar em sua rotina, destruindo-o no término.

Acontece o mesmo com o valor do ponteiro, por isso que utilizamos o ponteiro para ponteiro. Assim, podemos descer um nível no ponteiro, alcançando o ponteiro real, já que o primeiro é uma cópia.

Faça testes depurando (DEBUG mode) o código, removendo e adicionando os ponteiros. Assim você vai entender o porque.

claudio.g.chepa · 26 de fevereiro de 2013

Mas por que a função "void preOrdem(Arvore *raiz)" que mostra o vonteúdo da árvore funciona normalmente?

ScreenBlack · 26 de fevereiro de 2013

Porque você vai apenas ler o conteúdo, não havendo a necessidade em modifica-lo.

Sendo assim, a cópia do ponteiro estará referenciando o conteúdo correto.

Exemplo:


Ponteiro_1 ----------->	|		|
			|Memória_1	|
Ponteiro_2 ----------->	|		|

Nesse caso, o "Ponteiro_2" seria a cópia do ponteiro criada pela função, quando recebeu o parâmetro. Ambos os ponteiros apontam para a mesma área de memória.

Exemplo relacionando o novo nó dentro da função sem usar ponteiro duplo:


Ponteiro_1 ----------->	|		|
			|Memória_1	|
			|		|

Ponteiro_2 ----------->	|		|
			|Novo_Nó	|
			|		|

Nesse caso, "Novo_Nó" é o novo nó a ser adicionado na árvore. Como "Ponteiro_2" é uma cópia do ponteiro original, e que, terminando a rotina da função ele será destruído, logo, o novo nó ficará sem referência.

Exemplo relacionando o novo nó dentro da função usando ponteiro duplo:


Ponteiro_1 ----------->	|			|
			|			|
			|			|		|		|
			|Ponteiro_Original	|------------->	|Memória_1	|
			|			|		|		|
			|			|
Ponteiro_2 ----------->	|			|


Ponteiro_1 -----------> |			|
			|			|
			|			|		|		|
			|Ponteiro_Original	|------------->	|Novo_Nó	|
			|			|		|		|
			|			|
Ponteiro_2 -----------> |			|

Agora os ponteiros apontam pra um outro ponteiro, e este aponta para a área de memória. Assim, quando trocamos a referência do "Ponteiro_Original" para o "Novo_Nó", não perderemos ela quando a função for encerrada.

Bom, é isso. Espero que tenha entendido.

Se ficou dúvida, é só perguntar.