Árvore Binária de
Busca
Estrutura de Dados II
Prof. Gale
Árvores Conceitos
Existem alguns conceitos que são comuns a todos os tipos
de árvores. Eis alguns desses conceitos que devemos
conhecer:










Nó: item de informação com ramos para outros nós (descendentes).
Grau: número de sub-árvores de um nó.
Folhas: nós terminais (grau = 0).
Filhos de um nó: raízes das sub-árvores desse nó.
Pai: ancestral direto de um nó.
Grau de uma árvore: grau máximo dos nós da árvore.
Ancestral de um nó: todos os nós a partir da raiz até o pai do nó.
Descendentes de um nó: todos os nós nas sub-árvores de um nó.
Nível de um nó:Raiz tem nível 1. Nó no nível i, seus filhos estão no
nível i+1
Altura/profundidade de uma árvore: nível maior considerando
qualquer nó da árvore.
Árvores binárias
– árvore binária balanceada:
• os nós internos têm todos,
ou quase todos, 2 filhos
• qualquer nó pode ser
alcançado a partir da raiz em
O(log n) passos
Árvore Binária

É um conjunto finito de nós que pode ser vazio ou
consistir de uma raiz e duas árvores binárias disjuntas
chamadas sub-árvore esquerda e direita.
Fazendo Relação...
“Nó Lista Ligada” X
X “Nó de uma Árvore Binária”
Ilustrando, ficaria...
Árvore Binária de Busca
Árvores binárias de busca
– o valor associado à raiz é sempre maior que o
valor associado a qualquer nó da sub-árvore à
esquerda (sae)
– o valor associado à raiz é sempre menor ou igual
(para permitir repetições) que o valor associado a
qualquer nó da sub-árvore à direita (sad)
– quando a árvore é percorrida em ordem simétrica
(sae - raiz - sad), os valores são encontrados em
ordem não decrescente
Inserção de Nós
Outra inserção...
Nova Inserção...
E por fim...
Tipo árvore binária
– árvore é representada pelo ponteiro
para o nó raiz
struct arv
{
int info;
struct arv* esq;
struct arv* dir;
};
typedef struct arv Arv;
Operação de criação:
– árvore vazia representada por NULL
Arv* abb_cria (void)
{
return NULL;
}
Operação de impressão:
– imprime os valores da árvore em ordem
crescente, percorrendo os nós em ordem
simétrica
void abb_imprime (Arv* a)
{
if (a != NULL)
{
abb_imprime(a->esq);
printf("%d\n",a->info);
abb_imprime(a->dir);
}
}
Pesquisa em árvores binárias
de busca
– compare o valor dado com o
valor associado à raiz
– se for igual, o valor foi
encontrado
– se for menor, a busca
continua na sae
– se for maior, a busca continua
na sad
Operação de busca:
– explora a propriedade de ordenação da árvore
– possui desempenho computacional proporcional à
altura (O(log n) para o caso de árvore
balanceada)
Arv* abb_busca (Arv* r, int v)
{
if (r == NULL) return NULL;
else if (r->info > v) return abb_busca (r->esq,
v);
else if (r->info < v) return abb_busca (r->dir,
v);
else return r;
}
Operação de inserção:
– recebe um valor v a ser inserido
– retorna o eventual novo nó raiz da (sub- árvore)
– para adicionar v na posição correta, faça:
se a (sub-)árvore for vazia
– crie uma árvore cuja raiz contém v
• se a (sub-)árvore não for vazia
– compare v com o valor na raiz
– insira v na sae ou na sad, conforme o resultado
da comparação

Operação de remoção:
– recebe um valor v a ser inserido
– retorna a eventual nova raiz da árvore
– para remover v, faça:
• se a árvore for vazia
– nada tem que ser feito
• se a árvore não for vazia
– compare o valor armazenado no nó raiz com v
– se for maior que v, retire o elemento da subárvore à esquerda
– se for menor do que v, retire o elemento da
sub-árvore à direita
– se for igual a v, retire a raiz da árvore
Operação de remoção (cont.):
– para retirar a raiz da árvore, há 3
casos:
• caso 1: a raiz que é folha
• caso 2: a raiz a ser retirada possui
um único filho
• caso 3: a raiz a ser retirada tem dois
filhos
Exercícios
1.) Desenvolva um programa em “C” que crie uma árvore e
insira dados nesta árvore.
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
// definindo a estrutura da arvore
struct arv {
int info;
struct arv* esq;
struct arv* dir;
};
typedef struct arv Arv;
// Criação da árvore
Arv* abb_cria (void)
{
return NULL;
}
// Inserção de um nó
Arv* abb_insere (Arv* a, int v)
{
if (a==NULL)
{
a = (Arv*)malloc(sizeof(Arv));
a->info = v;
a->esq = a->dir = NULL;
}
else
if (v < a->info)
a->esq = abb_insere(a->esq,v);
else /* v > a->info */
a->dir = abb_insere(a->dir,v);
return a;
}
int main()
{
Arv* arvore;
arvore = abb_cria();
arvore
arvore
arvore
arvore
arvore
}
=
=
=
=
=
abb_insere(arvore,5);
abb_insere(arvore,7);
abb_insere(arvore,2);
abb_insere(arvore,11);
abb_insere(arvore,13);
getch();
return 0;
E a impressão??? A Visualização dos dados...???
Função de Impressão
// impressão dos dados da árvore
void abb_imprime (Arv* a)
{
if (a != NULL)
{
abb_imprime(a->esq);
printf("%d\n",a->info);
abb_imprime(a->dir);
}
}
Exercícios Propostos

Exercicio 1 - Gere uma arvore de 20
nós com valores aleatórios de 0 a
100 e mostre a arvore e os
endereços na tela
Exercícios Propostos
Exercicio 2 - Implemente uma função
que retorne a quantidade de folhas
de uma árvore binária. Essa função
deve obedecer ao protótipo:
// int folhas (Arv* a)
Exercícios Propostos
Exercicio 3 - Implemente uma função
que compare se duas árvores
binárias são iguais. Essa função deve
obedecer ao protótipo:
// Arv* igual (Arv* a, Arv* b)