Question
Tree Traversals HOW TO DO: Part 3: Create a binary tree of height 4 and test your code for pre-order, post-order and breadth-first traversals on
Tree Traversals
HOW TO DO: Part 3: Create a binary tree of height 4 and test your code for pre-order, post-order and breadth-first traversals on it. Present the test results in your report. To get full marks for your testing, you must describe clearly how you verified that your traversals are correct. Diagrams and accompanying explanations may help.
ANSWER FOR PART 1 AND 2 IS BELOW
In the code for Topic 5 (Trees), the implementation of BinaryTree includes a method for in-order traversalof the tree, printing out each node as it is visited.
The main() method in BinaryTreeDemo creates a binary tree manually of height 3, displays statistics, and performs an in-order traversal.
For this assignment, you have to make the following changes to the code:
Part 1: Add methods implementing pre-order and post-order traversals to the BinaryTree class, as described in the lecture notes. (6 marks: 3 for pre-order and 3 for post-order).
Part 2: Add a method implementing breadth-first traversal of the BinaryTree class, as was discussed in lectures see additional notes below. (6 marks)
Part 3: Create a binary tree of height 4 and test your code for pre-order, post-order and breadth-first traversals on it. Present the test results in your report. To get full marks for your testing, you must describe clearly how you verified that your traversals are correct. Diagrams and accompanying explanations may help. (8 marks)
Information on breadth-first traversal:
This is more complicated than depth-first traversal. As discussed in lectures, the general procedure is a non-recursive one in which you use a Queue to keep track of the order in which to visit nodes:
1. Begin with the root node on the queue
2. At each iteration, dequeue the node at the head of the queue, and enqueue its children to the end of the queue (if it has any), and visit the removed node
3. Repeat this until the queue is empty
you may opt to use the standard library class java.util.ArrayList as the queue: remove(0) removes the item at index 0 (head), while add(el) adds the specified element to the end of the ArrayList. Youll need to use the notation for generics.
import java.util.LinkedList;
import java.util.Queue;
public class BinaryTree
{
private static final long serialVersionUID = -1932834476575953631L;
private BinaryNodeInterface
public BinaryTree()
{
root = null;
} // end default constructor
public BinaryTree(T rootData)
{
root = new BinaryNode
} // end constructor
public BinaryTree(T rootData, BinaryTree
BinaryTree
{
privateSetTree(rootData, leftTree, rightTree);
} // end constructor
public void setTree(T rootData)
{
root = new BinaryNode
} // end setTree
public void setTree(T rootData, BinaryTreeInterface
BinaryTreeInterface
{
privateSetTree(rootData, (BinaryTree
(BinaryTree
} // end setTree
// 26.08
private void privateSetTree(T rootData, BinaryTree
BinaryTree
{
root = new BinaryNode
if ((leftTree != null) && !leftTree.isEmpty())
root.setLeftChild(leftTree.root);
if ((rightTree != null) && !rightTree.isEmpty())
{
if (rightTree != leftTree)
root.setRightChild(rightTree.root);
else
root.setRightChild(rightTree.root.copy());
} // end if
if ((leftTree != null) && (leftTree != this))
leftTree.clear();
if ((rightTree != null) && (rightTree != this))
rightTree.clear();
} // end privateSetTree
private BinaryNode
{
return (BinaryNode
} // end copyNodes
// 26.09
public T getRootData()
{
T rootData = null;
if (root != null)
rootData = root.getData();
return rootData;
} // end getRootData
// 26.09
public boolean isEmpty()
{
return root == null;
} // end isEmpty
// 26.09
public void clear()
{
root = null;
} // end clear
// 26.09
protected void setRootData(T rootData)
{
root.setData(rootData);
} // end setRootData
// 26.09
protected void setRootNode(BinaryNodeInterface
{
root = rootNode;
} // end setRootNode
// 26.09
protected BinaryNodeInterface
{
return root;
} // end getRootNode
// 26.10
public int getHeight()
{
return root.getHeight();
} // end getHeight
// 26.10
public int getNumberOfNodes()
{
return root.getNumberOfNodes();
} // end getNumberOfNodes
// 26.12
public void inorderTraverse()
{
inorderTraverse(root);
} // end inorderTraverse
private void inorderTraverse(BinaryNodeInterface
{
if (node != null)
{
inorderTraverse(node.getLeftChild());
System.out.println(node.getData());
inorderTraverse(node.getRightChild());
} // end if
} // end inorderTraverse
public void preorderTraverse()
{
preorderTraverse(root);
} // end preorderTraverse
private void preorderTraverse(BinaryNodeInterface
{
if (node != null)
{
System.out.println(node.getData());
preorderTraverse(node.getLeftChild());
preorderTraverse(node.getRightChild());
} // end if
} // end preorderTraverse
public void breadthFirst() {
BinaryNodeInterface
Queue
if (p != null) {
queue.offer(p);
while (!queue.isEmpty()) {
p = queue.poll();
System.out.println(p.getData());
if (p.getLeftChild()!= null)
queue.offer(p.getLeftChild());
if (p.getRightChild() != null)
queue.offer(p.getRightChild());
}
}
}
public void postorderTraverse()
{
postorderTraverse(root);
} // end postorderTraverse
private void postorderTraverse(BinaryNodeInterface
{
if (node != null)
{
postorderTraverse(node.getLeftChild());
postorderTraverse(node.getRightChild());
System.out.println(node.getData());
} // end if
} // end postorderTraverse
} // end BinaryTree
public class BinaryTreeDemo
{
public static void main(String[] args)
{
// Create a tree
System.out.println("Constructing a test tree ...");
BinaryTree
createTree1(testTree);
// Display some statistics about it
System.out.println(" Some statistics about the test tree ...");
displayStats(testTree);
// Perform in-order traversal
System.out.println(" In-order traversal of the test tree, printing each node when visiting it ...");
testTree.inorderTraverse();
// Perform pre-order traversal
System.out.println(" Pre-order traversal of the test tree, printing each node when visiting it ...");
testTree.preorderTraverse();
// Perform post-order traversal
System.out.println(" Post-order traversal of the test tree, printing each node when visiting it ...");
testTree.postorderTraverse();
System.out.println("Breadth First Traversal: ");
testTree.breadthFirst();
} // end of main
public static void createTree1(BinaryTree
{
// To create a tree, build it up from the bottom:
// create subtree for each leaf, then create subtrees linking them,
// until we reach the root.
System.out.println(" Creating a treee that looks like this: ");
System.out.println(" A ");
System.out.println(" / \\ "); // '\\' is the escape character for backslash
System.out.println(" B C ");
System.out.println(" / \\ / \\");
System.out.println("D E F G ");
System.out.println();
// First the leaves
BinaryTree
dTree.setTree("D");
// neater to use the constructor the initialisation ...
BinaryTree
BinaryTree
BinaryTree
// Now the subtrees joining leaves:
BinaryTree
BinaryTree
// Now the root
tree.setTree("A", bTree, cTree);
} // end createTree1
public static void displayStats(BinaryTree
{
if (tree.isEmpty())
System.out.println("The tree is empty");
else
System.out.println("The tree is not empty");
System.out.println("Root of tree is " + tree.getRootData());
System.out.println("Height of tree is " + tree.getHeight());
System.out.println("No. of nodes in tree is " + tree.getNumberOfNodes());
} // end displayStats
}
interface BinaryTreeInterface
{
/** Task: Sets an existing binary tree to a new one-node binary tree.
* @param rootData an object that is the data in the new trees root
*/
public void setTree(T rootData);
/** Task: Sets an existing binary tree to a new binary tree.
* @param rootData an object that is the data in the new trees root
* @param leftTree the left subtree of the new tree
* @param rightTree the right subtree of the new tree */
public void setTree(T rootData, BinaryTreeInterface
BinaryTreeInterface
} // end BinaryTreeInterface
interface TreeInterface
{
public T getRootData();
public int getHeight();
public int getNumberOfNodes();
public boolean isEmpty();
public void clear();
} // end TreeInterface
interface BinaryNodeInterface
{
/** Task: Retrieves the data portion of the node.
* @return the object in the data portion of the node */
public T getData();
/** Task: Sets the data portion of the node.
* @param newData the data object */
public void setData(T newData);
/** Task: Retrieves the left child of the node.
* @return the node that is this nodes left child */
public BinaryNodeInterface
/** Task: Retrieves the right child of the node.
* @return the node that is this nodes right child */
public BinaryNodeInterface
/** Task: Sets the nodes left child to a given node.
* @param leftChild a node that will be the left child */
public void setLeftChild(BinaryNodeInterface
/** Task: Sets the nodes right child to a given node.
* @param rightChild a node that will be the right child */
public void setRightChild(BinaryNodeInterface
/** Task: Detects whether the node has a left child.
* @return true if the node has a left child */
public boolean hasLeftChild();
/** Task: Detects whether the node has a right child.
* @return true if the node has a right child */
public boolean hasRightChild();
/** Task: Detects whether the node is a leaf.
* @return true if the node is a leaf */
public boolean isLeaf();
/** Task: Counts the nodes in the subtree rooted at this node.
* @return the number of nodes in the subtree rooted at this node */
public int getNumberOfNodes();
/** Task: Computes the height of the subtree rooted at this node.
* @return the height of the subtree rooted at this node */
public int getHeight();
/** Task: Copies the subtree rooted at this node.
* @return the root of a copy of the subtree rooted at this node */
public BinaryNodeInterface
} // end BinaryNodeInterface
class BinaryNode
{
private static final long serialVersionUID = 6828929352995534482L; // needed for serializable objects
private T data;
private BinaryNode
private BinaryNode
public BinaryNode()
{
this(null); // call next constructor
} // end default constructor
public BinaryNode(T dataPortion)
{
this(dataPortion, null, null); // call next constructor
} // end constructor
public BinaryNode(T dataPortion, BinaryNode
BinaryNode
{
data = dataPortion;
left = leftChild;
right = rightChild;
} // end constructor
public T getData()
{
return data;
} // end getData
public void setData(T newData)
{
data = newData;
} // end setData
public BinaryNodeInterface
{
return left;
} // end getLeftChild
public BinaryNodeInterface
{
return right;
} // end getRightChild
public void setLeftChild(BinaryNodeInterface
{
left = (BinaryNode
} // end setLeftChild
public void setRightChild(BinaryNodeInterface
{
right = (BinaryNode
} // end setRightChild
public boolean hasLeftChild()
{
return left != null;
} // end hasLeftChild
public boolean hasRightChild()
{
return right != null;
} // end hasRightChild
public boolean isLeaf()
{
return (left == null) && (right == null);
} // end isLeaf
// 26.06
public BinaryNodeInterface
{
BinaryNode
if (left != null)
newRoot.left = (BinaryNode
if (right != null)
newRoot.right = (BinaryNode
return newRoot;
} // end copy
// 26.11
public int getHeight()
{
return getHeight(this); // call private getHeight
} // end getHeight
// 26.11
private int getHeight(BinaryNode
{
int height = 0;
if (node != null)
height = 1 + Math.max(getHeight(node.left), getHeight(node.right));
return height;
} // end getHeight
// 26.11
public int getNumberOfNodes()
{
int leftNumber = 0;
int rightNumber = 0;
if (left != null)
leftNumber = left.getNumberOfNodes();
if (right != null)
rightNumber = right.getNumberOfNodes();
return 1 + leftNumber + rightNumber;
} // end getNumberOfNodes
} // end BinaryNode ================================================ See Output 
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started
