Estrutura de Dados II

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

ESTRUTURA DE 
DADOS II
Professor Me. Rogério de Leon Pereira
GRADUAÇÃO
Unicesumar
Reitor
Wilson de Matos Silva
Vice-Reitor
Wilson de Matos Silva Filho
Pró-Reitor de Administração
Wilson de Matos Silva Filho
Pró-Reitor de EAD
Willian Victor Kendrick de Matos Silva
Presidente da Mantenedora
Cláudio Ferdinandi
NEAD - Núcleo de Educação a Distância
Direção Operacional de Ensino
Kátia Coelho
Direção de Planejamento de Ensino
Fabrício Lazilha
Direção de Operações
Chrystiano Mincoff
Direção de Mercado
Hilton Pereira
Direção de Polos Próprios
James Prestes
Direção de Desenvolvimento
Dayane Almeida 
Direção de Relacionamento
Alessandra Baron
Head de Produção de Conteúdos
Rodolfo Encinas de Encarnação Pinelli
Gerência de Produção de Conteúdos
Gabriel Araújo
Supervisão do Núcleo de Produção de 
Materiais
Nádila de Almeida Toledo
Coordenador de conteúdo
Danillo Xavier Saes
Qualidade Editorial e Textual
Daniel F. Hey, Hellyery Agda
Design Educacional
Nádila de Almeida Toledo 
Camila Zaguini Silva
Fernando Henrique Mendes 
Rossana Costa Giani 
Projeto Gráfico
Jaime de Marchi Junior
José Jhonny Coelho
Editoração
Thayla Daiany Guimarães Cripaldi
Fernando Henrique Mendes
Revisão Textual
Jaquelina Kutsunugi, Keren Pardini, Maria 
Fernanda Canova Vasconcelos, Nayara 
Valenciano, Rhaysa Ricci Correa e Susana Inácio
Ilustração
Robson Yuiti Saito
C397 CENTRO UNIVERSITÁRIO DE MARINGÁ. Núcleo de Educação a 
Distância; PEREIRA, Rogério de Leon.
 
 Estrutura de dados II. Rogério de Leon Pereira. 
 (Reimpressão revista e atualizada)
 Maringá-Pr.: UniCesumar, 2016. 
 139 p.
“Graduação EaD”.
 
 1. Análise de Sistemas. 2. Estrutura de Dados. 3. EaD. I. Título.
ISBN 978-85-8084-578-5
CDD - 22 ed. 005.3
CIP - NBR 12899 - AACR/2
Ficha catalográfica elaborada pelo bibliotecário 
João Vivaldo de Souza - CRB-8 - 6828
Viver e trabalhar em uma sociedade global é um 
grande desafio para todos os cidadãos. A busca 
por tecnologia, informação, conhecimento de 
qualidade, novas habilidades para liderança e so-
lução de problemas com eficiência tornou-se uma 
questão de sobrevivência no mundo do trabalho.
Cada um de nós tem uma grande responsabilida-
de: as escolhas que fizermos por nós e pelos nos-
sos farão grande diferença no futuro.
Com essa visão, o Centro Universitário Cesumar – 
assume o compromisso de democratizar o conhe-
cimento por meio de alta tecnologia e contribuir 
para o futuro dos brasileiros.
No cumprimento de sua missão – “promover a 
educação de qualidade nas diferentes áreas do 
conhecimento, formando profissionais cidadãos 
que contribuam para o desenvolvimento de uma 
sociedade justa e solidária” –, o Centro Universi-
tário Cesumar busca a integração do ensino-pes-
quisa-extensão com as demandas institucionais 
e sociais; a realização de uma prática acadêmica 
que contribua para o desenvolvimento da consci-
ência social e política e, por fim, a democratização 
do conhecimento acadêmico com a articulação e 
a integração com a sociedade.
Diante disso, o Centro Universitário Cesumar al-
meja ser reconhecido como uma instituição uni-
versitária de referência regional e nacional pela 
qualidade e compromisso do corpo docente; 
aquisição de competências institucionais para 
o desenvolvimento de linhas de pesquisa; con-
solidação da extensão universitária; qualidade 
da oferta dos ensinos presencial e a distância; 
bem-estar e satisfação da comunidade interna; 
qualidade da gestão acadêmica e administrati-
va; compromisso social de inclusão; processos de 
cooperação e parceria com o mundo do trabalho, 
como também pelo compromisso e relaciona-
mento permanente com os egressos, incentivan-
do a educação continuada.
Seja bem-vindo(a), caro(a) acadêmico(a)! Você está 
iniciando um processo de transformação, pois quan-
do investimos em nossa formação, seja ela pessoal 
ou profissional, nos transformamos e, consequente-
mente, transformamos também a sociedade na qual 
estamos inseridos. De que forma o fazemos? Criando 
oportunidades e/ou estabelecendo mudanças capa-
zes de alcançar um nível de desenvolvimento compa-
tível com os desafios que surgem no mundo contem-
porâneo. 
O Centro Universitário Cesumar mediante o Núcleo de 
Educação a Distância, o(a) acompanhará durante todo 
este processo, pois conforme Freire (1996): “Os homens 
se educam juntos, na transformação do mundo”.
Os materiais produzidos oferecem linguagem dialó-
gica e encontram-se integrados à proposta pedagó-
gica, contribuindo no processo educacional, comple-
mentando sua formação profissional, desenvolvendo 
competências e habilidades, e aplicando conceitos 
teóricos em situação de realidade, de maneira a inse-
ri-lo no mercado de trabalho. Ou seja, estes materiais 
têm como principal objetivo “provocar uma aproxi-
mação entre você e o conteúdo”, desta forma possi-
bilita o desenvolvimento da autonomia em busca dos 
conhecimentos necessários para a sua formação pes-
soal e profissional.
Portanto, nossa distância nesse processo de cres-
cimento e construção do conhecimento deve ser 
apenas geográfica. Utilize os diversos recursos peda-
gógicos que o Centro Universitário Cesumar lhe possi-
bilita. Ou seja, acesse regularmente o AVA – Ambiente 
Virtual de Aprendizagem, interaja nos fóruns e en-
quetes, assista às aulas ao vivo e participe das discus-
sões. Além disso, lembre-se que existe uma equipe de 
professores e tutores que se encontra disponível para 
sanar suas dúvidas e auxiliá-lo(a) em seu processo de 
aprendizagem, possibilitando-lhe trilhar com tranqui-
lidade e segurança sua trajetória acadêmica.
Diretoria Operacional 
de Ensino
Diretoria de 
Planejamento de Ensino
Professor Me. Rogério de Leon Pereira
Possui graduação em Tecnologia em Processamento de Dados pelo Centro 
de Ensino Superior de Maringá (1999) e mestrado em Ciência da Computação 
pela Universidade Estadual de Maringá (2006). Atualmente é analista de 
informática da Universidade Estadual de Maringá. Tem experiência na área de 
Ciência da Computação, com ênfase em desenvolvimento de sistemas Web.
A
U
TO
R
SEJA BEM-VINDO(A)!
Dizem que todo homem precisa ter um filho, plantar uma árvore e escrever um livro. O 
que é um livro senão um filho que a gente cuida, alimenta, coloca embaixo do braço e 
investe toda a sua energia e aos poucos vê o seu crescimento e amadurecimento?
O que é um livro senão uma árvore que de forma inocente (ou não) é plantada na mente 
e no coração das pessoas e que um dia poderá dar flores, talvez até frutos.
O que é um livro senão um aglomerado de páginas com letras que juntas formam pala-
vras e com frases e parágrafos formam um... livro... muito óbvio.
Essa obra é uma continuação ao trabalho realizado no livro Estrutura de Dados I. Aqui 
damos seguimento ao assunto de forma mais aprofundada.
Abrimos as portas falando sobre os algoritmos de busca em largura e busca em profun-
didade, que são as principais técnicas de busca em grafos.
Irei apresentar também a fascinante estrutura conhecida como árvore binária, muito 
utilizada para a manipulação de grandes massas de dados tanto na memória principal 
como secundária. 
O próximo passo será investigar alguns algoritmos de pesquisa como a busca sequen-
cial, busca binária, árvore binária de busca, dentre outros conceitos pertinentes ao as-
sunto.
Fecharemos o conteúdo falando sobre algoritmos de ordenação. São tantos e tão inte-
ressantes que foram reservadas duas unidades inteiras para eles. Para aproximar mais 
o conteúdo acadêmico com a realidade do mercado, inserimos dois excelentes artigos 
que mostram como as técnicas de ordenação e de pesquisa são utilizadas na solução de 
problemas no dia a dia de um profissional de TI.
Espero que goste dessa pequena colherada de conhecimento e que ela sirva
para atiçar 
a sua fome pelo saber, pela tecnologia e pela ciência da computação.
APRESENTAÇÃO
ESTRUTURA DE DADOS II
8 - 9
SUMÁRIO
8 - 9
UNIDADE I
BUSCA EM GRAFOS
15 Introdução
16 Busca em Profundidade 
19 Busca em Largura 
22 Algoritmo de Dijkstra 
28 Considerações Finais 
UNIDADE II
ÁRVORES BINÁRIAS
37 Introdução
37 Árvore Binária 
39 Árvore Estritamente Binária 
41 Árvore Binária Completa 
42 Implementando Árvore Binária em C 
49 Uma Árvore Binária Diferente 
52 Considerações Finais 
SUMÁRIO
10 - 11
UNIDADE III
OPERAÇÕES DE BUSCA
63 Introdução
63 Conceitos Básicos 
66 Operação de Busca Sequencial 
67 Busca Sequencial Indexada 
69 A Busca Binária 
72 Busca Por Interpolação 
74 Busca em Árvores 
79 Considerações Finais 
UNIDADE IV
TÉCNICAS DE ORDENAÇÃO
85 Introdução
85 Preparando o Ambiente de Testes 
94 Ordenação por Bubblesort (Método da Bolha) 
97 Ordenação por Selectionsort 
99 Ordenação por Mergesort 
103 Considerações Finais 
SUMÁRIO
10 - 11
UNIDADE V
TÉCNICAS DE ORDENAÇÃO OTIMIZADAS
109 Introdução
109 Ordenação Por Quicksort 
113 Ordenação por Insertionsort 
115 Ordenação por Shellsort 
119 Considerações Finais 
 
127 CONCLUSÃO
129 REFERÊNCIAS
131 GABARITO
U
N
ID
A
D
E I
Professor Me. Rogério de Leon Pereira
BUSCA EM GRAFOS
Objetivos de Aprendizagem
 ■ Conhecer os principais algoritmos de busca em grafos e a sua 
aplicação.
Plano de Estudo
A seguir, apresentam-se os tópicos que você estudará nesta unidade:
 ■ Busca em profundidade
 ■ Busca em largura
 ■ Algoritmo de Dijkstra
