/* arvore.c
 *
 * Linguagem C - Árvores Binárias
 * Viva O Linux
 *
 * Enzo Ferber
 * 2015
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#define FOLHA		(Folha)malloc(sizeof(struct folha))
#define CMDSTR		500

typedef struct folha* Folha;

struct folha {
	int	info;

	Folha	esquerda;
	Folha	direita;
};

Folha inserir (Folha, int), deletar (Folha, int), procurar (Folha, int);
void imprimir_arvore (Folha, int);
void ordenada(Folha), preordenada(Folha), posordenada(Folha);
void cmd (void), help (void);

/* @ Folha inserir (Folha raiz, int info)
 *
 * Argumentos
 * ----------
 *	raiz	ponteiro para 'struct folha', estrutura de dado básica para
 *		construção da árvore
 *	info	nova informação a ser inserida
 *
 * Retorno
 * -------
 *	NULL	em caso de erro
 *	Folha	em caso de sucesso (nó 'raiz')
 */
Folha inserir (Folha raiz, int info)
{
	if (!raiz) {
		/* significa que o ponteiro é nulo, e que está é a posição
		 * para inserção.
		 *
		 * 1. Alocar e checar memória
		 */
		if (!(raiz = FOLHA)) {
			perror("inserir:malloc()");
			return NULL;
		}

		/* 2. Cópia da Informação
		 * 3. Ponteiros de referência
		 * 4. Retorno da nova folha
		 */
		raiz->info = info;
		raiz->esquerda = raiz->direita = NULL;

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

	/* retorna o ponteiro raiz
	 *
	 * Isso é necessário pois a função inserir é recursiva, e seu retorno
	 * é sempre atribuido ao mesmo ponteiro passado como argumento 'raiz',
	 *
	 * raiz->esquerda = inserir(raiz->esquerda,info)
	 * raiz->direita  = inserir(raiz->direta,  info)
	 */
	return raiz;
}

/* @ Folha deletar (Folha raiz, int info)
 *
 * Argumentos
 * ----------
 *	raiz	raiz principal da arvore
 *	info	informação procurada para deletar
 *
 *  Retorno
 *  -------
 *	raiz	em ambos os casos
 */
Folha deletar (Folha raiz, int info) {
	/* para deletar um nó, é necessário que esse nó exista.
	 * Então, vamos procurar pelo nó.
	 *
	 * A remoção de folhas em uma árvore é um pouco mais detalhada que sua
	 * similar para listas encadeadas.
	 *
	 * Existem alguns pontos a se considerar para remover uma folha:
	 *	1. A folha é também uma raiz (contém subárvores)?
	 *	2.
	 */
	Folha filho, n_raiz;

	/* se chegou ao final da arvore e nao encontrou nada para deletar....
	 */
	if (!raiz) return NULL;

	/* primeira comparação do programa:
	 *	Achamos a informação procurada?
	 */
	if (raiz->info == info) {
		/* 1. Existe uma raiz direita?
		 *	(uma raiz direita contém todos os elementos MAIORES que
		 *	a raiz que estamos excluindo).
		 *
		 * 2. Caso ela exista, ela será a nova raiz.
		 * 3. Os atuais elementos *menores* deverão ser anexados nos
		 *    menores elementos da nova raiz (segundo passo).
		 */
		if (raiz->direita) {
			/* 2. a nova raiz é a subárvore da direita, que contem
			 * todos os elementos MAIORES que a raiz a ser removida
			 */
			n_raiz = filho = raiz->direita;

			/* 3. a subárvore esquerda da nova raíz é percorrida
			 * até onde não houverem mais elementos. Isso nos dará
			 * o menor elemento maior que a folha esquerda de nossa
			 * raiz a ser removida.
			 */
			while(filho->esquerda)
				filho = filho->esquerda;

			/* o menor elemento maior que a raiz
			 * torna-se
			 * raiz de todos os elementos menores que a raiz
			 * removida
			 */
			filho->esquerda = raiz->esquerda;

			/* libera a memória do ponteiro */
			free (raiz);

			/* 1 + 2: nova raiz */
			return n_raiz;

		} else {
			/* caso não haja uma raiz direita (elementos MAIORES)
			 * que nossa raiz, a nova raiz da árvore seja o único
			 * elemento restante: a subárvore esquerda da árvore,
			 * ou os antigos elementos menores que a raiz removida.
			 */
			n_raiz = raiz->esquerda;

			/* libera a memória do ponteiro */
			free (raiz);

			/* retorno da nova raiz */
			return n_raiz;
		}

	} else if (info > raiz->info) {
		/* Caso a informação procurada seja maior que a informação na
		 * raiz, devemos então procurar pela informação na subárvore
		 * da direita (esta operação deverá ser congruente em todo o
		 * seu programa.
		 *
		 * Você não pode ordenar a inserção de um jeito e a remoção de
		 * outro!
		 */
		raiz->direita = deletar(raiz->direita, info);
	} else {
		/* Caso a informação seja menor que a raiz, procuraremos por ela
		 * nas subárvores da esquerda.
		 */
		raiz->esquerda = deletar(raiz->esquerda, info);
	}
	/* Lembre-se que as árvores binárias são estruturas de dados recursivas,
	 * e por esse motivo, é sempre bom saber o que se está retornando.
	 *
	 * Assim como na função de inserção, as chamadas recursivas à deletar()
	 * esperam como retorno uma raíz! Para onde a raiz->esquerda vai
	 * apontar quando a função retornar?
	 *
	 *	1. Se ela não for excluida, vai ser a própria raiz->esquerda
	 *	2. Caso seja excluída, será determinada pelo algoritmo no bloco
	 *	   if(raiz->info == info).
	 *
	 * Aqui, no final do escopo da função, significa que é um retorno de
	 * chamadas recursivas à deletar (já que o bloco raiz->info == info)
	 * retorna por si só. Já que este é um retorno das chamadas recursivas,
	 * deve retornar a raiz na qual foi chamada.
	 */
	return raiz;
}

Folha procurar (Folha raiz, int info)
{
	/* como todas as funções relativas a arvores binárias são recursivas,
	 * todas necessitam de um parametro de "parada de recursão", então,
	 * sempre que acharmos um nó NULO, retornamos (até porque não dá pra
	 * imprimir informações de um nó que não existe.
	 */
	if (!raiz) return NULL;

	if (info > raiz->info) return procurar(raiz->direita, info);
	else return procurar (raiz->esquerda, info);

	/* falhas, compilação, etc */
	return NULL;
}

void imprimir_arvore (Folha raiz, int level)
{
	register int i;

	/* como todas as funções relativas a arvores binárias são recursivas,
	 * todas necessitam de um parametro de "parada de recursão", então,
	 * sempre que acharmos um nó NULO, retornamos (até porque não dá pra
	 * imprimir informações de um nó que não existe.
	 */
	if (!raiz) return ;

	/* essa função é uma derivação da ordenação 'inorder', onde primeiro
	 * a arvore é percorrida até seu elemento mais esquerdo, e então é
	 * impressa a informação da raiz, e então é percorrida suas subárvores
	 * direitas.
	 *
	 * para imprimir de forma 'didática', essa função viaja primeiro pelas
	 * folhas direitas, imprime a raiz e então percorre as subárvores
	 * esquerdas.
	 */
	imprimir_arvore (raiz->direita, level + 1);

	for (i = 0; i < level * 2; i++ ) putchar(' ');
	printf("%d
", raiz->info);

	imprimir_arvore (raiz->esquerda, level + 1);
}

/* @ void ordenada (Folha raiz)
 *
 * Transversalização Ordenada
 * --------------------------
 * Primeiro é visitada a subárvore esquerda, depois a raiz e por último a
 * subárvore direita.
 */
void ordenada (Folha raiz)
{
	if (!raiz) return ;

	ordenada (raiz->esquerda);
	printf ("%d ", raiz->info);
	ordenada (raiz->direita);
}

/* @ void preordenada (Folha raiz)
 *
 * Transversalização Pré-Ordenada
 * ------------------------------
 * Primeiro é visitada a raiz, depois a subárvore esquerda e por último a
 * subárvore direita.
 */
void preordenada (Folha raiz)
{
	if (!raiz) return ;

	printf ("%d ", raiz->info);
	preordenada (raiz->esquerda);
	preordenada (raiz->direita);
}

/* @ void posordenada (Folha raiz)
 *
 * Transversalização Pós-Ordenada
 * ------------------------------
 * Primeiro é visitada a subárvore esquerda, depois a subárvore direita e por
 * último a raiz.
 */
void posordenada (Folha raiz)
{
	if (!raiz) return;

	posordenada (raiz->esquerda);
	posordenada (raiz->direita);
	printf ("%d ", raiz->info);
}

/******************************************************************************
 * Aqui termina todo o código relacionado às árvores binárias e começa o código
 * relative à interface.
 *
 */
void cmd (void)
{
	char cmd[CMDSTR], *arg;
	Folha raiz = NULL;

	help();

	while (1) {
		printf ("ArvoreBinaria> ");
		fgets (cmd, CMDSTR, stdin);

		if (!cmd) continue;

		switch (*cmd) {
		case 'i':
			arg = &cmd[2];
			arg = strtok(arg, " ");
			while (arg) {
				if (!raiz) raiz = inserir (raiz, atoi(arg));
				else inserir (raiz, atoi(arg));

				arg = strtok (NULL, " ");
			}
			break;
		case 'd':
			arg = &cmd[2];
			arg = strtok(arg, " ");
			while (arg) {
				raiz = deletar (raiz, atoi(arg));

				arg = strtok (NULL, " ");
			}
			break;
		case 'm':
			imprimir_arvore (raiz, 0);
			break;
		case 'o':
			ordenada(raiz);
			puts("");
			break;
		case 'r':
			preordenada(raiz);
			puts("");
			break;
		case 'p':
			posordenada(raiz);
			puts("");
			break;
		case 's':
			exit(0);
		case 'h':
			help();
			break;
		default:
			printf("Comando nao reconhecido.
");
			break;
		}

		memset (cmd, 0x0, CMDSTR);
	}
}

/* @ void help (void)
 *
*	i 20	vai inserir o elemento 20 na árvore
 *	d 20	vai remover o elemento 20 da árvore
 *	m	vai mostrar a árvore na tela
 *	o	transversalização ordenada
 *	r	transversalização pré-ordenada
 *	p	transversalização pós-ordenada
 *	s	sai do programa
 *	h	mostra a ajuda
 */
void help (void)
{
	printf ("    |    Arvores Binarias
");
	printf ("    |    Implementacao em C para o Viva O Linux
");
	printf ("    |    
");
	printf ("    |    Autor: Enzo Ferber
");
	printf ("    |    2015
");
	printf ("    |

");

	printf ("		Lista de comandos
");
	printf ("		-----------------
");
	printf ("		i %%d - Inserir um elemento
");
	printf ("		d %%d - Deletar um elemento
");
	printf ("		m    - Mostrar a arvore lateralmente
");
	printf ("		o    - Transversalizacao Ordenada
");
	printf ("		r    - Transversalizacao Pre-Ordenada
");
	printf ("		p    - Transversalizacao Pos-Ordenada
");
	printf ("		s    - Sair do programa
");
	printf ("		h    - Mostra a ajuda

");
}

int main (void)
{
	cmd ();
	return 0;
}