CS301 Assignments # 2 Solution Spring 2012

Suppose some VU campuses are connected to a central server placed at Lahore campus via leased lines such that each campus has a one hop (direct) connectivity to the central server or it has multi hop connection to Lahore campus via other campuses at provincial head quarters or regional campuses which are in turn connected to the Lahore Campus.

Here is a table showing campus names and assumed codes.

Below is the Binary Tree showing the leased line spanning in which each node contains one campus code while the edges show the direct connectivity between two campuses.

Write a C++ program to store this Binary Tree in computer memory in which each node has the campus code as value (campus name storing is excluded for the sake of simplicity).


Also print on screen, the post order traversal of stored binary tree in order to verify your solution.

Solution Guidelines:

• In coding there must be a class to create and manipulate tree nodes.
• There should be a function to create (store) this binary tree from two of its traversals given below.
• In main( ) function, use two arrays to store Preorder and Inorder traversals of the given binary tree.

Hint:

Use Preorder and Inorder Traversals of the Binary Tree for solving.

Write on paper, a manual Postorder traversal of the tree to see your screen printed Postorder traversal with it, for verification of your solution correctness.

[Preorder: 18  95  41  29  52  74  86  33  57  17  20] [Inorder:   41  95  74  52  29  18  86  57  17  33  20]

/****************** Assignment No. 2 : Solution **********************\

#include <iostream.h>
#include <conio.h>

//For the required binary tree implementation, two traversals of the tree are required;
//Pre Order Traversal and In Order Traversal

// TreeNode class to create a new node as well as set and get values from it.
class TreeNode
{
public:
//constructor

TreeNode(int value)
{
this->value = value;
this->left = NULL;
this->right = NULL;
}
//get and set value of the node
int getInfo()
{
return this->value;
}
void setInfo(int value)
{
this->value = value;
}
//left child
TreeNode* getLeft()
{
return left;
}
void setLeft(TreeNode* left)
{
this->left = left;
}
//right child
TreeNode* getRight()
{
return right;
}
void setRight(TreeNode* right)
{
this->right = right;
}
//Private data memebers include value of a node, left and right child
private:
int value;
TreeNode* left;
TreeNode* right;
}; //End of class TreeNode
//findposition(…) function is used to find the index of a node value in inorder traversal array.

int findPosition(int* arr, int val, int arrsize)
{
for(int i=0; i<arrsize;i++)
{
if(arr[i] == val)
return i;
}
return -1;
}

//createBTree function is used to creat Binary Tree from its preorder and inorder traversals.


TreeNode* createBTree(int* preorder, int* inorder, int arrsize)
{
if(arrsize == 0) return NULL;

int nodeVal = *preorder;
TreeNode* node = new TreeNode(nodeVal); //first node of the preorder will be the root
int newPos = findPosition(inorder, nodeVal, arrsize); //its index is find in inorder array
node->setLeft(createBTree(preorder+1, inorder, newPos));
node->setRight(createBTree(preorder+newPos+1, inorder+newPos+1, arrsize-newPos-1));
return node;
}

 

// postorder(0) function is used to print postorder traversal of the binary tree created

void postorder(TreeNode* troot)
{
if( troot != NULL)
{
postorder(troot->getLeft());
postorder(troot->getRight());
cout << troot->getInfo()<<” “;
}

}
//below is the main() function

int main()
{
int preorderarr[] = {18,95,41,29,52,74,86,33,57,17,20}; //array to store preorder traversal of the tree
int inorderarr[] = {41,95,74,52,29,18,86,57,17,33,20}; //array to store inorder traversal of the tree

TreeNode* btree = createBTree(preorderarr, inorderarr, 11);//tree creat

cout<<“***** Post order traversal of the given Tree ******” <<endl <<endl;
postorder(btree); // function call to print postorder traversal of the binary tree created

getche();
return 0;
}

 /****************** DOWNLOAD SOLUTION FROM HERE **********************\

 

CS301_Assignments_Solution_2_Spring_2012