Computação 2
Linguagem C
“Árvores com Alocação Dinâmica”.
Slides: Prof. João Fabro
UTFPR - Curitiba
O que são “Árvores” em
Programação?
• Árvores são estruturas de dados com alocação
dinâmica, parecidas com Listas Encadeadas!
• A diferença é que cada Elemento (ou nodo ou
nó) possui, além dos dados a serem armazenados, dois outros ponteiros:
– Um para o ramo da direita
– Outro para o ramo da esquerda
Árvores com Alocação Dinâmica
struct Elemento
{
char nome [100];
struct Elemento* esq;
struct Elemento* dir;
};
struct Elemento* Arvore;
//Ponteiro para o “topo” da Árvore
Exemplo de Árvore
Árvore:
Nome: Joao
Esq:
Dir:
Nome: Carlos
Esq:
Dir:
Nome: Adriano
Esq:
Dir:
NULL NULL
Nome: Paulo
Esq:
Dir:
Nome: Guilherme
Esq:
Dir:
NULL NULL
Nome:Luiz
Esq:
Dir:
NULL NULL
Nome: Ribamar
Esq:
Dir:
NULL NULL
Árvores com Alocação Dinâmica
struct Elemento
{
char nome [100];
struct Elemento* esq;
struct Elemento* dir;
};
struct Elemento* Raiz;
//Ponteiro para o “topo” da Árvore
Árvores com Alocação Dinâmica
void insere_nome_ordenado (struct Elemento **nodo, char *nominho)
{
struct Elemento *novo_no;
novo_no = (struct Elemento *) malloc(sizeof(struct Elemento) );
strcpy(novo_no->nome, nominho);
if(*nodo == NULL) // A árvore está vazia!!!
{
novo_no->esq = NULL;
novo_no->dir = NULL;
*nodo = novo_no;
}
else // A arvore não está vazia!!!
{
if (strcmp(*nodo->nome, nominho)>0)
insere_ordenado(&(nodo->dir), nominho);
else
insere_ordenado(&(nodo->esq), nominho);
}
}
Árvores com Alocação Dinâmica
Raiz:
NULL
Árvores com Alocação Dinâmica
Raiz:
NULL
Insere_ordenado(&Raiz, “Joao”);
Árvores com Alocação Dinâmica
nodo:
NULL
novo_no:
Nome: Joao
Esq:
Dir:
NULL NULL
Árvores com Alocação Dinâmica
Raiz:
Nome: Joao
Esq:
Dir:
NULL NULL
Árvores com Alocação Dinâmica
Raiz:
Nome: Joao
Esq:
Dir:
NULL NULL
Insere_ordenado(&Raiz, “Carlos”);
Árvores com Alocação Dinâmica
nodo:
Nome: Joao
Esq:
Dir:
novo_no:
Nome: Carlos
Esq:
Dir:
NULL NULL
Árvores com Alocação Dinâmica
Raiz:
Nome: Joao
Esq:
Dir:
Nome: Carlos
Esq:
Dir:
NULL NULL
NULL
Árvores com Alocação Dinâmica
Raiz:
Nome: Joao
Esq:
Dir:
Nome: Carlos
Esq:
Dir:
NULL NULL
Insere_ordenado(&Raiz, “Adriano”);
NULL
Árvores com Alocação Dinâmica
Raiz:
Nome: Joao
Esq:
Dir:
Nome: Carlos
Esq:
Dir:
Nome: Adriano
Esq:
Dir:
NULL NULL
NULL
NULL
Árvores com Alocação Dinâmica
Raiz:
Nome: Joao
Esq:
Dir:
Nome: Carlos
Esq:
Dir:
Nome: Adriano
Esq:
Dir:
NULL
NULL NULL
Insere_ordenado(&Raiz, “Paulo”);
NULL
Árvores com Alocação Dinâmica
Raiz:
Nome: Joao
Esq:
Dir:
Nome: Carlos
Esq:
Dir:
Nome: Adriano
Esq:
Dir:
NULL NULL
NULL
Nome: Paulo
Esq:
Dir:
NULL NULL
Árvores com Alocação Dinâmica
Raiz:
Nome: Joao
Esq:
Dir:
Nome: Carlos
Esq:
Dir:
Nome: Adriano
Esq:
Dir:
NULL
NULL NULL
Insere_ordenado(&Raiz, “Luiz”);
Nome: Paulo
Esq:
Dir:
NULL NULL
Árvores com Alocação Dinâmica
Raiz:
Nome: Joao
Esq:
Dir:
Nome: Carlos
Esq:
Dir:
Nome: Adriano
Esq:
Dir:
NULL NULL
NULL
Nome: Paulo
Esq:
Dir:
Nome:Luiz
Esq:
Dir:
NULL NULL
NULL
Árvores com Alocação Dinâmica
Raiz:
Nome: Joao
Esq:
Dir:
Nome: Carlos
Esq:
Dir:
Nome: Adriano
Esq:
Dir:
NULL
NULL NULL
Insere_ordenado(&Raiz, “Guilherme”);
Nome: Paulo
Esq:
Dir:
Nome:Luiz
Esq:
Dir:
NULL NULL
NULL
Árvores com Alocação Dinâmica
Raiz:
Nome: Joao
Esq:
Dir:
Nome: Carlos
Esq:
Dir:
Nome: Adriano
Esq:
Dir:
NULL NULL
Nome: Paulo
Esq:
Dir:
Nome: Guilherme
Esq:
Dir:
NULL NULL
Nome:Luiz
Esq:
Dir:
NULL NULL
NULL
Árvores com Alocação Dinâmica
Raiz:
Nome: Joao
Esq:
Dir:
Nome: Carlos
Esq:
Dir:
Nome: Adriano
Esq:
Dir:
NULL NULL
Nome: Paulo
Esq:
Dir:
Nome: Guilherme
Esq:
Dir:
NULL NULL
Insere_ordenado(&Raiz, “Ribamar”);
Nome:Luiz
Esq:
Dir:
NULL NULL
NULL
Árvores com Alocação Dinâmica
Raiz:
Nome: Joao
Esq:
Dir:
Nome: Carlos
Esq:
Dir:
Nome: Adriano
Esq:
Dir:
NULL NULL
Nome: Paulo
Esq:
Dir:
Nome: Guilherme
Esq:
Dir:
NULL NULL
Nome:Luiz
Esq:
Dir:
NULL NULL
Nome: Ribamar
Esq:
Dir:
NULL NULL
Árvores Binários: Listagem Ordenada!
• Agora como fazer para listar todos os nomes,
em ordem alfabética?
Árvores Binários: Listagem Ordenada!
• Agora como fazer para listar todos os nomes,
em ordem alfabética?
void listar_ordenado (struct Elemento* raiz)
{
if(raiz!=NULL)
{
listar_ordenado(raiz->esq);
printf(“%s\n”, raiz->nome);
listar_ordenado(raiz->dir);
}
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct Elemento
{
char nome [100];
struct Elemento* esq;
struct Elemento* dir;
int main()
{
char escolha;
Raiz = NULL; //Inicia a Árvore Vazia!
for ( ; ; )
{
escolha = menu ();
switch ( escolha )
{
case ‘i' :
case ‘I' : { insere(); } break;
};
case ‘l' :
case ‘L' : { listar_ordenado(Raiz); } break;
struct Elemento* Raiz;//Ponteiro para a “Raiz”
// da Árvore
case ‘r' :
case ‘R' : { remove(Raiz); } break;
char menu ();
case ‘t' :
case ‘T' : {
exit ( 0 );
} break;
default : { printf ( "Opcao invalida. \n" ); }
void insere ();
void insere_ordenado (struct Elemento **nodo,
char *nominho);
}
void listar_ordenado (struct Elemento* raiz);
printf ( "\n \n \n" );
}
void remove (struct Elemento *nodo);
system ( "Pause" );
return 0;
}
void insere ()
{
system ( "cls" );
printf ( "\n \n \n" );
char nome_local[100];
printf ( "Digite o Nome a inserir na Arvore: \n" );
fflush ( stdin );
gets (nome_local );
insere_ordenado(&Raiz, nome_local);
}
void remove (struct Elemento *nodo)
{
if(nodo!= NULL)
{
remove(nodo->esq);
remove(nodo->dir);
free(nodo);
}
}
void listar_ordenado (struct Elemento*
raiz)
{
if(raiz!=NULL)
{
listar_ordenado(raiz->esq);
printf("%s\n", raiz->nome);
listar_ordenado(raiz->dir);
}
}
char menu ()
{
printf ("\n \n \n");
char opcao;
printf ( "(I)nserir novo nome na Arvore. \n" );
printf ( "(L)istar ordenados . \n" );
printf ( "(R)emover Todos os Nomes da Arvore.\n" );
printf ( "(T)erminar. \n" );
fflush ( stdin );
scanf ( "%c", &opcao );
return opcao;
}
void insere_ordenado (struct Elemento **nodo, char *nominho)
{
struct Elemento *novo_no;
novo_no = (struct Elemento *) malloc(sizeof(struct Elemento) );
strcpy(novo_no->nome, nominho);
if(*nodo == NULL) // A árvore está vazia!!!
{
novo_no->esq = NULL;
novo_no->dir = NULL;
*nodo = novo_no;
}
else // A arvore não está vazia!!!
{
if (strcmp((*nodo)->nome, nominho)<0)
insere_ordenado(&(*nodo)->dir, nominho);
else
insere_ordenado(&(*nodo)->esq, nominho);
}
}