CES-11
Árvores
Conceito de árvore Definição recursiva de árvore Definições associadas a árvore Representações de árvores Ordenação dos nós de uma árvore

CONCEITO DE ÁRVORE
Tantos as pilhas como as filas são estruturas lineares, isto é, de uma única dimensão. Na sua implementação, as listas ligadas possibilitam maior flexibilidade que os vetores, mas mesmo assim não permitem a representação hierárquica de dados. Árvores (trees) são estruturas hierárquicas, formadas por vértices e arestas. Ao contrário das árvores naturais, são representadas de cima para baixo: a raiz está no topo e as folhas na base.

CONCEITO DE ÁRVORE
Cada nó tem um e apenas um pai (exceto a raiz) Cada nó tem zero ou mais filhos Um nó não pode ter um ancestral como filho
Caso contrário, surgiria um ciclo...

CONCEITO DE ÁRVORE
Cada elemento:
Tem um único pai (exceto a raiz) Pode ter vários filhos Não pode ser pai de nenhum ancestral

A raiz é o único nó que não possui ancestrais.
Ex: A

Árvore é uma estrutura recursiva: cada filho é também uma árvore.

As folhas são os nós sem filhos.
Ex: E, F, G, I, J, K

CONCEITO DE ÁRVORE
Exemplos:
Árvore nula: sem nós

CONCEITO DE ÁRVORE
O número de filhos por nó e as informações armazenadas diferenciam os tipos de árvores.

A árvore ao lado representa a expressão (3+6)*(4-1)+5: as folhas possuem valores e os nós intermediários, operadores matemáticos.

1

DEFINIÇÃO RECURSIVA DE ÁRVORE CES-11
Árvores
Conceito de árvore Definição recursiva de árvore Definições Representações de árvores Ordenação dos nós de uma árvore

Um único nó, por si mesmo, é também uma árvore sem filhos, onde ele é a raiz. Seja n um nó e T1, T2, ... , Tk, árvores de raízes n1, n2, ..., nk, respectivamente. Pode-se construir uma nova árvore tornando n pai de n1, n2, ..., nk.
n

n1

n2

n3

nk

T1

T2

T3

Tk

DEFINIÇÃO RECURSIVA DE ÁRVORE CES-11
Comprovação de que a figura abaixo é uma árvore:
I, J, K são árvores sem filhos H é raiz de uma nova árvore F e G são árvores sem filhos C é raiz de uma nova árvore E é uma árvore sem filhos B é raiz de uma nova árvore Como B, C e D são árvores, A é raiz de uma nova árvore Árvores
Conceito de árvore Definição recursiva de árvore Definições Representações de árvores Ordenação dos nós de uma árvore

DEFINIÇÕES

DEFINIÇÕES

Filho esquerdo de um nó é o seu único filho ou o primeiro filho mais à esquerda.
B é o filho esquerdo de A F é o filho esquerdo de C H é o filho esquerdo de D

Irmão direito de um nó é o irmão imediatamente à direita desse nó. Nó sem irmão direito é chamado de caçula.
C é o irmão direito de B K é o irmão direito de J H, G, K são caçulas E é primogênito e caçula

2

DEFINIÇÕES
Caminho de um nó n1 a outro nk: sequência de nós n1, n2, n3, . . . nk-1, nk tais que ni é pai de ni+1, com 1 ≤ i ≤ k.
Ex: A, AB, ABE, AC, B, ACG, CF, ADHJ, ADHK, DH, DHI, etc.

DEFINIÇÕES
Cada nó pode ser alcançado a partir da raiz através de uma sequência única de arestas, chamada de caminho. O nível (ou profundidade) de um nó é o comprimento do caminho da raiz até esse nó. Altura de um nó é o comprimento do mais longo caminho desse nó a alguma folha.

O comprimento de um caminho é a sua quantidade de arestas.
Ex: A = 0, AB = 1, DHI = 2 É o número de nós menos 1

Altura 3

Nível 0
Altura 2

A altura de uma árvore não vazia é o nível máximo de um nó nessa árvore.

Altura 1

Altura 1

Nível 1 Nível 2

Altura 0

Altura 0

Altura 0

Altura 1

Altura da árvore é 3

Altura 0 Altura 0 Altura 0

Nível 3

DEFINIÇÕES
Se há um caminho de ni para nj, então ni é ancestral de nj e nj é descendente de ni. Um nó é ancestral e descendente de si mesmo. Ancestral próprio ou descendente próprio de um nó é um ancestral ou descendente, respectivamente, diferente desse nó. Na árvore ao lado:
Ancestrais próprios de J: A, D, H Descendentes próprios de D: H, I, J, K

DEFINIÇÕES
Podemos redefinir raiz e folha com os conceitos de ancestral e descendente próprios:
Raiz: nó que não possui ancestral próprio Folha: nó que não possui descendente próprio (também chamado nó terminal)

O grau de um nó é o número de seus filhos.
É o número de sub-árvores disjuntas desse nó As folhas têm grau nulo

O grau de uma árvore é o máximo entre os graus de seus nós.

DEFINIÇÕES
Um nó que não é folha é chamado de nó interno ou nó não-terminal. Irmãos: filhos de um mesmo nó. Exemplos na árvore ao lado:
Grau de C? 2 Grau de G? 0 Grau da árvore? 3 Quais os irmãos de B? C e D Quais os irmãos de E? Não há Quais os nós não-terminais? A, B, C, D e H

DEFINIÇÕES
Um conjunto de árvores é chamado de floresta. Exemplo:

3

REPRESENTAÇÕES DE ÁRVORES CES-11
Árvores
Conceito de árvore Definição recursiva de árvore Definições Representações de árvores Ordenação dos nós de uma árvore

a) Forma convencional

b) Diagrama de conjuntos

REPRESENTAÇÕES DE ÁRVORES
c) Forma parentética
Coloca-se entre parêntesis a raiz, seguida das formas parentéticas de suas sub-árvores, ordenadas da esquerda para a direita

REPRESENTAÇÕES DE ÁRVORES
d) Forma tabulada
Diretoria Departamento de Fabricação Seção de Prensas Seção de Tornos Seção de Ferramentaria Seção de Fornos Seção de Banhos Químicos Departamento de Engenharia de Produção Seção de Desenvolvimento de Projetos Seção de Desenhos Seção de Controle de Qualidade Departamento de Manutenção Seção de Eletricistas Seção de Mecânica Seção de Hidráulica Seção de Instalações Prediais

(A (B (E)) (C (F) (G)) (D (H (I) (J) (K))) )

Identificação recursiva de uma forma parentética:
Sendo c um caractere genérico, (c) é uma forma parentética correta. Se α1, α2, α3, ..., αn são formas parentéticas corretas, com n > 0, então (c α1 α2 α3 ... αn) também será.

Cada nó aparece numa linha, e seus filhos são listados com uma tabulação a mais que a desse nó.
Ex: organograma de uma empresa, índice de livros, etc.

REPRESENTAÇÕES DE ÁRVORES CES-11
e) Forma numerada (ou itemizada)
1 – Estruturas de dados 1.1 – Listas lineares 1.1.1 – Estrutura contígua 1.1.2 – Estrutura encadeada 1.1.3 – Pilhas e filas 1.2 – Árvores 1.2.1 – Definições 1.2.2 – Estruturas de dados 1.2.3 – Árvores binárias 1.3 – Grafos 1.3.1 – Grafos orientados 1.3.2 – Grafos não orientados

Árvores
Conceito de árvore Definição recursiva de árvore Definições Representações de árvores Ordenação dos nós de uma árvore

Semelhante à anterior: a numeração de um nó tem como prefixo o número de seu pai, e como sufixo um número que o diferencie dos irmãos.

4

ORDENAÇÃO

DOS NÓS DE UMA ÁRVORE

ORDENAÇÃO

DOS NÓS DE UMA ÁRVORE

a) Ordenação dos filhos de um nó
Os filhos de um nó são ordenados da esquerda para a direita Por exemplo, as duas árvores abaixo têm o mesmo pai e os mesmos filhos, mas são diferentes:

b) Extensão da ordenação da esquerda para a direita
Se X e Y são irmãos e X está à direita de Y, então todos os descendentes de X estão à direita de todos os descendentes de Y. Exemplo: C e D são irmãos e C está à esquerda de D
F e G estão à esquerda de D, H, I, J e K J não está nem à direita nem à esquerda de H, D, e A

ORDENAÇÃO

DOS NÓS DE UMA ÁRVORE

PERCURSO

POR NÍVEL (OU LARGURA)

c) Ordenação de todos os nós de uma árvore
Existem formas de se ordenar e de se percorrer sistematicamente todos os nós de uma árvore:
Ordenação ou percurso por nível Ordenação ou percurso em pré-ordem Ordenação ou percurso em pós-ordem Ordenação ou percurso em ordem central (ou in-ordem)
Busca em profundidade Busca em largura

Passos:
Primeiramente, visita-se a raiz Depois visitam-se todos os filhos da raiz, da esquerda para a direita Depois os descendentes dos filhos da esquerda para a direita, e assim por diante... Também é chamada busca ou percurso em largura A B C D E F G HI J K

COMO IMPLEMENTAR LARGURA)?

O

PERCURSO

POR NÍVEL (OU

Implementação com uso de fila:
Depois que um nó é 24(d)-4.124.ET Q 1 0 0 RG 1 0 0 rg q 8.33333 0 0 8.33333 0 0 cm BT /R13 7.68 Tf 1 0 0 1 80.5195 198.681 T BI

5

PERCURSOS EM PROFUNDIDADE
Se T é uma árvore nula, então uma lista vazia será o percurso em pré-ordem, pós-ordem e ordem-central de T. Se T consiste em um só nó, esse nó será o percurso em pré-ordem, pós-ordem e ordem-central de A. Outros casos: seja T uma árvore de raiz n e sub-árvores T1, T2, ..., Tk.
n

PERCURSO EM PRÉ-ORDEM
Passos:
Primeiramente, a raiz n de T; Em seguida, os nós de T1 em pré-ordem; Depois, os nós de T2 em pré-ordem; Assim por diante, até os nós de Tk em pré-ordem.

n1

n2

n3

nk

n1

n2

T1

T2

T3

Tk

T1

T2

2

6
Por Assim Em fim Prim Passos: ida, EM PÓS PERCURSOostnde T. pós-ordem

PERCURSO EM ORDEM-CENTRAL
Artifício manual: anotar um nó folha ao passar por ele pela 1ª vez e um nó não-terminal ao passar por ele pela 2a vez. E B A F C G I HJ K D
void OrdCentral (node n) { if (n é folha) Escrever (n); else { OrdCentral (Filho esquerdo de n); Escrever (n); for (cada filho c de n, exceto o esquerdo, da esquerda para a direita) OrdCentral (c); } }

7

Comentários