Latest Activity In Study Groups

Join Your Study Groups

VU Past Papers, MCQs and More

We non-commercial site working hard since 2009 to facilitate learning Read More. We can't keep up without your support. Donate.

CS301-Data Structures Assignment No.3 Discussion And Solution Spring 2013 Due Date: May-15-2013

Instructions 

Assignment No. 03 
SEMESTER Spring 2013 
CS301‐ Data Structures 
Please read the following instructions carefully before solving & submitting assignment: 
It should be clear that your assignment will not get any credit (zero marks) if: 
o The assignment is submitted after due date. 
o The submitted code does NOT compile. 
o The submitted assignment is other than .CPP file. 
o The submitted assignment does NOT open or file is corrupted. 
o The assignment is copied (copied from other student or copied from handouts or internet). 
Uploading instructions 
 
Total Marks: 20 
 
Due Date: 15/5/2013 
You are required to Upload/Submit only ONE .CPP file. 
Don’t wait for grace day. Grace day is only given if there is problem on due date. Submit your solution within 
due date.  
Note that no assignment will be accepted through email if there is any problem on grace day. 
 
Note: Use ONLY Dev‐C++ IDE. 
Objective 
The objective of this assignment is  
 
o To make you familiar with different operations related to BST(binary search tree) 
 
For any query about the assignment, contact at cs301@vu.edu.pk
 
GOOD LUCK 
 

Question:
Write a C++ program to. 
1) Create a binary search tree named left tree and show the inorder, preorder and postorder traversal of that
left BST tree. 
2) Similarly, create a binary search tree named right tree and show the inorder, preorder and postorder 
traversal of that right BST tree. 
3) After creating left and right binary search trees, one by one pick up a node value from right binary 
Marks: 20 
search tree by any traversing method and then insert that value (which you picked up from right tree node)
in left binary search tree. Discard any duplicate value (in both right and left binary search trees) during
insertion of a value from right binary search tree to left binary search tree. 
4) The left binary search tree will be modified after inserting values from right binary search tree. Show the
inorder, preorder and postorder traversal of that modified left binary search tree. 
Note:
Please watch the attached demo.wmv video for complete details of what is required from you in this 3

assignment. The diagram given below is showing the pictorial representation of left binary search tree , right
binary search tree and the modified left binary search tree which is developed after inserting values into left
binary search tree from right binary search tree.

Left Binary Search Tree: 
15
11 22
24
10 12 20
19 23 25

Right Binary Search Tree: 
10
155 
64 14 20
19
23 

rd

Modified left binary search tree: 

15
4 
11 22
10 12 20 24 
25 23195 
6 
14

 
Solution Guidelines:

1. First understand the code given in handouts about binary search tree. 
2. You can use code give handouts to complete desired task.
3. For clearly understanding of assignment task see demo.wmv file attached with assignment file.
4. If you have any ambiguity about assignment send your query at cs301@vu.edu.pk. 

Lectures Covered:  This assignment covers Lecture #  10 to 15 
Deadline:           Your assignment must be uploaded / submitted on / before, Wednesday May 15, 2013. 

Views: 8030

Replies to This Discussion

Please Discuss here about this assignment.Thanks

Our main purpose here discussion not just Solution

We are here with you hands in hands to facilitate your learning and do not appreciate the idea of copying or replicating solutions.

Attachments:

     tariq bhai plz 301 ka solution share kr den. it is so confusing assignment.

pdf file is corrupt, plz upload it in dos format.

Share idea solution

plz discuss about assignment solution

Dear Students Share your views and problems about this Assignment here, So we can discuss and solve this Assignment, Don't wait for solutions , Start discussion because Discussion clear our concepts & provide best solutions. As Date sheet has come and Midterm exams will start on 25 May. So Please Focus on Lectures and Participate in Lecture Wise Discussions and Assignments , GDB, Quiz Discussions and Clear ur concepts Thanks  and Regards.

yrr complete solution ya idea post karna

+ Uѕмʌɴ thanks 

