Árvores

Prévia do material em texto

estrutura de dados II – 60 horas
Prof: Juliano Ratusznei.
Email: juliano.ratusznei@unicid.edu.br
Estrutura de Dado Árvore
Introdução à Estrutura de Dado Árvore
- Definições e terminologias;
- Aplicações;
- Representação computacional.
2
Árvore
Árvores são estruturas de dados hierárquicas.
Basicamente, árvores são formadas por um conjunto de elementos, os quais chamamos nodos (ou vértices) conectados de forma específica por um conjunto de arestas. 
Nível 0, é a raiz da árvore, e está no topo da hierarquia.
Outros nodos estão conectados ao nodo raiz e aos demais nodos
3
Árvore
4
Árvore
5
As conexões entre os nodos de uma árvore seguem uma nomenclatura genealógica. Um nodo em um dado nível está conectado a seus filhos (no nível abaixo) e a seu pai (no nível acima). A raiz da árvore, que está no nível 0, possui filhos mas não possui pai.
Árvore
Relacionamento Lógico ­ 
Hierarquia ou Subordinação 
Onde: ­ Um subconjunto dos componentes é subordinado a outro
6
Árvore
Utilização de Arvores?
 ONDE Na Computação?
7
Árvore
Pasta do Explorer
Histórico da WEB
Rotas de um trajeto Logístico
Chaves de Jogos de times de futebol
Entre outros...
8
Árvores
Arvore de Grau N – Decisão para jogar Tênis.
9
Árvores
Arvores de derivação de equações matemáticas e suas prioridades
(a*b)+(c/(d+e))
10
Árvores 
Ordenação de valores
11
Árvores
Diagramação de inclusão
12
Árvores
Diagrama de barras
13
Árvores
14
Árvore - Definição
Conjunto finito T de zero ou mais nós (nodos ou vértices), tal que:
Se número de nós é maior do que zero 
existe um nó denominado raiz da árvore, denotado por r(T)
os demais nós formam m ≥ 0 conjuntos disjuntos S1, S2, ..., Sm, onde cada um destes é uma árvore (Si são denominadas sub-árvores)
Se número de nós é igual a zero 
árvore vazia
A é a raiz
15
Árvores - Raízes
16
Árvores
17
Usando X como referência
Antecessor
Sucessor
Árvores 
Se x pertence à subárvore enraizada em v: 
­ x é descendente de v
v é ancestral de x
Se x é diferente de v, x é descendente próprio de v, e v é ancestral próprio de x ­ 
Um nó folha não possui descendentes próprios 
18
Árvores – grau de um Nó
Grau (ou grau de saída) ­ 
número de sub-árvores do nó ou
número de filhos de um nó
19
Árvore – grau da árvore
Grau de uma árvore ­ 
máximo entre os graus de seus nós
20
Árvore - nó
Nó interno (ou nó de derivação) ­
nó com grau maior do que zero
21
árvore - NÓ
Nó folha (nó terminal ou externo)
 ­ nó com grau igual a zero
22
Árvore - caminho
Um caminho é uma sequência de nós consecutivos distintos entre dois nós
 v1 alcança vk 
 vk é alcançado por v1
23
árvore - caminho
Comprimento do caminho ­ 
Número de ligações entre os nós do caminho
Comprimento do caminho = 3 (Número de arestas)
24
Árvore - nível
Nível = número de ligações entre a raiz e o nó, acrescido de uma unidade
25
árvores
Altura (profundidade) de um nó ­
número de ligações entre o nó e o nó folha (descendente dele) de maior nível, acrescido de uma unidade ­ 
Altura de nó folha é 1 
26
Árvores
27
Altura (profundidade) da árvore
­ maior nível dentre seus nós
árvores
Árvore ordenada ­ 
Ordem das sub-árvores é relevante ­ 
Uma árvore ordenada é aquela na qual os filhos estão ordenados ­ 
Assume-se que essa ordenação se desenvolva da esquerda para a direita 
28
árvores
Duas árvores são isomorfas quando puderem se tornar coincidentes pela permutação da ordem das subárvores
29
árvores
Floresta = Conjunto de árvores
30
31
image2.png
image3.png
image4.emf
image1.jpeg
image5.png
image6.png
image7.png
image8.png
image9.png
image10.png
image11.emf
ABDC
image12.png
image13.emf
ABCD
image14.png
image15.png
image16.emf
ABCD
image17.png
image18.emf
PaiXIrmãoFilho
image19.png
image20.png
image21.png
image22.png
image23.png
image24.png
image25.png
image26.png
image27.png
image28.png
image29.png
image30.png
image31.png
image32.png