This programming assignment is to implement the following using either Java or C
ID: 3588992 • Letter: T
Question
This programming assignment is to implement the following using either Java or C++.
1.
2. 3.
A function/method that take preorder and inorder traversal sequence and build the corresponding binary tree.
Both traversal sequences are stored as array.
Implement the non-recursive inorder, preorder and postorder traversal of the binary tree.
Implement the binary tree traversal by level, with the level number displayed.
You also have to implement the user interface, to allow user to test your code.
You can work as a team of two or work alone. If you work as a team, both of you have to submit the identical work with both names to D2L so that your grade can be recorded.
You must submit the following:
All the source codes
Your source code must be well-documented.
Documentation that describes what you did, and how to run your program
If the input inorder sequence = {2,5,6,10,12,14,15}; and preorder sequence = {10,5,2,6,14,12,15};
Then your output should look like the following : Constructed Tree :
Non-recursive inorder traversal : 2 5 6 10 12 14 15
Non-recursive preorder traversal : 10 5 2 6 14 12 15
Non-recursive postorder traversal : 2 6 5 12 15 14 10
by level traversal with Level number : Level 0 :10
Level 1 : 5 Level 1 :14 Level 2 : 2 Level 2 : 6 Level 2 :12 Level 2 :15
//////////////////////////////////////////////////////////////////////////////
In Java, the given node class should be used-
class Node<T>{ T data;
Node <T>left;
Node <T>right; public Node (T data){
this.data = data; left = null;
right = null;
}
// you may add more stuff here }
////////////////////////////////////////////////////////////////////////////////////////// In C++ , the given node structure or class should be used :
T value;
Node *left;
Template <class T> struct Node { T value;
Node *left;
Node *right; };
Explanation / Answer
JAVA CODE
-----------------Node.java-------------------
public class Node<T>
{
T data;
Node left;
Node right;
public Node (T data)
{
this.data = data;
left = null;
right = null;
}
// you may add more stuff here
}
-----------------BST.java-------------------
public class BST<T>
{
// store the index of pre_order array
int pre_order_index;
public Node createBSTUtil(T pre_order[], T post_order[], int p, int r, int size)
{
// if the call is invalid
if (pre_order_index >= size || p > r)
return null;
// First node in the preorder traversal is the root node
// create a new node root
Node root = new Node(pre_order[pre_order_index]);
// increment pre_order_index
pre_order_index++;
// if the array has only a single element
if (p == r || pre_order_index >= size)
// return the root node
return root;
int j;
// find preorder array element in the postorder array
for (j = p; j <= r; j++)
{
if (post_order[j] == pre_order[pre_order_index])
break;
}
if (j <= r)
{
// get the left child
root.left = createBSTUtil(pre_order, post_order, p, j, size);
// get the right child
root.right = createBSTUtil(pre_order, post_order, j + 1, r, size);
}
// return the root node
return root;
}
public Node createBST(T pre_order[], T post_order[], int size)
{
pre_order_index = 0;
// call constructTreeUtil function to construct BST
return createBSTUtil(pre_order, post_order, 0, size - 1, size);
}
static void inorder(Node root)
{
if (root == null)
return;
inorder(root.left);
System.out.print(root.data + " ");
inorder(root.right);
}
}
-----------------Test.java-------------------
public class Test
{
public static void main(String[] args)
{
Integer[] pre_order = { 10, 5, 2, 6, 14, 12, 15 };
Integer[] post_order = { 2, 6, 5, 12, 15, 14, 10 };
BST<Integer> ob = new BST<Integer>();
int size = pre_order.length;
Node root = ob.createBST(pre_order, post_order, size);
System.out.println("Inorder traversal of the constructed tree:");
ob.inorder(root);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.