Preorder Iterative - Binary Search Tree

Asked

Viewed 132 times

0

I have a function that runs through BST (Binary search Tree) recursive pre-order. The function is the following: 

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 make the iterative version of this function but I can never come to any conclusion. 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 (error included) that I am entering into type conflict.

If anyone can help me understand the resolution of this function iteratively... I’m starting Java and it’s very confusing yet.

IDE ERROR:

'Node cannot 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;
        }
    }

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

  • Add, if possible, the error that the IDE also shows, if it is a warning, print the question.

  • Add the Node class as well, because it is the center of the problem. Also add the Queue class.

  • But add in the role or add in general in the class I’m working in? Because this is provided by the teaching and these two classes are already integrated into the project we have worked on.

  • Do not add code image, add textual form, as you did with others.

  • Good point, thank you!

  • 1

    Iterative is solved as a Queue using a BFS (Breadth First Search) algorithm and without using recursiveness

  • But is it the only way to solve the problem? I can’t take anything from the code I’ve developed for recursion, and somehow turn into its iterative version?

Show 2 more comments

1 answer

0

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

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

But in your class Node, leftand rightare objects of the type Nodeand not the type Key, so you get the type conflict error, the method enqueueexpects an object of the type Key. Try to do queue.enqueue(node.left.key).

Browser other questions tagged java algorithm

You are not signed in. Login or sign up in order to post.