Agora sim. O melhor para o final. A função para remover um nó da árvore é um pouco mais complexa que as outras, mas nada assustador. Primeiro, delineamos a função:

1. Procurar pelo elemento;
2. Se achado, *excluir* o elemento.

E como excluir? Quais os possíveis casos?

1. Excluir um nó com ambas as raízes presentes.
2. Excluir um nó com apenas uma subárvore (esquerda ou direita):
    2.1. Subárvore direita inexistente.
    2.2. subárvore esquerda inexistente.
3. Excluir um nó onde ambas as subárvores são NULAS. Dê uma olhada no código completo da função e tente imaginar o que ela faz. E o mais importante, como atinge os princípios enumerados acima. Logo abaixo, duas ilustrações sobre 3 casos (1, 2.1 e 2.2).

/* @ Folha deletar (Folha raiz, int info)
 *
 * Argumentos
 * ----------
 *	raiz	raiz principal da arvore
 *	info	informação procurada para deletar
 *
 *  Retorno
 *  -------
 *	raiz	em ambos os casos (erro e sucesso)
 */
Folha deletar (Folha raiz, int info) {
	Folha filho, n_raiz;

	if (!raiz) return NULL;

	if (raiz->info == info) {
		if (raiz->direita) {
			n_raiz = filho = raiz->direita;

			while(filho->esquerda)
				filho = filho->esquerda;

			filho->esquerda = raiz->esquerda;

			free (raiz);
			return n_raiz;

		} else {
			n_raiz = raiz->esquerda;
			free (raiz);
			return n_raiz;
		}

	} else if (info > raiz->info)
		raiz->direita = deletar(raiz->direita, info);
	else
		raiz->esquerda = deletar(raiz->esquerda, info);

	return raiz;
}

Dissecando a função:

Folha deletar (Folha raiz, int info)

A declaração e o princípio de funcionamento da função "deletar" são exatamente iguais aos da função "inserir". "raiz" é um ponteiro para a raiz principal da árvore sendo analisada e "info" é a informação que queremos remover.

	Folha filho, n_raiz;

	if (!raiz) return NULL;

Esta é a primeira função que declara variáveis: dois ponteiros do tipo (struct folha *). "filho" e "n_raiz" serão usados como suporte nos testes condicionais mais a frente. "if (!raiz)" é o teste condicional de parada de recursão (ou de informe de erro, já que se a recursão chegar a esse ponto significa que o item a ser removido não foi encontrado).

	if (raiz->info == info) {

		// (tratamento dos casos de remoção)

	} else if (info > raiz->info)
		raiz->direita = deletar(raiz->direita, info);
	else
		raiz->esquerda = deletar(raiz->esquerda, info);

	return raiz;

Vamos de "trás para frente". Analisaremos o loop mais externo primeiro, para depois entrar em detalhes sobre os algoritmos de remoção. Esse loop é bem simples de ser entendido. O primeiro teste verifica se a informação na raiz atual é igual a informação a ser removida.

Caso não seja, o próximo teste condicional verificará se a informação a ser removida é MAIOR QUE a informação da raiz, em caso afirmativo, é realizada uma chamada recursiva na subárvore direita. (Lembre-se que para percorrermos a árvore precisamos sempre utilizar o mesmo algoritmo que utilizamos para inserir um novo elemento). Caso contrário, realizamos uma chamada recursiva na subárvore esquerda.

No final, retornamos à raiz.

Nota: o princípio de funcionamento é exatamente igual ao da função de inserção. Caso tenha dúvidas sobre como o processo recursivo vai funcionar, dê uma olhada na página "Inserção" deste artigo, que contém uma explicação maior e uma ilustração do processo.

Agora, o algoritmo de remoção:

if (raiz->direita) {
	n_raiz = filho = raiz->direita;

	while(filho->esquerda)
		filho = filho->esquerda;

	filho->esquerda = raiz->esquerda;

	free (raiz);
	return n_raiz;

} else {
	n_raiz = raiz->esquerda;
	free (raiz);
	return n_raiz;
}

Começamos com um teste condicional para verificar a existência da subárvore direita (itens maiores que a raiz). Caso ela exista, salvamos esse ponteiro nas variáveis "n_raiz" e "filho". "n_raiz" representa nossa nova raiz (como precisamos remover a raiz atual, uma nova raiz deverá tomar seu lugar). "filho" será usado para achar o menor elemento MAIOR QUE a raiz - esse conceito é muito importante e é realizado pelo próximo loop:

while(filho->esquerda)
	filho = filho->esquerda;

Enquanto houver uma raiz esquerda (itens menores) em "filho", avançaremos para ela ("filho = filho->esquerda" - lembra-se de como percorremos listas encadeadas?). Isso serve para encontrar o menor elemento maior que "raiz->info".

filho->esquerda = raiz->esquerda;

Aqui, anexamos as subárvores e resolvemos duas coisas. Primeiro, se a subárvore esquerda da raiz for NULL, ela vai continuar como NULL (caso 2, quando uma das subárvores é NULL). Segundo, se a subárvore esquerda existir (caso 1, ambas as subárvores presentes), vamos anexá-la à subárvore esquerda do menor elemento maior que a raiz, e isso garante a integridade da árvore.

free (raiz);
return n_raiz;

Liberamos a memória utilizada por "raiz", efetivando sua remoção da árvore e retornamos o ponteiro "n_raiz" (que foi salvo como apontando para "raiz->direta", ou o primeiro elemento maior que "raiz"). Esse elemento "n_raiz" passará a ser a nova raiz.

else {
	n_raiz = raiz->esquerda;
	free (raiz);
	return n_raiz;
}

Esse teste condicional é derivado do teste de existência de uma subárvore direita. Isso significa que este "else" vai tratar do caso 2 (subárvore direita inexistente) ou caso 3 (onde ambas as subárvores não estão presentes). "n_raiz = raiz->>esquerda" garante que se houver alguma informação na árvore, ela será retornada como nova raiz, e também garante que se não houver uma subárvore esquerda (caso 3, pois já sabemos que não há uma subárvore direita) NULL será retornado - ela garante que NULL será retornado graças ao algoritmo de inserção, que configura ambos os ponteiros de todos os novos elementos como NULL.