Arvores Binárias

Árvores

Linguagens de Programação II Página 1 de 15

1. Árvores

Uma árvore é uma estrutura de dados mais geral que uma lista duplamente ligada, na qual,

cada um dos seus nós contém uma chave e dois ou mais apontadores para outros nós. A

chave é a informação realmente importante, servindo os apontadores para interligação dos

nós e definição da estrutura da árvore.

As árvores geralmente são percorridas só num sentido: do inicio da árvore para os nós,

podendo contudo serem implementadas estruturas de árvores diferentes.

Exemplo: Lista Duplamente Ligada do tipo T

• É uma lista vazia, ou

• uma lista ligada de um elemento do tipo T com uma sublista de elementos do tipo T.

Exemplo: Árvore Binária do tipo T

• É uma árvore vazia, ou

• um nó do tipo T ligado a um conjunto de subarvores distintas do tipo T.

Árvores

Linguagens de Programação II Página 2 de 15

2. Representação de árvores

Árvore Genealógica:

Árvore de Decisão:

Árvores

Linguagens de Programação II Página 3 de 15

Árvore de Expressão:

Representação da expressão:

(a - b) * (c + d)

Árvore de Expressão: É uma forma

recursiva de representar uma expressão,

em forma de árvore, na qual os nós

internos representam os operadores e as

folhas da árvore representam os

operandos.

Nota:

• Na representação da expressão na árvore, teve-se em consideração as

precedências dos operadores, e a utilização de parênteses de modo a alterar as

precedências os operadores.

• Para efectuar-se o cálculo da expressão na forma sufixa, efectua-se a leitura da

árvore na forma “PósOrdem”, de modo a obter a expressão na forma sufixa.

2.1. Vantagens na utilização de árvores

• Administração de grandes quantidades de dados, em numa ordem qualquer,

permitindo a divisão de um conjunto de dados em subconjuntos menores, e

consequentemente mais eficiência nos métodos de procura de informação;

• Administração de informações hierárquicas, permitindo representar de uma

forma natural a hierarquia existente entre essa informação;

• Representação de processos decisórios, permitindo a obtenção de soluções

através da eliminação sucessiva de condições.

3. Nomenclatura

Raiz

O nó mais alto de uma árvore.

Nível

A raiz de uma árvore é definido como sendo o nível 0. Todos os nós que estão

directamente relacionados com a raiz da árvore, encontra-se no nível 1, e assim

sucessivamente.

Árvores

Linguagens de Programação II Página 4 de 15

Sucessor/Descendente

Um nó Y que se encontra num nível n+1 é sucessor/descendente directo de um nó X que

se encontra num nível n e directamente ligado a este, isto é, Y é descendente de X se:

Y = X-->esq ou Y = X-->dir

Antecessor/Ascendente

Caso inverso de sucessor/descendente.

Altura

Todos os elemento de uma árvore encontram-se num determinado nível. A altura de uma

árvore é dado pelo nível do nó de maior nível (= maior nível da árvore).

Folha

Se um nó não possui sucessores, este chama-se folha.

Nó Interno

É todo o nó que não é folha, isto é, é todo o nó que têm sucessores.

Grau de um nó

O número de sucessores directos de um nó é o seu grau.

Grau de uma árvore

O grau de uma árvore é o maior grau de entre todos os graus dos nós de uma árvore.

Árvore binária

São todas as árvore de grau 2, isto é, todas as árvores na qual os nós têm no máximo dois

descendentes.

Árvore binária de Procura

É uma árvores binária na qual os seus elementos encontram-se ordenados por ordem

crescente.

Árvores

Linguagens de Programação II Página 5 de 15

4. Árvores Binárias de Procura (Busca)

Árvores binárias de procura, também por vezes designadas por árvores binárias de busca,

generalizam a ideia de listas duplamente ligadas ordenadas por ordem crescente. Deste

modo, uma árvore binária é uma árvore de procura se em cada um dos seus nós verifica-se as