C++ // remove the smallest frequency tree from the list // Pre: l is a list cont
ID: 3683325 • Letter: C
Question
C++
// remove the smallest frequency tree from the list
// Pre: l is a list containing Trees of Frequencies.
// Post: the tree with smallest frequency has been removed // from the list.
// return: the Tree with smallest frequency in List l.
// Will return NULL if the list was empty.
TreeNode *remove_smallest(FrequencyList *l){
if (l == NULL) {
cerr << "Error in remove_smallest: given NULL list"
<< " Returning NULL, but anything could happen."
<< endl;
return NULL; }
// TODO: complete this function return NULL; }
Explanation / Answer
typedef TreeNode* Element;
typedef Frequency* TreeElement;
struct TreeNode {
TreeElement data; //stores a pointer to the data in this tree node
TreeNode *left; //reference to the left child tree
TreeNode *right; //reference to the right child tree
};
struct ListNode {
Element data; // stores a pointer to data in node
ListNode *next; // reference to next node in list
};
struct List {
ListNode *head; // reference to the first node in the list
int numElements; // the number of nodes in the list
};
struct Tree {
TreeNode *root;
};
struct FrequencyList {
List *I;
};
struct Frequency {
char data; // the character being represented
int count; // the number of occurrences of the character
};
TreeNode *remove_smallest(FrequencyList *I) {
if(I==Null)
{
cerr << "Error in remove_smallest: given NULL list"
return NULL;
}
else
{
newTree1 = remove_smallest(frequencies); // removes and returns smallest treeNode from list
newTree2 = remove_smallest(frequencies);
root->data->count = newTree1->data->count + newTree2->data->count;
root->left = newTree1;
root->right = newTree2;
root->data->data = 'D';
insert(newList, root); // inserts back into list
}
Tree * newTree = new Tree;
newTree->root = root;
return newTree;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.