14 - 15
INTRODUÇÃO
Essa unidade dá o pontapé inicial no estudo de estruturas de dados mais avan-
çadas. Veremos aqui os dois principais algoritmos de busca em grafos que são a 
base para técnicas mais complexas e eficientes. 
Veremos de perto o funcionamento do algoritmo de Dijkstra que é uma das 
melhores soluções de busca de caminhos de menor custo em grafos. 
Como leitura complementar foi inserido um artigo muito interessante dos 
professores Figueiredo e Gonzaga. Eles mostram um problema real de torres de 
transmissão, como o modelaram em um grafo e os algoritmos que usaram para 
procurar a melhor solução. 
O artigo é bem extenso e envolve alguns conceitos matemáticos que podem 
não ser de primeira necessidade para o aluno. Por isso deixei só as partes perti-
nentes ao nosso conteúdo e no final há o link para o artigo completo para aqueles 
que quiserem se aprofundar no assunto.
Lembre-se que se um problema puder ser modelado em um grafo, exis-
tem diversos algoritmos prontos que podem ser utilizados ou adaptados para 
solucioná-lo.
©SHUTTERSTOCK
14 - 15
Introdução
Re
pr
od
uç
ão
 p
ro
ib
id
a.
 A
rt
. 1
84
 d
o 
Có
di
go
 P
en
al
 e
 L
ei
 9
.6
10
 d
e 
19
 d
e 
fe
ve
re
iro
 d
e 
19
98
.
©SHUTTERSTOCK
16 - 17
BUSCA EM GRAFOS
Reprodução proibida. A
rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998.
I
BUSCA EM PROFUNDIDADE
Um grafo é uma estrutura formada por pelo menos um vértice (nó) e por um 
conjunto de arestas (arcos) que pode estar vazio. Cada aresta liga sempre dois nós 
do grafo. No algoritmo de busca em profundidade, o grafo precisa ser conexo, 
ou seja, a partir de um nó qualquer é possível navegar por suas arestas visitando 
todos os demais vértices.
Essa técnica faz com que todo um segmento do grafo seja visitado até o final 
antes que uma nova porção seja investigada. O Programa 1.1 mostra o algoritmo 
em linguagem C da técnica de busca em profundidade. 
A partir de um primeiro nó, o algoritmo coloca todos os vértices adjacentes 
em uma pilha e marca esse nó como visitado. Em seguida, ele pega o primeiro 
nó empilhado e repete o processo. A busca segue até que o alvo seja encontrado 
ou que a pilha esteja vazia.
A função buscaProfunda recebe quatro parâmetros. O primeiro é um pon-
teiro chamado grafo com a estrutura a ser pesquisada. Depois é o inteiro alvo 
que tem o valor que estamos procurando, o inteiro inicio que define de onde 
a pesquisa deve começar e o parâmetro tamanho que indica quantos nós exis-
tem no grafo.
16 - 17
Busca em Profundidade
Re
pr
od
uç
ão
 p
ro
ib
id
a.
 A
rt
. 1
84
 d
o 
Có
di
go
 P
en
al
 e
 L
ei
 9
.6
10
 d
e 
19
 d
e 
fe
ve
re
iro
 d
e 
19
98
.
//Função de Busca em Profundidade
int buscaProfunda(int *grafo, int alvo, int inicio, 
int tamanho){ 
 struct str_no pilha[tamanho]; 
 int indice = 0; 
 int achou = 0; 
 //procura o nó inicial 
 while(achou == 0){ 
 if (grafo->id == inicio){ 
 achou = 1; 
 } 
 else { 
 grafo = grafo->proximo; 
 } 
 } 
 achou = 0; 
 //procura o nó alvo 
 pilha[indice] = grafo; 
 indice++; 
 while (indice > 0 && achou ==0){ 
 if (grafo->id == alvo){ 
 achou = 1; 
 } 
 else { 
 while (grafo->proximo != Null){ 
 grafo = grafo->proximo; 
 pilha[indice] = grafo; 
 indice++; 
 } 
 //desempilha 
 grafo = pilha[indice]; 
 indice--; 
 } 
 } 
 return(grafo); 
}
Programa 1.1 – O Algoritmo de Busca em Profundidade
A primeira parte do algoritmo não é tão relevante, seu objetivo é encontrar a 
posição na lista de onde a pesquisa deve ser iniciada. Vamos ver no Programa 1.2 
mais a fundo o processo de empilhamento e desempilhamento que são o cerne 
da busca em profundidade.
18 - 19
BUSCA EM GRAFOS
Reprodução proibida. A
rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998.
I
//procura o nó alvo 
pilha[indice] = grafo; 
indice++; 
while (indice > 0 && achou ==0){ 
 if (grafo->id == alvo){ 
 achou = 1; 
 } 
 else { 
 while (grafo->proximo != Null){ 
 grafo = grafo->proximo; 
 pilha[indice] = grafo; 
 indice++; 
 } 
 //desempilha 
 grafo = pilha[indice]; 
 indice--; 
 } 
} 
return(grafo);
Programa 1.2 – Busca em Profundidade em detalhes
A pilha está vazia, então empilhamos a posição inicial da pesquisa. Temos 
uma variável indice que é usada para controlar o fluxo na pilha. O laço se repete 
enquanto houverem itens empilhados ou até que a busca seja concluída com 
sucesso.
Verificamos se o item atual é o item alvo, se for, alteramos o valor da vari-
ável achou e o laço será encerrado. No caso contrário o algoritmo visita os nós 
adjacentes ao nó atual e coloca-os na pilha. Acontece aí o processo de desempi-
lhamento no qual o último nó adjacente visitado será o ponto de partida para 
a próxima pesquisa.
Isso faz com que a pesquisa desça por um caminho até encontrar um nó que 
não tenha mais vértices adjacentes, nesse momento, o algoritmo inicia uma nova 
busca a partir do último nó empilhado.
Observe esse comportamento na Figura 1.
18 - 19
Busca em Largura
Re
pr
od
uç
ão
 p
ro
ib
id
a.
 A
rt
. 1
84
 d
o 
Có
di
go
 P
en
al
 e
 L
ei
 9
.6
10
 d
e 
19
 d
e 
fe
ve
re
iro
 d
e 
19
98
.
Figura 1: Exemplo de busca em profundidade
Fonte: <http://upload.wikimedia.org/wikipedia/commons/thumb/2/2c/Depthfirst.png/200px-Depthfirst.
png>
BUSCA EM LARGURA
A busca em largura se assemelha ao seu parente mais próximo que acabamos de 
estudar, a busca em profundidade. A principal diferença é que os nós visitados 
são enfileirados ao invés de empilhados. Isso garante que sejam percorridos 
primeiramente todos os nós mais próximos do nó atual, depois os menos dis-
tantes, os mais distantes e assim por diante.
Observe a Figura 2. A pesquisa foi iniciada no nó 1
usando o algoritmo de 
busca em largura. Ele irá visitar primeiro o nó 2, depois o 3, o 4 e assim por diante. 
20 - 21
BUSCA EM GRAFOS
Reprodução proibida. A
rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998.
I
1
3 42
5 6 7 8
9 10 11 12
Figura 2: Ordem que os nós são pesquisados na busca em largura
Fonte: <http://upload.wikimedia.org/wikipedia/commons/3/33/Breadth-first-tree.svg>
Se fôssemos aplicar a busca em profundidade no mesmo grafo começando 
pelo nó 1, a sequência seria: 1, 2, 5, 9, 10, 6, 3, 4, 7, 11, 12 e 8. Um resultado bem 
diferente, não acha?
O Programa 1.3 traz o algoritmo de busca em largura implementado na lin-
guagem C. Seu funcionamento é o mesmo que o Programa 1.1 com a diferença 
que substituímos a estrutura de pilha pela fila para armazenar os vértices visita-
dos durante a busca no grafo.
//Função de Busca em Largura 
int buscaLargura(int *grafo, int alvo, int inicio, 
int tamanho){ 
  struct str_no fila[tamanho]; 
 int indice = 0; 
 int achou = 0; 
 //procura o nó inicial 
 while(achou == 0){ 
 if (grafo->id == inicio){ 
 achou = 1; 
 } 
 else { 
 grafo = grafo->proximo; 
 } 
 } 
 achou = 0;
20 - 21
Busca em Largura
Re
pr
od
uç
ão
 p
ro
ib
id
a.
 A
rt
. 1
84
 d
o 
Có
di
go
 P
en
al
 e
 L
ei
 9
.6
10
 d
e 
19
 d
e 
fe
ve
re
iro
 d
e 
19
98
.
 //procura o nó alvo
  fila[indice] = grafo; 
 indice++; 
 while (indice > 0 && achou ==0){ 
 if (grafo->id == alvo){ 
 achou = 1; 
 } 
 else { 
 while (grafo->proximo != Null){ 
 grafo = grafo->proximo; 
        fila[indice] = grafo; 
 indice++; 
 } 
      //desenfileira 
 grafo = pilha[0]; 
 for (int i = 1; i < indice; i++){ 
 pilha[i-1] = pilha[i]; 
 } 
 indice--; 
 }
 } 
 return(grafo); 
}
Programa 1.3 – Busca em Largura
Dois algoritmos praticamente idênticos com apenas um pequeno detalhe. 
Um usa uma estrutura em pilha para guardar os nós visitados e o outro a 
estrutura de fila. Esse pequeno detalhe faz com que a busca seja totalmente 
diferente.
22 - 23
BUSCA EM GRAFOS
Reprodução proibida. A
rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998.
I
ALGORITMO DE DIJKSTRA
Em 1956, o cientista da computação holandês Edsger Dijkstra concebeu um algo-
ritmo que em sua homenagem passou a ser chamado de algoritmo de Dijkstra. 
Sua publicação ocorreu em 1958 e tem como objetivo solucionar o problema do 
caminho mais curto entre dois vértices em grafos conexos com arestas de pesos 
não negativos. 
O algoritmo de Dijkstra assemelha-se ao de busca em largura que acabamos 
de estudar, mas é considerado um algoritmo guloso, ou seja, toma a decisão que 
parece ótima no momento. A estratégia gulosa é muito interessante ao se tra-
tar de problemas complexos ou para análises em grandes quantidades de dados.
Imagine um GPS que precise buscar o caminho do ponto onde você está e 
um determinado endereço. Internamente o mapa das ruas são armazenadas em 
forma de grafos e para achar o caminho entre dois pontos basta realizar uma 
busca no grafo.
Porém, como praticamente todas as ruas de uma região são interligadas, a 
quantidade de caminhos possíveis será muito grande, por isso ignorar cami-
nhos de custo inicial elevado ajuda a diminuir de forma significativa a região de 
busca da melhor solução.
O algoritmo de Dijkstra leva em consideração uma matriz de custos. Cada 
entrada na matriz tem armazenado o custo (peso) da aresta entre dois vértices. 
Durante a visita aos vértices adjacentes, o programa inclui na fila apenas os vér-
tices de menor custo.
O Programa 1.4 traz a implementação completa do algoritmo de Dijkstra. 
Ele tem um menu de opções, permite a criação de um grafo e do peso de suas 
arestas. Ele calcula os caminhos mais curtos quaisquer dois pontos no grafo.
22 - 23
Algoritmo de Dijkstra
Re
pr
od
uç
ão
 p
