Arvore Apresenta O TG

Curso: Ciência da Computação (5º/4º semestre)
Disciplina: Teoria dos grafos
Prof. José Carlos Araújo Porto (Rochedo)

Assunto: Árvores e suas representações

1.Terminologia de Árvore
Árvore é um grafo convexo acíclico que tem um nó especial denominado raiz da árvore.
Se nenhum nó receber a denominação de raiz o grafo recebe o nome de árvore sem raiz ou árvore livre

As figuras 1 e 2 são duas árvores de raízes r.
Se considerarmos as duas arvores juntas teremos uma floresta.

Na figura 3 temos;
T1 e T2 são duas árvores disjuntas ou subárvores. r é o pai de r1 e r2. r1 e r2 são filhos de r
Os nós sem filhos são chamados de folhas Profundidade de um nó é o comprimento do caminho deste nó até a raiz da árvore.
Na figura 3 a profundidade do nó r2 é 1

Profundidade (altura) de uma árvore é o comprimento do caminho mais longo da raiz aos nós.
Na figura 3 a altura da árvore é 3

Árvore binária é a árvore que onde cada nó tem no máximo 2 filhos.

Árvore binária cheia é uma árvore binária que tem todos os nós internos com 2 filhos e todas as folhas possuem a mesma profundidade.
Exemplo: figura 5
Árvore binária completa é a árvore binária quase cheia. O nível mais baixo vai enchendo da esquerda para direita mas pode ter folhas faltando Exemplo: figura 6

Exercícios
1) Responda as perguntas a seguir sobre a árvore ilustra na figura

a) A árvore representada é binária? Completa ou Cheia?
Sim. Completa
b) Qual é altura da árvore?
2
c) Qual é o filho esquerdo do nó 2?
Nó 4
d) Qual é a profundidade do nó 5?
2

Exercícios
2) Responda as questões a seguir sobre o grafo na figura correspondente com raiz a.
a) Essa árvore é binária?
Sim
b) E uma árvore binária cheia?
Não
c) E uma árvore binária completa?
Sim
d) Qual nó é pai de e?
Nó b
e) Qual nó é o filho direito de e?
O nó e não tem filho.
O nó e é uma folha
f) Qual a profundidade do nó g?
2
g) Qual a altura da árvore?
3

2) Representação de árvores binárias por tabelas e ponteiros
Toda árvore binária pode ser representada uma