Estruturas de Dados - Árvores (Parte 1)

Prévia do material em texto

CIC/UnB - Estruturas de 
dados
Árvores
´´O jardineiro é Jesus e as árveres semos 
nozes´´
(youtube)
Árvores
● São estruturas de dados úteis para 
várias aplicações
● As observaremos de forma prática e não 
formal (matemática)
● Vamos iniciar pelas árvores binárias
 
 
Árvores binárias
● Uma árvore binária ou é vazia ou é 
formada de três subconjuntos disjuntos:
– raiz
– subárvore esquerda
– subárvore direita
● As subárvores podem ser vazias
● Cada elemento é denominado 'nó' ou 
'nódo' da árvore
 
 
Árvores binárias
●
 A
 B C
 D E F
 G H I
 
 
Árvores binárias
● Nomenclatura:
– A é raiz da árvore
– B é raiz da subárvore esquerda de A
– A é pai de B e de C
– C é filho direito de A
– D é filho esquerdo de B
– D e E são filhos de B
– G é descedente de E, B e A
– A é ancestral de G, E e B
– D e E são irmãos
– D, G H e I são folhas (não têm filhos)
– B, C, E e F são às vezes chamados ´galhos´
 
 
Árvores binárias
● Não é árvore binária:
 A
 B C
 D E F
 G H I
 
 
Árvores binárias
● Não é árvore binária:
 A
 B C
 D E F
 G H I
 
 
Árvores binárias
● Não é árvore binária:
 A
 B C
 D E F
 G H I
 
 
Árvores binárias
● Nota:
– Embora as árvores naturais cresçam a 
partir de suas raízes, fincadas no solo, 
tenham ramos ou galhos e suas folhas 
estejam no alto, nas representações 
gráficas de árvores quase sempre 
colocamos as raízes no alto e as folhas 
em baixo. 
– Quando se vai das raízes para as folhas 
se diz que estamos 'descendo' a 
árvore...
 
 
Árvores binárias
● Árvore estritamente binária:
 A
 B C
 D E G F
 H I 
(todo nó não folha tem subárvores não vazias)
 
 
Árvores binárias
● Uma árvore estritamente binária com n 
folhas tem sempre 2n – 1 nós.
● Verifique!...
 
 
Árvores binárias
● O nível de um nó da árvore é definido 
assim:
– a raiz tem nível 0
– qualquer outro nó tem o nível igual ao 
nível de seu pai + 1
● A profundidade de uma árvore é o nível 
do nó (ou nós) de maior valor da árvore, 
ou seja, é o comprimento do maior 
percurso da raíz até uma folha.
Árvores binárias
● Uma árvore de profundidade 'd' é dita 'completa' se todas as 
folhas estiverem no nível d: 
 A
 B C
 D E F G
 
 
 
Árvores binárias
● Se uma árvore binária tiver m nós no 
nível L, ela terá no máximo 2m nós no 
nível L + 1.
● Um árvore binária não vazia contém um 
nó no nível 0 (raiz) e no máximo 2L no 
nível L:
 p ex: 21 == 2 no nível 1
 22 == 4 no nível 2
 23 == 8 no nível 3 ...
Árvores binárias
● Dessa forma, o total de nós de uma 
árvore binária completa de profundidade 
d pode ser calculado assim:
tn = 20 + 21 + 22 + ... + 2d
que equivale a 2d+1 – 1
● Essa árvore conterá 2d folhas e 2d -1 nós 
que não são folhas.
Árvores binárias
● Profundidade número de nós
 0 1
 1 3
 2 7
 3 15
 4 32
 5 63
 6 127
 ...
 10 2047
Árvores binárias
● Dessa forma, se tivermos uma maneira 
interessante de organizar os dados em 
uma árvore, podemos atingir qualquer 
nó com um número relativamente 
pequeno de acessos – com no máximo 
10 acessos, por exemplo, podemos 
localizar 2047 nós diferentes...
Árvores binárias
● As árvores binárias completas são uma 
classe bem particular de árvores, que 
têm algumas propriedades interessante, 
no que diz respeito a representação.
● As árvores binárias 'quase completas' 
são menos estritas mas também têm 
propriedades interessantes.
Árvores binárias
● Uma árvore binária 'quase completa' é 
definida assim:
– Todas as folhas estão no nível d ou no 
nível d-1
– Se um nó tem um descendente direito 
folha no nível d, então todas as folhas 
que sejam suas descendentes 
esquerdas também estão no nível d 
Árvores binárias
● Árvore binária quase completa:
 A
 B C
 D E F G
 H I
 
 
