Livro-Texto - Unidade III

Prévia do material em texto

184
Unidade III
Unidade III
Anteriormente examinamos as estruturas de dados unidimensionais, ou uma sequência de elementos, 
dispostos um atrás do outro.
Quando precisamos, por exemplo, descrever o organograma de uma empresa, ou, então, pastas 
e subpastas que compõem o seu dispositivo de armazenamento, não conseguimos fazê-lo usando 
estruturas unidimensionais, porque a disposição não é sequencial, mas sim hierárquica. Nesses casos, 
em que um nó é ligado a mais de um nó, impossibilitando o uso de listas ou seus derivados, torna-se 
necessário o estudo de outra forma de organização estrutural, algo que veremos nesta unidade.
7 RECURSIVIDADE E ÁRVORE
7.1 Recursividade
Já sabemos que os vetores são limitados porque, desde o começo, precisamos saber a sua dimensão, 
e tivemos como solução o uso da alocação dinâmica da memória, para casos em que, a cada execução 
do programa, as suas dimensões podem mudar. No entanto, existem casos em que não somente a 
memória, mas o próprio programa tem de se adaptar a uma situação diferente a cada momento. Não é 
prático alterar o programa antes de cada execução. Para solucionar alguns desses problemas, podemos 
utilizar a recursividade. Existem certas ocasiões que apenas podem ser contornadas por meio dela.
A recursividade é a possibilidade de uma função se chamar, ou, então, voltar a ser chamada após 
a execução de funções que ela mesma chamou. Isso quer dizer que, a cada chamada, o programa abre 
um novo espaço na memória para a sua execução. A cada chamada recursiva é guardada uma cópia dos 
parâmetros, de modo que não percamos os valores das chamadas anteriores. Em princípio, enquanto 
houver memória para a recursividade, a função poderá ser reutilizada.
As funções recursivas têm duas características importantes:
• Ponto de parada: geralmente, um limite superior ou inferior da regra geral.
• Regra geral: redução da resolução do problema por meio da invocação recursiva de casos 
menores, resolvidos mediante a resolução de eventos ainda menores, e assim sucessivamente, até 
atingir o ponto de parada, que finaliza o método.
Para ilustrar, na figura a seguir consta a chamada de uma função recursiva, lembrando que tal 
função pode ser chamada a partir de qualquer outra função, não necessariamente da função principal 
(main) como na ilustração.
185
ESTRUTURAS DE DADOS
Figura 271– Chamada inicial de uma função recursiva
Ao executar a função recursiva, é verificada a chegada ao ponto de parada, onde a função recursiva 
termina a chamada a si mesmo. Quando é feita a chamada a memória do ponto de execução, naquele 
momento é preservada para que durante o retorno à função o programa continue trabalhando conforme 
já vinha sendo executado, utilizando o resultado da nova situação que a função recursiva devolveu. As 
memórias salvas são empilhadas a cada nova chamada, pois no retorno ela será desempilhada restaurando 
a situação do ponto de chamada, é o exemplo clássico da aplicação das pilhas visto anteriormente, a 
última informação salva será a primeira a ser recuperada (LIFO – Last in, First out). Na figura a seguir, 
como a condição não é alcançada, a função chama a si mesmo passando novos parâmetros.
Figura 272 – A condição de parada não é alcançada e a função é novamente invocada
Novamente a função verifica se o ponto de parada é alcançado e, enquanto ele não é alcançado, 
as chamadas são feitas sucessivamente, assim como cada memória é preservada. Conforme a lógica da 
função, as regras gerais podem ou não ser executadas antes ou depois das chamadas, e frequentemente 
a própria função faz parte da regra geral.
186
Unidade III
Figura 273 – As chamadas são feitas sucessivamente até alcançar o ponto de retorno
Ao encontrar o ponto de parada, a função passa a retornar ao ponto no qual foi invocada, retornando 
um valor alterado pela regra geral.
Figura 274 – Ao alcançar o ponto de retorno as chamadas 
são encerradas e retorna o valor alterado pela regra geral
A cada retorno à função que a chamou, a memória salva (desempilhada) passa a trabalhar com a 
informação retornada pela função recursiva. A função recursiva que já cumpriu o seu papel é eliminada 
da memória e o seu espaço liberado para novos usos.
187
ESTRUTURAS DE DADOS
Figura 275 – A função recursiva retorna valores trabalhados 
pela regra geral para a função que a chamou
Normalmente, o retorno acontece até alcançar a função original que a chamou, porém existem 
situações nas quais a recursividade é interrompida quando o seu objetivo é alcançado, algo muito 
comum em buscas.
Figura 276 – A função retorna ao ponto ao qual ela foi chamada
Exemplo de aplicação
Multiplicação de inteiro
1) Como exemplo, temos uma função recursiva para calcular uma multiplicação. A função chama 
a si mesmo sucessivamente e, a cada chamada, o valor do parâmetro y decresce, até chegar ao 
ponto de parada (y==1), e passa a ter retornos sucessivos, até a primeira chamada, retornando o 
valor alterado pela regra geral.
188
Unidade III
Uma multiplicação é a soma da quantidade de vezes a si mesmo:
3 × 4 = 3 + 3 + 3 + 3
4 × 3 = 4 + 4 + 4
Assim, utilizando a recursividade, o programa de multiplicação recursivo fica:
Figura 277 
Ou equivalentemente para o exemplo:
Figura 278 
Executando o exemplo para multiplicação 2 × 3, a função recursiva é chamada com os parâmetros 
2 e 3 (multi(2,3)). Na primeira função chamada, o ponto de retorno (y==1) não é alcançado, então 
a função é chamada novamente, porém com o parâmetro alterado, o valor de y quando a função é 
chamada é 3, e para a próxima recursividade o valor passa para 2.
Figura 279 – A função raiz chama a execução da função 
recursiva e verifica se o ponto de retorno foi alcançado
Na execução da primeira recursividade é verificado se com os parâmetros recebidos o ponto de 
parada é alcançado. No exemplo ainda não, pois o valor de y é 2. Por isso, uma nova recursividade é 
invocada passando o novo valor de y (1).
189
ESTRUTURAS DE DADOS
Figura 280 – Como o ponto de parada não foi alcançado, é 
chamada a primeira recursividade com o parâmetro alterado
Na segunda recursão, o ponto de parada é alcançado (y==1), a partir daí as funções passam a 
retornar para os pontos nos quais foram chamadas com o valor do retorno processado.
Figura 281 – O ponto de parada é alcançado na segunda recursividade, 
retornando o valor que participará na regra geral
Entre um retorno e outro, o valor retornado é alterado pela regra geral. No exemplo, o valor 
processado que será retornado é 4.
190
Unidade III
Figura 282 – O primeiro valor retornado é processado pela 
regra geral, retornando para a função que a chamou
Novamente o valor retornado pela função é alterado pela regra geral (6) e devolvido para a função 
que a chamou.
Figura 283 – O valor retornado é processado pela regra geral, retornando para a função que a chamou
Finalmente o resultado da função retorna à chamada inicial com o valor processado (2 × 3 = 6).
Figura 284 – O valor processado das diversas recursividades 
retorna a resposta ao ponto de chamada inicial
Neste exemplo, observamos claramente as condições fundamentais de uma função recursiva.
191
ESTRUTURAS DE DADOS
Ponto de parada:
y == 1
Regra geral:
int rec = mult(x, y - 1);
int rec = x + rec;
Ou:
x + mult(x, y - 1)
2) Como vimos, resumidamente, um algoritmo é uma sequência de instruções para resolvermos um 
problema. Existem problemas que somente podem ser resolvidos por meio da recursividade. 
Um exemplo é o caso do labirinto que pode ter caminhos diferentes até chegar a uma saída, e não 
seria uma solução alterar o algoritmo para cada labirinto diferente.
No exemplo, o labirinto deve ser cercado, sem saída para fora das bordas, e a partir de qualquer 
ponto interno devemos chegar a um tesouro.
Figura 285 
Figura 286 – Labirinto, os caminhos são espaços e as paredes são #
192
Unidade III
O programa percorre um labirinto iniciando de qualquer ponto livre, procurando caminhos viáveis 
que conduzam aotesouro. Várias alternativas dentro do labirinto devem ser tentadas. Se um caminho 
não for viável, ele volta ao ponto anterior e tenta a próxima alternativa (caminho não percorrido).
O programa pode percorrer um em quatro caminhos diferentes a partir do ponto em que se encontra 
(posição relativa 0, 0), como indicado a seguir:
Figura 287 – Adjacência das tentativas
A função, portanto, procura deslocar o movimento para uma das quatro casas adjacentes à que se 
encontra. O objetivo é encontrar um caminho livre (posição da tabela contendo espaço) não percorrido 
para tentar localizar o tesouro no labirinto utilizando-se da recursividade. Logo, o teste é feito para as 
quatro direções considerando-se que o “X” encontra-se sempre na posição relativa (0, 0). Ao encontrar 
o novo caminho, uma nova tentativa é feita a partir da direção superior até achar novamente um 
caminho livre. O primeiro ponto de retorno é quando o local testado já está ocupado, retornando para 
testar a próxima direção. Se não encontrar um caminho livre nas quatro direções, o segundo ponto de 
retorno é encontrado, retrocedendo para continuar as tentativas nas direções ainda não tentadas a 
partir do ponto anterior.
A função recursiva para percorrer todo o labirinto sem tentar localizar o tesouro é:
Figura 288 
Observa-se no programa que caso o caminho seja livre (m[i][j] == ‘ ‘) naquele ponto, as tentativas 
são efetuadas em cada uma das direções. Considerando o tesouro, o programa fica:
193
ESTRUTURAS DE DADOS
Figura 289 
O programa é encerrado quando a função atinge as coordenadas do tesouro (DI e DJ). Como o 
algoritmo funciona independentemente do tamanho ou desenho da tabela, para a execução será 
utilizada uma dimensão menor.
Figura 290 
Figura 291 – Labirinto menor desenhado para a execução
194
Unidade III
Iniciando da posição 1,1:
tenta(1, 1);
Acompanhado pela figura a seguir, é utilizada a sequência das chamadas recursivas da função tenta(). 
A partir da posição inicial é verificada a possibilidade de avançar para cima (posição 0,1), como ela não 
está livre, é tentada para a esquerda (1,0), que também está ocupada. A terceira tentativa (1,2) encontra 
uma posição livre passando a executar a partir dali as tentativas para cima, para a esquerda e direita, 
onde encontra novamente caminho livre. Nas duas posições já percorridas, existem tentativas ainda não 
testadas (para baixo), elas serão utilizadas caso não haja saída na direção tomada anteriormente.
Ao chegar na posição (1, 4), são feitas tentativas nas quatro direções sem encontrar saída. Desta forma, 
a recursão volta para a posição anterior e executa as tentativas faltantes. Os retornos acontecem até 
chegar na posição (1, 2), quando uma saída é encontrada na tentativa restante, no caso para baixo (2, 2).
Na posição (2, 2) é possível ir para baixo somente, então o próximo local a ser verificado é a posição (3,2). 
Em (3, 2) inicialmente testa-se para cima, porém está marcado como passado, depois testa-se para a 
direita. Como a direita está livre, a posição atual move para (3, 1). Exatamente a posição do tesouro, 
portanto atingindo o objetivo do programa.
Figura 292 – Sequência de execução da recursividade da função tenta
195
ESTRUTURAS DE DADOS
Este exemplo é um caso em que a função não necessariamente precisa retornar ao ponto de onde a 
primeira chamada foi feita, mas diversas possibilidades são testadas até chegar ao objetivo.
Consta a seguir o código completo:
#include <stdio.h>
#include <stdlib.h>
#define DIM 8
#define DI 4
#define DJ 4
/* matriz que define o ‘labirinto’*/
int m[DIM][DIM] =
{ {‘#’,’#’,’#’,’#’,’#’,’#’,’#’,’#’},
 {‘#’,’ ‘,’ ‘,’ ‘,’ ‘,’#’,’ ‘,’#’},
 {‘#’,’#’,’ ‘,’#’,’#’,’#’,’ ‘,’#’},
 {‘#’,’ ‘,’ ‘,’ ‘,’ ‘,’#’,’ ‘,’#’},
 {‘#’,’ ‘,’#’,’#’,’ ‘,’#’,’ ‘,’#’},
 {‘#’,’ ‘,’ ‘,’#’,’#’,’#’,’ ‘,’#’},
 {‘#’,’#’,’ ‘,’ ‘,’ ‘,’ ‘,’ ‘,’#’},
 {‘#’,’#’,’#’,’#’,’#’,’#’,’#’,’#’} };
void imprime() {
 int i, j;
 for (i = 0; i < DIM; i++) {
 for (j = 0; j < DIM; j++) {
 if ((i == DI) && (j == DJ))
 printf(“ T”, m[i][j]);
 else
 printf(“ %c”, m[i][j]);
 }
 printf(“\n”);
 }
 printf(“\n”);
 getchar();
}
void tenta(int i, int j) {
 printf(“tentando(%d,%d)\n”, i, j);
 if (m[i][j] == ‘ ‘) { /* alternativa viável */
 m[i][j] = ‘x’; /* marcar o caminho */
 imprime();
 if ((i == DI) && (j == DJ)) { /* atingiu o objetivo */
 printf(“/* atingiu o objetivo */\n”);
 imprime();
 getchar();
 exit(1);
 }
 else { /* tentar todas alternativas */
 printf(“posição (%d,%d)\n”, i, j);
 tenta(i + -1, j + 0);
 tenta(i + 0, j - 1);
196
Unidade III
 tenta(i + 0, j + 1);
 tenta(i + 1, j + 0);
 printf(“volta\n”);
 }
 m[i][j] = ‘ ‘; /* desfazer a marca */
 imprime();
 }
}
/* inicia a matriz m */
int main() {
 tenta(1, 1);
 getchar();
 return 0;
}
 Observação
As funções não recursivas são chamadas de iterativas.
7.2 Árvores
A importância das estruturas unidimensionais é inegável, mas elas não são adequadas para 
representarmos dados que devem ser dispostos de maneira hierárquica. Por exemplo, os arquivos 
(documentos) que criamos em um computador são armazenados em uma estrutura hierárquica de 
diretórios (pastas). Existe um diretório base no qual podemos armazenar diversos subdiretórios e 
arquivos. Por sua vez, nos subdiretórios, podemos armazenar outros subdiretórios e arquivos, e assim 
por diante, recursivamente. Além de arquivos, temos outros exemplos de estruturas multidimensionais, 
como o organograma de uma empresa ou os algoritmos de decisão.
Figura 293 – Estrutura de árvores aplicada nas pastas de armazenamento
197
ESTRUTURAS DE DADOS
Presidente
Vice-Presidente
Gerência Produção Gerência Comercial Gerência Tecnologia RHGerência Financeira
Contas a 
Pagar PCP Vendas Desenvolvimento
Contas a 
Receber Fábrica Marketing ProduçãoFiscal Estoque CRM Manutenção
Figura 294 – O organograma de uma empresa também é uma árvore
Alto AltoBaixo Baixo
Verificar I/O
Verificar swap
Problema na RAM Problema no aplicativo
In
ve
st
ig
ar
Problema no CPUI/O
Verificar % CPU
Alto Baixo
Servidor lento
Figura 295 – Estrutura de decisão utilizando a árvore
7.2.1 Árvores: definições e representações básicas
As árvores são estruturas de dados multidimensionais que permitem a representação de hierarquias, 
ou a representação em vários níveis. Uma árvore é composta de um conjunto de nós, que podem ou não 
ter ramificações. Existe um nó denominado raiz, que pode ou não ramificar em subárvores, cujas raízes são 
ligadas diretamente a essa raiz, e assim sucessivamente. Esses nós-raízes das subárvores são ditos filhos 
do nó pai, que podem ter mais nós filhos. Portanto, devido a esta característica de comportamento igual 
entre pai e filho, uma estrutura de árvore pode ser trabalhada usando a recursividade. Aqueles com filhos 
são comumente chamados de nós internos, enquanto os nós que não têm filhos são chamados de folhas, 
ou nós externos. Tradicionalmente desenha-se as árvores com a raiz para cima e as folhas para baixo.
Nós internos
Nós externos 
ou folhas
Raiz
Subárvore Subárvore
Subárvore
Subárvore
Subárvore
Subárvore
Subárvore
Figura 296 – Estrutura de árvore
198
Unidade III
Observamos que, por adotarmos tal forma de representação gráfica, não representamos explicitamente 
a direção dos ponteiros, subentendendo que eles apontam sempre do pai para os filhos.
7.2.2 Árvores binárias
A árvore binária é um caso especial em que um pai tem, no máximo, dois filhos (zero, um ou dois). 
Assim, recursivamente, os filhos são pais que têm, no máximo, dois filhos.
O uso da árvore binária é o mais difundido, e muitas vezes a adotamos sem saber que a estamos utilizando. 
Quando efetuamos (5 + 3) × 2 + (9 - 5), montamos uma árvore binária, como a vista na sequência ×
+
-
+
× 
( 5 + 3 ) ( 9 - 5 )x 2 +
Figura 297 – Árvore da resolução da equação
Em uma árvore binária, cada nó tem zero, um ou dois filhos. De maneira recursiva, define-se uma 
árvore binária como sendo:
• uma árvorevazia; ou
• um nó raiz com uma das subárvores, uma identificada como a subárvore da direita (SAD) ou da 
esquerda (SAE); ou
• um nó raiz tendo duas subárvores, identificadas como as subárvores da direita (SAD) e da 
esquerda (SAE).
Sendo as operações os nós e os números as folhas. Assim, na árvore a seguir, o nó A é a raiz, que 
tem como subárvores ou ramificações, do lado esquerdo, o nó B, e, do lado direito, o nó C, que, por sua 
vez, possui como subárvore, do lado esquerdo, o nó D, e, do lado direito, o nó E. Como B, D e E não têm 
ramificações, são chamados de folhas.
C
D E
A
B
Figura 298 – Árvore binária
199
ESTRUTURAS DE DADOS
Em uma árvore binária, o caminho percorrido para sair de um nó e chegar a outro sempre será único. 
Assim, a propriedade fundamental dela é que, da raiz até qualquer um dos seus nós, haverá somente 
um caminho. A quantidade de nós ou saltos percorridos da raiz (sem contá-la) até a folha mais distante 
determina a altura da árvore. Uma árvore apenas com raiz tem altura zero.
2
1
1
3
2
1
4
Altura = 0 Altura = 1 Altura = 2 Altura = 4
Figura 299 – A altura é determinada pela quantidade de saltos entre a raiz e o nó mais distante
Em uma árvore binária, quando um nó tem ramificações, cada uma delas recebe um nome. 
A ramificação esquerda receberá o nome de subárvore esquerda (SAE), e a ramificação direita será a 
subárvore direita (SAD).
raiz
SAE SAD
Figura 300 – Conjunto de um nó e suas ramificações
Mesmo tendo duas informações iguais, uma árvore que possui uma informação na SAE e outra que 
tem a mesma informação na SAD são diferentes.
A
B
A
B
Figura 301 – A ordem das ramificações é relevante
Uma propriedade importante é o fato de existir apenas um caminho entre quaisquer dois nós na árvore.
7.2.3 Percurso em árvores binárias
A posição da informação nas subárvores é importante, pois, muitas vezes, precisamos percorrer 
uma árvore para buscar informação, ou mesmo para descrevê-la. Ao percorrê-la, necessitamos de um 
critério, já que não podemos tomar um caminho qualquer, sob o risco de passarmos e colhermos dados 
de um mesmo nó.
200
Unidade III
Em uma árvore, o conceito de recursividade torna-se fundamental, pois, em árvores grandes, 
dificilmente teríamos duas subárvores iguais. Portanto, não podemos antever uma sequência fixa 
de operações.
Há três ordens de leitura principais, as quais veremos a seguir.
7.2.4 Percurso em pré-ordem ou prefixo (busca em profundidade)
O percurso em pré-ordem faz, recursivamente, a partir da raiz, o seguinte:
• Lê o nó.
• Vai para a SAE.
• Vai para a SAD.
• Retorna.
 Lembrete
A recursividade acontece quando uma função chama a si mesma, mas 
a cada chamada, a função passa a executar a si desde o início, e na volta 
retorna ao ponto em que foi chamada.
Para estudarmos os percursos, utilizaremos a árvore a seguir:
5
4
2 7
61 83
Figura 302 – Exemplo de árvore
201
ESTRUTURAS DE DADOS
Na pré-ordem a leitura é feita antes de tentarmos ir para esquerda ou direita. Inicialmente é montada 
a recursividade, L E D r, ou seja, ler o nó, ir para a SAE, ir para a SAD e retornar, iniciando a partir da raiz 
e fazendo a leitura dos nós.
5
4
2 7
61 83
L E D r
Percurso: 5
Figura 303 – Leitura do nó raiz
LED r
5
4
2 7
61 83
L E D r
Percurso: 5
Figura 304 – Executando a segunda chamada da recursividade, 
LED dirige para E (esquerda) em direção ao próximo nó
Observa-se na recursividade da raiz após focar no nó esquerdo que ainda resta executar o D do 
primeiro nó.
No segundo nó novamente a recursividade da pré-ordem (LED) é iniciada, efetuando a leitura.
5
4
2 7
61 83
LE D r
LED r
Percurso: 5 2
Figura 305 – No segundo nó é feita a leitura do nó seguinte
202
Unidade III
Continuando a recursividade do segundo nó, uma vez feita a leitura, o foco caminha para a esquerda.
5
4
2 7
61 83
LED r
LED r
L E D r
Percurso: 5 2
Figura 306 – No segundo nó o foco segue para a esquerda
No terceiro nó é feita a leitura.
5
4
2 7
61 83
LED r
LED r
LE D r
Percurso: 5 2 1
Figura 307 – Lê a folha
Após a leitura da folha, a recursividade não encontra nó à esquerda nem à direita, pois por se tratar 
de uma folha ela não possui SAE (subárvore esquerda) ou SAD (subárvore direita).
5
4
2 7
61 83
LED r
LED r
LE D r
Percurso: 5 2 1
5
4
2 7
61 83
LED r
LED r
LE D r
Percurso: 5 2 1
A) B)
Figura 308 – Na folha não existe folha nem à esquerda (A), nem à direita (B) ②
203
ESTRUTURAS DE DADOS
Como todas as chamadas foram executadas, a recursividade retorna à função anterior que a chamou.
5
4
2 7
61 83
LED r
LEDr
LE D r
L E D r
Percurso: 5 2 1
Figura 309 – Como todas as funções foram executadas, ela retorna para onde foi chamada
Ao retorno do nó esquerdo na atual função recursiva ainda resta ir para a direita.
5
4
2 7
61 83
LED r
LEDr
LE D r
L E D r
Percurso: 5 2 1
Figura 310 – No nó anterior, a operação faltante é ir para a direita
A função recursiva no novo nó inicia com a leitura da sua informação.
5
4
2 7
61 83
LED r
LEDr
LE D r
LE D r
Percurso: 5 2 1 3
Figura 311 – Realiza-se a leitura do nó
②
204
Unidade III
A próxima operação é seguir a recursividade para a esquerda, porém não é encontrado qualquer nó.
5
4
2 7
61 83
LED r
LEDr
LE D r
LED r
Percurso: 5 2 1 3
Figura 312 – O nó não possui subárvore à esquerda
Como não existe subárvore esquerda, a função recursiva avança para a subárvore direita.
5
4
2 7
61 83
LED r
LEDr
LE D r
LEDr
L E D r
Percurso: 5 2 1 3
Figura 313 – A recursividade no nó dirige-se para a direita
Ao chegar à folha, é feita a leitura da informação do nó.
5
4
2 7
61 83
LED r
LEDr
LE D r
LEDr
LE D r
Percurso: 5 2 1 3 4
Figura 314 – Faz-se a leitura do nó
205
ESTRUTURAS DE DADOS
Por se tratar de uma folha, ela não possui as subárvores esquerda e direita.
5
4
2 7
61 83
LED r
LEDr
LE D r
LEDr
LEDr
Percurso: 5 2 1 3 4
Figura 315 – Não é possível ir para a esquerda ou direita
Com as operações completadas, o foco da folha retorna ao nó em que houve a chamada.
5
4
2 7
61 83
LED r
LEDr
LE D r
LEDr
LEDr
Percurso: 5 2 1 3 4
Figura 316 – Como não tem para onde seguir, ela retorna para o nó que a chamou
Nos nós seguintes, também por não ter mais subárvores para avançar, a recursividade retorna 
até encontrar algo que possua operações a realizar. No caso, todo o ramo esquerdo está completo, 
chegando à raiz.
5
4
2 7
61 83
LED r
LEDr
LE D r
LEDr
LEDr
Percurso: 5 2 1 3 4
Figura 317 – Todo o ramo esquerdo foi percorrido
206
Unidade III
Na raiz, a operação de investigar à direita ainda se encontra aberta, portanto o percurso a partir da 
subárvore direita da raiz é iniciado.
5
4
2 7
61 83
LEDr
LEDr
LE D r
LEDr
LEDr
Percurso: 5 2 1 3 4
L E D r
Figura 318 – Indo para o nó à direita da raiz
Dando continuidade ao percurso pelo ramo direito, é feita a primeira operação do nó em foco, a 
sua leitura.
5
4
2 7
61 83
LED r
LEDr
LE D r
LEDr
LEDr
Percurso: 5 2 1 3 4 7
LE D r
Figura 319 – A leitura é feita indo para o nó à direita
Lida a informação, a operação seguinte é ir para a subárvore esquerda.
5
4
2 7
61 83
LED r
LEDr
LE D r
LEDr
LEDr
Percurso: 5 2 1 3 4 7
LE D r
L E D r
Figura 320 – Dirigindo para o nó à esquerda
207
ESTRUTURAS DE DADOS
No nó à esquerda novamente inicia-se o ciclo de leitura, a tentativa de ir para as subárvores esquerda 
e direita sem resultado, por se tratar de uma folha, e retornar ao nó que a chamou.
5
4
2 7
61 83
LED r
LEDr
LE D r
LEDr
LEDr
Percurso: 5 2 1 3 4 7 6
LE D r
LE D r
Figura 321 – A leitura é feita no nó da esquerda
5
4
2
61 3
LED r
LEDr
LE D r
LEDr
LEDr
Percurso: 5 21 3 4 7 6
LE D r
LED r
7
8
5
4
2
61 3
LED r
LEDr
LE D r
LEDr
LEDr
Percurso: 5 2 1 3 4 7 6
LE D r
LEDr
7
8
Figura 322 – Por se tratar de uma folha, as operações para esquerda e direita não são possíveis
5
4
2 7
61 83
LED r
LEDr
LE D r
LEDr
LEDr
Percurso: 5 2 1 3 4 7 6
LE D r
LEDr
Figura 323 – Feitas as operações, retorna-se ao nó que a chamou
Retornando ao nó que a chamou à esquerda, resta ainda o caminho para a direita. No nó à direita é 
feita a leitura da informação, passando para a operação seguinte, a tentativa para ir para a esquerda e 
para a direita, ambas sem sucesso.
208
Unidade III
5
4
2 7
61 83
LED r
LEDr
LE D r
LEDr
LEDr
Percurso: 5 2 1 3 4 7 6
LE Dr
L E D rLEDr
Figura 324 – A próxima operação é ir para a direita
5
4
2 7
61 83
LED r
LEDr
LE D r
LEDr
LEDr
Percurso: 5 2 1 3 4 7 6 8
LE Dr
LE D rLEDr
Figura 325 – Realiza-se a leitura da folha
5
4
2
61 3
LED r
LEDr
LE D r LEDr
LEDr
Percurso: 5 2 1 3 4 7 6 8
LE Dr
LED r
LEDr
7
8
5
4
2
61 3
LED r
LEDr
LE D r LEDr
LEDr
Percurso: 5 2 1 3 4 7 6 8
LE Dr
LED r
LEDr
8
7
Figura 326 – Tentativa de ir para a esquerda e direita na folha
Finalmente, sem outros nós a percorrer, acontece o retorno sucessivo das chamadas recursivas até 
chegar à raiz.
209
ESTRUTURAS DE DADOS
5
4
2 7
61 83
LED r
LEDr
LE D r
LEDr
LEDrPercurso: 5 2 1 3 4 7 6 8
LE Dr
LED r
LEDr
Figura 327 – Sem outros nós a percorrer, o processo recursivo retorna à raiz
Assim, o percurso está completo, com o resultado: 5 2 1 3 4 7 6 8.
7.2.5 Percurso em ordem ou infixo (ordem simétrica)
O percurso em ordem faz, recursivamente, a partir da raiz, o seguinte:
• Vai para a SAE.
• Lê o nó.
• Vai para a SAD.
• Retorna.
No percurso infixo a leitura é feita após varrer o ramo esquerdo, e depois percorre o ramo direito. Fazendo 
o percurso na mesma árvore, iniciando a partir da raiz, é executada a recursividade Esquerda-Leitura-Direita 
e retorno (ELDr). No exemplo a seguir, o caminho avança para a esquerda inicialmente até não encontrar 
mais nós.
EL D r
5
4
2 7
61 83
EL D r
EL D r
Percurso: 3
EL D r
5
4
2 7
61 83
EL D r
ELD r
Percurso: 1 4
EL D r
5
4
2 7
61 8
3
EL D r
Percurso: 2
EL D r
5
4
2 7
61 8
3
Percurso: 1
Figura 328 – O caminho é feito pela esquerda até não ter mais nós
210
Unidade III
Feita a leitura, o passo seguinte é tentar ir para o nó à direita sem sucesso, restando retornar o nó ao 
ponto de chamada da recursividade anterior. No nó anterior são feitas as operações seguintes, leitura e 
ida para a direita.
8
Percurso: 1 2 3
EL D r
5
4
2
61 3
ELDr
ELDr
8
7
Percurso: 1 2 2
EL D r
5
4
2 7
61 3
ELD r
ELDr
Percurso: 1 1
EL D r
5
4
2
61 3
EL D r
ELDr
8
7
Figura 329 – Na folha verifica-se à direita e retorna-se ao nó que a chamou, fazendo a leitura
Ao seguir pelo ramo à direita, o próximo nó não possui ramificação para a esquerda, realizando 
então a segunda operação da recursividade, após é feita a leitura da informação do nó, tentando e 
encontrando a sequência para uma nova recursividade no nó direito.
Percurso: 1 2 1
EL D r
5
4
2
61 3
ELDr
ELDr
EL D r
8
7
Percurso: 1 2 3 2
EL D r
5
4
2
61 3
ELDr
ELDr
ELD r
8
7
Percurso: 1 2 3 3
EL D r
5
4
2
61 3
ELDr
ELDr
ELDr
8
7
Figura 330 – No nó seguinte não existe caminho à 
esquerda, faz-se a leitura e tenta-se ir para a direita
O nó da direita é uma folha, portanto sem as subárvores esquerda e direita, efetua-se apenas a leitura.
8
Percurso: 1 2 3 1
EL D r
5
4
2 7
61 3
ELDr
ELDr
ELD r
EL D r
8
Percurso: 1 2 3 4 2
EL D r
5
4
2 7
61 3
ELDr
ELDr
ELDr
ELD r
8
Percurso: 1 2 3 4 3
EL D r
5
4
2 7
61 3
ELDr
ELDr
ELDr
ELDr
Figura 331 – Na folha são feitas as operações de tentar ir 
para a esquerda, leitura e tentativa de ir para a direita
211
ESTRUTURAS DE DADOS
Nas chamadas recursivas da subárvore esquerda da raiz somente restam os retornos. Partindo da 
folha, o foco retorna até a raiz.
Percurso: 1 2 3 4 1
EL D r
5
4
2 7
ELDr
ELDr
ELDr
ELDr
Percurso: 1 2 3 4 2
EL D r
5
4
2 7
ELDr
ELDr
ELDr
ELDr
Percurso: 1 2 3 4 3
EL D r
5
4
2 7
ELDr
ELDr
ELDr
ELDr
861 3 861 3 861 3
Figura 332 – As operações restantes das chamadas recursivas retornam até a raiz
Com o ramo esquerdo da raiz totalmente percorrido, é feita a leitura da informação antes de seguir 
para o ramo direito. No primeiro nó é realizada a primeira operação recursiva para a esquerda.
8
Percurso: 1 2 3 4 5 1
ELD r
5
4
2 7
61 3
ELDr
ELDr
ELDr
ELDr
8
Percurso: 1 2 3 4 5 2
ELDr
5
4
2 7
61 3
ELDr
ELDr
ELDr
ELDr
8
Percurso: 1 2 3 4 5 3
ELDr
EL D r
5
4
2 7
61 3
ELDr
ELDr
ELDr
ELDr
Figura 333 – Iniciando o percurso na subárvore direita da raiz
Na folha à esquerda, a nova recursividade tenta ir para a esquerda, sem sucesso, faz em seguida a 
leitura da informação, e tenta ir para a direita, também sem sucesso, retornando ao ponto de chamada 
do nó anterior.
Percurso: 1 2 3 4 5 6 Percurso: 1 2 3 4 5 63 4
ELDr ELDr
EL D r EL D r
5 5
4 4
2 27 7
ELDr ELDr
ELDr ELDr
ELDr ELDr
ELDr ELDr
ELDr ELDr
6 61 18 83 3
Percurso: 1 2 3 4 5 Percurso: 1 2 3 4 5 61 2
ELDr ELDr
EL D r EL D r5 5
2 27 7
8
ELDr ELDr
ELDr ELDr
ELDr ELDr
ELDr ELDr
EL D r ELD r
6 61 1 83 3
4 4
Figura 334 – No nó da esquerda são feitas as operações esquerda, leitura, direita e retorno
212
Unidade III
Terminado o nó à esquerda na função recursiva, restam as operações leitura e em seguida ida 
para a direita.
Percurso: 1 2 3 4 5 6 7 Percurso: 1 2 3 4 5 6 71 2
ELDr
ELD r
5
4
2 7
61 83
ELDr
ELDr
ELDr
ELDr
ELDr
ELDr
ELDr
5
4
2 7
61 83
ELDr
ELDr
ELDr
ELDr
ELDr
Figura 335 – No retorno é feita a leitura dirigindo-se para a direita
Finalmente na folha direita é feita a única operação possível, a leitura, e sucessivamente o retorno 
das chamadas até a raiz.
8
ELDr
ELDr
ELD r
5
4
2 7
61 3
ELDr
ELDr
ELDr
ELDr
ELDr
Percurso: 1 2 3 4 5 6 7 8 2
8
ELDr
ELDr
ELD r
5
4
2 7
61 3
ELDr
ELDr
ELDr
ELDr
ELDr
Percurso: 1 2 3 4 5 6 7 8 3
8
ELDr
ELDr
EL D r
5
4
2
61 3
ELDr
ELDr
ELDr
ELDr
ELDr
Percurso: 1 2 3 4 5 6 7 1
7
8
Percurso: 1 2 3 4 5 6 7 8 4
ELDr
ELDr
ELDr
5
4
2 7
61 3
ELDr
ELDr
ELDr
ELDr
ELDr
8
Percurso: 1 2 3 4 5 6 7 8 5
ELDr
ELDr
ELDr
5
4
2 7
61 3
ELDr
ELDr
ELDr
ELDr
ELDr
8
Percurso: 1 2 3 4 5 6 7 8 6
ELDr
ELDr
ELDr
5
4
2 7
61 3
ELDr
ELDr
ELDr
ELDr
ELDr
Figura 336 – No último nó são feitas as operações ELD e retorno, voltando até a raiz
213
ESTRUTURAS DE DADOS
 Saiba mais
O tipo chamado de árvore binária com costura nada mais é do que 
uma árvore simples que por ventura não tem um dos nós filhos. Caso não 
tenha a subárvore esquerda, o ponteiro nulo é substituído pelo endereço 
do antecessor. Por outro lado, se não tiver a subárvore direita, o ponteiro é 
substituído pelo endereço da subárvore esquerda.
O objetivo dessa alteração é facilitar o percurso em ordem, ou infixa. 
A única fonte com uma implementação funcional encontra-se em:
WIKIPEDIA. Árvore binária com costura. [s.d.]. Disponível em: 
https://bit.ly/3NMPdpi. Acesso em: 10 maio 2022.
7.2.6 Percurso em pós-ordem ou pós-fixoO percurso em pós-ordem faz, recursivamente, a partir da raiz, o seguinte:
• Vai para a SAE.
• Vai para a SAD.
• Lê o nó.
No percurso em pós-ordem, a leitura é feita somente após as visitas para a esquerda e direita. 
A função recursiva é E D L r – Esquerda-Direita-Leitura e retorno. O percurso inicia na raiz e segue 
sempre pela esquerda, até não encontrar mais nós na subárvore esquerda.
Percurso: Percurso: 1 2
ED L r
5
4
2 7
61 83
ED L r
ED L r
5
4
2 7
61 83
Figura 337 – A partir da raiz, a recursividade segue pelo ramo esquerdo até não encontrar mais nós
214
Unidade III
No último nó à esquerda é feita a tentativa de ir para a direita sem resultado, somente então é feita 
a leitura e o retorno ao nó que a chamou.
Percurso: 1 3
Percurso: 2Percurso: 
Percurso: 1
1
4
ED L r
ED L r
ED L r
5
4
2 7
61 83
ED L r
ED L r
EDL r
5
4
2 7
61 83
ED L r
ED L r
EDLr
5
4
2 7
61 83
ED L r
ED L r
EDLr
5
4
2 7
61 83
Figura 338 – As operações da função recursiva são feitas e retornam à função que chamou o nó
Retornando da folha à esquerda, a próxima operação é avançar pela direita enquanto não houver 
nós à esquerda. No exemplo a seguir, o primeiro nó não possui subárvore à esquerda, então novamente 
tenta-se ir para à direita, com sucesso.
Percurso: 1 2Percurso: 1 1
ED L r ED L r
EDL r EDL r
EDLr EDLr
ED L r EDL r
5 5
4 4
2 27 7
6 61 18 83 3
Figura 339 – Como ir para a direita precede a leitura, 
avança-se até não encontrar mais nós à esquerda
Por ser pós-ordem, as tentativas de ir para as subárvores esquerda e direita são feitas antes de ler 
a informação do nó. No caso, por ser uma folha, não existem caminhos nem para a esquerda, nem 
para a direita.
215
ESTRUTURAS DE DADOS
Percurso: 1 2Percurso: 1 1
ED L r
EDL r
EDLr
EDL r
ED L r
5
4
2 7
61 83
ED L r
EDL r
EDLr
EDL r
EDL r
5
4
2 7
61 83
Figura 340 – Na folha, as tentativas à esquerda e à direita são feitas antes da leitura
A partir da folha, são feitas repetidas operações de leitura e retorno até encontrar a chamada da raiz 
da ramificação.
8
ED L r
EDL r
EDLr
EDL r
EDLr
5
4
2 7
61 3
Percurso: 1 4 1
8
ED L r
EDL r
EDLr
EDL r
EDLr
5
4
2 7
61 3
Percurso: 1 4 2
8
ED L r
EDL r
EDLr
EDLr
EDLr
5
4
2 7
61 3
Percurso: 1 4 3 3
8
ED L r
EDL r
EDLr
EDLr
EDLr
5
4
2 7
61 3
Percurso: 1 4 3 4
8
ED L r
EDLr
EDLr
EDLr
EDLr
5
4
2 7
61 3
Percurso: 1 4 3 2 5
8
ED L r
EDLr
EDLr
EDLr
EDLr
5
4
2 7
61 3
Percurso: 1 4 3 2 6
Figura 341 – A partir da folha, o retorno é feito até a primeira chamada, sempre lendo o conteúdo
Indo para a direita, logo no primeiro nó existe a possibilidade de seguir para esquerda, portanto é 
necessário percorrê-lo antes de ir para a direita.
216
Unidade III
ED L r EDL r
ED L rEDLr EDLr
EDLr EDLr
EDLr EDLr
EDLr EDLr
5 5
4 4
2 27 7
6 61 18 83 3
Percurso: 1 4 3 2 2Percurso: 1 4 3 2 1
Figura 342 – Avança-se até não encontrar mais nós à esquerda, no caso o primeiro nó
Indo para a esquerda é testada a subárvore esquerda, sem sucesso, depois a direita, também sem 
sucesso, e somente então é feita a leitura.
8
Percurso: 1 4 3 2 2
EDL r
ED L r
EDL r
EDLr
EDLr
EDLr
EDLr
5
4
2 7
61 3 8
Percurso: 1 4 3 2 6 3
EDL r
ED L r
EDLr
EDLr
EDLr
EDLr
EDLr
5
4
2 7
61 38
Percurso: 1 4 3 2 1
EDL r
ED L r
ED L r
EDLr
EDLr
EDLr
EDLr
5
4
2 7
61 3
Figura 343 – Na folha não é possível ir para a esquerda ou direita, é feita a leitura
Após a leitura, resta retornar ao nó anterior. Nele ainda faltam avançar para direita e fazer a leitura.
Percurso: 1 4 3 2 6 2Percurso: 1 4 3 2 6 1
EDL r
ED L r
EDLr
EDLr
EDLr
EDLr
EDLr
5
4
2 7
61 83
EDL r
EDL r
EDLr
EDLr
EDLr
EDLr
EDLr
5
4
2 7
61 83
Figura 344 – Faz-se o retorno e no nó anterior o próximo passo é seguir para a direita
Na última folha não é possível ir para a esquerda ou direita, então é feita a leitura da informação do nó.
217
ESTRUTURAS DE DADOS
8
Percurso: 1 4 3 2 6 2
EDL r
ED L rEDLr
EDLr
EDLr
EDLr
5
4
2 7
61 3 8
Percurso: 1 4 3 2 6 8 3
EDL r
EDL r
EDLr
EDLr
EDLr
EDLr
EDLr
5
4
2 7
61 38
Percurso: 1 4 3 2 6 1
EDL r
EDL r
ED L r EDL r
EDLr EDLr
EDLr
EDLr
EDLr
EDLr
EDLr
5
4
2 7
61 3
Figura 345 – Na folha não é possível ir para a esquerda ou direita, é feita a leitura
Feita a leitura da folha, seguidamente é realizado o retorno à função que a chamou, e lá restando 
fazer apenas a leitura, a informação do nó é resgatada, novamente retornando à função recursiva 
anterior à chegada da raiz.
8
Percurso: 1 4 3 2 6 8 7 2
EDL r
EDLr
EDLr
EDLr
EDLr
EDLr
5
4
2 7
61 3 8
Percurso: 1 4 3 2 6 8 7 3
EDL r EDLr
EDLr
EDLr
EDLr
EDLr
EDLr
5
4
2 7
61 38
Percurso: 1 4 3 2 6 8 1
EDL r
EDL r
EDLr EDLr
EDLr EDLr EDLr
EDLr
EDLr
EDLr
EDLr
5
4
2 7
61 3
8
Percurso: 1 4 3 2 6 8 7 5
EDLr EDLr
EDLr
EDLr
EDLr
EDLr
5
4
2 7
61 38
Percurso: 1 4 3 2 6 8 7 4
EDL r EDLr
EDLr EDLr
EDLr EDLr
EDLr
EDLr
EDLr
EDLr
5
4
2 7
61 3
Figura 346 – A partir da folha é feita a leitura e o retorno até a raiz
7.3 Estrutura de árvores binárias em C
Assim como nas estruturas unidimensionais, nas árvores podemos definir um tipo para representar 
o nó de uma árvore binária.
218
Unidade III
Figura 347
Ou
Figura 348 
As estruturas podem ser representadas tanto na forma de árvore como em nó de lista, porém com 
dois deles próximos.
info
sae sad
ou info &sae &sad
Figura 349 – Representação da estrutura de nó da árvore
Como nas estruturas unidimensionais, a variável que era chamada de próximo, agora, passa a 
se chamar SAE e SAD, Subárvore Esquerda e Subárvore Direita, respectivamente, que são ponteiros 
autorreferenciados.
A manipulação dos nós é feita com as operações básicas vistas previamente. Serão descritas apenas 
operações cuja utilidade seja a mais geral possível. Uma operação que provavelmente deverá ser incluída 
em todos os casos é a iniciação de uma árvore vazia. Como uma árvore é representada pelo endereço 
do nó raiz, uma árvore vazia tem de ser representada pelo valor NULL. Assim, a função que inicia uma 
árvore vazia pode ser simplesmente:
Figura 350 
219
ESTRUTURAS DE DADOS
Para criar árvores não vazias, a operação cria na memória um nó raiz com a sua informação e suas 
duas subárvores, à esquerda e à direita. Essa função tem como valor de retorno o endereço do nó raiz 
criado, que será utilizado nas ligações entre os nós:
Figura 351 
A fim de criar um nó simples com uma informação, observe a figura a seguir:
8
Figura 352 – Nó simples
Na função main, devemos fazer:
Figura 353 
Com a função de inicialização é possível montar uma árvore completa. No exemplo a seguir, um 
novo nó é criado com o nó a1 já criado como sua subárvore direita.
Figura 354 
220
Unidade III
4
8
a2
a1
Figura 355 – O nó a1 é colocado na SAD do nó criado
É possível criar um nó independente e depois encaixá-lo na árvore. Um novo nó é criado, depois 
sendo atribuído na subárvore esquerda do nó a2 ().
Figura 356 
4
8
a2
a3
a1
2
4
8
a2
a3 a1
2
Figura 357 – Um novo nó é colocado na SAE do nó a2
Dessa forma, apenas com as funções cria e inicializa, é possível manualmente criar toda uma árvore.
Outra operação importante é verificar se uma árvore é ou não vazia.
Figura 358 
Como todas as estruturas, é necessária uma função para impressão ou busca. Por estarmos estudando 
as rotinas manuais, e não as específicaspara árvores binárias de busca, uma busca simples pode usar o 
mesmo princípio para a impressão. Assim, a função de impressão deve exibir o conteúdo da árvore. Ela 
precisa percorrer recursivamente a árvore, passando por todos os nós e devolvendo a sua informação. 
221
ESTRUTURAS DE DADOS
Como uma árvore binária é vazia ou composta de raiz e uma ou duas subárvores, para imprimir a 
informação de todos os nós da árvore, inicialmente precisamos testar se ela é vazia. Caso ela não seja, 
imprimimos a informação associada à raiz e chamamos (recursivamente) a função para imprimir os nós 
das subárvores.
Na impressão, todos os nós necessitam ser percorridos e, para isso, utiliza-se o conhecimento 
adquirido anteriormente em percursos. Dessa forma, para imprimir, existem três possibilidades:
Figura 359 – Impressão em pré-ordem
Figura 360 – Impressão em pós-ordem
Figura 361 – Impressão em ordem simétrica
 Observação
Assim como nas listas, uma árvore pode ser implementada em um vetor. 
Neste caso, o limite é a quantidade de elementos no vetor.
222
Unidade III
Figura 362 – Árvore binária implementada em um vetor
Logo, em um programa completo de árvore implementado manualmente, temos:
#include <stdio.h>
#include <stdlib.h>
struct arv {
 int info;
 struct arv* sae;
 struct arv* sad;
};
typedef struct arv Arv;
int vazia(Arv* a)
{
 return a == NULL;
}
Arv* inicializa(void)
{
 return NULL;
}
Arv* cria(int c, Arv* sae, Arv* sad) {
 Arv* p = (Arv*)malloc(sizeof(Arv));
 p->info = c;
 p->sae = sae;
 p->sad = sad;
 return p;
}
223
ESTRUTURAS DE DADOS
void imprime(Arv* a)
{
 if (!vazia(a)) {
 printf(“%d “, a->info); /* mostra raiz */
 imprime(a->sae); /* mostra sae */
 imprime(a->sad); /* mostra sad */
 }
}
void imprimec(Arv* a)/* impressão na forma < a <s>,<n> > em pré-ordem*/
{
 printf(“<”);
 if (!vazia(a)) {
 printf(“%d “, a->info); /* mostra raiz */
 imprimec(a->sae); /* mostra sae */
 printf(“,”);
 imprimec(a->sad); /* mostra sad */
 }
 printf(“>”);
}
void imprimepos(Arv* a)/* impressão na forma pós-ordem>*/
{
 if (!vazia(a)) {
 imprimepos(a->sae); /* mostra sae */
 imprimepos(a->sad); /* mostra sad */
 printf(“%d “, a->info); /* mostra raiz */
 }
}
void imprimeos(Arv* a)/* impressão na forma Ordem simétrica*/
{
 if (!vazia(a)) {
 imprimeos(a->sae); /* mostra sae */
 printf(“%d “, a->info); /* mostra raiz */
 imprimeos(a->sad); /* mostra sad */
 }
}
Arv* libera(Arv* a) {
 if (!vazia(a)) {
 libera(a->sae); /* libera sae */
 libera(a->sad); /* libera sad */
 free(a); /* libera raiz */
 }
 return NULL;
}
int busca(Arv* a, int c) {
 if (vazia(a))
 return 0; /* árvore vazia: não encontrou */
 else
 return a->info == c || busca(a->sae, c) || busca(a->sad, c);
}
224
Unidade III
int main() {
 Arv* a1 = cria(8, inicializa(), inicializa());
 imprimepos(a1);
 printf(“\n”);
 Arv* a2 = cria(4, inicializa(), a1);
 Arv* a3 = cria(2, inicializa(), inicializa());
 Arv* a4 = cria(1, inicializa(), inicializa());
 Arv* a5 = cria(3, a3, a4);
 a2->sae = a5;
 imprime(a2);
 printf(“\n”);
 imprimepos(a2);
 printf(“\n”);
 imprimeos(a2);
 printf(“\n”);
 if (busca(a2, 233))
 printf(“z encontrado”);
 else
 printf(“z nao encontrado”);
}
7.3.1 Árvores binárias de busca
Uma árvore binária de busca, ou árvore binária de pesquisa, é uma estrutura de dados em que todos os 
nós da subárvore esquerda possuem valor inferior ao nó raiz, assim como todos os nós da subárvore direita 
têm valor superior ao nó raiz. Dessa forma, a busca de um valor torna-se muito fácil, pois, a partir de simples 
comparações, podemos localizá-lo, com menos passos. Imagine, por exemplo, a sequência de entrada:
50 67 20 13 31 35 80 60 62 2 55 25
No caso de estrutura linear, os valores sequencialmente são:
50 31 6220 80 5567 35 213 67 25
Figura 363 – Entrada sequencial, unidimensional
Com a estrutura montada, na mesma sequência de entrada, em uma árvore a formação fica da 
seguinte forma:
2
13
20
50
67
8031 60
25 35 62
Figura 364 – Árvore binária de busca
225
ESTRUTURAS DE DADOS
Nesta árvore, para ir da raiz até quaisquer dos nós, são necessários, no máximo, três “pulos”. Se em 
uma busca precisássemos localizar o valor 2, procurando sequencialmente, teríamos de dar nove “pulos”.
50 31 6220 80 5567 35 213 67 25
1 2 3 4 5 6 7 8 9 
Figura 365 – Quantidade de passos para localizar o número 2
No caso da busca na árvore, sabendo que os valores menores estão na SAE, e os números maiores, 
na SAD, para procurar o número 2, partindo da raiz, como 2<50, procuramos na SAE; 2<20, então 
buscamos na SAE; 2<13, pesquisamos na SAE; e localizamos.
13
20
50
67
8031 60
25 35 622
3
2
1
Figura 366 – Quantidade de passos para localizar o número 2 em uma árvore binária de busca
Em três “pulos” o número é localizado, enquanto na busca sequencial a quantidade deles depende 
do momento em que o número foi digitado: quanto mais tarde, mais demorado para localizá-lo. Dessa 
forma, os gerenciadores de bancos de dados utilizam essa técnica nos índices, usando a informação dos 
campos-chave para os nós, e a busca torna-se bem mais rápida.
As operações existentes nessa estrutura de dados são: busca, inserção e remoção. Veremos essas 
operações a seguir.
7.3.1.1 Operação de busca
Na busca, as seguintes operações devem ser realizadas recursivamente, lembrando que, a cada 
movimentação, o novo nó passa a ser a raiz:
• Se o valor procurado for igual ao da raiz, o valor será encontrado.
• Se o valor procurado for menor que o da raiz, deveremos buscar na SAE.
• Se o valor procurado for maior que o da raiz, deveremos buscar na SAD.
• Se o nó for na folha da árvore, o valor requerido não terá sido encontrado.
226
Unidade III
Portanto, usando a árvore do exemplo para achar o valor 72 na árvore, partindo da raiz, teremos 
o seguinte:
Quadro 11 – Exemplo de árvore
 50
Se o valor procurado for igual ao da raiz, então o valor será 
encontrado: 50≠72 
Se o valor procurado for menor que o da raiz, deveremos 
buscar na subárvore da esquerda: 50>72 
Se o valor procurado for maior que o da raiz, deveremos 
buscar na subárvore da direita: 50<72
 
 
67
50
Se o valor procurado for igual ao da raiz, então ele será 
encontrado: 67≠72 
Se o valor procurado for menor que o da raiz, então 
deveremos buscar na subárvore da esquerda: 67>72 
Se o valor procurado for maior que o da raiz, deveremos 
buscar na subárvore da direita: 67<72
 
 
 
67
80
50 Se o valor procurado for igual ao da raiz, então ele será 
encontrado: 80≠72 
Se o valor procurado for menor que o da raiz, então 
deveremos buscar na subárvore da esquerda: não há SAE 
Se o valor procurado for maior que o da raiz, deveremos 
buscar na subárvore da direita: não há SAE 
Se o nó for na folha da árvore, o valor requerido não 
terá sido encontrado 
Como outro exemplo, devemos procurar o valor 31:
Quadro 12 – Outro exemplo de árvore
 50
Se o valor procurado for igual ao da raiz, então ele será 
encontrado: 50≠31 
Se o valor procurado for menor que o da raiz, então 
deveremos buscar na subárvore da esquerda: 50>31

 20
50
Se o valor procurado for igual ao da raiz, então ele será 
encontrado: 20≠31 
Se o valor procurado for menor que o da raiz, deveremos 
buscar na subárvore da esquerda: 20>31
Se o valor procurado for maior que o da raiz, deveremos 
buscar na subárvore da direita: 20<31
 
 

20
31
50
Se o valor procurado for igual ao da raiz, então ele 
será encontrado: 31=31
227
ESTRUTURAS DE DADOS
A função para a busca usa a recursividade seguindo pelas subárvores, depois para a esquerda ou 
direita conforme a comparação entre o valor procurado e o valor do nó corrente.
Figura 367 
7.3.1.2 Operação de inserção
A operação de inserção deve ser feita combastante critério, pois o novo valor inserido não pode 
quebrar a estrutura da árvore, mas é bem simples, uma vez entendida a operação de busca.
A operação de busca é efetuada, até encontrar uma subárvore livre ou uma folha, devemos obedecer 
aos seguintes critérios:
• Se a chave a ser inserida for menor que a chave do nó analisado, inseriremos a chave na 
subárvore esquerda.
• Se a chave a ser inserida for maior que a chave do nó analisado, inseriremos a chave na 
subárvore direita.
• Se a subárvore estiver ocupada, seguiremos com a busca.
Assim, para inserir o valor 72 na lista, é feita a busca até encontrar um nó com a subárvore livre 
adequada, ou folha, e fazemos a inserção.
Quadro 13 – Exemplo de árvore
50 72>50
Se a chave a ser inserida for menor que aquela do nó 
analisado, inseriremos a chave na subárvore esquerda 
Se a chave a ser inserida for maior que aquela do nó 
analisado, inseriremos a chave na subárvore direita 
67
50
72>67
Se a chave a ser inserida for menor que aquela do nó 
analisado, inseriremos a chave na subárvore esquerda 
Se a chave a ser inserida for maior que aquela do nó 
analisado, inseriremos a chave na subárvore direita 
228
Unidade III
67
80
50
72<80
Se a chave a ser inserida for menor que aquela do nó 
analisado, inseriremos a chave na subárvore esquerda 
13
20
50
67
8031 60
25 35 622 72 ② 
A função percorre a árvore recursivamente até encontrar um nó com o local vazio para inserir o 
novo nó.
Figura 368
7.3.1.3 Operação de remoção
Fazer a remoção de um nó sem comprometer a estrutura é um processo mais complexo. Para excluir 
um nó de uma árvore binária de busca, devem ser consideradas três situações:
• Remoção na folha.
• Remoção de um nó com um filho.
• Remoção de um nó com dois filhos.
229
ESTRUTURAS DE DADOS
Remoção na folha
A exclusão na folha é a mais simples, basta remover o nó da árvore. Assim, para remover o valor 72, 
é necessário retirá-lo da árvore.
13
20
50
67
8031 60
25 35 62 2
13
20
50
67
8031 60
25 35 622
Figura 369 – Remoção na folha
Remoção de folha com um filho
A operação de remoção de um nó com apenas um filho também não tem grande dificuldade. Ao 
excluir o nó, o filho sobe para a posição do pai.
Voltando à árvore anterior, ao excluir o nó 80, o seu filho, 72, assume o seu lugar.
13
20
50
67
8031 60
25 35 622
13
20
50
67
72
31 60
25 35 622

Figura 370 – Remoção de nó com uma folha
230
Unidade III
Ou, então, para remover o nó 13:
72
2
20
50
67
8031 60
25 35 62
13
20
50
67
72
8031 60
25 35 622

Figura 371 – Remoção de nó com uma folha
Remoção de folha com dois filhos
Neste caso, podemos fazer de duas maneiras diferentes:
• O nó a ser retirado é substituído pelo nó mais à direita da subárvore esquerda.
Na árvore do exemplo, teremos de remover a raiz:
72
13
20
35
67
8031 60
25 622
13
20 67
72
8031 60
25 35 622

Figura 372 – Substituição pelo nó mais à direita da SAE
231
ESTRUTURAS DE DADOS
• O nó a ser retirado é substituído pelo nó mais à esquerda da subárvore direita; nesta opção, para 
remover a raiz:
72
13
20
60
67
8031 62
25 352
13
20
50
67
72
8031 60
25 35 622

Figura 373– Substituição pelo nó mais à esquerda da SAD
Na programação, o algoritmo principal inicialmente fará a busca antes de analisar o nó a ser removido.
Figura 374 
Uma vez localizado o nó a ser removido, analisa-se se a folha não tem o filho esquerdo ou o filho 
direito. Caso tenha ambos, a remoção será como visto a seguir.
232
Unidade III
Figura 375 
No caso de ter dois filhos, escolhe-se um dos lados e localiza-se o nó que substituirá o nó removido. 
Existe um algoritmo que garante a localização do nó “mais à esquerda do lado direito”.
Se a escolha for pelo lado direito, os passos são:
• Ir para o primeiro nó do lado direito.
• Seguir sequencialmente através da subárvore esquerda até não ter mais para onde ir (encontrar 
nulo). Se o primeiro nó do lado direito não tiver filhos, ele mesmo será o nó eleito.
1
2
2
1
2
Figura 376 – Pelo lado direito inicia-se avançando um nó 
para o lado direito e depois segue-se para a esquerda
233
ESTRUTURAS DE DADOS
Figura 377 
Se a escolha for pelo lado esquerdo, os passos são:
• Ir para o primeiro nó do lado esquerdo.
• Seguir sequencialmente através da subárvore direita até não ter mais para onde ir (encontrar 
nulo). Se o primeiro nó do lado esquerdo não tiver filhos, ele mesmo será o nó eleito.
 Observação
Caso a árvore seja pequena o suficiente para ser observável, uma 
maneira simples de identificar os nós que tomarão na remoção de um nó 
com dois filhos é:
• Maior valor do lado esquerdo.
• Menor valor do lado direito.
Figura 378 
Consta a seguir o código completo:
#include <stdio.h>
#include <stdlib.h>
struct arv {
 int info;
 struct arv* sae;
 struct arv* sad;
234
Unidade III
};
typedef struct arv Arv;
int vazia(Arv* a)
{
 return a == NULL;
}
void imprime(Arv* a)
{
 if (!vazia(a)) {
 printf(“%d “, a->info); /* mostra raiz */
 imprime(a->sae); /* mostra sae */
 imprime(a->sad); /* mostra sad */
 }
}
void imprimec(Arv* a)/* impressão na forma < a <s>,<n> > em pré-ordem*/
{
 printf(“<”);
 if (!vazia(a)) {
 printf(“%d “, a->info); /* mostra raiz */
 imprimec(a->sae); /* mostra sae */
 printf(“,”);
 imprimec(a->sad); /* mostra sad */
 }
 printf(“>”);
}
void imprimepos(Arv* a)/* impressão na forma pós-ordem>*/
{
 if (!vazia(a)) {
 imprimepos(a->sae); /* mostra sae */
 imprimepos(a->sad); /* mostra sad */
 printf(“%d “, a->info); /* mostra raiz */
 }
}
void imprimeos(Arv* a)/* impressão na forma Ordem simétrica*/
{
 if (!vazia(a)) {
 imprimeos(a->sae); /* mostra sae */
 printf(“%d “, a->info); /* mostra raiz */
 imprimeos(a->sad); /* mostra sad */
 }
}
Arv* libera(Arv* a) {
 if (!vazia(a)) {
 libera(a->sae); /* libera sae */
 libera(a->sad); /* libera sad */
 free(a); /* libera raiz */
235
ESTRUTURAS DE DADOS
 }
 return NULL;
}
Arv* busca(Arv* r, int v)
{
 if (r == NULL) 
 return NULL;
 else 
 if (r->info > v) 
 return busca(r->sae, v);
 else 
 if (r->info < v) 
 return busca(r->sad, v);
 else 
 return r;
}
Arv* insere(Arv* a, int v)
{
 if (a == NULL) {
 a = (Arv*)malloc(sizeof(Arv)); a->info = v;
 a->sae = a->sad = NULL;
 }
 else
 {
 if (v < a->info)
 a->sae = insere(a->sae, v);
 else/* v < a->info */
 a->sad = insere(a->sad, v);
 }
 return a;
}
Arv* retira(Arv* r, int v)
{
 if (r == NULL)
 return NULL;
 else
 {
 if (r->info > v)
 r->sae = retira(r->sae, v);
 else
 {
 if (r->info < v)
 r->sad = retira(r->sad, v);
 else { /* achou o elemento nem a maior nem menor*/
 if (r->sae == NULL && r->sad == NULL) { /* é 
folha */
 free(r);
 r = NULL;
 }
 else
 {
 if (r->sae == NULL) { /* só tem filho à 
direita */
236
Unidade III
 Arv* t = r;
 r = r->sad;
 free(t);
 }
 else
 {
 if (r->sad == NULL) { /* só tem 
filho à esquerda */
 Arv* t = r;
 r = r->sae;
 free(t);
 }
 else { /* tem os dois filhos */
 Arv* pai = r;
 Arv* f = r->sae;
 while (f->sad != NULL) {
 pai = f;
 f = f->sad;
 }
 r->info = f->info; /* 
troca as informações */
 f->info = v;
 r->sae = retira(r->sae, 
v);
 }
 }
 }
 }
 }
 }
 return r;
}
int main() {
 Arv* a1 = insere(NULL, 50);
 imprimepos(a1);
 printf(“\n”);
 insere(a1, 20);
 insere(a1, 67);
 insere(a1, 13);
 insere(a1, 31);
 insere(a1, 60);
 insere(a1, 80);
 insere(a1, 2);
 insere(a1, 25);
 insere(a1, 62);
 insere(a1, 72);
 insere(a1, 35);
 a1 = retira(a1, 13);
 imprimeos(a1);
 printf(“\n”);
}
237
ESTRUTURAS DE DADOS
 Observação
A leitura de uma árvore binária de busca na ordem infixa sempre 
resultará em uma sequência em ordem crescente. Trata-se de uma das 
técnicas de ordenação conhecida como HeapSort.
 Lembrete
Para identificar se o TAD é uma árvore, ela não deverá ter controle, mas 
cada nó em vez de possuirum ponteiro apontando para o próximo, terá 
dois, que serão SAE e SAD.
 Saiba mais
Um dos usos mais comuns de árvore é o utilizado pelo site a seguir. Ao 
contrário do que parece, a sua implementação é bem simples.
Basicamente, o Akinator é uma árvore, na qual cada nó é uma pergunta 
e as respostas são as folhas. Cada vez que chega à folha e a reposta não é 
a conhecida por ele, o programa insere um novo nó contendo a resposta 
desconhecida, e transforma a folha anterior em uma pergunta. Desta forma, 
o site passa a adquirir novos conhecimentos.
AKINATOR. Akinator. [s.d.]. Disponível em: https://bit.ly/3oXKZk1. Acesso 
em: 10 maio 2022.
7.4 Pesquisa de dados: sequencial e binária
Definindo busca como a procura de um valor em uma estrutura, vimos no item anterior a árvore 
binária de busca, ou seja, o valor pesquisado está em uma árvore. Porém, se for necessário fazê-lo em 
um vetor, podemos usar o que vimos na figura 365, verificando célula a célula até encontrar a chamada 
busca sequencial.
7.4.1 Busca sequencial
A busca sequencial de forma intuitiva realiza uma primeira abordagem para resolver o problema, 
percorrendo o vetor da esquerda para a direita e verificando se o valor buscado foi encontrado. Em 
hipótese afirmativa, é retornado o índice do vetor no qual o elemento foi encontrado.
238
Unidade III
No caso, temos a função que recebe o vetor e o número procurado, além de um laço célula a célula. 
No evento de não localização, é retornado o número 1.
Figura 379 
7.4.2 Busca binária
A busca ou pesquisa binária é realizada em um vetor ordenado. Ela implementa o paradigma 
conhecido como divisão e conquista (divide and conquer). Essa técnica consiste em dividir um 
problema em problemas menores, no nosso caso reduzindo o vetor em pedaços menores, diminuindo a 
área para a busca.
O algoritmo para fazer a busca é:
• Verificar se o elemento que desejamos buscar é igual, menor ou maior que o elemento do 
meio do vetor.
— Se este valor for igual, então encontramos nosso elemento.
— Caso o valor seja menor, ignoramos o resto do vetor que for maior que este valor e buscamos 
somente em sua metade “menor”.
— Caso o valor pesquisado seja maior que o do elemento do meio, ignoramos a metade menor, e 
buscamos somente na metade “maior” do vetor, ou seja, a partir do elemento do meio.
Constam a seguir dois exemplos de busca binária.
Quadro 14– Buscar 37
2 48 8625 6812 57 9237 75
Se este valor for igual, então encontramos nosso elemento. 
37=48 
Caso o valor seja menor, ignoramos o resto do vetor que 
for maior que o valor e buscamos somente em sua metade 
“menor”. 37<48 
239
ESTRUTURAS DE DADOS
2 48 8625 6812 57 9237 75
Se este valor for igual, então encontramos nosso elemento. 
37=25 
Caso o valor seja menor, ignoramos o resto do vetor que 
for maior que o valor e buscamos somente em sua metade 
“menor”. 37<25 
Caso o valor pesquisado seja maior que aquele do elemento 
do meio, ignoramos a metade menor, e buscamos somente 
na metade “maior” do vetor, ou seja, a partir do elemento do 
meio. 37>25 
2 48 8625 6812 57 9237 75
Se este valor for igual, então o elemento foi encontrado. 
37=37 
Quadro 15 – Buscar 86
2 48 8625 6812 57 9237 75
Se este valor for igual, então encontramos nosso elemento. 
86=48 
Caso o valor seja menor, ignoramos o resto do vetor que 
for maior que o valor e buscamos somente em sua metade 
“menor”. 86<48 
Caso o valor pesquisado seja maior que aquele do elemento 
do meio, ignora-se a metade menor, e buscamos somente 
na metade “maior” do vetor, ou seja, a partir do elemento do 
meio. 86>48 
2 48 8625 6812 57 9237 75
Se este valor for igual, então encontramos nosso elemento. 
86=75 
Caso o valor seja menor, ignoramos o resto do vetor que 
seja maior que o valor e buscamos somente em sua metade 
“menor”. 86<75 
Caso o valor pesquisado seja maior que aquele do elemento 
do meio, ignoramos a metade menor, e buscamos somente 
na metade “maior” do vetor, ou seja, a partir do elemento do 
meio. 86>75 
2 48 8625 6812 57 9237 75
Se este valor for igual, então encontramos nosso elemento. 
86=86 
A implementação pode ser feita de duas maneiras, recursiva ou iterativa.
7.4.2.1 Implementação da busca binária recursiva
A busca é feita recursivamente no valor dentro do vetor vet. A cada nova chamada da função 
reduz-se o espaço de busca pela metade, chamando recursivamente o subvetor. Quando encontra o 
valor, retorna o índice no qual foi localizado. Caso contrário, retorna -1.
240
Unidade III
Figura 380 
7.4.2.2 Implementação da busca binária iterativa
A busca é feita iterativamente no valor dentro do vetor vet. A cada iteração do laço reduz-se o 
espaço de busca pela metade. Quando encontra o valor, retorna o índice no qual foi encontrado. Caso 
contrário, retorna -1.
Figura 381 
Consta a seguir a implementação completa:
#include <stdlib.h>
#include <stdio.h>
#define tamanho 10
 /**
 Busca sequencialmente o valor dentro do vetor vet.
 Se encontrar retorna o índice do valor, senão retorna -1.
 */
241
ESTRUTURAS DE DADOS
int buscaSeq(int vet[tamanho], int valor)
{
 for (int i = 0; i < tamanho; i++) {
 if (vet[i] == valor) {
 return i;
 }
 }
 return -1;
}
/*
 Busca recursivamente o valor dentro do vetor vet. A cada iteração
 reduz o espaço de busca pela metade chamando recursivamente o subvetor. 
 Quando encontra o valor retorna o índice onde ele foi encontrado. 
 Caso contrário retorna -1
 */
int buscaBinRec(int vet[tamanho], int inicio, int fim, int valor)
{
 int i = (inicio + fim) / 2;
 if (inicio > fim) {
 return -1;
 }
 if (vet[i] == valor) {
 return i;
 }
 if (vet[i] < valor) {
 return buscaBinRec(vet, i + 1, fim, valor);
 }
 else { // vet[i] > valor
 return buscaBinRec(vet, inicio, i - 1, valor);
 }
}
/**
 * Busca iterativamente o valor dentro do vetor vector. A cada iteração
 * reduz o espaço de busca pela metade sem fazer chamadas recursivas.
 * Ao encontrar o valor retorna seu índice. Caso contrário retorna -1
 */
int buscaBinIte(int vet[tamanho], int valor)
{
 int inicio = 0;
 int fim = tamanho - 1;
 while (inicio <= fim) { /* Condição de parada */
 int i = (inicio + fim) / 2; /* Calcula o meio do subvetor */
 if (vet[i] == valor) { /* Item encontrado */
 return i;
 }
 if (vet[i] < valor) { /* Item está no subvetor à direita */
 inicio = i + 1;
 }
 else { /* vet[i] > valor. Item está no subvetor à esquerda */
 fim = i;
 }
242
Unidade III
 }
 return -1;
}
int main()
{
 int vet[tamanho] = { 2, 12, 25, 37, 48, 57, 68, 75, 86, 92 };
 for (int i = 0; i < tamanho; i++) {
 /* Valor a ser buscado */
 int valor = vet[i];
 /* Testando a busca sequencial */
 printf(“Busca sequencial %d: \t\tposição:%d\n”, valor,
 buscaSeq(vet, valor));
 /* Busca sequencial - recursivo */
 printf(“Busca Binaria recursivo %d: \tposição:%d\n”, valor,
 buscaBinRec(vet, 0, tamanho - 1, valor));
 /* Busca sequencial iterativa */
 printf(“Busca Binaria itetativa %d: \tposição:%d \n”, valor,
 buscaBinIte(vet, valor));
 printf(“\n”);
 }
 return 1;
}
7.5 Ordenação de dados
Em diversas aplicações os dados devem ser armazenados obedecendo a uma determinada ordem. Para 
realizar a busca binária, por exemplo, o vetor necessita estar ordenado. Alguns algoritmos podem explorar a 
ordenação dos dados para operar de maneira mais eficiente, do ponto de vista de desempenho computacional. 
A fim de obter os dados ordenados, existem basicamente duas alternativas: a inserção dos elementos na 
estrutura de dados respeitando a ordenação (dizemos que a ordenação é garantida por construção) ou a 
partir de um conjunto de dados já criado, e aplicando um algoritmo para ordenar seus elementos.
Devido ao seu uso muito frequente, é importante ter à disposiçãoalgoritmos de ordenação (sorting) 
eficientes tanto em termos de tempo (devem ser rápidos) como em termos de espaço (precisam ocupar 
pouca memória durante a execução). Descreveremos os algoritmos de ordenação considerando o 
seguinte cenário:
• A entrada é um vetor cujos elementos precisam ser ordenados.
• A saída é o mesmo vetor com seus elementos na ordem especificada.
• O espaço que pode ser utilizado é apenas aquele do próprio vetor.
Veremos posteriormente alguns dos principais algoritmos e técnicas diversas.
243
ESTRUTURAS DE DADOS
7.5.1 Ordenação por troca BubbleSort (método da bolha)
A ideia básica do BubbleSort é percorrer os dados sequencialmente várias vezes. Em cada passagem 
pelos dados, os elementos são comparados com o seu sucessor. Se os elementos não estiverem ordenados, 
devemos trocá-los de posição. O processo é repetido seguidamente do início ao final do vetor até que o 
vetor fique ordenado. Neste método a ordenação acontece colocando os maiores valores no final do vetor.
Por exemplo:
Vetor inicial
48 8625 1237 257 92
1ª rodada 2ª rodada
48 8625 1237 257 92 37 225 5712 9248 86
48 8625 1237 257 92 37 225 5712 9248 86
57 8625 1237 248 92 48 225 5712 9237 86
37 8625 1257 248 92 12 225 5748 9237 86
37 8625 5712 248 92 12 225 5748 9237 86
37 8625 5712 248 92 12 225 5748 9237 86
37 9225 5712 248 86 12 8625 5748 9237 2
37 225 5712 9248 86 12 8625 5748 9237 2
244
Unidade III
3ª rodada 4ª rodada
12 8625 5748 9237 2 37 8625 248 9212 57
12 8625 5748 9237 2 37 8612 248 9225 57
37 8625 5748 9212 2 37 8612 248 9225 57
37 8625 5748 9212 2 37 8625 5748 9212 2
37 8625 5748 9212 2 37 8625 5748 9212 2
37 8625 248 9212 57 37 8625 248 9212 57
37 8625 248 9212 57 37 8625 248 9212 57
37 8625 248 9212 57 37 8625 248 9212 57
5ª rodada 6ª rodada
37 8625 248 9212 57 37 8612 482 9225 57
37 8612 248 9225 57 37 8612 482 9225 57
37 8612 248 9225 57 37 8625 482 9212 57
245
ESTRUTURAS DE DADOS
37 8612 248 9225 57 2 8612 4837 9225 57
37 8612 482 9225 57 2 8612 4837 9225 57
37 8612 482 9225 57 2 8612 4837 9225 57
37 8612 482 9225 57 2 8612 4837 9225 57
37 8612 482 9225 57 2 8612 4837 9225 57
7ª rodada 8ª rodada
2 8612 4837 9225 57 25 8612 4837 922 57
2 8612 4837 9225 57 25 862 4837 9212 57
25 8612 4837 922 57
25 8612 4837 922 57 25 862 4837 9212 57
 
Figura 382
Consta a seguir o código do BubbleSort:
void BubbleSort(int* v, int tam) {
 int i, j = tam, k;
 int trocou;
 do {
 tam--;
 trocou = 0;
 for (i = 0; i < tam; i++) {
 if (v[i] > v[i + 1]) {
 int aux = 0;
246
Unidade III
 aux = v[i];
 v[i] = v[i + 1];
 v[i + 1] = aux;
 trocou = 1;
 for (k = 0; k < j; k++)
 printf(“%d “, v[k]);
 printf(“\n”);
 }
 }
 } while (trocou);
}
7.5.2 QuickSort (método da troca e partição)
O QuickSort é método de ordenação que utiliza a técnica divide and conquer (dividir o problema inicial 
em dois subproblemas e resolver um problema menor utilizando a recursividade). Trata-se de um dos 
métodos mais rápidos de ordenação, apesar de às vezes partições desequilibradas poderem conduzir a uma 
ordenação lenta. Ele baseia-se na divisão do vetor em dois vetores menores, baseados em um elemento 
chamado pivô, normalmente o primeiro elemento do vetor. Um dos vetores contém os elementos menores 
que o pivô, enquanto o outro possui os maiores. O pivô é colocado entre ambos, ficando na posição média. 
Os dois vetores são ordenados de forma idêntica até que se chegue a um único deles ordenado.
Por exemplo:
6825 48 4837
0 1 2 3 4 5 6 7 8 9 10 11
6 552 51 92 9264 7552
25 48 68 92
1 4 9 11
25 37
0 2 3 4 6 7 9 10 11
2 48 68 9255 7552
pivot pivotpivot pivot
>75<75>37
<64 >64>6
<37
37 4825
0 1 2 3 4 6 7 8 9 10 11
62 52 75 6864 9255
pivot pivotpivot pivot
2 516 4825 55 75 6837 64 92 52
0 1 2 3 4 5 6 7 8 9 10 11
pivot pivot
<51 >51
2 6451 4892 55 75 3768 6 25 52
0 1 2 3 4 5 6 7 8 9 10 11
pivot
Figura 383 – QuickSort: a cada subvetor temos os números 
menores à esquerda do pivot e os maiores à direita
247
ESTRUTURAS DE DADOS
No exemplo anterior os números em azul não estão ordenados. Os números em amarelo são aqueles 
adotados como pivô para o vetor a ser subdividido. Os números em vermelho são aqueles já ordenados. 
O processo de ordenação, como se pode observar, é recursivo.
//Algoritmo de ordenação QuickSort
void QuickSort(int* v, int tam) {
 int j = tam, k;
 if (tam <= 1)
 return;
 else {
 int pivot = v[0];
 int a = 1;
 int b = tam - 1;
 do {
 while ((a < tam) && (v[a] <= pivot))
 a++;
 while (v[b] > pivot)
 b--;
 if (a < b) { // faz troca
 int temp = v[a];
 v[a] = v[b];
 v[b] = temp;
 a++;
 b--;
 }
 for (k = 0; k < j; k++)
 printf(“%d “, v[k]);
 printf(“\n”);
 } while (a <= b);
 // troca pivô
 v[0] = v[b];
 v[b] = pivot;
 // ordena subvetores restantes
 QuickSort(v, b);
 QuickSort(&v[a], tam - a);
 for (k = 0; k < j; k++)
 printf(“%d “, v[k]);
 printf(“\n”);
 }
}
7.5.3 Ordenação por inserção InsertionSort (método da inserção direta)
No método InsertionSort os elementos são inseridos nas suas posições corretas. Elemento a elemento 
são deslocados para posição correta deslocando para trás aqueles que estão em posições incorretas.
Quando o algoritmo é simples:
• O conteúdo da célula é eleito e comparado com o valor da célula anterior.
• Se o valor for maior, a célula anterior ocupa a posição seguinte e a comparação é feita com a 
célula anterior.
248
Unidade III
• Caso o valor anterior seja menor, ou chegou ao início, será a posição correta que a célula escolhida 
deverá ocupar.
• Uma vez localizada a célula eleita, ela passa para o elemento seguinte do vetor.
Por exemplo:
2º elemento 3º elemento 4º elemento
48 8625 1237 257 92 48 8625 1237 257 92 57 8625 1237 248 92
25>57
início 
48 8625 1237 2
57
92
48
8625 1237 257 92
57>48
início 
57 8625 12
37
248 92
57>37
início 
48
8625 1237 257 92
25>48 
início 
57 8625 12
37
248 92
48>37
início 
57 8625 12
37
248 92
25>37
início 
48 8625 1237 257 92 57 8625 1237 248 92 48 8625 1257 237 92
5º elemento 6º elemento 7º elemento
48 8625 1257 237 92 57 863712 24825 92 57 863712 24825 92
57>12
início 
48 8625
12
57 237 92 57 863712 24825
92
57>92
início 
57
86
3712 24825 92
92>86
início 
48>12
início 
48 8625
12
57 237 92 57 923712 24825
86
57>86
início 
37>12
início 
48 8625
12
57 237 92
25>37
início 
48 8625
12
57 237 92
249
ESTRUTURAS DE DADOS
início 
48 8625
12
57 237 92
37 8612 5748 225 92 57 863712 24825 92 57 923712 24825 86
8º elemento
48 925725 23712 86
48 925725
2
3712 86
92>2
início 
48 925725
2
3712 86
86>2
início 
48 925725
2
3712 86
57>2
início 
48 925725
2
3712 86
48>2
início 
48 925725
2
3712 86
37>2
início 
48 925725
2
3712 86
25>2
início 
48 925725
2
3712 86
12>2
início 
48 925725
2
3712 86
início 
37 864812 92252 57
 
Figura 384
250
Unidade III
Consta a seguir o código:
//Algoritmo de ordenação InsertionSort
void InsertionSort(int* v, int tam) {
 int i, j, k, chave;
 for (j = 1; j < tam; j++) {
 chave = v[j];
 i = j - 1;
 while ((i >= 0) && (v[i] > chave)) {
 v[i + 1] = v[i];
 i--;
 }
 v[i + 1] = chave;
 for (k = 0; k < j; k++)
 printf(“%d “, v[k]);
 printf(“\n”);
 }
 for (k = 0; k < j; k++)
 printf(“%d “, v[k]);
 printf(“\n”);
}
7.5.4 BinaryInsertionSort (método da inserção direta binária)
No InsertionSort, conforme a distribuição, pode ser bastante dispendioso chegar até a ordenação. 
Em um vetor contendo valores decrescentes as iterações teriam que percorrer diversas vezes toda a 
extensão dos valores já ordenados. Para otimizar o processo, o Binary Insertion Sort implementa uma 
busca binária a fim de encontrar o local correto para colocar o elemento eleito, ao contrário do Insertion 
Sort que necessita comparar sequencialmente cada célula até chegar na posição correta.
Por exemplo:
Vetor inicial
 37 861257 24825 92
0 1 2 34 5 6 7
2º elemento 3º elemento 4º elemento
37 8612 24825 92
0 1 2 3 4 5 6 757
1
buscaBin (0-0)  1
37 8612 225 92
0 1 2 3 4 5 6 7
57
2
buscaBin (0-1)  1
48
8612 225 92
0 1 2 3 4 5 6 7
48
3
buscaBin (0-2)  2
57
37
48 37 8612 225 92
0 1 2 3 4 5 6 7
1 
57
57 37 8612 225 92
0 1 2 3 4 5 6 748
57 8612 225 92
0 1 2 3 4 5 6 7
48
37
48 37 8612 225 92
0 1 2 3 4 5 6 7
57 57 37 8612 225 92
0 1 2 3 4 5 6 7
48 37 57 8612 225 92
0 1 2 3 4 5 6 7
48
251
ESTRUTURAS DE DADOS
5º elemento 6º elemento 7º elemento
57 86 23725 92
0 1 2 3 4 5 6 7
48
4
buscaBin (0-3)  0
12
37 86 24812
0 1 2 3 4 5 6 7
25
5
buscaBin (0-4)  5
57
92
37 24812
0 1 2 3 4 5 6 7
25
6
buscaBin (0-5)  5
57 92
86
37 86 248 92
0 1 2 3 4 5 6 7
25 57
12
37 86 24812
0 1 2 3 4 5 6 7
25 57
92
37 24812
0 1 2 3 4 5 6 7
25 57
86
92
37 86 248 92
0 1 2 3 4 5 6 7
25 5712 37 86 248 92
0 1 2 3 4 5 6 7
25 5712 37 92 248 86
0 1 2 3 4 5 6 7
25 5712
8º elemento
374812
0 1 2 3 4 5 6 7
25
7
buscaBin (0-6)  0
57 86 92
2
48 86 9225 57
0 1 2 3 4 5 6 7
12 37
2
48 86 9225 57
0 1 2 3 4 5 6 7
12 372
 
Figura 385
Consta a seguir o código da ordenação:
// Busca Binária para achar o local a ser inserido
// no vet[inicio..fim]
int buscaBin(int* vet, int item, int inicio, int fim)
{
 if (fim <= inicio)
 return (item > vet[inicio]) ? (inicio + 1) : inicio;
 int meio = (inicio + fim) / 2;
 if (item == vet[meio])
 return meio + 1;
 if (item > vet[meio])
 return buscaBin(vet, item, meio + 1, fim);
 return buscaBin(vet, item, inicio, meio - 1);
}
//Algoritmo de ordenação SelectionSort
252
Unidade III
void insertionBinSort(int* vet, int tam)
{
 int atual, loc, aux, k, valor;
 for (atual = 1; atual < tam; ++atual)
 {
 aux = atual - 1;
 valor = vet[atual];
 // achar o local onde o valor deve ser inserido
 loc = buscaBin(vet, valor, 0, aux);
 // Move todos os elementos depois do local para abrir espaço
 while (aux >= loc)
 {
 vet[aux + 1] = vet[aux];
 aux--;
 }
 vet[aux + 1] = valor;
 for (int z = 0; z < tam; z++) {
 printf(“%d “, vet[z]);
 if (z == atual)
 printf(“ “);
 }
 printf(“\n”);
 }
}
7.5.5 Ordenação por seleção SelectionSort (método da seleção direta)
O método SelectionSort consiste em encontrar repetidamente o menor elemento e colocá-lo na sua 
devida posição.
Para cada elemento, é necessário:
• Encontrar índice do menor valor no restante do vetor.
• Se o valor do elemento for maior que o menor valor do resto do vetor, é feita a troca entre eles.
Por exemplo:
Vetor Inicial
 37 86 248 92
0 1 2 3 4 5 6 7
57 1225
preenche o elemento do índice 0 preenche o elemento do índice 1 preenche o elemento do índice 2
37 86 248 92
0 1 2 3 4 5 6 7
57 1225
posição atual=0; posição do menor=1
37 86 2548 92
0 1 2 3 4 5 6 7
57 122
posição atual=1; posição do menor=2
37 86 2548 92
0 1 2 3 4 5 6 7
12 572
posição atual=2; posição do menor=3
253
ESTRUTURAS DE DADOS
37 86 248 92
0 1 2 3 4 5 6 7
57 1225
posição atual=0; posição do menor=2
37 86 2548 92
0 1 2 3 4 5 6 7
57 122
posição atual=1; posição do menor=3
37 86 2548 92
0 1 2 3 4 5 6 7
12 572
posição atual=2; posição do menor=3
37 86 248 92
0 1 2 3 4 5 6 7
57 1225
posição atual=0; posição do menor=3
37 86 2548 92
0 1 2 3 4 5 6 7
57 122
posição atual=1; posição do menor=4
37 86 2548 92
0 1 2 3 4 5 6 7
12 572
posição atual=2; posição do menor=3
37 86 248 92
0 1 2 3 4 5 6 7
57 1225
posição atual=0; posição do menor=4
37 86 2548 92
0 1 2 3 4 5 6 7
57 122
posição atual=1; posição do menor=4
37 86 2548 92
0 1 2 3 4 5 6 7
12 572
posição atual=2; posição do menor=3
37 86 248 92
0 1 2 3 4 5 6 7
57 1225
posição atual=0; posição do menor=4
37 86 2548 92
0 1 2 3 4 5 6 7
57 122
posição atual=1; posição do menor=4
37 86 2548 92
0 1 2 3 4 5 6 7
12 572
posição atual=2; posição do menor=7
37 86 248 92
0 1 2 3 4 5 6 7
57 1225
posição atual=0; posição do menor=4
37 86 2548 92
0 1 2 3 4 5 6 7
57 122
posição atual=1; posição do menor=4
37 86 4825 92
0 1 2 3 4 5 6 7
12 572
posição atual > posição do menor 
37 86 248 92
0 1 2 3 4 5 6 7
57 1225
posição atual=0; posição do menor=7
37 86 2548 92
0 1 2 3 4 5 6 7
12 572
posição atual > posição do menor 
37 86 2548 92
0 1 2 3 4 5 6 7
57 122
posição atual > posição do menor 
37 86 2548 92
0 1 2 3 4 5 6 7
57 122 37 86 2548 92
0 1 2 3 4 5 6 7
12 572 37 86 4825 92
0 1 2 3 4 5 6 7
12 572
preenche o elemento do índice 3 preenche o elemento do índice 4 preenche o elemento do índice 5
37 86 4825 92
0 1 2 3 4 5 6 7
12 572
posição atual=3; posição do menor=4
37 86 4825 92
0 1 2 3 4 5 6 7
12 572
posição atual=4; posição do menor=5
37 86 5725 92
0 1 2 3 4 5 6 7
12 482
posição atual=5; posição do menor=6
254
Unidade III
37 86 4825 92
0 1 2 3 4 5 6 7
12 572
posição atual=3; posição do menor=4
37 86 4825 92
0 1 2 3 4 5 6 7
12 572
posição atual=4; posição do menor=6
37 86 5725 92
0 1 2 3 4 5 6 7
12 482
posição atual=5; posição do menor=7
37 86 4825 92
0 1 2 3 4 5 6 7
12 572
posição atual=3; posição do menor=4
37 86 4825 92
0 1 2 3 4 5 6 7
12 572
posição atual=4; posição do menor=7
37 86 9225 57
0 1 2 3 4 5 6 7
12 482
posição atual > posição do menor 
37 86 4825 92
0 1 2 3 4 5 6 7
12 572
posição atual=3; posição do menor=4
37 86 5725 92
0 1 2 3 4 5 6 7
12 482
posição atual > posição do menor 
37 86 4825 92
0 1 2 3 4 5 6 7
12 572
posição atual > posição do menor 
37 86 4825 92
0 1 2 3 4 5 6 7
12 572 37 86 5725 92
0 1 2 3 4 5 6 7
12 482 37 86 9225 57
0 1 2 3 4 5 6 7
12 482
preenche o elemento do índice 6
37 86 9225 57
0 1 2 3 4 5 6 7
12 482
posição atual=6; posição do menor=7
37 86 9225 57
0 1 2 3 4 5 6 7
12 482
posição atual > posição do menor 
37 86 9225 57
0 1 2 3 4 5 6 7
12 482
 
Figura 386
Consta a seguir o código:
 //Algoritmo de ordenação SelectionSort
void SelectionSort(int* v, int tam) {
 int i, j, k, min;
 for (i = 0; i < (tam - 1); i++) {
255
ESTRUTURAS DE DADOS
 min = i;
 for (j = (i + 1); j < tam; j++) {
 if (v[j] < v[min]) {
 min = j;
 }
 }
 if (i != min) {
 int swap = v[i];
 v[i] = v[min];
 v[min] = swap;
 for (k = 0; k < tamanho; k++)
 printf(“%d “, v[k]);
 printf(“\n”);
 }
 }
} 
7.5.6 HeapSort (método da seleção em árvore)
O método de ordenação HeapSort consiste em uma árvore binária completa que obedece às 
seguintes propriedades:
• A raiz de uma árvore com Heap Máximo é sempre o maior valor da estrutura.
— Troque a posição da raiz com o último filho, o último elemento agora é o nó maior valor.
• Refaça o Heap sem o último elemento, pois ele já estará posicionado.
O HeapSort, assim como o SelectionSort, posiciona um a um os elementos no vetor, no caso de trás 
para frente, e utiliza uma técnica que evita percorrer o restante do vetor.
7.5.6.1 Conceito de Heap (ou Heap Binário)
Suas características são as seguintes:
• Uma árvore heap é binária, sendo que sua altura aumenta se todas as folhas de um nível 
estiverem preenchidas.
• O preenchimento é feito da esquerda para a direita.
Um heap pode ser visto como uma árvore binária ou como um vetor unidimensional. Observa-se 
que cada nó da árvore corresponde a um elemento do vetor e vice-versa. Na figura a seguir, as cores são 
correspondentes em ambos.
256
Unidade III
8 9 10
2
5 6
3
7
1
4
1 2 3 4 5 6 7 8 9 10 
1x2
2x2
3x2
4x2
5x2
(3x2)+1
(4x2)+1
(2x2)+1
Figura 387 – Heap-dualidade árvore, vetor
Outra característica é o fato de que exceto a raiz, qualquer posição do vetor obedece à seguinte 
formação:
Considerando i o índice de uma dada célula no vetor:
• i/2 é o pai do índice i.
• 2i é o filho esquerdo de i.
• 2i+1 é o filho direito de i.
Uma árvore chamada de Heap Máximo é aquela na qual o pai de cada nó (exceto a raiz) contém um 
valor maior que o filho.
Exemplo 1
Aplicando a equivalência entre vetor e matriz heap:
257
ESTRUTURAS DE DADOS
49
5
13
10958
4 5 6
1
32
5 951349 108
1 2