Iterative PreOrder - Binary Search Tree

0

I have a function that traverses BST ( binary search tree) in pre-order recursively. The function is as follows:

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
        }
    }

I'm trying to figure out how to do the iterative version of this function but I can never come to any conclusions. When in this part of the code

preOrder(queue,node.left); //Visitar a sub-árvore esquerda
preOrder(queue,node.right); //Visitar a sub-árvore direita

I try to write something like this:

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

The IDE warns me (with error included) that I'm getting into type conflict.

If someone can help me figure out the resolution of this function iteratively ... I'm starting Java and it's pretty confusing.

IDE ERROR:

'Node can not be converted to Key type'

Node Class

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;
        }
    }

Queue class

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;
    }
    
asked by anonymous 10.04.2018 / 13:00

1 answer

0

It seems like the problem is this, note that in its original function you make a queue.enqueue(node.key) call but for the iterative method you are trying to do

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

But in its class Node , left and right are objects of type Node and not type Key , so you get type conflict error, enqueue wait method an object of type Key . Try to queue.enqueue(node.left.key) .

    
08.05.2018 / 15:39