Árvores binárias
● Não é árvore binária quase completa:
 A
 B C
 D E F G
 H I J (J e E violam
 regra 2)
 
 
Árvores binárias
● Operações sobre árvores binárias – seja p 
um ponteiro para um nó da árvore
– info (p) - retorna a informação do nó
– left (p) - ponteiro para o filho esquerdo
– right(p) – ponteiro para o filho direito
– father(p) – ponteiro para o pai
– brother(p) – ponteiro para o irmão
– isleft(p)
– isright(p)
Árvores binárias
● Para a construção de uma árvore devem 
haver as funções:
– maketree(x) - cria a raiz, sem filhos
– setleft(p,x) - cria um filho esquerdo de p
– setright(p,x) – cria um filho direito de p
(x é a informação passada para cada nó)
Árvores binárias
● Percurso nas árvores binárias
– pré-ordem (ou profundidade)
– em-ordem (ou simétrica)
– pós-ordem
Árvores binárias
● Pré-ordem (ou profundidade)
– Visita-se a raiz
– Percorre-se a subárvore esquerda em pré-
ordem
– Percorre-se a subárvore direita em pré-
ordem
Árvores binárias
● Percurso em-ordem (ou simétrica)
– Percorre-se a subárvore esquerda em ordem
– Visita-se a raiz
– Percorre-se a subárvore direita em ordem
Árvores binárias
● Percurso em pós-ordem
– Percorre-se a subárvore esquerda em pós-
ordem
– Percorre-se a subárvore direita em pós-
ordem
– Visita-se a raiz
Árvores binárias
● Percurso em pré ordem: R E D
 A
 B C
 D E F
 G H I
 
 ?
Árvores binárias
● Percurso em pré ordem:
 A
 B C
 D E F
 G H I
 
 A B D G C E H I F
Árvores binárias
● Percurso em-ordem: E R D
 A
 B C
 D E F
 G H I
 
 
Árvores binárias
● Percurso em-ordem:
 AB C
 D E F
 G H I
 
 D G B A H E I C F
Árvores binárias
● Percurso em pós-ordem: E D R
 A
 B C
 D E F
 G H I
 
 
Árvores binárias
● Percurso em pós-ordem:
 A
 B C
 D E F
 G H I
 
 G D B H I E F C A
● Vimos, na aula anterior que as árvores podem 
ser usadas para classificação – no exemplo 
mostrado a seguir fomos entrando os 
elementos à medida em que se apresentavam, 
colocando os menores como filhos esquerdos 
dos nós já existentes e os maiores como filhos 
direitos.
 
● Depois da árvore formada, vimos que o 
percurso em-ordem daria a lista classificada 
dos elementos.
Árvores binárias
Árvores binárias
● Árvore de busca binária
 4
 3 8
 1 6 9
 2 5 7
 
 4 3 8 1 9 2 6 5 7
Árvores binárias
● Vimos também que se os elementos já se 
apresentassem em ordem teríamos uma 
árvore muito esquisita:
2
4
5
7
8
9
Árvores binárias
● Ou que se se apresentassem em ordem 
inversa também gerariam uma árvore no 
mínimo estranha:
2
4
5
7
8
9
Árvores binárias
● Isso sugere que para oferecer melhores 
resultados de busca binária seria 
interessante um 'balanceamento' da 
árvore, que será objeto de estudo mais a 
frente.
● Veremos a seguir outras aplicações para 
as árvores.
Árvores binárias
● As árvores podem representar 
expressões aritméticas:
 +
 
 A *
 B C
 A + B * C
Árvores binárias
● ou ainda:
 *
 
 + 
 A B C
 (A + B) * C
Árvores binárias
● O percurso em pós-ordem da primeira 
árvore dará sua versão polonesa:
 +
 
 A *
 B C
 A B C * +
Árvores binárias
● O percurso em pré-ordem da primeira 
árvore dará sua versão pré-fixa:
 +
 
 A *
 B C
 + A * B C
Árvores binárias
● a segunda delas visitada em pós-ordem:
 *
 
 + 
 A B C
 A B + C *
Árvores binárias
● Em outras palavras, se uma expressão 
está representada através de uma 
árvore, então o seu percurso em pós-
ordem produz sua representação em 
expressão polonesa.
● Isso é muito importante no tratamento 
de linguagens de programação, para 
auxiliar a tradução de expressões no 
código fonte para o código objeto
Árvores binárias
● Vamos agora para a representação e 
manipulação de árvores binárias em 
Linguagem C
● Uma primeira abordagem seria a de ter 
os nodos representados em um vetor, 
usando como ponteiros números inteiros 
destinados a conter índices dos demais 
elementos da árvore (filhos, pais, 
irmãos)
Árvores binárias
● #define NUMNODES 500
 struct nodetype {
 char info;
int left;
int right;
int father;
int isleft;
 };
 struct nodetype node[NUMNODES];
