this is basically like fill in the blank but for code using a template in windows c++ in visual studio for the mouth the work I need help with is the lab code which i believe is in the header part of the code i hope this explains this well enough for more info check the files its two this time around

Binary Search Tree or BST and

Huffman Compression

Data Structures and Algorithms Lab 8: Huffman.h The Scenario This is it. The final lab of DSA. Despite all the hats you’ve worn in this class, all the adventures you’ve gone on, there is one common thread to each of these lab adventures. And that thread is that it’s always been you working on these labs, of course! You’ve worked through a variety of problems and I want to thank you for all of your hard work this month! For the final lab, you will be assuming the role of yourself—we will be looking at something called Huffman Compression. Huffman Compression is a way of using Binary Search Trees organized by weight (in our case, frequency) as a means of compressing data. i.e. Let’s say you have a text document containing the entirety of J.R.R. Tolkien’s “The Hobbit”. You could certainly store it the uncompressed way with 8 bits per ASCII character in the document. But what if you want it to take up less space on your hard disk? How about compressing it for sending out via e-mail? Huffman compression is one solution that allows for lossless compression of files. Take for example, a file filled with 115 characters: All of which are ‘a’, ‘Z’, and ‘Q’. There are 100 ‘a’s, 10 ‘Z’s, and 5 ‘Q’s. Each ASCII character normally takes up 8 bits of storage. The goal of Huffman Compression is to reduce this from 920 bits down to something less substantial. Below is the tree generated for the compression. You may be wondering what each number is. Each leaf-node (node with no children) is the document’s character, followed by its frequency in the document. A 0 is assigned to each left path and a 1 is assigned to each right path from the root. This will be used to generate our new encoding table. As you can see in the figure above, ‘a’ would have a code that consists of a single bit: 0, while the less-common ‘Q’ and ‘Z’ would both be comprised of 2-bit codes: 11 and 10 respectively. This reduces the total size of the document to 120 bits instead of the original 920 bits. This is the power of Huffman Compression! For this lab, you’ll be generating a tree along with a list of the leaves, a frequency table consisting of the relative frequency of each character in a document, generating the encoding table, and doing other general tasks associated with Huffman Compression. In this lab, the comments in the code are a little bit more thorough than normal, so be sure to read them all very carefully! What To Do… Open Huffman.h. There will be instructions written in the comments on what is expected. Below is the gist of each function and variable… Variables: mFileNameThe name of the file for reading and writing. mFrequencyTableStores the frequency of each character. mLeafListContains all of the leaf nodes—the characters. mRootThe root of the Huffman tree! Set in GenerateTree instead of constructor. mEncodingTableThe encoding table generated from the tree. Functions: Huffman ConstructorTakes a file name and sets it. mRoot is set in GenerateTree instead, however. GenerateFrequencyTableOpens the file (defined in the variables!) and specifies it is in binary mode. Stores the count of the file in the final position of mFrequencyTable, and reads the file one byte at a time, incrementing each character’s position in mFrequencyTable. Don’t forget to close the file when you’re done! GenerateLeafListLoops through mFrequencyTable, creating new huff nodes and putting them into mLeafList for each character with a frequency greater than 0. GenerateTreeCreate a priority queue and use HuffCompare in it for the comparison crieteria. It will store HuffNode*s. Next, add all the values from mLeafList in. Now comes the tree generating part… While the queue has more than 1 node left, set two temporary pointers to the top two nodes. Pop them off of mLeafList and create a parent node for the two, setting the 1st node as left and the 2nd as the right. Then make the parent’s value -1 and set its frequency to the sum of its two children’s frequency. Set both node 1 and node 2’s parent to be the created parent node.Insert that new node into the priority queue. Once you finish, take a sip of coffee, tea, or water—you deserve it! Finally, Once there is only one node left in the queue, you can set that node to be mRoot. GenerateEncodingTableNow that your tree is made, you will write the code to generate the encoding table. Cycle through each node in mLeafList and move up from each all the way to the root. Keep track of whether each node is a left or a right child of its parent and at the end, reverse the sequence of bits. (This will show the route you must take from mRoot to the leaf.) Remember, the encoding table’s position is based on the value of each leaf. ClearTreeCall the helper function on mRoot and then afterwards, set mRoot to null. ClearTree (Helper!)Accepts a single HuffNode*. Recursive helper function for ClearTree. Recurses through both the left and right branches of the Tree and cleans up all dynamically allocated memory. CompressTakes a single parameter—the output File to write the data to. First, the function calls the functions you’ve written, creating the frequency table, leaf list, tree, and encoding table. Next, creates a Bit Output Stream (BitOStream) and supplies it the header, along with the file’s size. Next, opens the input file as an ifstream in binary mode. After this, does the actual compression—replaces every character in the original file with its bit-code from mEncodingTable. After all is said and done, closes both streams and Clears the Tree. If you used any dynamically allocated memory for this, deletes that as well. DecompressDoes the opposite of Compress! Accepts the file to write the uncompressed data to. mFileName will be the compressed file. Creates a BitIStream and reads the frequency table, then generates the leaft list, tree, and creates a stream for output in binary mode. Next, creates a char for writing and a temporary Boolean for reading into and traversing using. Next, create a node pointer to bookmark your place in the list—i.e. starting at mRoot. Go through the compressed file one bit at a time next, traversing through the tree. Once you reach a leaf, you know you’ve finished with the current bit and can write the value to the file. Next, close the streams and clear the tree. Tips, Tricks, and Resources · Functions/Data Members available in the priority queues class can be found on the Cplusplus.com documentation: · http://www.cplusplus.com/reference/queue/priority_queue/ · Don’t be scared to draw your trees out if needbe! · Thank you for all of your hard work in lab this month! Plagiarism Plagiarism and Academic Dishonesty are considered a very serious offense in this class and can have a range of consequences including suspension, and in very serious cases, expulsion. If you either share your code or copy someone else’s code, you will be given a 0 on your lab and can face further disciplinary action. In other words, don’t cheat please! Data Structures and Algorithms Lab 7: BST.h The Scenario Throughout your time in this class, you’ve had many different roles. You’ve been a painter, a dragon slayer, and a successful programmer. You drive to your favorite mountain peak to reflect upon your time and look out across the land. You’ve searched for answers. If only there was a simple way to find the answers to all of life’s questions. And better yet, a way of indexing all of those answers. Something that makes the search not quite so lengthy. What better way than a Binary Search Tree? A Binary Search Tree (BST) is, quite simply put, a Binary Tree that is also a Search Tree. To begin, let’s start with what a Binary Tree is. A Binary Tree is the same as a Linked List with one major difference: each node has two subsequent nodes instead of one. In fact, if you should choose, you could call a Linked List a Unary Tree and that would be an accurate name. Having two subsequent nodes instead of one creates a sprawling structure that is similar in shape to a tree when drawn out. See the illustration later in this lab. A Search Tree data structure is any Tree that is organized in a predictable way. In the illustration below, the BST is organized such that lower numbers are always on the left and larger are always on the right. This makes it incredibly easy to find values in the tree. Together, a Binary Tree and a Search Tree form a Binary Search Tree—i.e. a Binary Tree that is organized to make finding values much easier and use less processing power. Below is an illustration of a Binary Search Tree: As was mentioned, each node’s data determines its placement within the tree. Nodes to the left of the current node are all lower values than the current node while nodes to the right are all higher values. Further than this, no node within the entire left subtree of a current node will be greater than it’s value. This holds true for the right and being greater as well. Using this logic, try to find your way to the value “23” from the root. You will go left from 50 because 23 is lower than 50. The current node is now 30. 23 is less still so you will go left again to find yourself at a node with the value of 20. 23 is bigger than 20, so you will go right to the node with a value of 23. Hey, you found it! As you can see, this is much more efficient than a linked list or unorganized tree would be, where you would potentially have to examine every node. Also worth noting, and the reason I included node 36, is that a BST may have nodes that don’t make it a “balanced” tree. Nodes may exist at the end of any arrow. What To Do… Open BST.h. There will be instructions written in the comments on what is expected. Below is the gist of each function and variable… Variables: mRootThe root of the tree. The “Starting Point”, so to speak. dataThe data stored in each node. leftThe node to the left. (i.e. a node of lesser value.) rightThe node to the right. (i.e. a node of greater value.) Functions: Node ConstructorTakes a data parameter and sets the node’s data equal to it. Left and Right are initialized appropriately as well. BST ConstructorCreates an empty tree. (i.e. a tree with absolutely no nodes.) Initializes variable(s) where needed.