Estrutura de dados

Disponível somente no TrabalhosFeitos
  • Páginas : 3 (569 palavras )
  • Download(s) : 0
  • Publicado : 28 de março de 2012
Ler documento completo
Amostra do texto
Lista de exercícios – Árvores Binárias de Busca

1 – Escreva versões recursivas de TREE-MINIMUM and TREE-MAXIMUM.

R.: - Mínimo

public No minimoRecursivo(No no){if(no.getFilhoEsq()!=null){
return minimoRecursivo(no.getFilhoEsq());
}
return no;
}

- Máximo

public No maximoRecursivo(No no){
if(no.getFilhoDir()!=null){
return maximoRecursivo(no.getFilhoDir());
}
returnno;
}

2 – Escreva o procedimento TREE-PREDECESSOR.

R.: public No predecessor(No no){
if(no.getFilhoEsq()!=null){
return maximoRecursivo(no.getFilhoEsq());
}
No y = no.getPai();while(y!=null && no == y.getFilhoEsq()){
no = y;
y = y.getPai();
}
return y;
}

3 – Escreva a versão recursive do procedimento TREE-INSERT.

R.: (Para facilitar, uma versão recursiva.)public void inserirRec(ArvoreBusca a, No z){
No y = null;
No x = a.raiz();
if(x!=null){
y = x;
if(z.getElemento()<x.getElemento()){
inserirRec(a, x.getFilhoEsq());
}
else{
inserirRec(a,x.getFilhoDir());
}
}
z.setPai(y);
if(y==null)
a.addRaiz(z);
else if(z.getElemento()<y.getElemento())
y.setFilhoEsq(z);
else
y.setFilhoDir(z);
}

4 – A operação de deleção écomutativa, no sentido de que deletar x então y de uma ABB
leva à mesma árvore deletando y e depois x? Justifique sua resposta ou dê um contra-
exemplo.

R.: Não há diferença em deletar x e y ou y ex, pois o sucessor
de x ou y é deslocado para a posição correta, mantendo a estrutura da
árvore.

5 - Faça uma sub-rotina para verificar se duas árvores binárias de busca são similares. DuasABBs são SIMILARES se possuem a mesma distribuição de nós (independente dos valores
nos mesmos). Em uma definição mais formal, duas ABBs são SIMILARES se são ambas
vazias, ou se suas subárvoresesquerdas são similares e suas subárvores direitas também são
similares.

R.: public void similar(ArvoreBusca a, ArvoreBusca b){
No raiz1 = a.raiz();
No raiz2 = b.raiz();

int cEsq1 =...
tracking img