ro
ib
id
a.
 A
rt
. 1
84
 d
o 
Có
di
go
 P
en
al
 e
 L
ei
 9
.6
10
 d
e 
19
 d
e 
fe
ve
re
iro
 d
e 
19
98
.
//Bibliotecas 
#include <stdio.h> 
#include <stdlib.h> 
#include <math.h> 
 
//Variáveis 
int destino, origem, vertices = 0; 
int custo, *custos = NULL; 
 
//Prototipação 
void dijkstra(int vertices,int origem,int desti-
no,int *custos); 
void menu_mostrar(void); 
void grafo_procurar(void); 
void grafo_criar(void); 
 
//Função principal 
int main(int argc, char **argv) { 
 int opt = -1; 
 //Laço principal do menu 
 do { 
 //Desenha o menu na tela 
 menu_mostrar(); 
 scanf(“%d”, &opt); 
 switch (opt) { 
 case 1: 
 //cria um novo grafo 
 grafo_criar(); 
 break; 
 case 2: 
 //procura os caminhos 
 if (vertices > 0) { 
 grafo_procurar(); 
 } 
 break; 
 } 
 } while (opt != 0); 
  printf(“\nAlgoritmo de Dijkstra finaliza-
do...\n\n”); 
 system(“pause”); 
 return 0; 
}
Programa 1.4 – Algoritmo de Dijkstra em C
24 - 25
BUSCA EM GRAFOS
Reprodução proibida. A
rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998.
I
//Implementação do algoritmo de Dijkstra 
void dijkstra(int vertices,int origem,int destino,int 
*custos)
{ 
 int i, v, cont = 0; 
 int *ant, *tmp; 
 int *z; /* vertices para os quais se conhece 
o caminho minimo */ 
 double min; 
 double dist[vertices]; /* vetor com os custos dos 
caminhos */ 
 /* aloca as linhas da matriz */ 
 ant = (int*) calloc (vertices, sizeof(int *)); 
 if (ant == NULL) { 
 system(“color fc”); 
 printf (“** Erro: Memoria Insuficiente **”); 
 exit(-1); 
 } 
 tmp = (int*) calloc (vertices, sizeof(int *)); 
 if (tmp == NULL) { 
 system(“color fc”); 
 printf (“** Erro: Memoria Insuficiente **”); 
 exit(-1); } 
   z = (int *) calloc (vertices, sizeof(int *)); 
 if (z == NULL) { 
 system(“color fc”); 
 printf (“** Erro: Memoria Insuficiente **”); 
 exit(-1); 
 } 
 for (i = 0; i < vertices; i++) { 
 if (custos[(origem - 1) * vertices + i] !=- 1) { 
 ant[i] = origem - 1; 
 dist[i] = custos[(origem-1)*vertices+i]; 
 } 
 else { 
 ant[i]= -1; 
 dist[i] = HUGE_VAL;} 
      z[i]=0; 
 } 
   z[origem-1] = 1; 
 dist[origem-1] = 0; 
 /* Laco principal */ 
 do { 
 /* Encontrando o vertice que deve entrar em z */ 
 min = HUGE_VAL; 
 for (i=0;i<vertices;i++){ 
 if (!z[i]){ 
 if (dist[i]>=0 && dist[i]<min) { 
 min=dist[i];v=i; 
 }
 } 
 }
24 - 25
Algoritmo de Dijkstra
Re
pr
od
uç
ão
 p
ro
ib
id
a.
 A
rt
. 1
84
 d
o 
Có
di
go
 P
en
al
 e
 L
ei
 9
.6
10
 d
e 
19
 d
e 
fe
ve
re
iro
 d
e 
19
98
.
/* Calculando as distancias dos novos vizinhos de z */ 
 if (min != HUGE_VAL && v != destino - 1) { 
        z[v] = 1; 
 for (i = 0; i < vertices; i++){ 
 if (!z[i]) { 
 if (custos[v*vertices+i] != -1 && dist[v] 
 + custos[v*vertices+i] < dist[i]) { 
 dist[i] = dist[v] + custos[v*vertices+i]; 
 ant[i] =v; 
 } 
 } 
 } 
 } 
 } while (v != destino - 1 && min != HUGE_VAL); 
 /* Mostra o Resultado da busca */ 
 printf(“\tDe %d para %d: \t”, origem, destino); 
 if (min == HUGE_VAL) { 
 printf(“Nao Existe\n”); 
 printf(“\tCusto: \t- \n”); 
 } 
 else { 
 i = destino; 
 i = ant[i-1]; 
 while (i != -1) { 
 tmp[cont] = i+1; 
 cont++; 
 i = ant[i]; 
 } 
 for (i = cont; i > 0 ; i--) { 
 printf(“%d -> “, tmp[i-1]); 
 } 
 printf(“%d”, destino); 
 printf(“\n\tCusto: %d\n”,(int) dist[destino-1]);
} 
} 
 
void grafo_criar(void){ 
 do { 
 printf(“\nInforme o numero de vertices (no 
minimo 3 ): “); 
 scanf(“%d”, &vertices); 
 } while (vertices < 3 ); 
 if (!custos) { 
 free(custos); } 
 custos = (int *) malloc(sizeof(int)*vertices*ver-
tices); 
 //Se o compilador falhou em alocar espaço na memória 
 if (custos == NULL) { 
 system(“color fc”); 
 printf (“** Erro: Memoria Insuficiente **”); 
 exit(-1); 
 }
26 - 27
BUSCA EM GRAFOS
Reprodução proibida. A
rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998.
I
 //Preenchendo a matriz com -1 
 for (int i = 0; i <= vertices * vertices; i++){ 
 custos[i] = -1; 
 } 
 do { 
 system(“cls”); 
 printf(“Entre com as Arestas:\n”); 
 do { 
 printf(“Origem (entre 1 e %d ou ‘0’ para 
sair): “, vertices); 
 scanf(“%d”, &origem); 
 } while (origem < 0 || origem > vertices); 
 if (origem) { 
 do { 
 printf(“Destino (entre 1 e %d, menos %d): “, 
vertices, origem); 
 scanf(“%d”, &destino); 
 } while (destino < 1 || destino > vertices || 
destino == origem); 
 do { 
 printf(“Custo (positivo) do vertice 
%d para o vertice %d: “, origem, destino); 
 scanf(“%d”,&custo); 
 } while (custo < 0); 
 custos[(origem-1) * vertices + destino - 
1] = custo; 
 } 
 } while (origem); 
}
//Busca os menores caminhos entre os vértices 
void grafo_procurar(void){ 
 int i, j; 
 system(“cls”); 
 system(“color 03”); 
 printf(“Lista dos Menores Caminhos no Grafo Dado: 
\n”); 
 for (i = 1; i <= vertices; i++) { 
 for (j = 1; j <= vertices; j++) { 
 dijkstra(vertices, i,j, custos); 
 } 
 printf(“\n”); 
 } 
 system(“pause”); 
 system(“color 07”); 
} 
26 - 27
Algoritmo de Dijkstra
Re
pr
od
uç
ão
 p
ro
ib
id
a.
 A
rt
. 1
84
 d
o 
Có
di
go
 P
en
al
 e
 L
ei
 9
.6
10
 d
e 
19
 d
e 
fe
ve
re
iro
 d
