OI PESSOAL EU ESTOU A TENTAR FAZER UM ITERADOR QUE PERCORRE A MINHA ARVORE BINARIA
EM PREORDER
A SEGUIR APRESENTO O ITERADOR INORDER :
A MINHA DUVIDA E:"COMO FAZER UM METODO PREDECESSOR() QUE DEVOLVE O MEU SUCESSOR PREORDER.ISTO E UM METODO COMO O SUCESSOR() QUE APRESENTO MAIS ABAIXO
EU JA ESTOU A FAZER O PREDECESSOR MAS ESTOU A ENCARRAR DIFICULDADES:
EIS O PREDECESSOR()
private BSTNodo predecessor (BSTNodo umNo)
{
if (umNo == null) return null;
else if (umNo.left != null) return p;
else if(umNo.left==null&&umNo.pai.right!=null) return umNo.pai.right;
else...............................................................................
…
…aqui comeca o problema;
ESTE ITERADOR ESTA A CORRER SEM PROBLEMA MAS E INORDER
// iterador inorder privado inorder da classe BST
private class TreeIterator implements Iterator
{
private BSTNodo ultDevolv = null;
private BSTNodo next;
// construtor do iterador
// Inicializa o iterador colocando-o a pontar
// para o menor Nodo da BST
private TreeIterator()
{
next = raiz;
if (next != null)
while (next.left != null)
next = next.left;
}// fim do construtor
// Retorna true se ha um elemento na BST
// a frente da actual posicao do Iterador
// de contrario devolve false
public boolean hasNext()
{ return next != null;
} // fim do metodo hasNext
// Retorna o elemento seguinte
// a actual posicao do iterador
public Object next()
{
ultDevolv= next;
next = sucessor(next);
return ultDevolv.elem;
} // fim do metodo next
// Se o ultimo elemento devolvido pelo Iterador
// ainda estiver na BST
// remove-o da estrutura
public void remove()
{
System.out.println(" remove no iterador foi desactivado");
} // fim do metodo remove
} // fim da classe TreeIterator
//METODO SUCESSOR()
//sucessor Inorder
// Se p possui um sucessor, retorna o endereco do nodo
// de contrario devolve null
private BSTNodo sucessor (BSTNodo umNo)
{
if (umNo == null) return null;
else if (umNo.right != null)
{ // successor e leftmost de BSTNodo
// na subarvore direita de umNo
BSTNodo p = umNo.right;
while (p.left != null)
p = p.left;
return p;
} // umNo tem um filho a direita
else
{
// subir a esquerda e depois a direita
BSTNodo p = umNo.pai;
BSTNodo ch = umNo;
while (p != null && ch == p.right)
{ ch = p;
p = p.pai;
} // while
return p;
} // umNo nao tem filho a direita
} // fim do metodo sucessor
ABRACOS
