Árvores Binárias: Estrutura e Operações

Prévia do material em texto

Estrutura de Dados
AULA 7
Árvores
Estrutura de Dados
UNIP - Ciência da Computação e Sistemas de Informação
• A estrutura de dados de árvores é bastante utilizada 
quando um ou mais dos seguintes itens é importante: 
acesso direto e seqüencial eficientes; facilidade de 
inserção e remoção de elementos; boa taxa de 
utilização de memória; e utilização de memória 
primária e secundária.
• As árvores são desenvolvidas utilizando-se os 
conceitos da lista ligada e recursão.
Árvores
• A árvore é uma estrutura de dados bidimensional, não 
linear, utilizada na programação de computadores que 
se compõem de nós e arcos. 
• Essas árvores são representadas de cima para baixo 
com a raiz no topo e as folhas na base, diferente das 
árvores naturais. 
• A raiz é um nó que não possui pai, ou seja, outros nós 
acima dele e as folhas são nós que não possuem 
filhos, ou seja, nós abaixo delas, ou melhor, só 
possuem filhos nulos
Árvores
• Podemos dizer que, de modo geral, uma árvore 
possui as seguintes características:
– nó raiz - é o primeiro nó da árvore e que fica acima de qualquer outro 
nó. Todos os outros nós são descendentes deste nó. Existe somente 
um nó raiz em qualquer estrutura de árvore;
– nó folha - é o último nó da árvore e, por isso, ele não possui 
descendentes. Pode existir mais do que uma nó folha;
– nó interior - é o nó que está no interior da árvore. Este nó possui 
descendentes e ascendentes e não pode ser o nó raiz e nem o nó 
folha;
– trajetória - é o número de nós que possui entre um nó e outro;
– grau do nó - é o número de descendentes que um nó possui. Também 
pode ser definido como o número de subárvores que um nó possui;
– altura da árvore - é o número máximo de níveis que podem ter os nós 
da árvore; e
– altura do nó - é o número máximo de níveis que podem ter os 
descendentes desse nó, inclusive com este nó.
Árvores
• Uma árvore binária pode estar vazia ou pode ser 
composta de três partes: o nó raiz, a subárvore à 
direita do nó raiz e a subárvore à esquerda do nó raiz. 
Essas partes também são árvores binárias. Uma sub 
árvore binária também pode estar vazia. Cada 
elemento da árvore binária é o que chamamos de nó 
e cada ligação de um nó para outro é o que 
chamamos de arco. 
Árvores Binárias
• Para exemplificar o funcionamento de uma árvore 
binária, vamos representar uma árvore binária de 
letras, de acordo com a regra (recursiva): "todo 
elemento à esquerda é menor que a raiz, todo 
elemento à direita é maior ou igual à raiz".
• Uma árvore binária com essa propriedade é chamada 
árvore de busca binária.
Árvores Binárias
• Inicialmente, esta árvore binária está vazia, ou seja, 
não existe elementos na árvore binária, portanto, a 
raiz da árvore binária é nula, conforme mostra a figura 
abaixo:
Árvores Binárias
• Vamos, então, inserir a letra E na árvore binária, em 
seguida inserir a letra A, depois a letra U, e, por 
último, a letra O, conforme a seqüência abaixo. 
• Perceba que o tamanho da árvore binária muda, 
dependendo do nível em que a letra é inserida:
Árvores Binárias
• Se quisermos remover um elemento da árvore binária, 
podemos remover qualquer elemento que esteja na 
árvore binária, por exemplo, vamos remover a letra U, 
observando a figura abaixo:
Árvores Binárias
• Uma propriedade fundamental de qualquer árvore 
binária é a de que existe um único caminho de sua 
raiz para qualquer nó. 
• Assim, podemos considerar que a altura de uma 
árvore binária é o comprimento do caminho mais 
longo que pode ter determinada árvore binária. 
Árvores Binárias
• Assim, por exemplo, uma árvore binária com um único 
nó, a raiz, tem altura igual a zero; uma árvore binária 
com dois nós, um nó raiz e um nó folha, tem altura 
igual a 1; e assim por diante. A árvore binária da figura 
abaixo tem altura igual a 3.
Árvores Binárias
• Podemos separar uma árvore binária em níveis. O 
nível zero é o nível no qual se encontra o nó raiz. O 
nível 1 é o nível no qual estão os nós abaixo do nó 
raiz e assim por diante, conforme mostra a figura 
abaixo. 
A Árvore Binária Completa e o seu Número de Nós
• Uma árvore binária é considerada completa se todo 
nó possuir uma subárvore binária à esquerda e outra 
à direita, com exceção de todos os nós folhas, que 
devem estar no mesmo nível.
• Observando a figura perceba que, no nível 1, a árvore 
binária possui 2 = 21 nós, no nível 2 a árvore binária 
possui 4 = 22 nós, no nível 3 a árvore binária possui 8 
= 23 nós, e assim por diante, até que, no nível n, a 
árvore binária possua 2n nós. Assim, considerando 
também o nó raiz, uma árvore binária completa possui 
20 + 21 + 22 + 23 + ... + 2n nós. 
A Árvore Binária Completa e o seu Número de Nós
• inserir - a operação de inserir insere um elemento na 
árvore binária;
• remover - a operação de remover exclui um elemento 
da árvore binária.
• retornaRaiz – a operação para devolver o elemento 
da raiz.
Operações em Árvores Binárias
Métodos em Árvores Binárias
class BIntNo{
int valor;
BIntNo esq, dir;
BIntNo(int novoValor){
valor = novoValor;
}
}
class ArvoreBinaria {
private BIntNo raiz;
public int retornaRaiz () {
return raiz.valor;
}
Métodos em Árvores Binárias
private BIntNo inserir(BIntNo arvore, int novoNo) {
if (arvore == null) {
return new BIntNo(novoNo);
} else {
if (novoNo < arvore.valor) {
arvore.esq = inserir(arvore.esq, novoNo);
} else {
arvore.dir = inserir(arvore.dir, novoNo);
}
}
return arvore;
}
public void inserir(int novoValor) {
raiz = inserir(raiz, novoValor);
}
Métodos em Árvores Binárias
public void excluirNo(int item) {
BIntNo tempNo, pai, filho, temp;
tempNo = raiz;
pai = null;
filho = raiz;
while (tempNo != null && tempNo.valor != item) {
pai = tempNo;
if (item < tempNo.valor) {
tempNo = tempNo.esq;
} else {
tempNo = tempNo.dir;
}
}
Métodos em Árvores Binárias
if (tempNo == null) {
System.out.println("item não localizado!");
}
if (pai == null) { // significa que estamos excluindo a raiz
if (tempNo.dir == null) {
Raiz = tempNo.esq;
} else {
if (tempNo.esq == null) {
Raiz = tempNo.dir;
} else {
for (temp = tempNo, filho = tempNo.esq; 
filho.dir != null;
temp = filho, filho = filho.dir);
if (filho != tempNo.esq) {
temp.dir = filho.esq;
filho.esq = Raiz.esq;
}
filho.dir = Raiz.dir;
Raiz = filho;
}
}
Métodos em Árvores Binárias
} else { // não estamos excluindo a raiz
if (tempNo.dir == null) {
if (pai.esq == tempNo) {
pai.esq = tempNo.esq;
} else {
pai.dir = tempNo.esq;
}
} else {
if (tempNo == null) {
if (pai.esq == tempNo) {
pai.esq = tempNo.dir;
} else {
pai.dir = tempNo.dir;
}
} else {
Métodos em Árvores Binárias
} else {
for (temp = tempNo, filho = tempNo.esq;
filho.dir != null;
temp = filho, filho = filho.dir);
if (filho != tempNo.esq) {
temp.dir = filho.esq;
filho.esq = tempNo.esq;
}
filho.dir = tempNo.dir;
if (pai.esq == tempNo) {
pai.esq = filho;
} else {
pai.dir = filho;
}
}
}
}
}
• Exercício: inserir os seguintes elementos em uma 
árvore binária:
• 10, 20, 8, 2, 1, 15, 30, 18, 9, 3, 6, 5, 4
Árvores Binárias
10
20
15 30
18
8
92
3
6
5
4
1
Árvores Binárias
• Exercício: remover o elemento 8 da árvore anterior
Árvores Binárias
• Outra operação comum é percorrer uma árvore 
binária 
• Uma árvore não tem uma ordem natural a ser 
percorrida. Desse modo, alguns métodos de percorrer 
são definidos, e iremos analisar três desses métodos. 
Todos os métodos sãopercorridos de forma recursiva, 
de modo que percorrer uma árvore binária envolve 
visitar a raiz e percorrer suas subárvores esquerda e 
direita. A diferença entre os métodos é a ordem na 
qual essas operações são efetuadas
Operações em Árvores Binárias
• Pré-ordem (ou percurso em profundidade)
Visitamos (e processamos) a raiz
Percorremos a subárvore esquerda em pré-ordem
Percorremos a subárvore direita em pré-ordem
• Em ordem (ou ordem simétrica)
Percorremos a subárvore esquerda em ordem simétrica
Visitamos (e processamos) a raiz
Percorremos a subárvore direita em ordem simétrica
• Pós-ordem 
Percorremos a subárvore esquerda em pós-ordem
Percorremos a subárvore direita em pós-ordem
Visitamos (e processamos) a raiz
Operações em Árvores Binárias
• Exercício: implementar os métodos abaixo
– public void imprimePreOrdem();
– public void imprimeEmOrdem();
– public void imprimePosOrdem();
Árvores Binárias
public void imprimePreOrdem() {
imprimePreOrdem(Raiz);
System.out.println();
}
private void imprimePreOrdem(BIntNo no) {
if (no != null) {
System.out.print(no.valor + " ");
imprimePreOrdem(no.esq);
imprimePreOrdem(no.dir);
}
}
Árvores Binárias
public void imprimeEmOrdem() {
imprimeEmOrdem(Raiz);
System.out.println();
}
private void imprimeEmOrdem(BIntNo no) {
if (no != null) {
imprimeEmOrdem(no.esq);
System.out.print(no.valor + " ");
imprimeEmOrdem(no.dir);
}
}
Árvores Binárias
public void imprimePosOrdem() {
imprimePosOrdem(Raiz);
System.out.println();
}
private void imprimePosOrdem(BIntNo no) {
if (no != null) {
imprimePosOrdem(no.esq);
imprimePosOrdem(no.dir);
System.out.print(no.valor + " ");
}
}
Árvores Binárias
• Exercício: percorrer a árvore abaixo em
– Pré-Ordem
– Em Ordem
– Pós Ordem
Árvores Binárias
10
20
15 30
18
8
92
3
6
5
4
1
• Exercício: percorrer a árvore abaixo em
– Pré-Ordem: 10 8 2 1 3 6 5 4 9 20 15 18 30
– Em Ordem: 1 2 3 4 5 6 8 9 10 15 18 20 30
– Pós Ordem: 1 4 5 6 3 2 9 8 18 15 30 20 10 
Árvores Binárias
Solução