árvores_EDA_2017.1.md

Árvores

Definição

• Relação de hierarquia ou de composição entre nós.
• Conjunto finito de um ou mais nós, tais que:

a) sempre existe um nó raiz;
b) os demais nós formam subárvores;

• Cada nó de uma árvore é também raíz de uma subárvore.

Terminologia

• Grau:

Quantidade de subárvores do nó.
Corolário: um nó com grau 0 é uma folha.

• Nível:

Cada nó possui seu nível = adjecências até chegar na raiz.
Corolário: a raiz tem nível 0.

• Altura: nível mais alto da árvore.

Árvores Binárias

• Grau de cada nó sempre <= 2.
• Corolário: podem haver 2 subárvores, a da esquerda e a da direita.
• Corolário: se grau = 1, então deve ser determinado a qual lado pertence a subárvore.
• Podem chegar em O(log n) para inserção, busca e deleção.

Árvore Estritamente Binária

• Todo nó não folha tem 2 subárvores.

Árvore Binára Completa

• Árvore extritamente binária com altura X em que todas as folhas possuem nível = X.

Aplicações

• Útil quando é preciso tomar decisões bidirecionais. Ex: armazenamento de dados ordenados.

Percorrendo uma Árvore

• Pré-ordem (percurso em profundidade).

Centro, Esquerda, Direita.
a) Visitamos o nó atual;
b) Visitamos a subárvore esquerda;
c) Visitamos a subárvore direita;

• Em ordem (ordem simétrica).

Esquerda, Centro, Direita.
a) Visitamos a subárvore esquerda;
b) Visitamos o nó atual;
c) Visitamos a subárvore direita;

• Pós-ordem (percurso em profundidade).

Esquerda, Direita, Centro.
a) Visitamos a subárvore esquerda;
b) Visitamos a subárvore direita;
c) Visitamos o nó atual;

Código

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

typedef struct tree{
	struct tree* left;
	struct tree* right;
	int value;
}tree;

static int insert(tree** node, int value);
static int dell(tree** node, int value);
static tree** find_max(tree** node);
static void preOrdem(tree* node);
static void emOrdem(tree* node);
static void posOrdem(tree* node);

int main(){
	int item, flag, i=0;
	tree* root = NULL;
	
	srand(time(NULL));
	
	printf("Os números inseridos na árvore são:\n");
	for(; i<20; i++){
		item = rand()%100;
		printf("%d ", item);
		flag = insert(&root, item);
	}
	
	printf("\n\n- Pré-ordem:\n");
	preOrdem(root);
	printf("\n- Em ordem:\n");
	emOrdem(root);
	printf("\n- Pós-ordem:\n");
	posOrdem(root);
	
	printf("\n\nQual node quer deletar? ");
	scanf("%d", &item);
	flag = dell(&root, item);
	
	printf("\n- Pré-ordem:\n");
        preOrdem(root);
        printf("\n- Em ordem:\n");
        emOrdem(root);
        printf("\n- Pós-ordem:\n");
        posOrdem(root);
	
	return 0;
}

/**
 * retorna 1 se inseriu, 0 se já havia inserido.
 */
int insert(tree** node, int value)
{
	if(*node == NULL){
		*node = malloc(sizeof(tree));
		(*node)->left = (*node)->right = NULL;
		(*node)->value = value;
		return 1;
	}
	if(value < (*node)->value)
		return insert(&(*node)->left, value);
	if(value > (*node)->value)
		return insert(&(*node)->right, value);
	return 0;
}
/**
 * retorna 1 se deletou, 0 se não havia o que deletar.
 */
int dell(tree** node, int value)
{
	tree *to_dell, *max_left, **max_left_ptr;

	if(*node == NULL)
		return 0;
	if(value < (*node)->value)
		return dell(&(*node)->left, value);
	if(value > (*node)->value)
		return dell(&(*node)->right, value);
	
	if((*node)->left == NULL && (*node)->right == NULL){
		free(*node);
		*node = NULL;
	}
	else if((*node)->right == NULL){
		//Então (*node)->left != NULL
		to_dell = *node;
		*node = (*node)->left;
		free(to_dell);
	}
	else if((*node)->left == NULL){
		//Então (*node)->right != NULL
		to_dell = *node;
		*node = (*node)->right;
		free(to_dell);
	}
	else{
		//Então  (*node)->right != NULL && (*node)->left != NULL
		to_dell = *node;
		
		max_left_ptr = find_max(&to_dell->left);
		max_left = *max_left_ptr;
		
		//Modificando o maior nó da subárvore esquerda
		*max_left_ptr = max_left->left;
		
		//Atualizando o valor do nó atual
		max_left->left = to_dell->left;
		max_left->right = to_dell->right;
		*node = max_left;
		
		free(to_dell);
	}
	return 1;
}
/**
 * retorna o maior nó de uma subárvore
  */
tree** find_max(tree** node)
{
	if((*node)->right != NULL)
		return find_max(&(*node)->right);
	return node;
}
/**
 * Centro, Esquerda, Direita
 */
void preOrdem(tree* node)
{
	if(node != NULL){
		printf("%d\n", node->value);
		preOrdem(node->left);
		preOrdem(node->right);
	}
}
/**
 * Esquerda, Centro, Direita
 */
void emOrdem(tree* node)
{
	if(node != NULL){
		emOrdem(node->left);
		printf("%d\n", node->value);
		emOrdem(node->right);
	}
}
/**
 * Esquerda, Direita, Centro
 */
void posOrdem(tree* node)
{
	if(node != NULL){
		posOrdem(node->left);
		posOrdem(node->right);
		printf("%d\n", node->value);
	}
}