Juliana Jenny Kolb
Home > Simulados on-line > Questões de Concursos > Tecnologia da Informação (TI) > Algoritmos e Estruturas de Dados > Estruturas de Dados
Listas não Lineares – Árvores Binárias
Uma árvore é um conjunto de nós composto de um nó especial (chamado raiz) e conjuntos disjuntos de nós subordinados ao nó raiz que são eles próprios (sub)árvores.
Terminologia
Grau de um nó: a quantidade de subárvores do nó;
Grau de uma árvore: grau máximo dentre todos os nós da estrutura;
Folhas de uma árvore: nós de grau zero;
Filhos de x: raízes das subárvores de x; x é o nó pai de seus filhos;
Ancestrais de x: todos nós no caminho desde a raiz até x.
Nível de x: a raiz é nível 1; se um nó está no nível n, seus filhos estão no nível n+1;
Altura de um nó folha é sempre 1;
Altura de um nó não folha: a altura máxima dentre todas suas subárvores + 1;
Altura de uma árvore é a altura de sua raiz.
Uma árvore de grau m é dita m-ária. Árvores m-árias são de difícil representação e manipulação (por exemplo, a definição de muitos ponteiros em cada nó representa um grande desperdício de espaço ocupado por ponteiros NULL). Por este motivo, árvores m-árias são geralmente representadas por árvores binárias (veja definição a seguir) sem perda de propriedades.
Em computação, árvores (e especialmente árvores binárias) são usadas para armazenar dados (chaves e outros campos de informação) em seus nós da mesma forma que listas sequenciais e listas ligadas.
Árvores Binárias
Uma árvore binária é uma estrutura vazia ou um nó raiz e duas subárvores chamadas esquerda e direita, as quais são também árvores binárias (vazias ou não). É importante observar que uma árvore binária não é apenas uma árvore de grau máximo dois, pois há também a questão de ordem (esquerda e direita) de subárvores, conceito este que não existe na definição de árvore comum discutida no item anterior.
* os nós de uma árvore binária possuem graus zero, um ou dois.
Propriedades
Implementação Estática
Embora a implementação dinâmica seja mais comum, árvores binárias podem ser representadas em um vetor.
Isso é especialmente útil em aplicações que não sofrem grande volume de inserções e exclusões; nos demais casos a representação dinâmica continua sendo a preferida.
Os nós da árvore são dispostos ao longo do vetor em níveis, da esquerda para a direita, começando pela raiz (que ocupa a primeira posição). Como os nós inexistentes deixam posições vazias no vetor, algum tipo de controle deve ser feito para diferenciar posições livres e ocupadas (e.g., com uso de um campo booleano).
Percursos em árvore binária
Convenção: as operações possíveis (determinadas pelos ponteiros existentes) são três: visitar a raiz, deslocar-se para a esquerda e deslocar-se para a direita. A esquerda sempre tem prioridade sobre direita.
Os percursos possíveis de acordo com esta convenção são:
– Pré-ordem: visita a raiz, esquerda e direita.
– Em ordem: esquerda, visita a raiz e direita.
– Pós-ordem: esquerda, direita e visita raiz.
Referência Bibliográfica
Honda, Willian Yukio; Paraboni, Ivandré. ACH2023 – ALGORITMOS E
ESTRUTURAS DE DADOS I. Trabalho Acadêmico, 2011.