Estruturas de Dados - T.332

Capítulo 8

Árvores




8.1 Árvores Binárias

Exemplo de Árvore: Taxonomias

Árvores representam também processos

Exemplo: Árvores de Decisão


Representação de Árvores

Árvores possuem Níveis

Representação de Árvores

a) Como um conjunto
com seus subconjuntos

b) Em notação de Listas
(LISP!). Pode também
ser interpretada como
uma notação de conjuntos.


c) Como uma estrutura
hierárquica indentada.

Árvore para o Exemplo anterior
(Niklaus Wirth - rabiscado em Alemão


Utilidade

Definições

Seqüência

Uma lista de um tipo básico T é ou
a) a lista vazia ou
b) o encadeamento de um elemento do tipo T com uma lista com o tipo-base T.

Árvore do tipo-base T (Definição Recursiva)

É ou
a) a árvore vazia ou
b) um nó do tipo T com um conjunto finito de (sub-)árvores distintas do tipo T encadeadas .

n

Lista Encadeada é uma árvore degenerada.


Nomenclatura

Raiz

Um Nó X que está (diretamente) abaixo de Y

Nível

Altura

Folha

Nó Interno

Grau de um nó interno

Grau de uma árvore

Árvore Binária

Profundidade

Comprimento de Caminho

Comprimento Médio de Caminho


Representação Interna de Árvores

Estruturas com Ponteiros

Árvore Balanceada

Tarefas: Construção de uma Árvore Binária

u

Árvores como estrutura p/Organizar Informação:

A árvore deverá possuir altura mínima

Como?

Solução: Árvore Binária Balanceada

Algoritmo:

Algoritmo : Árvore
Binária Balanceada

Algoritmo : Imprime Árvore Binária

8.1.1. Exercício

Implemente uma árvore binária balanceada para dados de entrada constituídos por um conjunto de números inteiros.