Ir para o conteúdo
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

20_LESI

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

Mensagens Recomendadas

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ê?

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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!

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros 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.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora

×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.