Centro Federal de Educação Tecnológica do Espírito Santo
Unidade de Ensino Descentralizada de Colatina
Tecnólogo em Redes de Computadores
PROGRAMAÇÃO II
Prof. Jean Eduardo Glazar
4. ÁRVORE
Uma árvore impõe uma estrutura hierárquica em uma coleção de itens. Um exemplo familiar
é a árvore genealógica. Árvores despontam de forma natural em várias áreas da ciência da
computação. Por exemplo, árvores são usadas para organizar informações em sistemas de
banco de dados e para representar a estrutura sintática de programas fontes em
compiladores.
FUNDAMENTOS
Uma árvore é uma coleção finita de n 0 nodos. Se n = 0, dizemos que a árvore é nula.
Caso contrário, uma árvore apresenta as seguintes características:
•
existe um nodo especial denominado raiz;
•
os demais nodos são particionados em T1, T2, ..., Tk estruturas disjuntas de árvores;
•
as estruturas T1, T2, ..., Tk denominam-se subárvores.
OBS: todo nodo de uma árvore é a raiz de uma subárvore.
A exigência de que as estruturas T1, T2, ...,Tk sejam coleções disjuntas, garante que um
mesmo nodo não aparecerá em mais de uma subárvore ao mesmo tempo, ou seja, nunca
teremos subárvores interligadas. Observe que cada uma das estruturas Ti é organizada na
forma de árvore, isto caracteriza uma definição recursiva.
Abaixo é dado um exemplo de representação gráfica de uma árvore.
1
Centro Federal de Educação Tecnológica do Espírito Santo
Unidade de Ensino Descentralizada de Colatina
Tecnólogo em Redes de Computadores
TERMOS MAIS USADOS
• Grau de um nodo: número de subárvores de um nodo. Por exemplo, na figura acima, o
nodo a tem grau 3, o nodo d tem grau 2 e o nodo c tem grau 1.
• Grau de uma árvore: o grau de uma árvore (n-áridade) é definido como sendo igual ao
máximo dos graus de todos os seus nodos. Na ilustração, podemos constatar que o grau
da árvore é 3, pois nenhum nodo tem mais de 3 subárvores.
• Folhas de uma árvore: é um nodo que possui grau 0, ou seja, que não possui
subárvores. Também conhecido como nodo terminal. No exemplo dado, são folhas os
nodos e, k, g, l, m, i e j.
• Filhos de um nodo X: são as raízes das subárvores do nodo X. Neste caso, o nodo X é o
pai. Os filhos do nodo b são e, f e g; h é o pai de l e m; os filhos do mesmo pai
denominam-se irmãos.
• Ancestrais de um nodo: são todos os nodos ao longo do caminho, a partir da raiz até o
nodo.
• Descendentes de um nodo: são todos os nodos abaixo deste nodo até as folhas.
• Nível de um nó: por definição dizemos que a raiz de uma árvore encontra-se no nível 1.
Estando um nodo no nível n, seus filhos estarão no nível n+1.
• Altura ou profundidade: é definida como sendo o máximo dos níveis de todos os seus
nodos. Uma árvore nula tem altura 0. A árvore da figura mostrada tem altura igual a 4. A
subárvore com raiz d tem altura 2.
4.1.
ÁRVORES BINÁRIAS
Uma árvore binária é uma árvore que pode ser nula, ou então tem as seguintes
características:
• existe um nodo especial denominado raiz;
• os demais nodos são particionados em T1, T2 estruturas disjuntas de árvores binárias;
• T1 é denominada subárvore esquerda e T2 subárvore direita da raiz.
Árvore binária é um caso especial de árvore em que nenhum nodo tem grau superior a 2,
isto é, nenhum nodo tem mais que dois filhos. Adicionalmente, para árvores binárias existe
um “senso de posição”, ou seja, distingue-se entre uma subárvore esquerda e uma direita.
Por exemplo, as árvores binárias abaixo são consideradas distintas: a primeira tem a
subárvore direita nula e a segunda, a esquerda.
2
Centro Federal de Educação Tecnológica do Espírito Santo
Unidade de Ensino Descentralizada de Colatina
Tecnólogo em Redes de Computadores
Propriedades
1. Número máximo de nodos no nível i (i > 1) de uma árvore binária é 2(i –1).
2. Número máximo de nodos em um árvore binária de altura k é 2 k – 1.
A terminologia básica utilizada para árvores binárias é a mesma definida para árvores de
grau genérico. Podemos dizer agora filho esquerdo, filho direito, etc.
4.2.
ÁRVORES DE BUSCA BINÁRIA
Uma árvore binária, cuja raiz armazena o elemento R, é denominada árvore de busca
binária se:
•
todo elemento armazenado na subárvore esquerda é menor que R;
•
nenhum elemento armazenado na subárvore direita é menor que R;
•
as subárvores esquerda e direita também são árvores de busca binária.
A árvore abaixo é um exemplo de árvore binária.
O próximo exemplo tem o elemento d na raiz, todos os elementos na subárvore esquerda (a,
b e c) são menores que a raiz, nenhum elemento da subárvore direita (d, e, f) é menor que a
raiz e, no entanto, ela não é uma árvore de busca binária. Isto é devido ao fato de a
subárvore esquerda não ser uma árvore de busca binária. Note que a subárvore esquerda,
cuja raiz é a, tem uma subárvore esquerda que armazena um elemento maior que a raiz.
Logo, a árvore como um todo não está de acordo com a definição e não é considerada,
portanto, uma árvore de busca binária.
3
Centro Federal de Educação Tecnológica do Espírito Santo
Unidade de Ensino Descentralizada de Colatina
Tecnólogo em Redes de Computadores
Operações Básicas em Árvores de Busca Binária
Ao implementarmos árvores binárias, precisamos definir o formato dos nodos a serem
empregados na organização dos dados. Como cada nodo precisa armarzenar um elemento
e referenciar duas subárvores, podemos defini-lo como a seguir. Note que estaremos
implementando uma árvore de caracteres, por alocação dinâmica. É possível implementar
utilizando vetores, mas isto é muito pouco utilizado na prática, pelas limitações que já se
conhece na implementação por vetores e porque não é uma programação muito intuitiva.
PRINCIPAIS FUNÇÕES
CriarArvore – Inicia a árvore vazia.
ArvoreVazia – Retorna verdadeiro se a árvore estiver vazia e falso caso contrário.
CriarNodoArvore – Aloca memória para um novo nodo e retorna o seu apontador.
Inserir – Insere um elemento na árvore.
Remover – Remove um elemento na árvore.
Localizar – Localiza um elemento em uma árvore.
Imprimir – Imprime a árvore. Existem várias estratégias para imprimir uma árvore.
Destruir – Destroi a árvore, liberando a memória dos nodos.
DEFINIÇÃO
TYPE Informacao = RECORD
chave : integer;
{ ou string ou outro tipo para pesquisa }
{ demais elementos de cada nodo da árvore, por exemplo:
nome, cpf, telefone, etc ... }
END;
Arvore = ^NodoArvore;
NodoArvore = RECORD
info : Informacao;
filhoEsq : Arvore;
filhoDir : Arvore;
{ Árvore da esquerda }
{ Árvore da direita }
END;
Árvore binária (quando dissermos árvore binária estaremos sempre nos referindo a árvore
de busca binária) para nós será um ponteiro para a raiz da árvore. Como para muita
estruturas definidas anteriormente, uma árvore binária vazia será representada por uma
variável ponteiro nula. Então, se tivermos em um programa uma variável arv do tipo Arvore,
que represente uma árvore binária e os seguintes elementos nesta árvore: a, b, d, e, f e g,
teremos em memória a seguinte situação.
4
Centro Federal de Educação Tecnológica do Espírito Santo
Unidade de Ensino Descentralizada de Colatina
Tecnólogo em Redes de Computadores
4.3.
INSERÇÃO
Com relação à inserção de um elemento numa árvore binária, os novos elementos inseridos
entrarão sempre na condição de folhas, isto é, um nodo não pode entrar numa árvore e já
assumir filhos.
Para inserir o elemento c na árvore da figura acima, começamos pelo nodo raiz apontado
pela variável arv (do tipo Arvore). Como c é menor que e, tomamos a subárvore da
esquerda. Comparando com a nova raiz, temos c > b e concluímos que o elemento c deverá
ser armazenado na subárvore direita. O processo se repete até chegarmos a uma subárvore
nula. Neste ponto, uma folha é alocada (para armazenar o novo elemento) e entra como raiz
da subárvore nula. No nosso exemplo, o elemento c entraria como sub-árvore esquerda do
nodo que armazena o elemento d.
Inserir um elemento numa árvore vazia é trivial. Se a árvore não se encontra vazia e o
elemento a inserir é menor que a raiz, o inserimos na subárvore esquerda; caso contrário,
devemos inseri-lo na subárvore direita.
Antes de definirmos uma função para inserir um elemento na árvore, vamos definir as
funções CriarArvore, ArvoreVazia e CriarNodoArvore.
ALGUMAS IMPLEMENTAÇÕES:
{######
Inicializar a árvore vazia
######}
PROCEDURE CriarArvore ( VAR A : Arvore);
BEGIN
A := NIL;
{ Árvore vazia. Apontador aponta para nada}
END;
5
Centro Federal de Educação Tecnológica do Espírito Santo
Unidade de Ensino Descentralizada de Colatina
Tecnólogo em Redes de Computadores
{###### Retorna TRUE se a árvore estiver vazia
#######
e FALSE caso contrario
#####
##### }
FUNCTION ArvoreVazia ( VAR A : Arvore ) : BOOLEAN;
BEGIN
IF ( A = NIL )
THEN ArvoreVazia := TRUE
ELSE ArvoreVazia := FALSE;
END;
{######
{######
{######
Aloca memória para um determinado NODO e
######}
retorna o apontador para este NODO. Se não for possível }
alocar memória, retorna NIL
######}
FUNCTION CriarNodoArvore ( e : informacao ) : Arvore;
VAR aux : Arvore;
BEGIN
IF MaxAvail < SIZEOF(NodoArvore) { ** Testa se existe memória *}
THEN BEGIN
WRITELN(‘Não existe memória suficiente’);
CriarNodoArvore := NIL;
END
ELSE BEGIN
NEW(aux);
aux^.info := e;
{** Copiar todo o registro de E para INFO}
CriarNodoArvore := aux;
END;
END;
Passemos agora a uma função para inserir um elemento em uma árvore binária.
{###### Insere um elemento ‘novo’ em um árvore binária ‘arv’ ######}
PROCEDURE Inserir ( VAR arv : Arvore; novo : Arvore );
BEGIN
{ se arvore for VAZIA, então a inserção é direta }
IF ( ArvoreVazia(arv) )
THEN BEGIN
arv := novo;
novo^.filhoEsq := NIL;
novo^.filhoDir := NIL;
END
ELSE BEGIN { se nao for vazia, então insere em um dos filhos }
{ verifica em qual arvore será inserido: na subarvore }
{ esquerda ou direita }
IF (novo^.info.chave < arv^.info.chave)
THEN Inserir(arv^.filhoEsq,novo)
ELSE Inserir(arv^.filhoDir,novo);
END;
END;
6
Centro Federal de Educação Tecnológica do Espírito Santo
Unidade de Ensino Descentralizada de Colatina
Tecnólogo em Redes de Computadores
4.4.
ATRAVESSAMENTO EM ÁRVORES BINÁRIAS
Atravessar uma árvore binária significa passar de forma sistemática, por cada um de seus
nodos, realizando um certo processamento. Os tipos mais conhecidos de atravessamento
são três:
•
em-ordem
•
pré-ordem
•
pós-ordem
No atravessamento em-ordem visitamos primeiro o lado esquerdo, depois a raiz e
finalmente o lado direito. No pré-ordem, visitamos a raiz e então o lado esquerdo e direito
repectivamente. Finalmente, no pós-ordem, o lado esquerdo e direito são, nesta ordem,
visitados e só então visitamos a raiz.
Para entender melhor cada tipo, vamos a um exemplo simples. Seja a árvore abaixo.
De acordo com o explicado acima, os elementos desta árvore seriam acessados na seguinte
ordem (de acordo com os três tipos de atravessamento):
•
em-ordem: a, b, c
•
pré-ordem: b, a, c
•
pós-ordem: a, c, b
Note que estes tipos de atravessamento servem para árvores binárias de uma forma geral.
No exemplo dado, temos uma árvore de busca binária. Nestes tipos de árvore binária, o
atravessamento em-ordem corresponde a um acesso na ordem crescente dos elementos.
Vamos a um exemplo um pouco maior.
7
Centro Federal de Educação Tecnológica do Espírito Santo
Unidade de Ensino Descentralizada de Colatina
Tecnólogo em Redes de Computadores
Caso fosse aplicado o atravessamento em-ordem para a árvore acima, os nodos seriam
visitados na ordem: a, b, c, d, e, f. Para obter esta sequência, é fácil perceber que primeiro
aplicamos o atravessamento em-ordem na subárvore esquerda (da raiz de d), visitando
portanto os elementos a, b, c. Depois, visitamos o elemento d (a raiz) e finalmente,
aplicamos o atravessamento em-ordem na subárvore direita, visitando portanto, os elemento
e e f.
Percemos então que, mais uma vez, podemos produzir um algoritmo recursivo para realizar
atravessamentos. No caso do algoritmo para atravessamento em-ordem, seja uma árvore
arv, teremos então o seguinte:
•
arv é uma árvore nula: não há nada a fazer;
•
Realizamos o atravessamento em-ordem da subárvore esquerda da raiz de arv;
•
Visitamos o elemento da raiz;
•
Realizamos o atravessamento em-ordem da subárvore direita da raiz de arv;
Os algoritmos para atravessamento pré-ordem e pós-ordem podem ser generalizados
segundo o mesmo raciocínio, só muda a ordem das ações.
Um uso muito comum de atravessamento é para imprimir os elementos de uma árvore.
Vamos então codificar funções para imprimir os elementos de uma árvore de busca binária.
Vejamos as três funções abaixo, uma para cada tipo de atravessamento.
{###### Imprime a árvore EM-ORDEM ######}
PROCEDURE ImprimirEmOrdem ( VAR arv : Arvore );
BEGIN
IF ( NOT ArvoreVazia(arv) )
THEN BEGIN
ImprimirEmOrdem(arv^.filhoEsq);
write(arv^.info.chave);
{ Imprimir todos os campos}
ImprimirEmOrdem(arv^.filhoDir);
END;
END;
{###### Imprime a árvore PRE-ORDEM ######}
PROCEDURE ImprimirPreOrdem ( VAR arv : Arvore );
BEGIN
IF ( NOT ArvoreVazia(arv) )
THEN BEGIN
write(arv^.info.chave);
{ Imprimir todos os campos }
ImprimirPreOrdem(arv^.filhoEsq);
ImprimirPreOrdem(arv^.filhoDir);
END;
END;
8
Centro Federal de Educação Tecnológica do Espírito Santo
Unidade de Ensino Descentralizada de Colatina
Tecnólogo em Redes de Computadores
{###### Imprime a árvore POS-ORDEM ######}
PROCEDURE ImprimirPosOrdem ( VAR arv : Arvore );
BEGIN
IF ( NOT ArvoreVazia(arv) )
THEN BEGIN
ImprimirPosOrdem(arv^.filhoEsq);
ImprimirPosOrdem(arv^.filhoDir);
write(arv^.info.chave);
{ Imprimir todos os campos }
END;
END;
Começamos a falar de atravessamento, dizendo que "atravessar uma árvore é passar
(visitar) por todos os seus nodos realizando, para cada um deles, um certo processamento".
Vimos funções que utilizam esses atravessamentos para imprimir elementos de uma árvore
de busca binária, entretanto qualquer outra tarefa, que se aplique a uma determinada
necessidade, pode ser feita. Por exemplo, poderíamos criar uma função para desalocar
todos os nodos de uma árvore de busca binária, quando essa não fosse mais necessária no
programa. Esta função utilizará um atravessamento pós-ordem. Vejamos abaixo.
{###### Destrói a árvore desalocando todos os seus nodos ######}
PROCEDURE Destruir( VAR arv : Arvore );
BEGIN
IF ( NOT ArvoreVazia(arv) )
THEN BEGIN
Destruir(arv^.filhoEsq);
Destruir(arv^.filhoDir);
DISPOSE(arv);
END;
END;
4.5.
LOCALIZAR UM ELEMENTO EM ÁRVORES BINÁRIAS
Se o elemento a ser localizado não se encontra na raiz da árvore, procuraremos este
elemento na sub-árvore esquerda caso ele seja menor que a raiz, e na sub-árvore direita
caso contrário. Portanto a nossa função seria:
{##### Localizar um elemnto em uma árvore. Retorna o ponteiro #####}
{##### para o elemento se encontrar e NIL caso contrário
#####}
FUNCTION Localizar( VAR arv : Arvore; e : TipoDaChave) : Arvore;
BEGIN
IF (ArvoreVazia(arv) )
THEN Localizar := NIL
ELSE BEGIN
IF (e = arv^.info.chave)
THEN Localizar := arv
ELSE IF (e < arv^.info.chave )
THEN Localizar := Localizar(arv^.filhoEsq,e)
ELSE Localizar := Localizar(arv^.filhoDir,e);
END;
END;
9
Centro Federal de Educação Tecnológica do Espírito Santo
Unidade de Ensino Descentralizada de Colatina
Tecnólogo em Redes de Computadores
4.6.
REMOÇÃO
O algoritmo para remoção em árvore de busca binária é talvez o mais trabalhoso que temos.
Ainda sim, após analisarmos todos os possíveis casos, ele parecerá bastante simples. Para
facilitar o entendimento, vamos admitir inicialmente que o elemento a ser removido
encontra-se na raiz da árvore de busca binária arv. Nestas condições, temos três
possibilidades:
1. a raiz não possui filhos: a solução é trivial. Podemos remover a raiz e anular arv;
2. a raiz possui um único filho: podemos remover o nodo raiz, substituindo-o pelo seu
nodo-filho;
3. a raiz possui dois filhos: não é possível que os dois filhos assumam o lugar do pai.
Escolhemos então o nodo que armazena o menor elemento na subárvore direita de arv.
Para entender a solução adotada para o terceiro caso, precisamos lembrar da definição de
árvore de busca binária. Segundo esta definição, não podemos ter elementos maiores nem
iguais à raiz numa subárvore esquerda. Também não podemos ter elementos menores que
a raiz numa subárvore direita. Ora, se tomamos o menor elemento da subárvore direita e o
posicionamos na raiz, então continua valendo a definição.
Sabemos que o menor elemento numa árvore de busca binária encontra-se no nodo que
ocupa a posição mais à esquerda possível. Este nodo certamente não terá um filho
esquerdo pois se o tivesse não seria o menor da árvore. Pode, entretanto, ter um filho direito
(maior ou igual).
Primeiro, desenvolveremos uma função que procura na árvore, o nodo que armazena o seu
menor elemento, desliga-o da árvore e retorna um poteiro para este nodo. Lembrando que
se este nodo tiver um filho direito, este tomará o lugar do pai.
{##### Funcao que procura o menor nodo e o retira da arvore #####}
FUNCTION TiraMenor(VAR arv : Arvore) : Arvore;
VAR aux : Arvore;
BEGIN
IF ( ArvoreVazia(arv^.filhoEsq) )
THEN BEGIN
aux := arv;
arv := arv^.filhoDir;
aux^.filhoDir := NIL;
TiraMenor := aux;
END
ELSE TiraMenor := TiraMenor(arv^.filhoEsq));
END;
Tendo implementado a função TiraMenor, podemos remover facilmente um nodo que tenha
dois filhos. Observe a árvore do desenho abaixo:
10
Centro Federal de Educação Tecnológica do Espírito Santo
Unidade de Ensino Descentralizada de Colatina
Tecnólogo em Redes de Computadores
Se quiséssemos remover o nodo raiz desta árvore bastariam as linhas de código abaixo:
VAR pn : Arvore;
BEGIN
. . .
pn := TiraMenor(arv^.filhoDir);
arv^.info = pn^.info;
DISPOSE(pn);
. . .
END;
Para entender o que a linha aux := TiraMenor(arv^.filhoDir); faz, observe o
desenho abaixo:
Abaixo mostramos a função para realizar a remoção de um elemento da árvore. Sempre
testamos se a raiz da árvore é o elemento a ser removido. Se for, basta abranger as três
11
Centro Federal de Educação Tecnológica do Espírito Santo
Unidade de Ensino Descentralizada de Colatina
Tecnólogo em Redes de Computadores
possibilidades mostradas em parágrafos anteriores. Se não, chamamos a mesma função
recursivamente, até encontrar o elemento como sendo raiz de alguma subárvore.
{ ##### Procedimeno para remover um nodo da arvore. ##### }
PROCEDURE Remover ( VAR arv : Arvore; e : informacao);
VAR pn : Arvore;
BEGIN
IF ( NOT ArvoreVazia(arv) )
THEN BEGIN
IF ( arv^.info.chave = e.chave)
THEN BEGIN
pn := arv;
IF ( ArvoreVazia(arv^.filhoEsq) )
THEN arv := arv^.filhoDir
ELSE IF ( ArvoreVazia(arv^.filhoDir) )
THEN arv := arv^.filhoEsq
ELSE BEGIN
pn := TiraMenor(arv^.filhoDir);
arv^.info := pn^.info;
END;
DISPOSE(pn);
END
ELSE IF ( e.chave < arv^.info.chave )
THEN Remover(arv^.filhoEsq, e)
ELSE Remover(arv^.filhoDir, e);
END;
END;
Com todas as funções vistas até agora já podemos realizar testes. Abaixo é dado o progrma
principal de exemplo que utiliza tudo que falamos até agora. Junte todas as funções que
vimos até agora e experimente executar o programa exemplo abaixo.
VAR arv, aux : Arvore;
e : Informacao;
BEGIN
ClrScr;
CriarArvore(arv);
e.chave := 'H';
Inserir(arv,CriarNodoArvore(e));
e.chave := 'B';
Inserir(arv,CriarNodoArvore(e));
e.chave := 'A';
Inserir(arv,CriarNodoArvore(e));
IF ( localizar(arv,'C') = NIL )
THEN writeln('Nao achou');
imprimiremordem(arv);
writeln;
imprimirpreordem(arv);
12
Centro Federal de Educação Tecnológica do Espírito Santo
Unidade de Ensino Descentralizada de Colatina
Tecnólogo em Redes de Computadores
writeln;
imprimirposordem(arv);
writeln;
e.chave := 'B';
Remover(arv,e);
imprimiremordem(arv);
Destruir(arv);
readln;
end.
4.7.
EXERCÍCIOS
1. Considere a árvore esquematizada a seguir, determine:
a) O grau de cada nodo;
b) O grau da árvore;
c) Quais são os nodos folhas;
d) Os filhos de C;
e) Os ancestrais de B, G e I;
f) O nível e altura do nodo F;
g) O nível e altura do nodo A;
h) A altura da árvore.
2. Seja uma árvore de busca binária inicialmente vazia, esquematize o seu estado final,
após terem sido inseridos os elementos 4, 1, 0, 5, 3, 7, 2, 6, 9 e 8, nesta ordem.
3. Informe o resultado após utilizar os seguintes atravessamentos na árvore do exercício 1.
a) em-ordem;
b) pós-ordem;
c) pré-ordem.
4. Descreva como seria o algoritmo para contar o número de nodos não-terminais numa
árvore de busca binária.
5. Escrever uma função que calcule a altura de uma árvore binária dada. A altura de uma
árvore é igual ao máximo nível de seus nós.
6. Faça uma função que retire o maior elemento de uma árvore de busca binária.
13
Centro Federal de Educação Tecnológica do Espírito Santo
Unidade de Ensino Descentralizada de Colatina
Tecnólogo em Redes de Computadores
Respostas:
5)
FUNCTION CalculaAltura (VAR arv : Arvore);
VAR x,y : INTEGER;
BEGIN
IF ( ArvoreVazia(arv) )
THEN CalculaAltura := 0
ELSE BEGIN
x := CalculaAltura(arv^.filhoEsq);
y := CalculaAltura(arv^.filhoDir);
IF ( x > y )
THEN CalcularAltura := 1 + x
ELSE CalcularAltura := 1 + y;
END;
END;
14