Note for All Members: You don’t need to go any other site for this assignment/GDB/Online Quiz solution, Because All discussed data of our members in this discussion are going from here to other sites. You can judge this at other sites yourself. So don’t waste your precious time with different links.

koi tu right solution do

help to koi ker nahi raha :(

to phir solution may help to kary

    #include <iostream>
    using namespace std;


    //..Tree Node Class
    class TreeNode
    {


    private:
    //variable to store number, left and right subtree pointer
    int number;
    TreeNode* left;
    TreeNode* right;


    public:
    //Default Constructor
    TreeNode()
    {


    number = 0;
    this->left = NULL;
    this->right = NULL;
    }
    //..Overload Constructor to initialize node with number value
    TreeNode(int no)
    {
    this->number = no;
    this->left = NULL;
    this->right = NULL;
    }


    //Getter for number
    int getNumber()
    {
    return number;
    }
    //Setter for number
    void setNumber(int no)
    {
    this->number = no;
    }
    //Setter for left subtree
    void setLeft(TreeNode* leftNode)
    {
    if(left != NULL)
    {
    delete left;
    }
    this->left = leftNode;
    }
    //Getter for left Tree
    TreeNode* Left()
    {
    return left;
    }
    //Setter for right tree
    void setRight(TreeNode* rightNode)
    {
    if(right != NULL)
    {
    delete right;
    }
    this->right = rightNode;
    }
    //Getter for right tree
    TreeNode* Right()
    {


    return right;
    }


    };


    //..Binary Search Tree Class
    class BinarySearchTree
    {
    private:
    //variable for root node
    TreeNode* root;


    public:
    //Method for inserting nodes in tree from given array
    void insert(int numbers[], int arraySize)
    {
    if(root != NULL)
    {
    delete root;
    }
    //Take a first value from array and make it root
    root = new TreeNode(numbers[0]);
    for (int i = 1; i < arraySize; i++)
    {
    insert(root, numbers[i]);
    }


    }
    //getter for Root
    TreeNode* Root()
    {
    return this->root;
    }
    //Method for inserting new node in tree with given number
    void insert(TreeNode* root, int no)
    {
    //Create a new node with given number
    TreeNode* newNode = new TreeNode(no);


    TreeNode *p, *q;
    //starting travasering from root from root
    p = q = root;


    //Continue until we found a node with matching number or a place for inserting new node
    while ((no != p->getNumber()) && q != NULL)
    {
    p = q;
    if(no < p->getNumber())
    {
    q = p->Left();
    }
    else
    {
    q = p->Right();
    }
    }
    //if the node already exists with this number show message and delete node
    if(no == p->getNumber())
    {
    cout "\nAttempt to insert duplicate Value... " p->getNumber() " .... Dicarded" endl;
    delete newNode;
    }
    //if number value is less then value in root then make it left subchild of root
    else if (no < p->getNumber())
    {
    p->setLeft(newNode);
    }
    //if number is greater then make right subchild
    else
    {
    p->setRight(newNode);
    }
    }


    //Method for inserting nodes from an other bineary search tree
    void insert(BinarySearchTree* tree, int leftTreeSize, int rightTreeSize)
    {
    //flatten the right bst to sorted array
    int index = 0;
    TreeNode* rightTreeNodes[rightTreeSize];
    insertNodesToArray(tree->root, rightTreeNodes, &index);


    //similarly flatten the left bst to sorted array
    int index2 = 0;
    TreeNode* leftTreeNodes[leftTreeSize];
    insertNodesToArray(root, leftTreeNodes, &index2);


    //decalre array to save numbers from both arrays
    int finalArray[rightTreeSize];


    int i = 0, j = 0, k = 0;


    //continue untill we have numbers from both array
    while (i < rightTreeSize && j < leftTreeSize)
    {
    //if the value at right tree is less then insert it number to final array
    if(rightTreeNodes[i]->getNumber() < leftTreeNodes[j]->getNumber())
    {
    finalArray[k] = rightTreeNodes[i]->getNumber();
    i++;
    }
    else
    {
    //else insert the left tree value in final array
    finalArray[k] = leftTreeNodes[j]->getNumber();
    j++;


    }
    k++;
    }


    //if the right tree has more nodes then left tree insert it to array.
    while (i < rightTreeSize)
    {
    finalArray[k] = rightTreeNodes[i]->getNumber();
    i++, k++;
    }
    //if the left tree has more nodes then insert it.
    while (j < leftTreeSize)
    {
    finalArray[k] = leftTreeNodes[j]->getNumber();
    j++, k++;
    }


    //finally create left tree from scratch using final array.
    insert(finalArray, k);


    }


    //This method converts the bst to sorted array using the inorder traverse.
    void insertNodesToArray(TreeNode* root, TreeNode* noodes[], int* index)
    {


    if (root != NULL)
    {
    insertNodesToArray(root->Left(), noodes, index);
    }
    if (root && root->getNumber())
    {
    noodes[(*index)] = root;
    (*index)++;


    }
    if (root && root->Right() != NULL)
    {
    insertNodesToArray(root->Right(), noodes, index);
    }


    }
    //mehtod for diplaying preOrder
    void preOrder(TreeNode* node)
    {
    if (node != NULL)
    {
    cout " " node->getNumber();
    preOrder(node->Left());
    preOrder(node->Right());
    }


    }
    //method for displaying inOrder
    void inOrder(TreeNode* node)
    {
    if (node != NULL)
    {
    inOrder(node->Left());
    cout " " node->getNumber();
    inOrder(node->Right());
    }


    }
    //method for diplaying post order
    void postOrder(TreeNode* node)
    {
    if (node != NULL)
    {
    postOrder(node->Left());
    postOrder(node->Right());
    cout " " node->getNumber();
    }
    }


    };


    int main(int argc, const char * argv[])
    {


    //Declaring Array for left and right trees
    const int leftTreeSize = 10;
    const int rightTreeSize = 9;
    int leftArray[] = {11, 19, 15, 23, 22, 24, 25, 12, 10, 20};
    int rightArray[] = {5,6,10,4,19,23,20,15,14};


    //Creating Left and Right Trees
    BinarySearchTree* leftTree = new BinarySearchTree();
    leftTree->insert(leftArray, leftTreeSize);
    BinarySearchTree* rightTree = new BinarySearchTree();
    rightTree->insert(rightArray, rightTreeSize);


    //printing the required statements


    cout "\nPrinting Left Tree";
    cout "\nPre Order Travsel is \n";
    leftTree->preOrder(leftTree->Root());
    cout "\nIn Order Travsel \n";
    leftTree->inOrder(leftTree->Root());
    cout "\nPost Order Travsel \n";
    leftTree->postOrder(leftTree->Root());


    cout "\n\nPrinting Right Tree";
    cout "\nPre Order Travsel is \n";
    rightTree->preOrder(leftTree->Root());
    cout "\nIn Order Travsel \n";
    rightTree->inOrder(leftTree->Root());
    cout "\nPost Order Travsel \n";
    rightTree->postOrder(leftTree->Root());


    cout "\n\nTransfering the data to left Tree";
    leftTree->insert(rightTree, leftTreeSize, rightTreeSize);


    cout "\nPrinting the order after transfering \n";
    cout "\nPrinting Left Tree";
    cout "\nPre Order Travsel is \n";
    leftTree->preOrder(leftTree->Root());
    cout "\nIn Order Travsel \n";
    leftTree->inOrder(leftTree->Root());
    cout "\nPost Order Travsel \n";
    leftTree->postOrder(leftTree->Root());
    cout "\n\n" endl;
    system("pause");
    return 0;
    }

RSS

Looking For Something? Search Below

Latest Activity

VIP Member Badge & Others

How to Get This Badge at Your Profile DP

------------------------------------

Management: Admins ::: Moderators

Other Awards Badges List Moderators Group

© 2021   Created by + M.Tariq Malik.   Powered by

Promote Us  |  Report an Issue  |  Privacy Policy  |  Terms of Service