In java programming language Question 1: A Breadth-First Traversal of a Binary T

Question

In java programming language
Question 1: A Breadth-First Traversal of a Binary Tree
You will use a queue to assist you with performing a breadth-first traversal of a binary tree.
The Tree Class
The recommended starting point for this question is Listing 8.1 in Chapter 8 of Lafore.
• Copy the tree.java code (Listing 8.1, page 406-415). Example programs from Lafore are available on the Down-
loads tab at http://www.informit.com/store/data-structures-and-algorithms-in-java-9780672324536.
Be sure to add a credit to the author in the .java file that you will submit.
• Make sure that you understand the methods in the above code, and post on the course discussion forum if you
have any questions.
• Modify the code as appropriate so that the Nodes contain only the integer (key) data field.
• Read through the remainder of this question before proceeding.
A Queue to store Nodes
Create a Queue class where each item stored in the Queue is a Node.
You may choose the underlying implementation for your queue that you think is most appropriate (e.g. linked list
or array). The implementation that you choose should be hidden from a user of the class. That is, the user will
enqueue and dequeue Nodes, and will not know how they are managed inside the queue.
Your queue must have the following methods:
• A constructor that creates an empty queue.
• A boolean isEmpty() method that returns a boolean, indicating whether the queue is empty.
• A boolean enqueue(Node toAdd) method that will insert the given Node into the queue. This method will
return true if the enqueue is successful, and return false if the enqueue fails.
• A Node dequeue() method that will dequeue and return the Node at the front of the queue. This method
removes the returned Node from the queue. This method should return null if the user tries to dequeue from
an empty queue.
• A Node peek() method that returns the Node at the front of the queue. This method does not remove the
returned Node from the queue. This method should return null if the user tries to peek at an empty queue.
A Breadth-First Traversal of the Tree
Code listing 8.1 included three types of depth-first traversals (preorder, inorder, postorder). You will implement a
breadth-first traversal, that prints the data in the Nodes, in the order that you visit each Node.
A breadth-first traversal is one in which all of the nodes on a particular level of the tree are traversed (left to right)
before descending to a lower level of the tree. A queue is used to keep track of the nodes so that they are visited
level-by-level.
The exact details of this method are intentionally not provided and you must use your knowledge of trees and queues
to develop a working algorithm.
In the comments for your breadth-first method, in one paragraph, describe the algorithm you use to
perform the breadth-first traversal.
Some hints:
• The queue is what makes this type of traversal possible.
• You will start by adding the root node of your tree to a queue of nodes.
• You will print the data as Nodes are removed from the queue.
• Note that while the three depth-first traversals are implemented using recursion, you will not use recursion in
this method and the breadth-first traversal will look entirely different.
• If you choose to use a linked list implementation for the queue, be careful when setting references to Nodes in
the list. The nodes in the queue’s linked list will in turn hold nodes from your tree (i.e. you need a second type
of node that holds the tree nodes). Each tree node in your queue must retain its references to its children.
Your Main Class (please name it A3Q1<your last name><your student id>)
Your main method should perform the following:
• Insert 20 random integers (with values between 1 and 999) in a binary search tree.
• Print the tree using a preorder traversal.
• Print the tree using an inorder traversal.
• Print the tree using a postorder traversal.
• Print the tree using a breadth-first traversal.

Explanation / Answer

import java.io.*;

import java.util.*;

// Class BreadFirstSearch definition

class BFS

{

// To store number of vertices

private int vertices;

// To store adjacency Lists of type integer

private LinkedList<Integer> adjacency[];

// Parameterized constructor definition

BFS(int ver)

{

// Assigns number of vertices ver to instance variable

vertices = ver;

// Dynamically allocates memory

adjacency = new LinkedList[ver];

// Loops till number of vertices

for (int c = 0; c < ver; ++c)

adjacency[c] = new LinkedList<Integer>();

}// End of parameterized constructor

// Method to add an edge into the graph

void addEdge(int ver, int wai)

{

adjacency[ver].add(wai);

}// End of method

// Method to display BFS traversal from a given source start

void BFSMethod(int start)

{

// Initially mark all the vertices as not visited(By default set as false)

boolean visited[] = new boolean[vertices];

// Create a queue for BFS

LinkedList<Integer> queueBFS = new LinkedList<Integer>();

// Initially mark the current node as visited and enqueue it

visited[start] = true;

queueBFS.add(start);

// Loops till end of the queue

while (queueBFS.size() != 0)

{

// Dequeue a vertex from queue and print it

start = queueBFS.poll();

System.out.print(start + " ");

// Get all adjacent vertices of the dequeued vertex start

// If a adjacent has not been visited, then mark it visited and enqueue it

Iterator<Integer> c = adjacency[start].listIterator();

// Loops till data found

while (c.hasNext())

{

// Stores the data in num

int num = c.next();

// Checks if not visited

if (!visited[num])

{

// Sets the visited status of num of visited array to true for visited

visited[num] = true;

queueBFS.add(num);

}// End of if condition

}// End of inner while loop

}// End of outer while loop

}// End of method

// main method definition

public static void main(String args[])

{

// Generates Random class object

Random ran = new Random();

// Declares BFS class object with 20 vertices

BFS bfs = new BFS(20);

int w;

// Loops 20 times

for(int r = 0; r < 20; r++)

{

// Creates random wait between 0 to 20

w = ran.nextInt(20 - 0) + 0;

// Adds the edges

bfs.addEdge(r, w);

}// End of for loop

System.out.println("Breadth First Traversal (Starting from vertex 2)");

// Calls the method to traverse from node 2

bfs.BFSMethod(2);

}// End of main method

}// End of class

Sample Output:

Following is Breadth First Traversal (starting from vertex 2)

2 16 10 5 15 11

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.