UNIP – Ciência da Computação
---------------------------------------------------------------------------------------------------------Lógica de Programação
Programação
ÁRVORES
Uma árvore é uma estrutura de dados bidimensional, não linear, que possui
propriedades espaciais e admite muitas operações de conjuntos dinâmicos,
tais como: consulta, inserção, remoção, entre outros. É diferente das listas e
pilhas, uma vez que estas são estruturas de dados lineares.
Uma árvore, de modo geral, possui as seguintes características:
nó raiz: nó do topo da árvore, do qual descendem os demais nós. É o
primeiro nó da árvore;
nó interior: nó do interior da árvore (que possui descendentes);
nó terminal: nó que não possui descendentes;
trajetória: número de nós que devem ser percorridos até o nó
determinado;
grau do nó: número de nós descendentes do nó, ou seja, o número de
subárvores de um nó;
grau da árvore: número máximo de subárvores de um nó;
altura da árvore: número máximo de níveis dos seus nós;
altura do nó: número máximo de níveis dos seus nós;
Para exemplificar a explicação sobre as características de uma árvore,
vamos fazer uma análise da árvore apresentada na figura 1:
a
b
d
c
f
e
i
g
h
j
k
|Figura 1| Árvores
o nó a é determinado nó raiz, tem grau dois pois possui dois filhos, os nós
b e c, que também podem ser chamados de subárvores ou nós
descendentes;
o nó b tem grau três pois possui três filhos : os nós d, e e f; o nó b também
é denominado pai dos nós d, e e f;
----------------------------------------------------------------------------------------------------Prof. Marcelo Nogueira
1
UNIP – Ciência da Computação
---------------------------------------------------------------------------------------------------------Lógica de Programação
Programação
os nós d e e são nós terminais, isto é, não possuem descendentes e por
isso têm grau zero;
o nó f tem grau dois e tem como filhos os nós i e j;
o nó i é um nó terminal e possui grau zero;
o nó j tem grau um e é pai do nó k, que é terminal;
o nó c tem grau dois e é pai dos nós g e h, que são nós terminais;
a árvore possui grau três, pois este é o número máximo de nós
descendentes de um único pai;
a árvore tem altura igual a 5, já o nó b tem altura igual a 4, o nó c tem
altura igual a 2, o nó k tem altura igual a 1 e assim por diante;
para definirmos a trajetória a ser percorrida vamos supor que se deseje
chegar ao nó j, então o caminho a ser percorrido será a, b, f, j, conforme
ilustrado na figura 2.
a
b
d
c
f
e
i
g
h
j
k
|Figura 2| Trajetória
As árvores podem ser do tipo listas generalizadas ou binárias. As árvores do
tipo listas generalizadas possuem nós com grau maior ou igual a zero,
enquanto uma árvore do tipo binária sempre possui nós com grau menor ou
igual a 2. Veja os exemplos de árvores apresentados na Figura 3.
ÁRVORES BINÁRIAS
Conforme já dissemos anteriormente, uma árvore binária sempre possui nós
com grau menor ou igual a dois, isto é, nenhum nó possui mais do que dois
descendentes
----------------------------------------------------------------------------------------------------Prof. Marcelo Nogueira
2
UNIP – Ciência da Computação
---------------------------------------------------------------------------------------------------------Lógica de Programação
Programação
Árvore como lista generalizada
Árvore binária
a
b
e
a
c
f
d
g
h
b
i
c
d
f
e
j
h
g
i
j
|Figura 3| Árvores
57
45
77
60
13
9
25
5
55
84
78
95
|Figura 4| Árvore Binária
diretos (dois filhos). Nesse tipo de árvore também existe uma
particularidade quanto à posição dos nós: os nós da direita sempre possuem
valor superior ao do nó pai, e os nós da esquerda sempre possuem valor
inferior ao do nó pai.
O algoritmo a seguir apresenta as variáveis que serão utilizadas para a
manipulação da árvore – note que existe grande similaridade com os nós
criados para manipulação das listas. O algoritmo tem a definição de um
----------------------------------------------------------------------------------------------------Prof. Marcelo Nogueira
3
UNIP – Ciência da Computação
---------------------------------------------------------------------------------------------------------Lógica de Programação
Programação
registro que possui as variáveis valor, esq e dir, a variável apontador, que
será utilizada para fazer a referência a nós localizados à direita e a esquerda
(da raiz ou do nó pai), e a variável raiz, que guardará o valor do nó raiz da
árvore.
EXEMPLO 1: PSEUDOCÓDIGO QUE REPRESENTA UMA ÁRVORE BINÁRIA.
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
algoritmo BArvore
aaatipo apontador: ^no_arvore
aaatipo no_arvore: registro
aaaaaaaaaaaaaaaaaaavalor: inteiro
aaaaaaaaaaaaaaaaaaaesq: apontador
aaaaaaaaaaaaaaaaaadir: apontador
aaatipo no_arvore: fim
aaavar
aaavarraiz: apontador
Função inserir (arvore: no_arvore, novoNo: inteiro): no_arvore
aaavar
aaavarapoio: no_arvore
aaainicio
aaavarSe (arvore = nulo) então
aaavarSe apoio.valor ← novoNo
aaavarSe retorne (apoio)
aaavarSenão
aaavarSe Se (novoNo < arvore.valor) então
aaavarSe Se arvore^.esq ← inserir(arvore^.esq, novoNo)
aaavarSe Senão
aaavarSe Se arvore^.dir ← inserir(arvore^.dir, novoNo)
aaavarSe Fim-se
aaavarFim-se
aaavarretorne (arvore)
aaaFim
Procedimento inserirNo (novoValor: inteiro)
aaainicio
aaavarraiz ← inserir (raiz,novoValor)
aaafim
Procedimento exibir_esquerdo
aaaarv: no_arvore
aaainicio
aaainiarv ← raiz
aaainiSe (arv <> nulo) então
aaainiSe (mostre(arv ^.valor)
exibir_esquerdo(arv ^.esq)
aaainifim
Procedimento exibir_direito
aa arv: no_arvore
aa inicio
aa iniarv ← raiz
aa iniinicio
aa iniiniSe (arv <> nulo) então
aa iniiniSe (mostre (arv^.valor)
exibir_direito (arv^.dir)
aa iniinifim
u
----------------------------------------------------------------------------------------------------Prof. Marcelo Nogueira
4
UNIP – Ciência da Computação
---------------------------------------------------------------------------------------------------------Lógica de Programação
Programação
51.
52.
53.
54.
Procedimento exibir_raiz( )
aaainicio
aaainimostre (“Raiz”, raiz)
aaafim
Os comentários serão feitos juntamente com os comentários do programa.
EXEMPLO 2: PSEUDOCÓDIGO
PARA
REPRESENTAR
O
PROCEDIMENTO
DA
EXCLUSÃO DE NÓS COM ÁRVORES BINÁRIAS.
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
Procedimento excluirNo (item: inteiro)
var
aaatempNo: no_arvore
aaapai: no_arvore
aaafilho: no_arvore
aaatemp: no_arvore
inicio
aaatempNo ← raiz
aaapai ← nulo
aaafilho ← raiz
aaaEnquanto (tempNo < > nulo .e. tempNo^.valor < > item) faça
aaaEnqpai ← tempNo
aaaEnqSe(item < tempNo^.valor) então
aaaEnqSe(tempNo ← tempNo^.esq
aaaEnqSenão
aaaEnqSeatempNo ← tempNo^.dir
aaaEnqFim-se
aaaEnqSe (tempNo = nulo) então
aaaEnqSe (Mostre (“item não localizado”)
aaaEnqFim-se
aaaEnqSe (pai = nulo) então
aaaEnqSe (Se (tempNo^.dir = nulo)
aaaEnqSe (Se (raiz ← tempNo^.esq
aaaEnqSe (Fim-se
aaaEnqSe (Se (tempNo.esq = nulo)
aaaEnqSe (Se (raiz ← tempNo^.dir
aaaEnqSe (Fim-se
aaaEnqSenão
aaaEnqSe (temp ← tempNo
aaaEnqSe (filho ← tempNo^.esq
aaaEnqSe (Enquanto (filho.dir < > nulo) faça
aaaEnqSe (Enqtemp ← filho
aaaEnqSe (Enq filho ← filho^.dir
aaaEnqSe (Fim-enquanto
aaaEnqSe (Se (filho < > tempNo^.esq) então
aaaEnqSe (Se temp^.dir ← filho.^esq
aaaEnqSe (Se temp.^esq ← raiz.^esq
aaaEnqSe (Fim-se
aaaEnqSe (filho.^dir ← raiz.^dir
aaaEnqSe (raiz ← filho
aaaEnqFim-se
aaaEnqSe (tempNo.^dir = nulo) então
aaaEnqSe Se (pai.^esq = tempNo.^esq
aaaEnqSe Se (pai.^esq ← tempNo.^esq
aaaEnqSe Senão
aaaEnqSe Se (pai.^dir ← tempNo.^esq
aaaEnqSe Fim-se
----------------------------------------------------------------------------------------------------Prof. Marcelo Nogueira
5
UNIP – Ciência da Computação
---------------------------------------------------------------------------------------------------------Lógica de Programação
Programação
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
aaaEnqSenão
aaaEnqSe Se (tempNo^.esq = tempNo) então
aaaEnqSe Se Se (pai.^esq = tempNo) então
aaaEnqSe Se Se (pai^.esq ← tempNo^.dir
aaaEnqSe Se Senão
aaaEnqSe Se Se (pai^.dir ← tempNo^.dir
aaaEnqSe Se fim-se
aaaEnqSe Senão
aaaEnqSe Se (temp ← tempNo
aaaEnqSe Se (filho ← tempNo^.esq
aaaEnqSe Se (Enquanto (filho.dir < > nulo) faça
aaaEnqSe Se (Enqtemp ← filho
aaaEnqSe Se (Enqfilho ← filho^.dir
aaaEnqSe Se (Fim-enquanto
aaaEnqSe Se (Se (filho < > tempNo.esq) então
aaaEnqSe Se (Enqtemp.^dir ← filho.esq
aaaEnqSe Se (Enqfilho.^esq ← tempNo.esq
aaaEnqSe Se (Fim-se
aaaaaaaaaaaafilho.^dir ← tempNo.^dir
aaaaaaaaaaaaSe (pai^.esq = tempNo) então
aaaaaaaaaaaaSe (pai.^esq ← filho
aaaaaaaaaaaaSenão
aaaaaaaaaaaaSe (pai.^dir ← filho
aaaaaaaaaaaafim-se
aaaEnqSe Senão
fim
----------------------------------------------------------------------------------------------------Prof. Marcelo Nogueira
6