Árvores

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

*
*
Árvores e suas Representações
*
*
Terminologia de Árvores
Uma árvore é um grafo conexo acíclico com um nó especial, denominado raiz da árvore.
Um grafo conexo acíclico sem nenhum nó designado de raiz é chamado uma árvore sem raiz ou árvore livre.
Se T1, T2, ... , Tn são árvores disjuntas com raízes r1, r2, ... , rn, o grafo formado colocando-se um novo nó r ligado, por um único arco, a cada um dos nós r1, r2, ... , rn é uma árvore com raiz r. Os nós r1, r2, ... , rn são os filhos de r e r é pai de r1, r2, ... , rn.
*
*
A profundidade de um nó em uma árvore é o comprimento do caminho da raiz ao nó; a raiz tem profundidade 0 (zero).
A profundidade (altura) de uma árvore é a maior profundidade dos nós na árvore; em outras palavras, é o comprimento do caminho mais comprido da raiz até um dos nós.
Um nó sem filhos é chamado de folha da árvore; todos os nós que não são folhas são nós internos.
Em uma árvore binária cada nó tem, no máximo, dois filhos. Em uma árvore binária, cada filho de um nó é chamado de filho esquerdo ou filho direito.
*
*
Uma árvore binária cheia é uma árvore que tem todos os nós internos com dois filhos e onde todas as folhas estão à mesma profundidade.
Uma árvore binária completa é uma árvore binária que é quase cheia; o nível mais baixo da árvore vai se enchendo da esquerda para a direita mas pode ter folhas faltando.
*
*
Aplicações de Árvores
Os arquivos em seu computador estão organizados em uma estrutura hierárquica (de árvore), assim como os tópicos em muitos sistemas de ajuda.
Um vírus de computador espalha-se através do correio eletrônico. A cada segundo, 4 novas máquinas são infectadas. Uma estrutura de árvores quaternária mostra a disseminação do vírus.
Expressões algébricas envolvendo operações binárias podem ser representadas por árvores binárias rotuladas.
*
*
Representações de Árvores Binárias
Árvores binárias têm características especiais que gostaríamos de capturar na representação, a saber, a identidade do filho esquerdo e do direito.
O equivalente de uma matriz de adjacência é uma tabela com duas coluna (ou uma tabela de registros) onde os dados para cada nós são os filhos esquerdo e direito daquele nó.
O equivalente de uma lista de adjacência é uma coleção de registros com três campos contendo, respectivamente, o nó em questão, um ponteiro para o registro do nó filho esquerdo e um ponteiro para o registro do nó filho direito.
*
*
Algoritmos de Percurso em Árvores
Os três algoritmos mais comuns de percurso em árvores são os percursos em pré-ordem, em ordem simétrica, e em pós-ordem.
Nesses métodos de percurso, ajuda usar uma visão recorrente de árvores, onde a raiz de uma árvore tem ramificações para as raízes de suas subárvores.
Os termos pré-ordem, ordem simétrica e pós-ordem referem-se à ordem de visita da raiz em comparação aos nós das subárvores.
*
*
No percurso em pré-ordem, a raiz é visitada primeiro e depois processam-se as subárvores, da esquerda para a direita, cada uma delas em pré-ordem.
No percurso em ordem simétrica, a subárvore da esquerda é percorrida em ordem simétrica, depois a raiz é visitada e depois as outras subárvores são visitadas da esquerda para a direita, sempre em ordem simétrica. 
No percurso em pós-ordem, a raiz é a última a ser visitada, após o percurso, em pós-ordem, de todas as subárvores da esquerda para a direita.