C: Números em ordem crescente e árvores binárias

Vou mostrar neste artigo como implementar árvores binárias e como usá-las para organizar números em ordem crescente. Embora eu só mostre três funções (uma para inserir, uma para calcular o tamanho e uma para imprimir), é fácil alterá-las para que elas desempenhem o papel desejado.

Começaremos pela definição de uma árvore binária. Elas recebem esse nome pois de cada folha (leaf) podem sair dois troncos (branch). Elas se parecem mais ou menos com isso:

    4
   / \
  2   7
 / \   \
1   3   8

Do 4 saem dois troncos, o da esquerda com o número 2 e o da direita com o número 7. Do 2 saem novamente dois troncos, o da esquerda com o número 1 e o da direita com o número 3. Já do número 7, sai apenas um tronco, com o número 8.

Perceba que na ilustração a cima, quando se vai à esquerda, o valor daquela folha é sempre menor que o da folha a cima e quando se vai à direita, o valor é maior. É exatamente isso que usaremos para organizar nossos números em ordem crescente.

Mas antes de começarmos a falar de algoritmos, primeiro vamos definir um struct que represente nossa árvore binária:

struct leaf {
	int value;
	struct leaf* lft;
	struct leaf* rgt;
};

Ela guardará um valor value e terá um ponteiro que aponta para a folha à esquerda (left, lft) e um que aponta para a folha à direita (right, rgt).

Inserindo valores

Árvores binárias funcionam de maneira semelhante à listas, a diferença sendo que enquanto listas têm, geralmente, apenas um ponteiro, árvores possuem dois. Por isso, recomendo a quem for continuar que já esteja familiarizado com as operações de inserir um novo nó em uma lista.

O que a função insert() faz é criar uma nova folha se o ponteiro que for passado como argumento for NULL ou decidir para que lado da árvore seguir, usando aquela idéia que eu apresentei mais no início do artigo: se for menor, ir à esquerda; se for maior, ir à direita. Se for igual não importa muito, mas na implementação atual ele irá à direita.

Usando a árvore que usei de exemplo mais a cima, se quiséssemos adicionar o número 5, teríamos o seguinte:

  • Começamos pela folha com o número 4, ou seja, uma folha diferente de NULL. Sendo assim, a função insert tem de decidir para que lado continuar. Como 5 é maior que 4, ela vai à direita.
  • Agora estamos no número 7 (também diferente de NULL) e iremos adicionar o número 5, que é menor que 7, então vamos à esquerda.
  • À esquerda de 7 não há nada (agora sim, NULL), então criaremos uma nova folha e faremos 7->lft apontar para essa nova folha.

Antes de mostrar o código, só gostaria de chamar a ATENÇÃO para o fato de que após chamar malloc eu não verifico se o ponteiro retornado foi NULL. Se for esse o caso, o programa teve algum problema na hora de alocar memória e algo deve ser feito: fechar o programa, avisar o usuário, etc. Dado o aviso, agora sim, o código:

void insert(struct leaf** tree, int value)
{
	struct leaf* current = *tree;

	if(current == NULL)
	{
		struct leaf* new_leaf = malloc(sizeof(struct leaf));
		new_leaf->value = value;
		new_leaf->lft = NULL;
		new_leaf->rgt = NULL;

		*tree = new_leaf;
	}

	else
	{
		if(value < current->value)
			insert(&(current->lft), value);
		else
			insert(&(current->rgt), value);
	}
}

Imprimindo a árvore

O algoritmo para imprimir é basicamente o mesmo que será usado para qualquer outra coisa que use árvores binárias. Começamos da folha mais à esquerda e vamos subindo e indo à direita. Fazemos tudo isso usando recursão (chamamos a função dentro da própria), então podemos chamar a função passando a “raiz” da árvore que a função se encarrega de chegar à folha mais à esquerda.

O código:

void print_tree(struct leaf* tree)
{
	struct leaf* current = tree;
	
	if(current != NULL)
	{
		print_tree(current->lft);
		printf("%d ",current->value);
		print_tree(current->rgt);
	}
}

Bonsai ou sequóia?

Sim! A piada infame a cima foi para avisar-lhe que iremos usar a mesma idéia de recursão para calcular o tamanho da nossa árvore. A função length soma o número de folhas à esquerda, soma um para a folha atual e soma o número de folha à direita e depois retorna o valor.

O código:

int length(struct leaf* tree)
{
	int count = 0;
	struct leaf* current = tree;

	if(current != NULL)
	{
		count += length(current->lft);
		count++;
		count += length(current->rgt);
	}

	return count;
}

Todo o código

Aqui está todo o código, com um main que mostra como usar as funções:

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

struct leaf {
	int value;
	struct leaf* lft;
	struct leaf* rgt;
};

void print_tree(struct leaf* tree);
void insert(struct leaf** tree, int value);
int length(struct leaf* tree);

int main(int argc, char* argv[])
{
	struct leaf* root = NULL;

	insert(&root, 6);
	insert(&root, 8);
	insert(&root, 7);
	insert(&root, 2);
	insert(&root, 4);

	print_tree(root);
	printf("\nsize:%d\n",length(root));

	return(EXIT_SUCCESS);
}

void print_tree(struct leaf* tree)
{
	struct leaf* current = tree;
	
	if(current != NULL)
	{
		print_tree(current->lft);
		printf("%d ",current->value);
		print_tree(current->rgt);
	}
}

void insert(struct leaf** tree, int value)
{
	struct leaf* current = *tree;

	if(current == NULL)
	{
		struct leaf* new_leaf = malloc(sizeof(struct leaf));
		new_leaf->value = value;
		new_leaf->lft = NULL;
		new_leaf->rgt = NULL;

		*tree = new_leaf;
	}

	else
	{
		if(value < current->value)
			insert(&(current->lft), value);
		else
			insert(&(current->rgt), value);
	}
}

int length(struct leaf* tree)
{
	int count = 0;
	struct leaf* current = tree;

	if(current != NULL)
	{
		count += length(current->lft);
		count++;
		count += length(current->rgt);
	}

	return count;
}

Bônus!

“Mas tio, e se eu quiser os números na ordem decrescente?” Fácil! Basta invertemos a ordem em que a função faz a recursão. Trocando current->lft e current->rgt de posição na função print_tree, ela irá imprimir os números na ordem decrescente:

void reverse_print_tree(struct leaf* tree)
{
	struct leaf* current = tree;
	
	if(current != NULL)
	{
		print_tree(current->rgt);
		printf("%d ",current->value);
		print_tree(current->lft);
	}
}
Publicidade

2 Respostas para “C: Números em ordem crescente e árvores binárias

  1. Leonardo maio 25, 2009 às 5:32 pm

    Não sei se depende do compilador, mas se alguém estiver utilizando o codeblocks coloque antes do malloc ‘(struct leaf*), senão dá erro de compilação.
    linha do codigo:struct leaf* new_leaf = malloc(sizeof(struct leaf));
    linha correta exemplo:struct leaf* new_leaf = (struct leaf) malloc(sizeof(struct leaf));

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair /  Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair /  Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair /  Alterar )

Conectando a %s

%d blogueiros gostam disto: