Jump to content
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

Sign in to follow this  
20_LESI

[SOLVED] Duvida na implementação de arvores de procura

Recommended Posts

20_LESI

Boa noite! Estou a implementar uma arvore binaria de procura, e encalhei numa função, a que retira o menor elemento da arvore!

Implementei assim a versão recursiva:

ABint extractMin(ABint btree, int *n)
{	
if(btree)
{
	if(btree->left)
		btree = extractMin(btree->left ,n);
	else
	{
		*n = btree->value;
		free(btree);
	}
}

return btree;
} 

O menor elemento fica no endereço que passo por referência, mas ao imprimir a arvore ele continua lá, e não era suposto. Alguém me sabe dizer porquê?

Share this post


Link to post
Share on other sites
pedrosorio

Porque quando fazes "free" estás apenas a dizer que a memória ocupada por essa estrutura passa a estar "livre", isso não significa que os conteúdos sejam substituídos de imediato. Como não alteras o apontador na árvore, ele continua a apontar para a memória que tu libertaste e enquanto ela não for substituída, a árvores permanece intacta. Usualmente coloca-se esse apontador a NULL.


Não respondo a dúvidas por mensagem.

Share this post


Link to post
Share on other sites
20_LESI

Só agora percebi porque o free() dá tanto barraco...

Ainda assim, isto não funciona! A única alteração que fiz foi substituir o free ao apontador, por isto:

btree = btree->right

Pois apercebi-me que se não o fizer, o algoritmo estaria incorrecto.

ABint extractMin(ABint btree, int *n)
{	
if(btree)
{
	if(btree->left)
		btree = extractMin(btree->left, n);
	else
	{
	   	*n    = btree->value;
		btree = btree->right;
	}
}

return btree;
}

Acontece exactamente o mesmo que me estava a acontecer com o código antigo!

EDIT: Descobri! O problema estava aqui:

btree = extractMin(btree->left, n);

Devia ter feito:

btree->left = extractMin(btree->left, n);

Obrigado pela dica!

Share this post


Link to post
Share on other sites
mogers

Isto não funciona como tu pretendes.

Imagina que  btree = pai->left  (na chamada recursiva colocaste pai->left e o btree nessa chamada fica com esse valor).

btree é um apontador cujo endereço de memória é o mesmo de pai->left. Contudo, btree não é uma referência de pai->left, é apenas uma cópia, ou seja, ao alterares o apontador btree, o pai->left fica na mesma.

Para fazeres o que pretendes precisas de passar um apontador para apontador,

ABint* extractMin(ABint *btree, int *n)
{       
        if( *btree)
        {
                if( (*btree)->left)
                        extractMin( & (*btree)->left, n);
                else
                {
                         *n    = (*btree)->value;
                        *btree = (*btree)->right;
                }
        }
        return btree;
}

edit2: acho que compliquei, creio que isto é equivalente à tua alteração


"What we do for ourselves dies with us. What we do for others and the world, remains and is immortal.", Albert Pine

Blog pessoal : contém alguns puzzles, algoritmos e problemas para se resolver com programação.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.