EDA 6

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Estrutura de Dados e Arquivos
Remis Balaniuk
(adaptado do material do prof. Nicolas Anquetil)
Unidade 5
Árvores
Definição
Representação
Árvores binarias
Árvores (definição)
Em matemática, uma árvore é um tipo especial de grafo:
tem um nó especial chamado “raiz”
não tem ciclo no grafo
tem um caminho da raiz para todos os outros nós
Árvores (definições)
Os nós 'b', 'c' e 'd' são os filhos da raiz ('h' e 'i' são filhos de 'g' que é filho de 'd', etc.)
'a' é o pai de 'b', 'c' e 'd'.
Os nós sem filhos ('e', 'f', 'c', 'h' e 'i') são folhas ou nós terminais
Nós filhos do mesmo pai são irmãos
O nível da raiz é 1, o nível dos demais nós é o nível do pai mais 1 (nível de 'b' = 2)
A altura da árvore é o número máximo de nível dela (no exemplo, a altura é 4)
Árvores (definições)
O grau de um nó é o número de filhos dele (grau de 'a' = 3, grau de 'd' = 1)
O grau da árvore (ou n-aridade) é o máximo dos graus de seus nodos (grau do exemplo=3)
Os filhos da raiz podem ser considerados raizes de sub-árvores ('b' é a raiz da sub-árvore: 'b', 'e', 'f')
Árvores binárias
Uma árvore binária é uma árvore de grau 2 (nenhum nó tem mais de 2 filhos)
Árvores binárias são decompostas em:
A raiz
Uma sub-árvore (binária) esquerda
Uma sub-árvore (binária) direita
Duas árvores binárias diferentes:
Árvores binárias
Árvores binárias podem ser implementadas assim: typedef struct s_cel { char elem; struct s_cel *esq,*dir,*pai; } cel;
 typedef cel* no;
Obs: o campo ‘pai’ nem sempre é necessário
Operações básicas sobre árvores binárias
no esq(no p): retorna o nó abaixo à esquerda de p
no dir(no p): retorna o nó abaixo à direita de p
no pai(no p): retorna o nó pai de p
no irmao(no p): retorna o nó irmão de p
bool aesq(p): retorna TRUE se p é o filho da esquerda de seu pai
bool adir(p): retorna TRUE se p é o filho da direita de seu pai
exercício
Implemente as operações irmao, aesq e adir em função da estrutura no dada e as operações esq, dir e pai.
Árvores binárias (atravessamento)
Atravessar uma árvore significa percorrer todos os seus nós, efetuando uma operação para cada
Tradicionalmente, existem 3 atravessamentos possíveis de uma árvore:
infixa ou em-ordem
prefixa ou pré-ordem
posfixa ou pós-ordem
Árvores binárias (em-ordem)
No atravessamento infixa, vamos tratar a sub-árvore esquerda em primeiro, depois a raiz e finalmente a sub-árvore direita
Por exemplo, imprimir as ávores exemplos em-ordem (atravessamento infix) produz os resultados:
Árvores binárias (pré-ordem)
No atravessamento prefixa, vamos tratar a raiz em primeiro, depois a sub-árvore esquerda e finalmente a sub-árvore direita
Imprimir as ávores exemplos pré-ordem (atravessamento prefix) produz os resultados:
Árvores binárias (pós-ordem)
No atravessamento posfixa, vamos tratar a sub-árvore esquerda em primeiro, depois a sub-árvore direita e finalmente a raiz 
Imprimir as ávores exemplos pré-ordem (atravessamento prefix) produz os resultados:
exercícios
Mostre o resultado das impressões em-ordem, pré-ordem e pós-ordem da árvore abaixo:
Árvores binárias (pré-ordem)
typedef struct s_cel { char elem; struct s_cel *esq,*dir;
} cel;
typedef cel* no;
void prefixado(no raiz) {
	pilha p;
	no q;
	inicializa(&p);
	if(raiz!=NULL) {
			push(&p,raiz);
			while(!vazia(p)) {
				q=pop(&p);
				visita(q);	
				if(dir(q)!=NULL) push(&p,dir(q));
				if(esq(q)!=NULL) push(&p,esq(q)); 		
			}
	}
}
Árvores binárias (pré-ordem)
Exercício :
Implemente a versão recursiva do algoritmo anterior.
Exercícios
Mostre o resultado das impressões em-ordem, pré-ordem e pós-ordem da árvore exemplo: (Qual é a correspondância com as notações polonesas previamente vistas?)
Escrever uma rotina C para comparar duas árvores binárias (retorna True se forem iguais)
Escrever em C as rotinas recursivas de impressão de uma árvore binária em ordem infixa, prefixa e posfixa
Escrever em C uma calculadora posfixa baseada numa árvore binária. 
Lendo uma árvore
Para teste dos exercícios anteriores implemente uma rotina recursiva que leia do teclado o conteúdo da árvore da seguinte forma:
le_arvore(raiz) {
	raiz->elem=le_conteudo()
	vai_ter_filho_a_esquerda? {
				raiz->esq=alocano()
				le_arvore(raiz->esq)
 }
	vai_ter_filho_a_direita? {
				raiz->dir=alocano()
				le_arvore(raiz->dir)
 }
}