e 
19
98
.
Eu separei para você a parte principal do algoritmo de Djkstra no Programa 1.5. 
A variável min irá guardar o menor valor encontrado. Ela é inicializada com um 
valor muito grande. A constante HUGE_VAL está presente na biblioteca math.h 
e foi criada para essa finalidade.
Em seguida, existe um laço de repetição em que é verificado se a distância 
entre o vértice atual e o vértice adjacente é menor do que o contido na variável 
min. Se for o valor da variável é atualizado e o processo repete até que o vértice 
não tenha mais nós adjacentes.
min = HUGE_VAL;
for (i=0;i<vertices;i++){
  if (!z[i]){
 if (dist[i]>=0 && dist[i]<min) {
 min=dist[i];v=i;
 } 
 }
}
Programa 1.5 – O coração de Djkstra
E na prática como se aplica? Digamos que você trabalhe para uma empresa aérea. 
Cada aeroporto é um nó e cada voo entre dois aeroportos é uma aresta. Você pode 
possuir uma tabela na qual conste o preço da passagem entre dois trechos; ou 
ainda existir uma segunda tabela que tenha a duração dos voos entre as cidades. 
//Desenha o menu na tela 
void menu_mostrar(void){ 
 system(“cls”); 
 printf(“Implementacao do Algoritmo de Dijask-
tra\n”); 
 printf(“Opcoes:\n”); 
 printf(“\t 1 - Adicionar um Grafo\n”); 
 printf(“\t 2 - Procura Os Menores Caminhos no Gra-
fo\n”); 
 printf(“\t 0 - Sair do programa\n”); 
 printf(“? “); 
}
28 - 2928 - 29
BUSCA EM GRAFOS
Reprodução proibida. A
rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998.
I
No balcão de venda, o algoritmo de Dijkstra pode procurar a melhor rota 
entre a origem e o destino levando em consideração o valor da passagem ou o 
tempo de duração do voo.
Imagine a aplicação dessa técnica no ramo da logística, ou no roteamento 
de pacotes m uma rede comercial ou na escolha do fornecedor com melhor rela-
ção custo por tempo de entrega.
O algoritmo de Dijkstra é muito utilizado em situações onde é preciso mini-
mizar custos ou otimizar recursos. 
CONSIDERAÇÕES FINAIS
Nesta unidade, vimos os dois principais métodos de busca em grafos, a busca 
em profundidade e a busca em largura. Ambas as técnicas são simples e bem 
parecidas, alterando apenas a forma como os vetores visitados são armazenados.
Esses algoritmos são a base para praticamente todas as demais soluções para 
a busca de caminho em grafos conexos. 
O próprio algoritmo de Dijkstra, que tivemos a oportunidade de estudar, 
é um algoritmo de busca em largura modificado para uma solução específica, 
que é encontrar o menor caminho entre dois vértices para grafos em que pos-
suam pesos nas arestas. 
O conhecimento dessas técnicas é muito importante, pois, se um problema 
puder ser modelado na forma de um grafo, existem diversos algoritmos que 
podem ser utilizados ou adaptados para encontrar a solução, como você verá no 
artigo Aplicação de métodos de busca em grafos com nós parcialmente orde-
nados à locação de torres de transmissão apresentado no final dessa unidade.
28 - 2928 - 29
Separei um artigo muito interessante para você. É um trabalho que mostra na prática 
como a estrutura de grafos e algoritmos de busca são aplicados para a solução de pro-
blemas reais. Como o artigo é muito extenso e o seu conteúdo um pouco denso, resolvi 
fazer alguns recortes deixando os pontos mais importantes em relação à nossa matéria. 
Convido você a acessar o link no final do artigo e fazer uma leitura completa e se apro-
fundar ainda mais sobre o assunto.
APLICAÇÃO DE MÉTODOS DE BUSCA EM GRAFOS COM NÓS 
PARCIALMENTE ORDENADOS À LOCAÇÃO DE TORRES DE TRANSMISSÃO
Por: João Neiva de Figueiredo; Clóvis C. Gonzaga
RESUMO
Este artigo aborda o problema de locação 
ótima de torres de transmissão como uma 
aplicação de métodos de busca em grafos 
com nós parcialmente ordenados com uma 
modelagem que aplica a este problema 
pela primeira vez o conceito de relações de 
preferência entre nós. São primeiramente 
apresentados resultados sobre grafos e 
algoritmos de busca. As restrições eletro-
mecânicas e topográficas à obtenção do 
caminho de custo mínimo são descritas, são 
definidos os nós, arcos, custos e caminhos, 
além de outros componentes do grafo e 
são descritos os algoritmos de otimização 
utilizados. O trabalho introduz e demons-
tra a validade de relações de preferência 
entre nós, que são utilizadas (juntamente 
com comparações de custos) no processo 
de eliminação de caminhos. Este procedi-
mento aumenta a eficiência dos algoritmos 
de otimização utilizados.
Introdução
Este artigo apresenta algoritmos para otimi-
zação da locação de torres de transmissão 
e baseia-se numa modelagem inovadora 
do problema de locação de torres como 
um problema de decisões seqüenciais com 
a construção recorrente de um grafo atra-
vés da aplicação repetida de um operador 
sucessor. O trabalho introduz um processo 
de eliminação de caminhos no grafo base-
ado em relações de preferência entre nós 
que não havia sido utilizado anteriormente 
para resolver este tipo de problema e que 
resulta em aumento de eficiência na deter-
minação de uma linha de transmissão de 
custo mínimo. O objetivo do trabalho é 
apresentar uma modelagem original para 
o problema de locação de torres de trans-
missão que apresenta melhorias sobre 
algoritmos consagrados por incorporar a 
estes relações de preferência entre nós. 
Acreditamos que esta forma de modela-
gem tem amplas aplicações em outros tipos 
de problemas.
Descrição do problema.
O projeto de uma linha de transmissão com-
preende diversas etapas: especificação das 
características elétricas da linha, escolha 
do traçado, determinação de caracterís-
ticas mecânicas das torres, levantamento 
topográfico e, finalmente, a locação das 
30 - 31
torres de transmissão sobre o traçado 
escolhido. Da etapa de determinação de 
características mecânicas das torres resulta
a definição dos tipos de torres que serão 
utilizadas na linha. Resulta também desta 
etapa a especificação detalhada de todos 
os limites mecânicos que cada tipo de torre 
pode suportar, as diversas alturas disponí-
veis para cada tipo de torre e o custo de 
cada par (tipo, altura) de torre. As restri-
ções mecânicas são numerosas e incluem 
esforço transversal máximo, esforço verti-
cal mínimo para os cabos de transmissão 
e para os cabos pára-raios, trações longitu-
dinais e transversais para cadeias em torres 
de suspensão bem como outras restrições 
particulares a torres de ancoragem e de sus-
pensão. Os custos de cada torre dependem 
apenas de seu tipo e altura.
A etapa seguinte é a especificação das 
restrições topográficas com o completo 
levantamento do perfil do terreno ao longo 
do traçado da linha. As restrições topo-
gráficas incluem a altura de segurança do 
cabo (altura mínima do cabo ao solo), a 
topografia do terreno, trechos de locação 
proibida (como, por exemplo, rios e estra-
das a serem cruzados pela linha) e pontos 
de locação obrigatória. O cabo suspenso 
entre duas torres toma o formato de uma 
catenária, que neste trabalho (e normal-
mente) é aproximada por uma parábola. Ela 
deve necessariamente superar uma distân-
cia mínima do solo em todos os pontos do 
perfil topográfico (a altura de segurança). A 
catenária de segurança é a catenária virtual 
que tangencia o perfil topográfico, partindo 
do ponto na torre que representa sua altura 
decrescida da altura de segurança naquele 
ponto do traçado. Neste trabalho, o termo 
catenária é utilizado para significar catená-
rias de segurança, as ilustrações mostram 
torres com catenárias de segurança e as tor-
res têm suas alturas decrescidas da altura 
de segurança. Ao final desta etapa são 
conhecidas as restrições mecânicas e as 
restrições topográficas para o problema e 
têm-se todos os dados para iniciar o pro-
cesso de otimização – os tipos e alturas (e 
conseqüentemente custos) das torres de 
transmissão, bem como a descrição com-
pleta do perfil topográfico do terreno.
Os esforços mecânicos a que está subme-
tida uma torre somente são determinados 
quando são conhecidas as localizações e 
alturas das duas torres adjacentes a ela, ou 
seja, o tipo e conseqüentemente o custo 
de uma torre depende de sua localização 
e também da localização e altura da torre 
que a precede e da torre que a segue no tra-
çado. Conseqüentemente o procedimento 
de locação de torres passa pelo exame de 
trechos de perfil topográfico imediata-
mente à frente da última torre locada para 
identificar a melhor opção para a locação 
da próxima torre e determinar o tipo e o 
custo da torre anterior. Como será descrito 
abaixo, modelamos este problema através 
da utilização de um grafo que incorpora 
todas as opções possíveis de locação para 
a linha. Este grafo é criado recursivamente 
através de um operador sucessor aplicado 
de forma seqüencial às torres que com-
põem o extremo de linha de transmissão 
mais promissor a cada momento. Após um 
breve resumo da literatura será descrita a 
modelagem bem como os algoritmos para 
solução do problema.
O algoritmo de Dijkstra
O algoritmo de Dijkstra pode ser aplicado 
diretamente ao problema. Devido ao 
fato de o problema ser de natureza con-
30 - 31
tínua, dificilmente dois caminhos terão 
o mesmo nó terminal. Conseqüentemente 
haverá poucas eliminações de caminhos, 
e as listas podem crescer explosivamente. 
Mesmo com a utilização de tolerâncias 
para comparações entre nós, o número de 
eliminações pode ser insuficiente. O melhor 
método para reduzir as listas consiste na 
utilização de uma relação de preferência 
entre nós, descrita abaixo.
O algoritmo A*
O algoritmo A*, que reduz o número de 
expansões feitas por Dijkstra, depende de 
uma subestimativa para o custo de uma 
linha de transmissão entre um nó dado e 
o fim do perfil topográfico. Esta subesti-
mativa pode ser facilmente obtida através 
do cálculo do custo de uma linha remanes-
cente que tenha mesmo comprimento em 
um “perfil topográfico perfeito” com ondu-
lações acompanhando as catenárias entre 
as torres.
Conclusão
Este trabalho apresentou um algoritmo 
para otimização de locação de torres de 
transmissão que propõe a otimização 
global de todo o traçado e utiliza algorit-
mos eficientes de busca em grafos, com 
a incorporação de uma relação de prefe-
rência entre nós além de comparações de 
custo. Este procedimento resulta em um 
aumento de eficiência na determinação de 
uma linha de transmissão de custo mínimo. 
A modelagem em teoria de grafos utilizada 
foi detalhada, foram descritos os algorit-
mos que se beneficiam da incorporação 
de relações de preferências entre nós, e foi 
descrita a relação de preferência entre nós 
com demonstração de sua validade.
Referências Bibliográficas
(1) Bob, R.; Dabekis, C. & Fullerton, F. (1963). 
Electronic Computer Permits Optimized 
Tower Spotting of Electric Transmission 
Towers. IEEE Transactions on Power Appa-
ratus and Systems, 66.
(2) Çalis, H. (1992). A Computer Program 
for Optimization of Tower Spotting. Tese de 
Mestrado, Gazi University, Ankara, Turquia.
(3) Cherdshant, S. (1997). A Computer Pro-
gram for the Selection of Optimum Stations 
and Heights of Transmission Towers. Tese de 
Mestrado, King Mongkut Institute of Tech-
nology, Bangkok, Tailândia.
(4) Gonzaga, C. (1978). Busca de Caminhos 
em Grafos e Aplicações. I Reunião de Mate-
mática Aplicada, IBM, RJ.
(5) Gonzaga, C. (1973). Estudo de Algorit-
mos de Busca em Grafos e Sua Aplicação a 
Problemas de Planejamento. Tese de Dou-
torado, COPPE–UFRJ, Rio de Janeiro.
(6) Hart, P.; Nilsson, N. & Raphael, B. (1968). 
A Formal Basis for the Heuristic Deter-
mination of Minimum Cost Paths.  IEEE 
Transactions on Systems Science and Cyber-
netics, 4(2).
(7) Neiva de Figueiredo, J. (1978). Locação 
Ótima de Torres de Transmissão Utilizando 
Teoria de Grafos. Dissertação de Mestrado. 
COPPE/UFRJ.
(8) Neiva de Figueiredo, J.; Gonzaga, C. & 
Maculan, N. (1979). Localização Ótima de 
Torres de Transmissão Utilizando Teoria de 
Grafos. Revista Brasileira de Pesquisa Opera-
cional, II(2), 12-22.
32 - 3332 - 33
(9) Nilsson, N. (1971).  Problem Solving 
Methods in Artificial Intelligence. McGraw-
-Hill Computer Science Series.
FIGUEIREDO, João Neiva de; GONZAGA, 
Clóvis C. Aplicação de métodos de busca 
em grafos com nós parcialmente orde-
nados à locação de torres de tranmissão.
Pesqui. Oper. Rio de Janeiro, v. 23, n. 1, 
jan. 2003. Available from <http://www.
scielo.br/scielo.php?script=sci_arttex-
t&pid=S0101-74382003000100015&l-
ng=en&nrm=iso>. Access on 06 Fev. 
2013. <http://dx.doi.org/10.1590/S0101-
74382003000100015.>
32 - 3332 - 33
1. Qual é a principal diferença entre a Busca em Largura e a Busca em Profundida-
de?
2. Em que caso a Busca em Largura é mais eficiente que a Busca em Profundidade?
3. O que diferencia o algoritmo de Dijkstra e a busca em largura?
4. Digite no seu computador o Programa 1.4. Entre com o Grafo (ou parte dele) 
abaixo e faça simulações de busca de caminho mais curto entre duas cidades.
Campo Mourão
Cascavel
125
150
175
200
220
90 135
110150
205
275
12530
25
20
20
10
35
90
Foz do Iguaçu
Guarapuava
Irati
Ponta Grossa
Curitiba
OurinhosLondrinaArapongas
Mandaguari
Maringá
Jandaia do Sul
Apucarana
Fonte: <http://www.professeurs.polymtl.ca/michel.gagnon/Disciplinas/Bac/IA/ResolProb/MapaParana.gif>
U
N
ID
A
D
E II
Professor Me. Rogério de Leon Pereira
ÁRVORES BINÁRIAS
Objetivos de Aprendizagem
 ■ Conhecer a estrutura de árvore binária.
 ■ Aprender sobre árvore estritamente binária.
 ■ Reconhecer uma árvore binária completa.
 ■ Implementar uma árvore binária em linguagem
