CS301 Assignment # 3 Solution Spring 2013
Page 1 of 1 • Share
CS301 Assignment # 3 Solution Spring 2013
by ChIntoo Wed May 15, 2013 6:55 pm
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[You must be registered and logged in to see this link.]
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 [You must be registered and logged in to see this link.].
Lectures Covered: This assignment covers Lecture # 10 to 15
Deadline: Your assignment must be uploaded / submitted on / before, Wednesday May 15, 2013.
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[You must be registered and logged in to see this link.]
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 [You must be registered and logged in to see this link.].
Lectures Covered: This assignment covers Lecture # 10 to 15
Deadline: Your assignment must be uploaded / submitted on / before, Wednesday May 15, 2013.
ChIntoo- Monstars
- Posts : 92
Join date : 2011-02-13
Re: CS301 Assignment # 3 Solution Spring 2013
by ChIntoo Wed May 15, 2013 6:57 pm
Binary tree traversal: Preorder, Inorder, and Postorder
In order to illustrate few of the binary tree traversals, let us consider the below binary tree:
[You must be registered and logged in to see this image.]Preorder traversal: To traverse a binary tree in Preorder, following operations are carried-out (i) Visit the root, (ii) Traverse the left subtree, and (iii) Traverse the right subtree.
Therefore, the Preorder traversal of the above tree will outputs:
7, 1, 0, 3, 2, 5, 4, 6, 9, 8, 10Inorder traversal: To traverse a binary tree in Inorder, following operations are carried-out (i) Traverse the left most subtree starting at the left external node, (ii) Visit the root, and (iii) Traverse the right subtree starting at the left external node.
Therefore, the Inorder traversal of the above tree will outputs:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10Postorder traversal: To traverse a binary tree in Postorder, following operations are carried-out (i) Traverse all the left external nodes starting with the left most subtree which is then followed by bubble-up all the internal nodes, (ii) Traverse the right subtree starting at the left external node which is then followed by bubble-up all the internal nodes, and (iii) Visit the root.
Therefore, the Postorder traversal of the above tree will outputs:
0, 2, 4, 6, 5, 3, 1, 8, 10, 9, 7
Therefore, the Preorder traversal of the above tree will outputs:
7, 1, 0, 3, 2, 5, 4, 6, 9, 8, 10Inorder traversal: To traverse a binary tree in Inorder, following operations are carried-out (i) Traverse the left most subtree starting at the left external node, (ii) Visit the root, and (iii) Traverse the right subtree starting at the left external node.
Therefore, the Inorder traversal of the above tree will outputs:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10Postorder traversal: To traverse a binary tree in Postorder, following operations are carried-out (i) Traverse all the left external nodes starting with the left most subtree which is then followed by bubble-up all the internal nodes, (ii) Traverse the right subtree starting at the left external node which is then followed by bubble-up all the internal nodes, and (iii) Visit the root.
Therefore, the Postorder traversal of the above tree will outputs:
0, 2, 4, 6, 5, 3, 1, 8, 10, 9, 7
ChIntoo- Monstars
- Posts : 92
Join date : 2011-02-13
Re: CS301 Assignment # 3 Solution Spring 2013
by Victoria333 Wed May 15, 2013 6:57 pm
- Code:
class Idea...cpp
/* This file contains the TreeNode class declaration. TreeNode contains the functionality for a binary tree node */
1. #include <stdlib.h>
2.
3. template <class Object>
4.
5. class TreeNode
6. {
7. public:
8. // constructors
9. TreeNode()
10. {
11. this->object = NULL;
12. this->left = this->right = NULL;
13. };
14.
15. TreeNode( Object * object )
16. {
17. this->object = object;
18. this->left = this->right = NULL;
19. };
20.
21. Object * getInfo()
22. {
23. return this->object;
24. };
25.
26. void setInfo(Object * object)
27. {
28. this->object = object;
29. };
30.
31. TreeNode * getLeft()
32. {
33. return left;
34. };
35.
36. void setLeft(TreeNode * left)
37. {
38. this->left = left;
39. };
40.
41 TreeNode * getRight()
42. {
43. return right;
44. };
45.
46. void setRight(TreeNode * right)
47. {
48. this->right = right;
49. };
50.
51. int isLeaf( )
52. {
53. if( this->left == NULL && this->right == NULL )
54. return 1;
55. return 0;
56. };
57.
58. private:
59. Object * object;
60. TreeNode * left;
61. TreeNode * right;
62. }; // end class TreeNode
Victoria333- Monstars
-
Posts : 267
Join date : 2013-05-12
Age : 35
Location : Victoria
Re: CS301 Assignment # 3 Solution Spring 2013
by Victoria333 Wed May 15, 2013 6:58 pm
- Code:
1. #include <iostream>
2. #include <stdlib.h>
3. #include "TreeNode.cpp"
4.
5. int main(int argc, char * argv[])
6. {
7. int x[] = {14,15,4,9,7,18,3,5,16,4,20,17,9,14,5,-1};
8. TreeNode <int> * root = new TreeNode<int>();
9. root->setInfo( &x[0] );
10. for(int i = 1; x[i] > 0; i++ )
11. {
12. insert( root, &x[i] );
13. }
14. }
15.
16. void insert (TreeNode <int> * root, int * info)
17. {
18. TreeNode <int> * node = new TreeNode <int> (info);
19. TreeNode <int> * p, * q;
20. p = q = root;
21. while( *info != *(p->getInfo()) && q != NULL )
22. {
23. p = q;
24. if( *info < *(p->getInfo()) )
25. q = p->getLeft();
26. else
27. q = p->getRight();
28. }
29.
30. if( *info == *( p->getInfo() ) )
31. {
32. cout "attempt to insert duplicate: " *info endl;
33. delete node;
34. }
35. else if( *info < *(p->getInfo()) )
36. p->setLeft( node );
37. else
38. p->setRight( node );
39. } // end of insert
Victoria333- Monstars
-
Posts : 267
Join date : 2013-05-12
Age : 35
Location : Victoria
Re: CS301 Assignment # 3 Solution Spring 2013
by Victoria333 Wed May 15, 2013 6:59 pm
IDEA NOT SOLUTION
- Code:
#include <stdlib.h>
#include <stdio.h>
typedef struct node_s
{
int value;
struct node_s* left;
struct node_s* right;
} *node;
node tree(int v, node l, node r)
{
node n = malloc(sizeof(struct node_s));
n->value = v;
n->left = l;
n->right = r;
return n;
}
void destroy_tree(node n)
{
if (n->left)
destroy_tree(n->left);
if (n->right)
destroy_tree(n->right);
free(n);
}
void preorder(node n, void (*f)(int))
{
f(n->value);
if (n->left)
preorder(n->left, f);
if (n->right)
preorder(n->right, f);
}
void inorder(node n, void (*f)(int))
{
if (n->left)
inorder(n->left, f);
f(n->value);
if (n->right)
inorder(n->right, f);
}
void postorder(node n, void (*f)(int))
{
if (n->left)
postorder(n->left, f);
if (n->right)
postorder(n->right, f);
f(n->value);
}
/* helper queue for levelorder */
typedef struct qnode_s
{
struct qnode_s* next;
node value;
} *qnode;
typedef struct { qnode begin, end; } queue;
void enqueue(queue* q, node n)
{
qnode node = malloc(sizeof(struct qnode_s));
node->value = n;
node->next = 0;
if (q->end)
q->end->next = node;
else
q->begin = node;
q->end = node;
}
node dequeue(queue* q)
{
node tmp = q->begin->value;
qnode second = q->begin->next;
free(q->begin);
q->begin = second;
if (!q->begin)
q->end = 0;
return tmp;
}
int queue_empty(queue* q)
{
return !q->begin;
}
void levelorder(node n, void(*f)(int))
{
queue nodequeue = {};
enqueue(&nodequeue, n);
while (!queue_empty(&nodequeue))
{
node next = dequeue(&nodequeue);
f(next->value);
if (next->left)
enqueue(&nodequeue, next->left);
if (next->right)
enqueue(&nodequeue, next->right);
}
}
void print(int n)
{
printf("%d ", n);
}
int main()
{
node n = tree(1,
tree(2,
tree(4,
tree(7, 0, 0),
0),
tree(5, 0, 0)),
tree(3,
tree(6,
tree(8, 0, 0),
tree(9, 0, 0)),
0));
printf("preorder: ");
preorder(n, print);
printf("\n");
printf("inorder: ");
inorder(n, print);
printf("\n");
printf("postorder: ");
postorder(n, print);
printf("\n");
printf("level-order: ");
levelorder(n, print);
printf("\n");
destroy_tree(n);
return 0;
}
Victoria333- Monstars
-
Posts : 267
Join date : 2013-05-12
Age : 35
Location : Victoria
Re: CS301 Assignment # 3 Solution Spring 2013
by Victoria333 Wed May 15, 2013 6:59 pm
A binary search tree or BST is abinary tree in symmetric order.
A binary search tree can:
Be empty
Have a key and not more than two other subtrees, which are called left subtree and right subtree.
A binary search tree is in symmetric order, it means:
Each node contains a key.
Each node’s key is smaller than all node’s keys in the right subtree and bigger than all node’s keys in the left subtree.
A binary search tree is also known as sorted or ordered binary tree.
A binary search tree can:
Be empty
Have a key and not more than two other subtrees, which are called left subtree and right subtree.
A binary search tree is in symmetric order, it means:
Each node contains a key.
Each node’s key is smaller than all node’s keys in the right subtree and bigger than all node’s keys in the left subtree.
A binary search tree is also known as sorted or ordered binary tree.
Victoria333- Monstars
-
Posts : 267
Join date : 2013-05-12
Age : 35
Location : Victoria
Re: CS301 Assignment # 3 Solution Spring 2013
by ChIntoo Wed May 15, 2013 7:01 pm
C binary search tree implementation
We can use a structureto model the binary search tree node a follows:
The node structure has three members:
We can use a structureto model the binary search tree node a follows:
| 1 2 3 4 5 6 | typedef struct node { int data; struct node* left; struct node* right; } node; |
The node structure has three members:
- data: stores node’s key, which is an integer. You can store a string, a pointerto a structure or(void*). For the sake of simplicity, we will use a binary search tree of integers.
- left: points to the left subtree.
- right: points to the right subtree
ChIntoo- Monstars
- Posts : 92
Join date : 2011-02-13
Re: CS301 Assignment # 3 Solution Spring 2013
by ChIntoo Wed May 15, 2013 7:02 pm
hahahah sab ka hi bura hal hy aik loadshading aur uper se assignments pe assignments lagta hy vu walun ko aur koi kam nhi hy........... [You must be registered and logged in to see this image.]
ChIntoo- Monstars
- Posts : 92
Join date : 2011-02-13
Re: CS301 Assignment # 3 Solution Spring 2013
by Victoria333 Wed May 15, 2013 7:03 pm
VU sucks....... Really disgusting management at VU........ One cannot dream of getting the degree...... Pls ALLAH help us !!!
Victoria333- Monstars
-
Posts : 267
Join date : 2013-05-12
Age : 35
Location : Victoria
Similar topics» CS504 Assignment # 2 Solution Spring 2013
» PSY101 Assignment # 1 Solution Spring 2013
» MGMT628 Assignment # 01 Solution Spring 2013
» CS501 Assignment # 03 Solution Spring 2013
» CS614 Assignment # 3 Solution Spring 2013
» PSY101 Assignment # 1 Solution Spring 2013
» MGMT628 Assignment # 01 Solution Spring 2013
» CS501 Assignment # 03 Solution Spring 2013
» CS614 Assignment # 3 Solution Spring 2013
Page 1 of 1
Permissions in this forum:
You cannot reply to topics in this forum
» Goorevi App
» AMERICA EARNS! - Gift Card App
» Kanba - Manage your Tasks
» Hemangiom'App
» MindfulMe - Mental Health App
» Learn Candlestick Patterns
» Woh Pagal Si Episode 52 to 62 - Top Pakistani Drama
» Nearu - share your socials