Solution Idea!
#include <bits/stdc++.h> using namespace std; class HeapNode_Min { // Tree node of Huffman public: //Add data members here. char d; unsigned f; HeapNode_Min *l, *r; HeapNode_Min(char d, unsigned f = -1) { //Complete the body of HeapNode_Min function this->d = d; this->f = f ; this->l = NULL; this->r = NULL; } }; class Analyze { // two heap nodes comparison public: bool operator()(HeapNode_Min* l, HeapNode_Min* r) { //add return before statement and statement is completed. return (l->f > r->f); //Complete this statement } }; void display_Codes(HeapNode_Min* root, string s) // To print codes of huffman tree from the root. { if (!root) return; if (root->d != '$') cout root->d "\t: " s "\n"; display_Codes(root->l, s + "0"); display_Codes(root->r, s + "1"); //Complete this statement by passing arguments } void HCodes(char data[], int freq[], int s) // builds a Huffman Tree { HeapNode_Min *t,*r, *l ; // top, right, left priority_queue<HeapNode_Min*, vector<HeapNode_Min*>, Analyze> H_min; int a=0; while (a<s){H_min.push(new HeapNode_Min(data[a], freq[a])); ++a;} while (H_min.size() != 1) { l = H_min.top(); H_min.pop(); r = H_min.top(); H_min.pop(); t = new HeapNode_Min('$', r->f + l->f); t->r = r; t->l = l; H_min.push(t); } display_Codes(H_min.top(), ""); } int main() { int frequency[] = { 3, 6, 11, 14, 18, 25 }; char alphabet[] = { 'A', 'L', 'O', 'R', 'T', 'Y' }; //Complete this statement by passing data type to both sizeof operators int size_of = sizeof(alphabet) / sizeof(*alphabet); cout"Alphabet"":""Huffman Code\n"; cout"--------------------------------\n"; //Call Huffman_Codes function. HCodes(alphabet, frequency, size_of); return 0; }SOLVED CS301 Assignment 2 Solution and Discussion Spring 2020
-
Re: CS301 Assignment 2 Solution and Discussion
Assignment No. 02
Spring 2020
CS301- Data Structures
Total Marks: 20Due Date: 17-Jun-2020
Instructions
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:
The assignment is submitted after due date.
The submitted assignment is other than .CPP file.
The submitted code does NOT compile.
The submitted assignment does NOT open or file is corrupted.
The assignment is copied (from other student or ditto copy from handouts or internet).Uploading instructions
For clarity and simplicity, you are required to upload/submit only one .CPP file.Note: Use only Dev-C++ IDE.
Objectives
The objectives of this assignment are; To make you familiar of programming with Tree data structure
To traverse Binary Search Tree (BST) using different techniques
To perform some basic operations on BSTFor any query about the assignment, contact at [email protected]
Good Luck!
Total Marks: 20
Problem Statement:
As you know, Binary Search Tree (BST) has property that on the addition of a node in the tree, we compare it with root node. If new node is less than root node, it can be added to the left sub-tree. Otherwise, it will be added to the right sub-tree. So, the BST will have numbers (or nodes) less than the root in the left sub-tree and the numbers greater than the root will be in the right sub-tree.
Following is a snapshot of Binary Search Tree (BST).
You are required to develop a C++ program implementing Binary Search Tree (BST) data structure for the above scenario.
For this you need to;
- Construct Binary Search Tree, based upon above given tree data
- Calculate minimum node (or number), maximum node, height and total number of nodes for BST
Details:
Your solution must contain a tree node class named as TNode, insert() method, buildTree() method, minNode() method, maxNode() method, treeHeight() method and countNodes() method. You should call BuildTree() method in main() method and call insert() method inside BuildTree() method so that insert() method can actually add nodes in BST.
You must call the above-mentioned methods from main to calculate minimum node, maximum node, height and total number of nodes for the BST.
Remember, the height of root node is 1 while depth or level of root node is 0 in tree.
Required Output:
Note:
Make sure to follow class name, method names and variable/objects names as mentioned above in the scenario. Moreover, your solution must be according to the Required Output. Otherwise, you will get Zero marks.
Lectures Covered: Lecture No. 09 to 16.
Deadline: Your assignment must be uploaded / submitted on or before, Jun 17, 2020. -
#include<iostream> using namespace std; class TNode{ private: node* root; public: TNode(); int isEmpty(); void buildTree(int item); void insert(int item,node *,node *); void minNode(node*); void maxNode(node*); int countNodes(node*); int treeHeight(node*); void displayBinTree(); }; TNode::TNode(){ root = NULL; } int TNode::isEmpty() { return (root == NULL); } void TNode::buildTree(int item){ node *p = new node; node *parent; cout <<"Insert node in BST :" << item <<endl; insert(item,p,parent); } void TNode::insert(int item,node * p,node * parent){ p->data=item; p->left=NULL; p->right=NULL; parent=NULL; if(isEmpty()){ root = p; } else{ node *ptr; ptr = root; while(ptr != NULL){ parent = ptr; if(item > ptr->data){ ptr = ptr->right; } else{ ptr = ptr->left; } } if(item < parent->data){ parent->left = p; } else{ parent->right = p; } } } void TNode::minNode(node* p){ while (p->left != NULL){ p = p->left; } cout << "Minimum value : " << p->data <<endl; } void TNode::maxNode(node* p){ while (p->right != NULL){ p = p->right; } cout << "Maximum value : " << p->data <<endl; } int TNode::countNodes(node* p){ int node = 1; //Node itself should be counted if (p == NULL){ return 0; } else{ node += countNodes(p->left); node += countNodes(p->right); return node; } } int TNode::treeHeight(node* p){ if (p == NULL) { return 0; } else { int left_side = treeHeight(p->left); int right_side = treeHeight(p->right); if (left_side > right_side) { return(left_side + 1); } else { return(right_side + 1); } } } void TNode::displayBinTree(){ cout <<endl<<endl; minNode(root); maxNode(root); cout <<"Height of BST : "<<treeHeight(root); cout <<"\nTotal nodes : "<<countNodes(root); } int main(){ TNode b; int data[] = {7,2,9,1,5,14}; cout <<"Constructing Binary Search Tree by Inserting Nodes One by One "<<endl; cout <<"------------------------------------------------------------- "<<endl; int arrSize = sizeof(data)/sizeof(data[0]); for(int i = 0; i < arrSize; i++) { b.buildTree(data[i]); } }


100% Off on Your FEE Join US! Ask Me How?