C.
Plano de Estudo
A seguir, apresentam-se os tópicos que você estudará nesta unidade:
 ■ Árvore Binária
 ■ Árvore Estritamente Binária
 ■ Árvore Binária Completa
 ■ Implementando Árvore Binária em C
 ■ Uma Árvore Binária diferente
36 - 37
INTRODUÇÃO
Nesta unidade, estudaremos uma estru-
tura de dados útil para várias aplicações: 
a árvore binária. Defi niremos algumas 
formas dessa estrutura de dados e mos-
traremos como podem ser implementadas 
na linguagem C. A árvore como estrutura 
é muito utilizada para organizar infor-
mações armazenadas tanto na memória 
principal como na secundária. Isso se dá 
devido ao fato de ser fácil e rápida a pes-
quisa de dados em árvores. Daremos foco 
no entendimento da estrutura e não na 
sua defi nição matemática.
ÁRVORE BINÁRIA
Segundo Tenenbaum (1995, p. 303),
Uma árvore binária é um conjunto fi nito de elementos que está vazio 
ou é particionado em três subconjuntos disjuntos. O primeiro subcon-
junto contém um único elemento, chamado raiz da árvore. Os outros 
dois subconjuntos são em si mesmos árvores binárias, chamadas su-
bárvores esquerda e direita da árvore original. Uma subárvore esquer-
da ou direita pode estar vazia. Cada elemento de uma árvore binária é 
chamado nó da árvore.
A Figura 3 apresenta um exemplo de árvore binária. Essa árvore possui 9 nós, 
sendo A o nó raiz da árvore. Ela possui uma subárvore esquerda com raiz em 
B e uma direita com raiz em C. A subárvore com raiz em B possui uma subár-
vore esquerda com raiz em D, e a direita com raiz em E. A subárvore com raiz 
em C possui uma subárvore esquerda vazia e uma subárvore direita com raiz 
©shutterstock
36 - 37
Introdução
Re
pr
od
uç
ão
 p
ro
ib
id
a.
 A
rt
. 1
84
 d
o 
Có
di
go
 P
en
al
 e
 L
ei
 9
.6
10
 d
e 
19
 d
e 
fe
ve
re
iro
 d
e 
19
98
.
38 - 39
ÁRVORES BINÁRIAS
Reprodução proibida. A
rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998.
II
em F. As árvores binárias com raiz em D, G, H e I possuem subárvore direita e 
esquerda vazias. 
A
C B
D E F 
H IG 
Figura 3: Um exemplo de árvore binária
Fonte: o autor
Se A é o nó raiz de uma árvore binária e tem uma subárvore com raiz em B, 
então se diz que A é pai de B e B é filho esquerda de A. Na mesma forma, se A 
tem uma subárvore direita com raiz em C, diz-se que A é pai de C e C é filho 
direita de A. Um nó sem filhos é chamado de folha. Na árvore representada pela 
Figura 3 os nós D, G, H e I são considerados folhas.
Os nós D e E são ambos filhos de B, dessa forma podemos considerá-los 
como nós irmãos. Também podemos classificar os nós de acordo com a sua 
hereditariedade. O nó B é ancestral dos nós D, E e G, da mesma forma que esses 
três nós são descendentes de B. 
Uma árvore binária é um tipo de grafo que tem regras específicas na sua 
construção. Cada nó tem no máximo dois filhos e um único pai, excetuando-
se o nó raiz da árvore principal que é órfão.
38 - 39
Árvore Estritamente Binária
Re
pr
od
uç
ão
 p
ro
ib
id
a.
 A
rt
. 1
84
 d
o 
Có
di
go
 P
en
al
 e
 L
ei
 9
.6
10
 d
e 
19
 d
e 
fe
ve
re
iro
 d
e 
19
98
.
Quando se percorre uma árvore a partir da raiz em direção às folhas, diz-se 
que está caminhando na árvore para baixo ou que está descendo na árvore. De 
forma análoga, quando se está percorrendo uma árvore a partir de uma de suas 
folhas em direção à raiz, diz--se que está caminhando para cima ou subindo na 
árvore. Se fôssemos fazer uma analogia entre uma árvore na informática e uma 
árvore real (planta), na computação as árvores seriam representadas de cabeça 
para baixo.
ÁRVORE ESTRITAMENTE BINÁRIA
Uma árvore é considerada estritamente binária se todo nó que não for folha 
tenha sempre subárvores direita e esquerda não vazias. Na Figura 4, temos um 
exemplo de árvore estritamente binária. São considerados folhas os nós C, D, F 
e G. Os nós A, B e E possuem subárvores esquerda e direita não vazias.
A 
C B 
D E
G F 
Figura 4: Um exemplo de árvore estritamente binária
Fonte: o autor.
A árvore apresentada na Figura 3 não pode ser considerada como uma árvore 
estritamente binária já que o nó C possui uma subárvore esquerda vazia, e o nó 
E possui uma subárvore direita vazia.
40 - 41
ÁRVORES BINÁRIAS
Reprodução proibida. A
rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998.
II
A quantidade de nós presentes em uma árvore estritamente binária se dá 
pela fórmula ( ) 1*2 −= fn em que f é o número de folhas na árvore. Vamos 
testar essa fórmula a partir da árvore representada pela Figura 4. 
A árvore possui 4 folhas, quais sejam os nós: C, D, F e G. Aplicando-se a 
fórmula temos:
( ) 1*2 −= fn
Como f = 4, substituímos o valor de f na fórmula:
( ) 14*2 −=n
Realizamos a multiplicação e, em seguida, a subtração:
( ) 18 −=n
Temos então que:
7=n
A árvore possui exatamente 7 nós: A, B, C, D, E, F e G. 
Também podemos calcular a quantidade de folhas em uma árvore estrita-
mente binária pela dedução da fórmula ( ) 1*2 −= fn :
( ) 1*2 −= fn
Adicionando 1 em ambos os lados da igualdade:
( ) 11*21 +−=+ fn
Efetuando-se o cálculo:
( )fn *21 =+
Dividindo ambos os lados da igualdade por 2:
( )
2
*2
2
1 fn
=
+
Efetuando-se o cálculo:
fn =+
2
1
40 - 41
Árvore Binária Completa
Re
pr
od
uç
ão
 p
ro
ib
id
a.
 A
rt
. 1
84
 d
o 
Có
di
go
 P
en
al
 e
 L
ei
 9
.6
10
 d
e 
19
 d
e 
fe
ve
re
iro
 d
e 
19
98
.
Vamos inverter os lados da igualdade para deixar a variável isolada à esquerda:
2
1+
=
nf
No caso da árvore estritamente binária da Figura 4, sabemos que possui 7 
nós. Colocando na fórmula:
2
17 +
=f
Realizando a soma e, em seguida, a divisão:
2
8
=f
Temos que:
4=f
A árvore possui exatamente 4 folhas: C, D, F e G. 
ÁRVORE BINÁRIA COMPLETA
O nó raiz de uma árvore binária é considerado como de nível 0. A partir dela, 
cada nó possui um nível a mais do que o seu pai. Por exemplo, na árvore biná-
ria da Figura 5, o nó C está no nível 1, F está no nível 2 e o nó M no nível 3. A 
profundidade de uma árvore binária é dada pelo maior nível de qualquer folha 
na árvore. Isso equivale ao tamanho do percurso mais distante da raiz até uma 
folha qualquer. Dessa forma, a profundidade da árvore da Figura 5 é 3. 
Quando uma árvore estritamente binária possuir todas as folhas no último 
nível, ela é chamada de árvore binária completa. A Figura 5 demonstra uma 
árvore binária completa de profundidade 3.
42 - 43
ÁRVORES BINÁRIAS
Reprodução proibida. A
rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998.
II
A
C B 
E D
I H K J 
G F 
M L O N 
Figura 5: Um exemplo de árvore binária completa
Fonte: o autor
IMPLEMENTANDO ÁRVORE BINÁRIA EM C
Existem várias formas de implementar uma árvore binária. A mais simples dela 
é usar um vetor de nós. Cada nó possui pelo menos três valores: pai, esquerda 
e direita. O atributo pai vai apontar para a posição no vetor do pai do nó. O 
atributo esquerda vai armazenar a posição da raiz da subárvore esquerda, e o 
atributo direita guarda a posição da raiz da subárvore direita. Vamos adicionar 
mais um atributo dado que irá armazenar o valor do nó.
//Estrutura
struct str_no {
 char dado;
 int esquerda;
 int direita;
 int pai;
};
Programa 2.1 – Estrutura do nó
42 - 43
Implementando Árvore Binária em C
Re
pr
od
uç
ão
 p
ro
ib
id
a.
 A
rt
. 1
84
 d
o 
Có
di
go
 P
en
al
 e
 L
ei
 9
.6
10
 d
e 
19
 d
e 
fe
ve
re
iro
 d
