Árvores em Estruturas de Dados: Conceitos e Percursos
Classificado em Formação e Orientação para o Emprego
Escrito em em 
português com um tamanho de 3,13 KB
Árvores: Conceitos Fundamentais
Problemas das Listas Lineares
- Forte característica sequencial (possui grande flexibilidade, mas é um ponto fraco): a movimentação é feita alcançando um nó de cada vez.
Definição e Propriedades das Árvores
- Árvores são estruturas hierárquicas.
- Principais aplicações: Algoritmos de compactação, busca, compiladores, inteligência artificial, computação gráfica.
- Definição: Uma árvore é um conjunto finito de N elementos denominados nós.
- Quando N=0: Árvore nula.
- Nó principal: Raiz. Demais: Subárvores.
- Grau: Número de subárvores de um nó.
- Filhos e Irmãos.
- Folha: Nó de grau 0.
- Nível: Distância de um nó até a raiz.
- Altura (Profundidade): Nível do último nó + 1.
(Desenho de apoio)
Árvores Binárias
Maior aplicação em computação. É quando nenhum nó tem mais de 2 filhos (grau <= 2).
Tipos de Árvores Binárias
- Árvore Estritamente Binária (Desenho de apoio): Todo nó que não é folha possui subárvores esquerda e direita não vazias, ou seja, todo nó possui 0 ou 2 filhos.
- Árvore Binária Completa: Árvore estritamente binária onde todos os nós folha encontram-se no último ou no penúltimo nível da árvore.
- Árvore Binária Cheia: Árvore estritamente binária onde todos os nós folha encontram-se no último nível.
Representação de Expressões Aritméticas
- (Desenho de apoio)
- Menor Prioridade: RH2
- Operandos: Folhas
- Operadores: Nunca (nós internos)
Árvore Binária de Busca (ABB)
- Usar arrays não é eficiente na inserção e remoção pela necessidade de reorganização dos elementos para a manutenção da ordenação.
- Usar listas resolve a inserção e remoção, mas o problema é que a pesquisa é sequencial.
- A Árvore Binária de Busca (ABB) possui boa eficiência em inserção, remoção e busca, estando sempre ordenada.
Percurso de Árvores: Listagem de Elementos
- Conceito de Visita: Percorrer a estrutura da árvore.
- Duas formas principais: Caminhando por profundidade e por largura.
Percurso em Profundidade
Todos os descendentes de um nó filho são processados antes do próximo nó filho. Existem três formas:
- Infixa (em ordem): Folha Esquerda, Raiz, Folha Direita (Ex: A + B → Esquerda, Raiz, Direita)
- Pós-fixa (pós-ordem): Folha Esquerda, Folha Direita, Raiz (Ex: AB+)
- Pré-fixa (pré-ordem): Raiz, Folha Esquerda, Folha Direita (Ex: +AB)
Percurso em Largura
- Ocorre de forma horizontal: da raiz para todos os nós filhos, depois para os filhos desses nós e assim sucessivamente.
- Cada nível da árvore é pesquisado antes que o próximo nível seja iniciado.
- O passeio em largura é denominado percurso em nível.