Tenho uma função que percorre a BST (binary search tree) em pré-ordem de forma recursiva. A função é a seguinte:
public Iterable<Key> preOrder()
{
Queue<Key> queue = new Queue<Key>();
preOrder(queue,root);
return queue;
}
//Criação do método para a verificação pretendida. Método recursivo
private void preOrder(Queue<Key> queue,Node node)
{
if(node != null)
{
queue.enqueue(node.key); //Visitar o nó
preOrder(queue,node.left); //Visitar a sub-árvore esquerda
preOrder(queue,node.right); //Visitar a sub-árvore direita
}
}
Estou a tentar perceber como fazer a versão iterativa dessa função mas nunca consigo chegar a nenhuma conclusão. Quando nesta parte do código
preOrder(queue,node.left); //Visitar a sub-árvore esquerda
preOrder(queue,node.right); //Visitar a sub-árvore direita
Tento escrever algo deste género:
queue.enqueue(node.left);
queue.enqueue(node.right);
O IDE avisa-me (com erro inclusive) que estou a entrar em conflito de tipos.
Se alguém me conseguir ajudar a perceber a resolução desta função de forma iterativa... estou a iniciar Java e fica bem confuso ainda.
ERRO IDE:
'Node não pode ser convertido para tipo Key'
Classe Node
private class Node {
private Key key; // sorted by key
private Value val; // associated data
private Node left, right; // left and right subtrees
private int size; // number of nodes in subtree
public Node(Key key, Value val, int size) {
this.key = key;
this.val = val;
this.size = size;
}
}
Classe Queue
public class Queue<Item> implements Iterable<Item> {
private Node<Item> first; // beginning of queue
private Node<Item> last; // end of queue
private int n; // number of elements on queue
// helper linked list class
private static class Node<Item> {
private Item item;
private Node<Item> next;
}