Listas não Lineares – Árvores Binárias

Juliana Jenny Kolb

teste seu conhecimento

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.

Deixe uma resposta