0

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;
    }
7
  • Adicione, se possivel, o erro que a IDE mostra tambem, se for um aviso, poste um print na pergunta.
    – user28595
    Commented 10/04/2018 às 11:01
  • Adicione a classe Node tambem, pois ela é o centro do problema. Tambem adicione a classe Queue.
    – user28595
    Commented 10/04/2018 às 11:12
  • Mas adicionar na função ou adicionar em geral na classe em que estou a trabalhar? Porque isto é fornecido pelo ensino e essas duas classes já são integradas no projeto sobre o qual trabalhámos.
    – João
    Commented 10/04/2018 às 11:13
  • Não adicione imagem de codigo, adicione de forma textual, como fez com os outros.
    – user28595
    Commented 10/04/2018 às 11:24
  • 1
    Iterativo é resolvido como uma Queue utilizando um algoritmo BFS (Breadth First Search) e sem utilizar recursividade
    – Isac
    Commented 10/04/2018 às 11:32

1 Resposta 1

0

Parace que o problema é o seguinte,note que, na sua função original, você faz uma chamada queue.enqueue(node.key) mas para o método iterativo você está tentando fazer

queue.enqueue(node.left);
queue.enqueue(node.right);

Mas na sua classe Node, lefte rightsão objetos do tipo Nodee não do tipo Key, por isso você recebe o erro de conflito de tipos, o método enqueueespera um objeto do tipo Key. Tente fazer queue.enqueue(node.left.key).

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .