Question 1: A Breadth-First Traversal of a Binary Tree You will use a queue to a
ID: 3911524 • Letter: Q
Question
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://vww. intormit.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 undenstand the methods in the above code, and post on the course discusion 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 quene must have the following methods: . A constructor that creates an empty quee . A boolean isEmpty) method that returns a boolean, indicating whether the queue is emptyExplanation / Answer
Answer 1.)
The first questions asks us basically to take a tree and print all types (level order or bredth-first, postorder and preorder) of traversals of a binary tree. First of all, let us revise these 3 concepts.
Bredth-first traversal or level order traversal - In this type of traversal, the nodes are traversed according to their depths, i.e., the nodes at height 1 are traversed before node of height 2 and nodes of height 2 are traversed before nodes of height 3 and so on.
Postorder traversal - In this type of traversal the left subtree is traversed then the right subtree and then the node itself.
Preorder traversal - The root is traversed then the left subtree and then the right subtree.
So now coming to the question. The initial code has to be from the book Data Structures and algorithms by Lafore according to the question. So we take the template code from that book and modify it for bredth-first traversal.
In this code first of all the root is inserted in the queue. Now, while the queue is not empty, the front is dequeued and its child are inserted into the queue after visiting that node. Thus the nodes are traversed according to their depths.
The final code for first question is -
// tree.java
// demonstrates binary tree
// to run this program: C>java TreeApp
import java.io.*;
import java.util.*; // for Stack class
////////////////////////////////////////////////////////////////
class Node
{
public int iData; // data item (key)
public Node leftChild; // this node's left child
public Node rightChild; // this node's right child
public void displayNode() // display ourself
{
System.out.print(iData);
System.out.print(", ");
}
} // end class Node
////////////////////////////////////////////////////////////////
class MyQueue<T> // Making it generic and immutable so that it can be used for all cases
{
private List<T> Q = null;
public MyQueue() {
this.Q = new LinkedList<T>();
}
public Boolean enqueue(T newItem) {
if(Q.add(newItem))
return true;
return false;
}
public T dequeue() {
//List<T> copyQ = new LinkedList<T>(this.Q);
T x = Q.get(0);
Q.remove(0);
return x;
}
public T peek() {
return this.Q.get(0);
}
public int size() {
return this.Q.size();
}
public boolean isEmpty() {
return this.Q.size() == 0;
}
}
class Tree
{
private Node root; // first node of tree
// -------------------------------------------------------------
public Tree() // constructor
{ root = null; } // no nodes in tree yet
// -------------------------------------------------------------
public Node find(int key) // find node with given key
{ // (assumes non-empty tree)
Node current = root; // start at root
while(current.iData != key) // while no match,
{
if(key < current.iData) // go left?
current = current.leftChild;
else // or go right?
current = current.rightChild;
if(current == null) // if no child,
return null; // didn't find it
}
return current; // found it
} // end find()
// -------------------------------------------------------------
public void insert(int id)
{
Node newNode = new Node(); // make new node
newNode.iData = id;
if(root==null) // no node in root
root = newNode;
else // root occupied
{
Node current = root; // start at root
Node parent;
while(true) // (exits internally)
{
parent = current;
if(id < current.iData) // go left?
{
current = current.leftChild;
if(current == null) // if end of the line,
{ // insert on left
parent.leftChild = newNode;
return;
}
} // end if go left
else // or go right?
{
current = current.rightChild;
if(current == null) // if end of the line
{ // insert on right
parent.rightChild = newNode;
return;
}
} // end else go right
} // end while
} // end else not root
} // end insert()
// -------------------------------------------------------------
public boolean delete(int key) // delete node with given key
{ // (assumes non-empty list)
Node current = root;
Node parent = root;
boolean isLeftChild = true;
while(current.iData != key) // search for node
{
parent = current;
if(key < current.iData) // go left?
{
isLeftChild = true;
current = current.leftChild;
}
else // or go right?
{
isLeftChild = false;
current = current.rightChild;
}
if(current == null) // end of the line,
return false; // didn't find it
} // end while
// found node to delete
// if no children, simply delete it
if(current.leftChild==null &&
current.rightChild==null)
{
if(current == root) // if root,
root = null; // tree is empty
else if(isLeftChild)
parent.leftChild = null; // disconnect
else // from parent
parent.rightChild = null;
}
// if no right child, replace with left subtree
else if(current.rightChild==null)
if(current == root)
root = current.leftChild;
else if(isLeftChild)
parent.leftChild = current.leftChild;
else
parent.rightChild = current.leftChild;
// if no left child, replace with right subtree
else if(current.leftChild==null)
if(current == root)
root = current.rightChild;
else if(isLeftChild)
parent.leftChild = current.rightChild;
else
parent.rightChild = current.rightChild;
else // two children, so replace with inorder successor
{
// get successor of node to delete (current)
Node successor = getSuccessor(current);
// connect parent of current to successor instead
if(current == root)
root = successor;
else if(isLeftChild)
parent.leftChild = successor;
else
parent.rightChild = successor;
// connect successor to current's left child
successor.leftChild = current.leftChild;
} // end else two children
// (successor cannot have a left child)
return true; // success
} // end delete()
// -------------------------------------------------------------
// returns node with next-highest value after delNode
// goes to right child, then right child's left descendents
private Node getSuccessor(Node delNode)
{
Node successorParent = delNode;
Node successor = delNode;
Node current = delNode.rightChild; // go to right child
while(current != null) // until no more
{ // left children,
successorParent = successor;
successor = current;
current = current.leftChild; // go to left child
}
// if successor not
if(successor != delNode.rightChild) // right child,
{ // make connections
successorParent.leftChild = successor.rightChild;
successor.rightChild = delNode.rightChild;
}
return successor;
}
// -------------------------------------------------------------
public void traverse(int traverseType)
{
switch(traverseType)
{
case 1: System.out.print(" Preorder traversal: ");
preOrder(root);
break;
case 2: System.out.print(" Inorder traversal: ");
inOrder(root);
break;
case 3: System.out.print(" Postorder traversal: ");
postOrder(root);
break;
case 4: System.out.print(" Bredthfirst traversal: ");
bfs(root);
break;
}
System.out.println();
}
// -------------------------------------------------------------
private void bfs(Node localRoot)
{
MyQueue<Node> q = new MyQueue<Node>();
q.enqueue(localRoot);
while(!q.isEmpty())
{
Node x = (Node)q.dequeue();
System.out.print(x.iData + " ");
if(x.leftChild != null)
q.enqueue(x.leftChild);
if(x.rightChild != null)
q.enqueue(x.rightChild);
}
}
private void preOrder(Node localRoot)
{
if(localRoot != null)
{
System.out.print(localRoot.iData + " ");
preOrder(localRoot.leftChild);
preOrder(localRoot.rightChild);
}
}
// -------------------------------------------------------------
private void inOrder(Node localRoot)
{
if(localRoot != null)
{
inOrder(localRoot.leftChild);
System.out.print(localRoot.iData + " ");
inOrder(localRoot.rightChild);
}
}
// -------------------------------------------------------------
private void postOrder(Node localRoot)
{
if(localRoot != null)
{
postOrder(localRoot.leftChild);
postOrder(localRoot.rightChild);
System.out.print(localRoot.iData + " ");
}
}
// -------------------------------------------------------------
public void displayTree()
{
Stack globalStack = new Stack();
globalStack.push(root);
int nBlanks = 32;
boolean isRowEmpty = false;
System.out.println(
"......................................................");
while(isRowEmpty==false)
{
Stack localStack = new Stack();
isRowEmpty = true;
for(int j=0; j<nBlanks; j++)
System.out.print(' ');
while(globalStack.isEmpty()==false)
{
Node temp = (Node)globalStack.pop();
if(temp != null)
{
System.out.print(temp.iData);
localStack.push(temp.leftChild);
localStack.push(temp.rightChild);
if(temp.leftChild != null ||
temp.rightChild != null)
isRowEmpty = false;
}
else
{
System.out.print("--");
localStack.push(null);
localStack.push(null);
}
for(int j=0; j<nBlanks*2-2; j++)
System.out.print(' ');
} // end while globalStack not empty
System.out.println();
nBlanks /= 2;
while(localStack.isEmpty()==false)
globalStack.push( localStack.pop() );
} // end while isRowEmpty is false
System.out.println(
"......................................................");
} // end displayTree()
// -------------------------------------------------------------
} // end class Tree
////////////////////////////////////////////////////////////////
class TreeApp
{
public static void main(String[] args) throws IOException
{
int value;
Tree theTree = new Tree();
// Inserting 20 random integers in the tree
for(int i = 0; i < 20; i++)
theTree.insert((int)(Math.random()*(999)+1));
theTree.traverse(1);
theTree.traverse(2);
theTree.traverse(3);
theTree.traverse(4);
} // end main()
// -------------------------------------------------------------
public static String getString() throws IOException
{
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
String s = br.readLine();
return s;
}
// -------------------------------------------------------------
public static char getChar() throws IOException
{
String s = getString();
return s.charAt(0);
}
//-------------------------------------------------------------
public static int getInt() throws IOException
{
String s = getString();
return Integer.parseInt(s);
}
// -------------------------------------------------------------
} // end class TreeApp
////////////////////////////////////////////////////////////////
Note - The output shall be customised based on the requirements. The current format is like the one given in Lafore as recommended in the question.
Answer 2)
In this question, the stack and queue are implemented. Now we have to construct the tree from postfix/ prefix expression.
To construct a tree from postfix expression, we create a stack. On encountering a operand we ush it into stack. On encountering an operator, we pop 2 operands from stack, create a new expression tree with children as those operands and push it into the stack.
Similarly to construct a tree from prefix, we reverse the expression and construct the postfix for that expression.
The sample code for stack :-
class MyStack <T>
{
private ArrayList<T> stack;
public MyStack()
{
stack = new ArrayList<T> ();
top = 0;
}
private int top;
public int size () { return top; }
public Boolean isEmpty()
{
return this.top == 0;
}
public void push (T item) {
stack.add (top++, item);
}
public Boolean pop () {
stack.remove (--top);
return true;
}
public T peak()
{
return this.stack.get(top - 1);
}
}
Use string as the data type of data in Nodes.
Sample code for main function :-
Tree theTree;
String ln = getString();
while(ln != null)
{
if(ln.charAt(0) == 'C')
{
System.out.println(ln.substring(8));
ln = getString();
continue;
}
else if(ln.charAt(0) == 'S')
{
theTree.simplify();
ln = getString();
continue;
}
else if(ln.charAt(0) == 'N')
{
String[] temp = ln.substring(4).split(' ');
if(ln.charAt(4) == '*' || ln.charAt(4) == '+' || ln.charAt(4) == '/' || ln.charAt(4) == '-')
{
temp = ln.substring(4).reverse().split(' ');
MyStack<Tree> s = new MyStack<Tree>();
for(String x : temp)
{
if(x.equals("+") || x.equals("-") || x.equals("*") || x.equals("/"))
{
Node t1 = s.pop();
Node t2 = s.pop();
Node t3 = new Node();
t3.leftChild = t1;
t3.rightChild = t2;
s.push(t3);
}
else
{
Node t = new Node();
t.iData = x;
t.leftChild = t.rightChild = NULL;
s.push(t);
}
}
theTree = s.top();
}
else
{
MyStack<Tree> s = new MyStack<Tree>();
for(String x : temp)
{
if(x.equals("+") || x.equals("-") || x.equals("*") || x.equals("/"))
{
Node t1 = s.pop();
Node t2 = s.pop();
Node t3 = new Node();
t3.leftChild = t1;
t3.rightChild = t2;
s.push(t3);
}
else
{
Node t = new Node();
t.iData = x;
t.leftChild = t.rightChild = NULL;
s.push(t);
}
}
theTree = s.top();
}
ln = getString();
continue;
}
else if(ln.equals("PRINTPREFIX"))
{
theTree.traverse(1);
ln = getString();
continue;
}
else if(ln.equals("PRINTINFIX"))
{
theTree.traverse(2);
ln = getString();
continue;
}
else
{
theTree.traverse(3);
ln = getString();
continue;
}
}
Hope it helped you.. Happy studying!!
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.