Estrutura de dados

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());
}
return no;
}

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 e x, 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. Duas
ABBs 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árvores esquerdas 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 =