Árvores binárias
● A árvore estará distribuída na array, com 
a raiz começando em algum lugar dela, 
ou convencionado ou apontado por uma 
variável externa.
● Após a escolha da raiz, que pode, por 
exemplo, estar convenientemente 
colocada no elemento de índice zero da 
array, todos os demais elementos se 
encaixam (se apontam)
Árvores binárias
● Há uma lista de espaço disponível (LED), 
apontada pela variável global 'avail', que 
no começo abrange toda a array:
void initavail () {
 /* A lista disponivel inicia no nodo 0. Seu link left aponta
 o proximo nodo disponivel. O ultimo contem o valor 0 */
 avail=0; contanodo=0; // inicia o ponteiro e o contador
 for (i=0; i< NUMNODES; i++) nodes[i].left=i+1;
 nodes[NUMNODES-1].left = 0;
}
Árvores binárias
● Sempre que um nodo for necessário:
int getnode() {
 i=avail;
 avail=nodes[i].left;
 if (avail==0) return (-1); // tree overflow
 else {
 contanodo++; // para contar os nodos ativos
 return(i); // retornado o indice do prox nó disp
 }
}
Árvores binárias
● Para devolver os nodos à LED
void freenode(int n) {
 nodes[n].left=avail;
 avail=n;
 contanodo--;
}
Árvores binárias
● A árvore começa com a raiz sendo 
inserida no nodo 0, com seu conteúdo:
int maketree(int *root, char inf) {
 initavail();
 *root=getnode();
 nodes[*root].father=-1;
 nodes[*root].info=inf;
 nodes[*root].isleft=-1;
 nodes[*root].left=-1;
 nodes[*root].right=-1;
}
● O 'pai' da raíz é nulo (-1), como os demais campos. A 
chamada a maketree apaga eventuais árvores anteriores
Árvores binárias
● Para criar um filho esquerdo:
int setleft(int dad, char inf) {
 i=getnode();
 nodes[dad].left=i;
 nodes[i].father=dad;
 nodes[i].info=inf;
 nodes[i].left=-1;
 nodes[i].right=-1;
 nodes[i].isleft=1;
 return(i);
}
Árvores binárias
● Para criar um filho direito:
int setright(int dad, char inf) {
 i=getnode();
 nodes[dad].right=i;
 nodes[i].father=dad;
 nodes[i].info=inf;
 nodes[i].left=-1;
 nodes[i].right=-1;
 nodes[i].isleft=0;
 return(i);
}
Árvores binárias
● Pronto, já podemos criar a árvore. As 
rotinas já vistas estão empacotadas 
dentro de um programa de testes. No 
procedimento main desse programa 
existem diversas chamadas àquelas 
rotinas.
● Vamos detalhar o tema mais um pouco:
Árvores binárias
● O programa começa assim:
int main(void) {
 int nodo, esq, dir, nl, k; char value, cmd=' ';
 while (cmd!='t') {
 printf("Entre cmd: c-criar raiz, e-criar filho esquerdo,\n");
 printf(" d-criar filho direito, p-percorrer,\n");
 printf(" l-liberar nodo, i-ir para nodo\n");
 printf(" s-estatísticas, t-terminar\n");
 scanf("%c%c",&cmd,&nl);
 if (cmd!='t') {
switch (cmd){
case 'c' :
 printf("entre valor raiz:");
 scanf("%c%c",&value,&nl); 
 maketree(&nodo,value);
 break;
case 'e' :
Árvores binárias
● Como viram, os comandos são:
 Entre cmd: c-criar raiz, e-criar filho esquerdo,
 d-criar filho direito, p-percorrer,
 l-liberar nodo, i-ir para nodo,
 s-estatísticas, t-terminar
● Assim, deve-se primeiro criar a árvore, com o comando c, dando o valor ao 
seu nodo raíz, e a partir daí ir incluindo os filhos, netos, etc.
● Ao criar-se um filho, com os comandos e ou d, o foco do programa passará 
para o nodo filho. Portanto, ao incluir-se de novo um filho, este será filho 
do filho. O comando i vai permitir retornar ao pai, ou ir a outros nodos da 
árvore.
● Vamos detalhar estes comandos e os demais a seguir
 
Árvores binárias
● Para criar a árvore, o que deve ser feito 
pelo menos uma vez, como primeira 
operação, chamamos o comando c:
case 'c' :
 printf("entre valor raiz:");scanf("%c%c",&value,&nl); 
 maketree(&nodo,value);
 break;
1 - Nos é pedido o valor da raiz, que é repassado para o procedimento 
maketree, já visto. 
2 – maketree devolverá em nodo o valor do índice do nodo alocado na 
array (sempre 0, na realidade).
 
Árvores binárias
● Para criar o filho esquerdo, chamamos e: 
 case 'e' 
 printf("entre valor filho esquerdo:");
 scanf("%c%c",&value,&nl);
 nodo=setleft(nodo,value);
 break;
Veja que setleft guardará o valor da info passado em value e devolverá 
para nodo o valor do índice alocado para esse nodo filho. Dessa forma, o 
foco mudará para esse filho recém-criado.
O setright funciona exatamente da mesma forma, do outro lado.
Árvores binárias
● Após a criação de um filho, se quisermos 
voltar ao pai, para criar o outro filho, 
podemos usar o comando i: 
 case 'i' :
 printf("entre para onde ir:\n");
 printf(" p-para o pai\n");
 printf(" e-para filho esquerdo\n");
 printf(" d-para filho direito\n");
 printf(" i-para nodo de certa info \n");
 printf(" n-para n-esimo nodo\n");
 scanf("%c%c",&value,&nl);
 switch (value) {
 case 'p' :
 nodo=nodes[nodo].father;
 break; 
Árvores binárias
● Na verdade o comando i oferece várias 
alternativas: ir para o pai, ir para o filho direito 
ou esquerdo, ir para um nodo do qual se sabe o 
índice ou ir para um nodo do qual se sabe o 
conteúdo.
● Essa escolha é oferecida, o campo value 
recebe a opção escolhida
● Ir para pai, filhos ou para um índice é fácil:
Árvores binárias
● switch (value) {
 case 'p' :
 nodo=nodes[nodo].father;
 break;
 case 'e' :
 if (nodes[nodo].left>-1) nodo=nodes[nodo].left;
 break;
 case 'd' :
 if (nodes[nodo].right>-1) nodo=nodes[nodo].right;
 break;
 case 'n' :
 printf("entre com o numero do nodo:");
 scanf("%d%c",&k,&nl);
 if ((k>-1)&(k<avail)) nodo=k;
 break;
 }
Árvores binárias
● Ir para um certo nódo do qual se conhece algo 
da informação é mais complicado: 
case 'i' :
 printf("entre com a info do nodo:");
 scanf("%c%c",&value,&nl);
 value=findnode(value,0);
 if (value<0) printf(">>nodo não encontrado\n");
 else nodo=value;
 break;
● Vamos estudar esse algorítmo findnode...
Árvores binárias
● O algorítmo é recursivo e visa encontrar 
um elemento do qual se conhece um 
valor do campo de informação.
● Ele faz um percurso em pré-ordem, 
parando se encontrar o elemento na raiz 
da subárvore...
● Se não encontrar, ele tenta na subarvore 
esquerda e na direita... Se não encontrar 
em ambas, devolve o valor -1 
Árvores binárias
● int findnode(int inf, int nodo) {
 int ret=-1;
 if (nodes[nodo].info==inf) return (nodo); // encontrou!
 else {
 if (nodes[nodo].left>-1) ret=findnode(inf,nodes[nodo].left);
 if (ret>-1) return (ret); // encontrou na esquerda!
 if (nodes[nodo].right>-1) 
 return (findnode(inf,nodes[nodo].right)); // estará na direita?
 else return(-1); // não encontrou também na direita...
 }
}
Árvores binárias
● A qualquer momento o programa pode 
percorrer a árvore em pré-ordem:
void pre_ord(int tree) {
 printf("%c ", nodes[tree].info);
 if (nodes[tree].left>0) pre_ord(nodes[tree].left);
 if (nodes[tree].right>0) pre_ord(nodes[tree].right);
}
● Faça os algorítmos para em-ordem e pos-ordem...
Árvores binárias
● void em_ord(int tree) {
 if (nodes[tree].left>0) em_ord(nodes[tree].left);
 printf("%c ", nodes[tree].info);
 if (nodes[tree].right>0) em_ord(nodes[tree].right);
}
void pos_ord(int tree) {
 if (nodes[tree].left>0) pos_ord(nodes[tree].left);
 if (nodes[tree].right>0) pos_ord(nodes[tree].right);
 printf("%c ", nodes[tree].info);
}
Árvores binárias
● Vamos agora observar o programa 
inteiro
● E o seu funcionamento.