cap08ED LISTAS LINEARES FILA E PILHA

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

*
Estrutura de Dados
José Marcos Barbosa da Silveira
jmarcosbs@hotmail.com
*
Objetivos
Entender os fundamentos e aplicações de Árvores. 
*
ÁRVORES
Nos capítulos anteriores examinamos as estruturas de dados que podem ser chamadas de unidimensionais ou lineares, como vetores e listas. A importância dessas estruturas é inegável, mas elas não são adequadas para representarmos dados que devem ser dispostos de maneira hierárquica. Por exemplo, os arquivos (documentos) que criamos num computador são armazenados dentro de uma estrutura hierárquica de diretórios (pastas). Existe um diretório base dentro do qual podemos armazenar diversos sub-diretórios e arquivos. Por sua vez, dentro dos sub-diretórios, podemos armazenar outros sub-diretórios e arquivos, e assim por diante, recursivamente. 
*
ÁRVORES
Neste capítulo, vamos introduzir árvores, que são estruturas de dados adequadas para a representação de hierarquias. A forma mais natural para definirmos uma estrutura de árvore é usando recursividade. Uma árvore é composta por um conjunto de nós. Existe um nó r, denominado raiz, que contém zero ou mais sub-árvores, cujas raízes são ligadas diretamente a r. Esses nós raízes das sub-árvores são ditos filhos do nó pai, r.
Nós com filhos são comumente chamados de nós internos e nós que não têm filhos são chamados de folhas, ou nós externos. É tradicional desenhar as árvores com a raiz para cima e folhas para baixo, ao contrário do que seria de se esperar. 
*
ÁRVORES - DEFINIÇÃO
Definição
É um conjunto finito T de um ou mais nós, tais que:
a) Existe um nó principal chamado raiz (root);
b) Os demais nós formam n >= 0 conjuntos disjuntos T1, T2, ... Tn, onde cada um destes subconjuntos é uma árvore. As árvores Ti (i >= 1 e i <= n) recebem a denominação de sub-árvores.
*
ÁRVORES - TERMINOLOGIA
Terminologia
Grau
Indica o número de sub-árvores de um nó.
Observação: Se um nodo não possuir nenhuma sub-árvore é chamado de Nó Terminal ou Folha. 
*
ÁRVORES - TERMINOLOGIA
Nível
É o comprimento (número de linhas) do caminho (raiz até nó).
*
ÁRVORES - TERMINOLOGIA
Altura
É o nível mais alto da árvore. Na árvore acima, a altura é igual a 2.
Floresta
É um conjunto de zero ou mais árvores disjuntas, ou seja, se for eliminado o nó raiz da árvore, as sub-árvores que restarem chamam-se de florestas.
*
ÁRVORES BINÁRIAS
Árvores Binárias
São estruturas do tipo árvore onde o grau de cada nó é menor ou igual a dois.
*
ÁRVORES - CONVERSÃO
Conversão de Árvore Genérica em Árvore Binária
 
- Ligar os nós irmãos;
- Remover a ligação entre o nó pai e seus filhos, exceto as do primeiro filho;
*
ÁRVORES - CONVERSÃO
Nota: O nó da sub-árvore à esquerda é filho e o nó da sub-árvore à direita é irmão.
*
ÁRVORES - CAMINHAMENTO
Caminhamento em Árvores
 
Consiste em processar de forma sistemática e ordenada cada nó da árvore apenas uma vez, obtendo assim uma seqüência linear de nós. Abaixo é mostrado os tipos de caminhamentos:
 
*
ÁRVORES - CAMINHAMENTO
Caminhamento Pré-Fixado (Pré-Ordem)
1) Visitar a raiz
2) Caminhar na sub-árvore da esquerda
3) Caminhar na sub-árvore à direita
Observação: “Visitar” significa qualquer operação em relação à informação (info) do nodo.
Caminhamento: ABDECFG
 
Caminhamento In-Fixado
1) Caminhar na sub-árvore da esquerda
2) Visitar a raiz
3) Caminhar na sub-árvore da direita
Caminhamento: DBEACGF
*
ÁRVORES - CAMINHAMENTO
Caminhamento Pós-Fixado
1) Caminhar na sub-árvore da esquerda
2) Caminhar na sub-árvore da direita
3) Visitar a raiz
Caminhamento: DEBGFCA
*
EXERCÍCIOS
1) Dada a árvore abaixo responda as perguntas seguintes:
*
 Nodo Grau Nível Raiz/Folha
 A 
 B 
 C 
 D 
 E 
 F 
 G 
 H 
 I 
 J 
 L 
 M 
EXERCÍCIOS
*
Exercício
2) Transformar a árvore abaixo em binária.
*
Exercício
3) Faça a travessia depois da árvore ter sido transformada para binária (exercício 2).
Caminhamento Pré-Fixado:
Caminhamento In-Fixado:
Caminhamento Pós-Fixado:
 
*
Bibliografia
Veloso, P. A.S. ESTRUTURAS DE DADOS. CAMPUS, 2000.
Pereira, Silvio do Lago. Estrutura de dados Fundamentais. ÉRICA, 1996.
Bucknall, J. ALGORITIMOS E ESTRUTURAS DE DADOS COM DELPHI. BERKELEY BRASIL, 2002.
Wirth, N. ALGORITMOS E ESTRUTURAS DE DADOS. LTC, 1989.
Szwarcfiter, J. L. ESTRUTURAS DE DADOS E SEUS ALGORITMOS. LTC, 1994.