e 
19
98
.
Com a estrutura já definida no Programa
2.1, vamos criar uma variável do 
tipo vetor de str_no. Esse vetor terá o tamanho definido por uma constante 
chamada tamanho. Precisaremos também de uma variável do tipo inteiro que 
servirá de índice para o nosso vetor.
//Constantes
#define tamanho 100
//Variáveis
struct str_no arvore[tamanho];
int indice=0;
Programa 2.2 – Variáveis 
Para inserir um nó na árvore, eu preciso saber o seu valor, quem é o seu pai 
e se ele é um filho esquerda ou direita. Mesmo sabendo quem é o pai, antes de 
fazer a inserção no vetor eu preciso encontrar a sua localização. Vou criar uma 
função chamada arvore_procura que retorna um valor inteiro (posição no 
vetor) e tem como parâmetro o nome do pai.
//Procura nó
int arvore_procura(char dado){
 if (indice != 0){
 for (int i = 0; i<indice; i++){
 if (arvore[i].dado == dado) {
 return (i);
 } 
 }
 }
 else {
 return (0); 
 }
}
Programa 2.3 – Procurando um nó na árvore
44 - 45
ÁRVORES BINÁRIAS
Reprodução proibida. A
rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998.
II
Note que o Programa 2.3 faz uma verificação no valor da variável indice. Se 
o valor for 0 significa que a árvore está vazia e o valor a ser inserido será a raiz da 
árvore. A função leva em conta de que o pai está presente na árvore, já que não foi 
previsto nenhum tipo de retorno de erro para o caso do pai não ser encontrado.
Já fizemos a leitura do valor a ser inserido e já sabemos quem é o seu pai e 
qual a sua descendência. Por meio da função demonstrada no Programa 2.3 pas-
samos o valor do pai como parâmetro e obtivemos como retorno a sua posição 
no vetor. Agora estamos prontos para a inserção do novo nó na árvore.
Vamos criar uma função nova, chamada arvore_insere. Ela terá como parâ-
metro um valor inteiro que representa a posição do pai no vetor, o valor dado 
digitado pelo usuário e a sua posição de descendência (se é filho do lado esquerdo 
ou direito).
//Inserir nó
void arvore_insere(int pai, char dado, int lado){
 switch (lado){
 case E:
 arvore[pai].esquerda = indice;
 arvore[indice].dado = dado;
 arvore[indice].pai = pai;
 arvore[indice].esquerda = -1; 
 arvore[indice].direita = -1; 
 indice++; 
 break;
 case D:
 arvore[pai].direita = indice;
 arvore[indice].dado = dado;
 arvore[indice].pai = pai;
 arvore[indice].esquerda = -1; 
 arvore[indice].direita = -1; 
 indice++; 
 break;
 }
}
Programa 2.4 – Inserindo um nó na árvore
44 - 45
Implementando Árvore Binária em C
Re
pr
od
uç
ão
 p
ro
ib
id
a.
 A
rt
. 1
84
 d
o 
Có
di
go
 P
en
al
 e
 L
ei
 9
.6
10
 d
e 
19
 d
e 
fe
ve
re
iro
 d
e 
19
98
.
No Programa 2.2, criamos uma variável chamada indice que guarda a pri-
meira posição livre da arvore. O parâmetro pai recebido na função indica qual 
a posição do nó pai. Se o novo nó for filho esquerdo, atribuiremos o valor de 
indice ao atributo esquerdo na arvore na posição pai (linha 5, Programa 2.4). 
No caso de filho direito, colocamos o valor de indice no atributo direito (linha 
13, Programa 2.4).
O próximo passo é guardar o nome do nó no atributo dado e a referência 
do pai. Vamos marcar com -1 os valores de esquerda e direita para identificar 
que ambos os ponteiros não apontam para uma subárvore. Esses passos estão 
demonstrados no Programa 2.4 nas linhas 6 a 10 para filho esquerda e 14 a 18 
para filho direita.
O Programa 2.5 traz uma implementação completa de uma Árvore Binária 
em linguagem C. Ele traz a declaração de bibliotecas, constantes e variáveis auxi-
liares, função principal, função para desenhar o menu de opções dentre muitas 
outras linhas de código.
//Bibliotecas
#include <stdio.h>
#include <stdlib.h>
//Constantes
#define tamanho 100
#define E 0
#define D 1
#define R -1
//Estrutura
struct str_no {
 char dado;
 int esquerda;
 int direita;
 int pai;
};
//Variáveis
struct str_no arvore[tamanho];
int lado,indice=0;
int opt=-1;
char pai, no;
46 - 47
ÁRVORES BINÁRIAS
Reprodução proibida. A
rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998.
II
//Prototipação
void arvore_insere(int pai, char dado, int lado);
int arvore_procura(char dado);
void menu_mostrar(void);
//Função principal
int main(void){
 int temp; 
 do {
 menu_mostrar();
 scanf(“%d”, &opt);
 switch (opt){
 case 1:
 printf(“\nDigite o valor do PAI: “);
 scanf(“%c”,&pai);
 scanf(“%c”,&pai);
 printf(“Digite o valor do NO: “);
 scanf(“%c”,&no);
 scanf(“%c”,&no); 
 printf(“Digite o lado da subarvore (E=%d/
D=%d/R=%d): “, E,D,R);
 scanf(“%d”,&lado); 
 temp = arvore_procura(pai);
 arvore_insere(temp,no,lado);
 break;
 case 2:
 printf(“Digite o valor do NO: “);
 scanf(“%c”,&no);
 scanf(“%c”,&no);
 temp = arvore_procura(no); 
 printf(“No %c\nFilho Esquerda: %c \nFilho 
Direita: %c\n\n”, arvore[temp].dado, 
arvore[arvore[temp].esquerda].dado, 
arvore[arvore[temp].direita].dado);
 system(“pause”); break; }
 }while (opt!=0);
 system(“pause”);
 return(0);
}
46 - 47
Implementando Árvore Binária em C
Re
pr
od
uç
ão
 p
ro
ib
id
a.
 A
rt
. 1
84
 d
o 
Có
di
go
 P
en
al
 e
 L
ei
 9
.6
10
 d
e 
19
 d
e 
fe
ve
re
iro
 d
e 
19
98
.
//Inserir nó
void arvore_insere(int pai, char dado, int lado){
 switch (lado){
 case E:
 arvore[pai].esquerda = indice;
 arvore[indice].dado = dado;
 arvore[indice].pai = pai;
 arvore[indice].esquerda = -1; 
 arvore[indice].direita = -1; 
 indice++; 
 break;
 case D:
 arvore[pai].direita = indice;
 arvore[indice].dado = dado;
 arvore[indice].pai = pai;
 arvore[indice].esquerda = -1;
 arvore[indice].direita = -1;
 indice++; 
 break;
 case R:
 arvore[indice].dado = dado;
 arvore[indice].pai = -1; 
 arvore[indice].esquerda = -1; 
 arvore[indice].direita = -1;
 indice++; 
 break; }
}
//Procura nó
int arvore_procura(char dado){
 if (indice != 0){
 for (int i = 0; i<indice; i++){
 if (arvore[i].dado == dado) {
 return (i); } }
 }
 else {
 return (0); }
}
48 - 49
ÁRVORES BINÁRIAS
Reprodução proibida. A
rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998.
II
Programa 2.5 – Implementação de Árvore Binária em C
LINGUAGEM C
Acabamos de ver uma forma de armazenar uma árvore binária em um vetor. 
Essa implementação é bem simples e rápida, mas longe do ideal. Voltamos ao 
mesmo problema de estruturas anteriores onde muita memória é alocada na 
execução do programa para uma aplicação que pode ou não precisar de todo o 
espaço reservado na memória. 
O Programa 2.5 procura sempre a primeira posição livre no vetor para posi-
cionar um novo nó na árvore. Dessa forma, a ordenação da estrutura estará 
diretamente ligada à ordem que os nós foram adicionados. 
//Desenha o menu na tela
void menu_mostrar(void){
 system(“cls”);
 for (int i = 0; i < indice; i++){
 printf(“| %c “,arvore[i].dado);
 }
 printf(“\n1 - Inserir um NO na arvore”);
 printf(“\n2 - Pesquisar um NO na arvore”);
 printf(“\n0 - Sair...\n\n”); 
}
48 - 49
Uma Árvore Binária Diferente
Re
pr
od
uç
ão
 p
ro
ib
id
a.
 A
rt
. 1
84
 d
o 
Có
di
go
 P
en
al
 e
 L
ei
 9
.6
10
 d
e 
19
 d
e 
fe
ve
re
iro
 d
e 
19
98
.
UMA ÁRVORE BINÁRIA DIFERENTE
Outra forma de armazenar uma árvore binária em um vetor
é reservar as posições 
de acordo com o nível e descendência de cada nó. O primeiro nó a ser armaze-
nado é a raiz da árvore e ele ficará na primeira posição do vetor, lembrando que 
os vetores em C começam na posição 0.
A 
CB 
D E
F 
Figura 6: Uma árvore binária com 6 nós e profundidade 3
Fonte: o autor
Vamos simular a inserção da árvore representada pela Figura 6 em um vetor de 
16 posições. O primeiro nó a ser inserido será a raiz da árvore A e ocupará a 
posição 0 do vetor.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
A
Como nosso objetivo é manter a árvore indexada dentro do vetor, vamos 
reservar a primeira posição p logo após o nó para armazenar o filho esquerdo 
e a segunda posição p para o filho direito. Assim, para um nó armazenado em 
uma posição p qualquer, seu filho esquerdo estará na posição p+1 e seu filho 
direito na posição p+2. Vamos inserir os nós B e C no vetor.
©shutterstock
©
SH
U
TT
ER
ST
O
CK
50 - 51
ÁRVORES BINÁRIAS
Reprodução proibida. A
rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998.
II
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
A B C
O nó A está na posição p=0, então é esperado que seu filho esquerdo esteja na 
posição p+1=1 e o filho direito na posição p+2=2 do vetor, o que é verdade. 
Vamos inserir agora os nós D e E.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
A B C D E
Usando a fórmula que foi proposta, para encontrar os filhos de B na posição 1 
do vetor, o filho esquerdo estará na posição p+1=2 e o direito na posição p+2=3, 
o que não é verdade, logo a fórmula que propusemos não serve para resolver o 
problema de ordenação de árvore binária em vetor de dados.
Uma árvore binária cresce de forma geométrica já que cada nó tem dois 
filhos que, por sua vez, são duas subárvores que podem estar vazias ou não. 
Independente de o filho existir, seu espaço precisa ser reservado no vetor. 
Como todo nó em uma árvore binária tem dois filhos, vamos modificar a 
fórmula para 2*p+1 para o filho esquerdo e 2*p+2 para o filho direito, sendo p 
a posição do nó no vetor.
50 - 51
Uma Árvore Binária Diferente
Re
pr
od
uç
ão
 p
ro
ib
id
a.
 A
rt
. 1
84
 d
o 
Có
di
go
 P
en
al
 e
 L
ei
 9
.6
10
 d
e 
19
 d
e 
fe
ve
re
iro
 d
