TG Arvore
1772 palavras
8 páginas
Curso: Ciência da Computação.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.
A figura 4 é uma árvore binária.
A figura 5 é uma árvore binária cheia
A figura 6 é uma árvore binária completa
Exercícios
TG- Árvores – Prof. Rochedo - pág. 1
1) Responda as perguntas a seguir sobre a árvore ilustra na figura
a)
b)
c)
d)
A árvore representada é binária? Completa ou Cheia?
Qual é altura da árvore?
Qual é o filho esquerdo do nó 2?
Qual é a profundidade do nó 5?
2) Responda as questões a seguir sobre o grafo na figura correspondente com raiz a.
a)
b)
c)
d)
e)
f)
g)
Essa árvore é binária?
E uma árvore binária cheia?
E uma árvore binária completa?
Qual nó é pai de e?
Qual nó é o filho direito de e?
Qual a profundidade do nó g?
Qual a altura da árvore?
2. Representação de árvores binárias por tabelas e ponteiros
Toda árvore binária pode ser representada uma tabela e ponteiros.
Exemplo
Arvore binária tabela Filho esquerdo
Filho direito
1
2
3
2
4
5
3
0
6
4
0
0
5
0
0
6
0
0
ponteiros