Estrutura de Dados

1

Instituto Luterano de Ensino Superior de Ji-Paraná
Curso Bacharelado em Informática
Estrutura de Dados I
Prof.: José Luiz A. Duizith

ÁRVORE (TREE)
Estrutura hierárquica (+ complexa)
Conceito:
Uma árvore “A” é um conjunto finito de de “n” nodos talque se N > 0 então: 1) Existe um nodo especial chamado raiz árvore.
2) Os restantes N-1 nodos estÃo particionados em “m” conjuntos disjuntos
A1,A2,....,An cada um dos quais é por sua vez uma árvore. Estas árvores
A1,A2,....,An sÃo chamadas de sub-árvores da raiz.
Representação:
a) Diagrama de Venn

B

E
J

I
K

A
CC
F
L

G

D

D
M
O

H
N

Estrutura de Dados I
Prof. José Luiz Andrade Duizith

P

2

b) Por Grafos:
A
A1

B
E

I

J

C
F

K

{RAIZ (ROOT) } acessa todos os nodos

L

A2

G

D

H

M

N

A3
P

O

Árvore Genérica (filhos de m > 0)
Obs.: Se cortar a Raiz A, ficaria 3 subconjuntos: A1,A2,A3.
c) Paragrafação:
A
B
E
I
J
K
F
L
C
D

G
H
P

M
N
O

Mais a esquerda → representam a raiz
Mais a direita → subconjunto

Conceitos:
Estrutura de Dados I
Prof. José Luiz Andrade Duizith

3

Um nodo raiz é dito ser um nodo pai das suas sub-árvores, cujos nodos por sua vez são os nodos filhos do nodo raiz.
→ nodo pai

X
K

Y

Z

→ nodo filho

3 filhos → Grau 3
Nodo Irmão: possuem o mesmo pai
Grau de 1 nodo: é o nº de sub-árvores que o nodo possui: se Grau = 0 → então o nodo é chamado extreno terminal ou folha
(nodos que não tem filho) se Grau > 0 → então o nodo é chamado interno
Nível de 1 nodo : é o nº de linhas (arestas) que ligam o nodo ao nodo raiz.
Nível do nodo raiz = 0
→ no desenho acima, qual o nível de k→nível=1 quantas linhas percorre até chegar a raiz.

Altura de 1 árvore : é definida pelo nível mais alto da árvore.
Nº de linhas
Ex: altura da árvore representada por grafos : 3
Floresta : conjunto (finito) de árvores disjuntas.
Se eu tirasse a raiz A então eu ficaria c/ 3