Arvore estrutura de dados

Estrutura de dados

Pode-se representar uma arvore de muitos outros modos, mas é interessante notar que, dentre os exemplos apresentados , a representação hierárquica é a que permite uma melhor visualização parentizada e não parentizada e não parentizada não permitem boa visualização da estrutura, mais podem ser uteis para guardar em arquivos os dados de uma arvore.

O desenho abaixo, não representa uma arvore , pois cada nó só pode ter um pai.

TERMINOLOGIA

Subárvore; cada nó da árvore é a raiz de uma subárvore.
GRAU: o numero de subárvores de um nó é o grau daquele nó.
FOLHA: Um nó de grau igual a zero é denominado folha ou nó terminal.
NÍVEL: O nível de nó é definido da seguinte forma ; a raiz da arvore tem nível 0, enquanto o nível dos demais nós é igual ao número de linhas que o liga a raiz , é o comprimento do caminho que vai da raiz até este nó.
ALTURA: É definida como sendo o nível mais alto da arvore

EXEMPLO.

A altura da arvore é igual á 3, pois corresponde ao nível mais alto.

Lista de exercícios (individual para próxima aula

1ª Considerando a arvore ao lado:
a)Quantas subarvores ela contem ?
R: 8 subárvore

b)Qual o grau de cada nó?
R:
Nó Grau nível
A 2 0
B 0 1
C 3 1
D 2 2
E 0 2
F 1 2
G 0 3
H 0 3
I 0 3

c)Liste os ancestrais dos nós B,G e I?;
R: b=a ; g=d ; i=f.

d)Faça na representação parentizada.
R:A(B())C(D(G())

e) Faça na representação não parentizada.
R: A2 b0 c3 d2 e0 f1 g0 h0 i0

f)Faça na representação por conjuntos.

2º a)Qual a raiz da arvore ?
R:A

b)Quais são os nodos folhas ?
R:Não tem nó nas folhas

c)Qual o grau de cada nó?;f=1;0=1;y=1;g=1;p=1;z=2;8=0;
R:a=4;b=2; f=1;0=1;y=1;g=1;p=1;z=2;8=0;9=0;c=1;h=2;r=0;s=2;w=0;3=0;d=3;k=1;t=1;4=0;e=1;n=0

d)Qual o nível de cada nó?
R:Nível0=a; 1=b; c; d; e; 2=f; h; i; k; m; n; 3=0; p; r; s; t; 4=y; z; w; 3; 4; 5=8; 9.

e)Faça a representação parentizada