e 
19
98
.
Aplicando as novas fórmulas para o nó A que está na posição 0, temos que 
2*p+1=1 é a posição de B (filho esquerdo de A) e 2*p+2=2 é a posição de C 
(filho direito de A).
Para B que está na posição 1, temos que 2*p+1=3 que é a posição de D (filho 
esquerdo de B) e 2*p+2=4 é a posição de D (filho direito de B).
O nó C é uma folha, podemos dizer que ele não tem filhos ou que seus 
filhos são árvores vazias. Como o nosso objetivo é manter o vetor ordenado, a 
posição dos filhos de C será reservada aplicando a fórmula proposta. Assim a 
posição 2*p+1=5 ficará disponível para o filho esquerdo de C e 2*p+2=6 para 
o seu filho direito.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
A B C D E - -
O próximo será D, que também é uma folha. Então será reservado no vetor as 
posições 2*p+1=7 e 2*p+2=8.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
A B C D E - - - -
O último nó de nível 2 (E) possui um filho direito (F) que será armazenado na 
posição 2*p+2=10 do vetor criado para a nossa árvore binária. 
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
A B C D E - - - - - F
No primeiro momento, podemos pensar que essa não é uma boa abordagem. 
Se a árvore não for binária completa, existirão vários espaços vazios no vetor 
lembrando uma memória fragmentada. Por outro lado, estaremos ocupando 
exatamente a mesma quantidade de memória que a implementação anterior. 
A principal diferença é que nesse modelo os nós da árvore estarão indexados, 
assim é possível obter as informações de forma rápida e precisa, utilizando-se 
do índice ao invés de percorrer toda a estrutura.
Uma árvore binária também pode ser criada dinamicamente. Basta ter um 
ponteiro esquerdo e direito que apontará para os filhos e um ponteiro para 
o pai.
Esse material criado pelo Prof. Paulo Feofiloff da USP traz um resumo dos 
principais termos relacionados a árvores binárias, além de exemplos ilustra-
dos e trechos de código em linguagem C.
<http://www.ime.usp.br/~pf/algoritmos/aulas/bint.html>.
52 - 5352 - 53
ÁRVORES BINÁRIAS
Reprodução proibida. A
rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998.
II
CONSIDERAÇÕES FINAIS
Nesta unidade, foi apresentada ao aluno uma nova estrutura de dados: a árvore 
binária. Ela lembra muito um grafo, porém essas duas estruturas se diferem 
pelos seguintes motivos:
1. O grafo pode não ter nenhuma aresta e contém no mínimo um único 
vértice.
2. Uma árvore pode ser vazia e todos os nós podem ser de no máximo grau 
3, sendo que cada nó tem um único pai e dois filhos.
Vimos duas formas de representar essa poderosa estrutura pelo uso de vetores. 
No primeiro modelo o vetor vai sendo preenchido à medida que a árvore é lida. 
Cada nó entra na árvore na primeira posição livre da variável.
A segunda implementação possui uma abordagem focada em indexar os nós 
dentro do vetor, posicionando-os de acordo com a sua ascendência e descendência. 
A importância da estrutura de árvore binária e da sua representação inde-
xada ficará clara na próxima unidade quando tratarmos dos mais usuais métodos 
de pesquisa em memória.
52 - 5352 - 53
1. Faça a implementação em linguagem C de uma estru-
tura de árvore binária para a criação de uma árvore di-
nâmica, seguindo os seguintes passos:
a. Crie um atributo para armazenar o valor do nó.
b. Crie um ponteiro para o pai.
c. Crie um ponteiro para o filho esquerdo.
d. Crie um ponteiro para o filho direito.
2. Para cada árvore abaixo, identifique os seus componentes seguindo o exemplo 
da letra a.
a) A 
CB 
D 
Raiz A
Nós A, B, C, D
Folhas C, D
Com um filho B
Com dois 
filhos A
Nível 0 A
Nível 1 B, C
Nível 2 D
Nível 3
Profundidade 2
54 - 55
b) A 
C B 
D E F 
H I G 
Raiz
Nós
Folhas
Com um filho
Com dois filhos
Nível 0
Nível 1
Nível 2
Nível 3
Profundidade
c) A 
C B 
D E 
G F 
54 - 55
Raiz
Nós
Folhas
Com um filho
Com dois filhos
Nível 0
Nível 1
Nível 2
Nível 3
Profundidade
d) A 
C B 
E D 
I H K J 
G F 
M L ON 
Raiz
Nós
Folhas
Com um filho
Com dois filhos
Nível 0
Nível 1
Nível 2
Nível 3
Profundidade
56 - 57
 e) 
A 
CB 
D E 
F 
Raiz
Nós
Folhas
Com um filho
Com dois filhos
Nível 0
Nível 1
Nível 2
Nível 3
Profundidade
3. O que uma árvore precisa para ser considerada uma árvore estritamente binária?
4. Quais são as características de uma árvore binária completa?
5. Para cada árvore dada, preencha o seu vetor de forma indexada, conforme o 
exemplo da letra a.
a. A 
C B 
D 
56 - 57
0 1 2 3 4 5 6 7 8 9
A B C D
b. A 
C B
D E F 
H IG 
0 1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19
c. A 
C B 
D E 
G F 
0 1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19
58 - 59
d. 
A
C B 
E D
I H K J 
G F 
M L O N 
0 1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19
e. A 
CB 
D E 
F 
0 1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19
Material Complementar
MATERIAL COMPLEMENTAR
58 - 59
Algoritmos
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, 
Clifford Stein 
Editora: Elsevier
Sinopse: Este livro apresenta um texto abrangente sobre o 
moderno estudo de algoritmos para computadores. É uma 
obra clássica, cuja primeira edição tornou-se amplamente 
adotada nas melhores universidades em todo o mundo, bem 
como padrão de referência para profissionais da área.
Nesta terceira edição, totalmente revista e ampliada, as 
mudanças são extensivas e incluem novos capítulos, exercícios e 
problemas; revisão de pseudocódigos e um estilo de redação mais claro. A edição brasileira conta 
ainda com nova tradução e revisão técnica do Prof. Arnaldo Mandel, do Departamento de Ciência 
da Computação do Instituto de Matemática e Estatística da Universidade de São Paulo.
Elaborado para ser ao mesmo tempo versátil e completo, o livro atende a alunos dos cursos de 
graduação e pós-graduação em algoritmos ou estruturas de dados.
U
N
ID
A
D
E III
Professor Me. Rogério de Leon Pereira
OPERAÇÕES DE BUSCA
Objetivos de Aprendizagem
 ■ Aprender os conceitos básicos de busca.
 ■ Estudar diferentes algoritmos de busca.
Plano de Estudo
A seguir, apresentam-se os tópicos que você estudará nesta unidade:
 ■ Conceitos básicos
 ■ Operação de busca sequencial
 ■ Busca sequencial indexada
 ■ A busca binária
 ■ Busca por interpolação
 ■ Busca em árvores
62 - 63
INTRODUÇÃO
Nesta unidade, estudaremos alguns métodos de como pesquisar grandes quan-
tidades de dados em busca de uma determinada informação. Veremos como a 
organização dos dados torna o processo de busca mais eficiente. Como a operação 
de busca é uma tarefa muito comum na ciência da computação, o conhecimento 
desses métodos é de suma importância para todo o profissional que deseja se 
tornar um bom programador.
CONCEITOS BÁSICOS
Antes de nos aprofundarmos no estudo de algoritmos de busca, vamos tratar 
de alguns termos que utilizaremos nesta unidade. Uma tabela ou arquivo é um 
conjunto de registros. Um registro é um conjunto de dados.
Existe uma chave associada a cada registro, se ela estiver dentro do próprio 
registro ela é chamada de chave interna, chave embutida ou incorporada. No 
caso da chave ficar fora do registro ela é chamada de chave externa. 
Para todos os registros dentro de uma tabela pelo menos um dos campos pre-
cisa ter um valor único para assim diferenciar cada um dos registros. Esse campo 
é chamado de chave primária. 
Por exemplo, vamos imaginar que temos uma tabela de clientes. Cada registro 
dessa tabela representa um cliente e cada cliente possui um conjunto de dados, 
conforme a Figura 7.
©
sh
ut
te
rs
to
ck
62 - 63
Introdução
Re
pr
od
uç
ão
 p
ro
ib
id
a.
 A
rt
. 1
84
 d
o 
Có
di
go
 P
en
al
 e
 L
ei
 9
.6
10
 d
e 
19
 d
e 
fe
ve
re
iro
 d
e 
19
98
.
64 - 65
OPERAÇÕES DE BUSCA
Reprodução proibida. A
rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998.
III
TABELA: CLIENTES
Registro
CPF
Nome
Rua
CEP
Telefone
Figura 7: Exemplo da Tabela clientes e os dados de um Registro
Posso identificar os clientes pelo nome? Não pode, porque existem homôni-
mos, ou seja, pessoas com o mesmo nome como José Maria da Silva, Roberto 
Carlos dos Santos etc.
Também não posso usar a Rua ou o CEP, pois vários clientes podem morar 
na mesma localidade. Se eu e a minha esposa formos clientes dessa empresa, 
nosso Telefone também aparecerá mais de uma vez na tabela.
Para esse caso específico, sobrou o CPF (Cadastro de Pessoa Física), que 
é realmente único, não existem duas pessoas no Brasil com o mesmo CPF. Se 
nenhum dos campos do registro fosse potencial para servir de chave primária, 
poderíamos criar um novo campo chamado codigo ou id e atribuir um número 
único para cada um dos registros.
Ainda pensando nesse exemplo, imagine que a empresa dona dessas infor-
mações pretenda fazer uma ação de marketing e tenha como objetivo atingir 
apenas os clientes que residam em uma determinada cidade, bairro ou em uma 
rua específica. Posso estar fazendo uma busca na Tabela clientes pelos campos 
Rua ou CEP. Quando um atributo com informações não únicas é utilizado em 
uma pesquisa ele é chamado de chave secundária.
Todo campo de um registro em uma tabela pode servir como chave em po-
tencial, dependendo da informação desejada ou da regra de busca utilizada.
©s
hu
tte
rst
ock
64 - 65
Conceitos Básicos
Re
pr
od
uç
ão
 p
ro
ib
id
a.
 A
rt
. 1
84
 d
o 
Có
di
go
 P
en
al
 e
 L
ei
 9
.6
10
 d
e 
19
 d
e 
fe
ve
re
iro
 d
e 
19
98
.
Como você deve ter aprendido, 
as grandes massas de dados 
ficam armazenados em dispo-
sitivos de memória secundária, 
como disco rígido, disco óptico, 
fita magnética, memória flash, 
dentre outros.
Porém, todo dado para 
ser manipulado precisa neces-
sariamente estar na memória 
principal. Como a relação entre as 
duas memórias é desproporcio-
nal, ou seja, um computador tem 
Gb de memória RAM enquanto 
possui Tb de memória de armazenamento, somente uma pequena parcela dos 
dados pode ser analisada por vez.
Dessa forma, é muito mais inteligente carregar apenas uma tabela de cha-
ves do que todos os registros de um arquivo. Encontrada a referência desejada, 
busca-se no disco apenas a porção desejada de informação.
Alguns algoritmos são especializados em realizar buscas em arquivos de 
chaves primárias, outros por chaves secundárias. Alguns são mais rápidos em 
arquivos menores, outros ideais para grandes quantidades de informações.
Um algoritmo de busca tem como objetivo, a partir de um argumento x rece-
bido, encontrar em uma tabela um registro que possua uma chave x equivalente. 
Ele irá retornar todos os dados do registro, ou o índice da sua posição em um 
vetor ou ainda um ponteiro para uma posição na memória.
Se não houver no arquivo um registro compatível com o argumento pes-
quisado, o algoritmo não obtém sucesso na sua busca e retorna uma mensagem 
de erro, um índice inválido ou um ponteiro nulo. Segundo Tenenbaum (1995), 
uma busca com sucesso é chamada recuperação.
66 - 67
OPERAÇÕES DE BUSCA
Reprodução proibida. A
rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998.
III
OPERAÇÃO DE BUSCA SEQUENCIAL
A busca sequencial é de longe a forma mais simples de pesquisa. Ela pode ser 
utilizada tanto para o caso em que a tabela está armazenada em um vetor como 
em uma lista ligada. 
A partir da primeira posição no vetor (ou do primeiro nó da lista), com-
para-se o valor atual da estrutura com o argumento x passado. Repete-se esse 
procedimento com cada um dos valores até que seja encontrado o valor dese-
jado ou o final da tabela.
O Programa 3.1 traz um exemplo de busca sequencial em C. A função bus-
caSequencial recebe três parâmetros: o vetor vec a ser pesquisado, o argumento 
arg a ser procurado e o tamanho tam do vetor. 
São criadas duas variáveis locais. A variável i serve de índice para percorrer 
o vetor, enquanto a variável achou é usada para identificar se a busca foi con-
cluída antes do final do vetor.
Como os vetores em C começam pela posição 0, a variável i também foi ini-
cializada com esse valor, para que a pesquisa realmente dê início pelo começo 
do vetor. A variável achou foi inicializada com -1.
Durante o laço de repetição é verificado se a variável de controle i atingiu o 
tamanho máximo tam recebido como parâmetro. O valor de i é incrementando 
sempre no final do laço, garantindo que a busca percorra o vetor até o final. 
Adicionalmente o laço possui outra regra de parada que verifica o valor da vari-
ável achou. Ela foi inicializada com -1, porém, se o valor for encontrado, a sua 
posição no vetor será atribuída ao valor de achou.
Ao final a função retorna o valor da variável achou. Ele será -1 se a busca 
tiver falhado ou no caso contrário a posição do registro no vetor.
©shutterstock
66 - 67
Busca Sequencial Indexada
Re
pr
od
uç
ão
 p
ro
ib
id
a.
 A
rt
. 1
84
 d
o 
Có
di
go
 P
en
al
 e
 L
ei
 9
.6
10
 d
e 
19
d
e 
fe
ve
re
iro
 d
e 
19
98
.
//Funçãoo de Busca Sequencial 
int buscaSequencial(int vec[], int arg, int tam){ 
 int i = 0, achou = -1; 
 while ((i < tam) && (achou == -1)){ 
 if (vec[i]==arg){ 
 achou = i; 
 } 
 i++; 
 } 
 return(achou); 
}
Programa 3.1 - Busca Sequencial
Se considerarmos que os registros no vetor não estão organizados de forma 
alguma, a pesquisa poderá encontrar o valor desejado na primeira ou na última 
posição da estrutura. Imagine que a tabela seja muito grande e buscar alguma 
informação procurando em todos os registro pode ter um custo computacional 
muito elevado. Uma maneira de melhorar isso é a técnica de busca sequencial 
indexada.
BUSCA SEQUENCIAL INDEXADA
Não é possível prever qual será o valor buscado em uma pesquisa e nem a posi-
ção onde o registro está armazenado no vetor, menos ainda se ele está ou não 
presente na tabela.
Tudo depende do que está armazenado e o que se costuma pesquisar. 
Se em uma tabela de clientes as buscas são feitas por pessoas que 
habitem na mesma região demográfica para efetuar ações mais pre-
cisas e eficazes de marketing, uma boa ideia seria criar um índice 
específico ordenado por cidade, estado ou CEP.
Se o síndico do prédio onde você mora entrega o boleto do con-
domínio começando pelos apartamentos do último andar até o 
68 - 69
OPERAÇÕES DE BUSCA
Reprodução proibida. A
rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998.
III
térreo, seria interessante que houvesse um índice com o número do apartamento 
ordenado de forma decrescente. 
Em uma loja de departamentos especializada em produtos de moda feminina 
é muito provável que o usuário busque uma cliente do sexo feminino ao invés 
de um homem, por isso os dados devem ser ordenados primeiro por gênero.
Se for observado que alguns argumentos específicos sejam procurados com 
mais frequência, esses registros podem ser movidos para uma região mais pró-
xima do início da tabela, fazendo com que futuras buscas sejam cada vez mais 
rápidas. Tenenbaum (1995) fala de um método em particular, muito simples 
e que traz bons resultados chamado método da transposição, no qual o regis-
tro recuperado com sucesso é trocado pelo registro imediatamente anterior.
Imagine um vetor de valores inteiros que esteja ordenado de forma crescente. 
A busca sequencial procuraria o valor desejado em cada uma das posições até 
encontrá-lo ou chegar ao final do arquivo, o que ocorrer primeiro. Mesmo no 
caso do registro não existir na tabela, todo o arquivo será percorrido.
Porém, como sabemos que a estrutura está ordenada de forma ascendente, 
no momento em que for encontrado um número maior do que o que está sendo 
procurado, não há mais necessidade de continuar a pesquisa, porque certamente 
o valor procurado não estará no restante da tabela. Nessa linha de raciocínio, 
podemos dizer que compensa classificar um arquivo antes de pesquisar infor-
mações dentro dele.
A técnica de busca sequencial indexada consiste em criar uma tabela auxi-
liar ao arquivo de dados. Nessa tabela, deve constar pelo menos dois campos: 
a chave de busca e o endereço do registro na tabela original. A tabela de índice 
pode ser ordenada de forma ascendente, descendente ou de qualquer outra forma 
que seja mais compatível com as principais buscas que utilizarão a chave con-
tida na tabela auxiliar. 
Mais uma vez mencionando uma suposta tabela de clientes como exemplo, 
fisicamente os registros estão gravados em disco pela ordem como os clientes 
são cadastrados no sistema. Se a busca for efetuada pelo número do CPF do 
cliente, uma nova tabela é criada contendo o CPF e a posição original do regis-
tro na tabela de clientes.
68 - 69
A Busca Binária
Re
pr
od
uç
ão
 p
ro
ib
id
a.
 A
rt
. 1
84
 d
o 
Có
di
go
 P
en
al
 e
 L
ei
 9
.6
10
 d
e 
19
 d
e 
fe
ve
re
iro
 d
e 
19
98
. A BUSCA BINÁRIA
A forma mais eficiente de efetuar pesquisa em um arquivo ordenado sem a neces-
sidade de tabelas auxiliares é a busca binária. A estratégia consiste em comparar 
o argumento chave ao elemento do meio da tabela. Se forem iguais, a busca terá 
terminado com sucesso. No caso contrário, o vetor será divido em duas meta-
des, e a pesquisa será repetida na metade inferior se o argumento for menor do 
que o valor do meio da tabela ou na parte superior se o argumento for maior.
A cada iteração, a busca binária reduz a quantidade de possíveis candida-
tos pela metade. Vale ressaltar que essa estratégia funciona apenas em estruturas 
cujos dados se encontram ordenados. Sua implementação em vetores não é muito 
complexa e um exemplo em C é apresentado no Programa 3.2. 
Esse algoritmo não pode ser utilizado com listas dinâmicas devido às carac-
terísticas da sua estrutura. Mesmo criando um ponteiro especial que aponte para 
o meio da lista, toda vez que o problema for dividido, a lista precisará ser percor-
rida novamente para achar o meio da nova metade da lista, o que torna o tempo 
de execução do algoritmo muito extenso.
Se todos os valores de um vetor estiverem ordenados de forma crescente, 
uma pesquisa pode ser interrompida assim que um valor maior do que o 
procurado for visitado. O mesmo acontece de forma análoga para um vetor 
ordenado de forma decrescente.
70 - 71
OPERAÇÕES DE BUSCA
Reprodução proibida. A
rt. 184 do Código Penal e Lei 9.610 de 19 de fevereiro de 1998.
III
//Função de Busca Binária 
int buscaBinaria(int vec[], int arg, int tam){ 
 int menor, maior, meio; 
 menor = 0; 
 maior = tam-1; 
 while (menor <= maior){ 
 meio = (menor + maior)/2; 
 if (arg == vec[meio]){ 
 return(meio); 
 } 
 if(arg < vec[meio]){ 
 maior = meio - 1; 
 } 
 else { 
 menor = meio + 1; 
 } 
 } 
 return(-1); 
}
Programa 3.2 - Busca Binária
A função buscaBinaria do Programa 3.2 recebe três parâmetros: o vetor vec que 
será pesquisado, o argumento arg que será procurado e o tamanho tam do vetor. 
São criadas três variáveis internas, uma para marcar a posição de início (menor) 
da pesquisa, o limite a ser pesquisado (maior) e para marcar o meio do vetor. 
A variável menor é inicializada com valor 0, que na linguagem C representa 
o início do vetor. A variável maior é inicializada com o valor tam-1 já que um 
vetor de tamanho n vai de 0 até n-1.
O laço será repetido enquanto a variável menor for menor ou igual a vari-
ável maior. Nele será calculada a posição do meio entre menor e maior. Se o 
argumento arg estiver na posição meio do vetor vec, a função retorna o valor 
de meio e o algoritmo concluiu a recuperação.
Se a recuperação ainda não foi concluída, é preciso atualizar o valor da vari-
ável meio. Como sabemos que o vetor se encontra ordenado, se o argumento 
arg for menor do que o conteúdo no vetor vec na posição meio, então a busca 
deverá ser feita entre a posição menor e a metade. Caso contrário, a busca deve 
continuar entre a metade e o final do vetor.
70 - 71
A Busca Binária
Re
pr
od
uç
ão
 p
ro
ib
id
a.
 A
rt
. 1
84
 d
o 
Có
di
go
 P
en
al
 e
 L
ei
 9
.6
10
 d
e 
19
 d
e 
fe
ve
re
iro
 d
e 
19
98
.
Vamos simular uma busca binária em um vetor ordenado de 10 posições, 
demonstrado na Figura 8. O valor do argumento a ser encontrado é 5. 
a. A variável menor será inicializada com 0 e maior com 9 (tamanho – 1).
b. Para o cálculo do meio do vetor fazemos:
( )
2
maiormenormeio +=
( )
2
90 +
=meio
( )
2
9
=meio
5,4=meio
Como a variável meio é do tipo inteiro, a posição que indica a metade do vetor 
é 4. O valor contido no vetor na posição meio é 16, que é maior do que o argu-
mento pesquisado 5. 
c. Como o valor não foi encontrado, o laço é repetido