Answered step by step
Verified Expert Solution
Question
1 Approved Answer
1 3 . 7 LAB: Iterable 2 - 3 - 4 treeIn this lab, the Tree 2 3 4 class is extended to support iteration
LAB: Iterable treeIn this lab, the Tree class is extended to support iteration with a rangebased for loop. Such support is provided via the implementation of an iterator that can iterate through the tree's keys in ascending order.An iterator is an object that maintains a pointer to a specific element in a collection and can move to the next element. Ex: A Tree iterator points to the tree's minimum key upon construction. The iterator can then move to the second to minimum key, then the third to minimum, and so on After moving past the tree's last key, the iterator can move no further.Overview of iterable objects in CThis lab requires implementation of a simplified iterator that:implements the dereference operator to return the key that the iterator currently points toimplements the preincrement operator to advance to the next key,supports copy construction and copy assignment, andsupports equality and inequality comparison.Rangebased for loops work on any class that implements the begin and end member functions such that each returns an iterator. So Tree implements begin and end Trees begin member function returns an instance of TreeIterator object representing the inclusive starting point of iteration: the tree's minimum key. Trees end member function returns an instance of TreeIterator object representing the exclusive ending point of iteration: one beyond the tree's maximum key.Step : Inspect the Nodeh fileInspect the Nodeh file. Access Nodeh by clicking on the orange arrow next to main.cpp at the top of the coding window. Nodeh is read only and has a complete implementation of a Node class for a tree node. Member variables are protected and so must be accessed through the provided getter and setter functions.Step : Inspect the TreeIterator.h fileInspect the TreeIterator.h file. The TreeIterator class is declared, but required member functions are not implemented. The implementation must satisfy the following requirements:Iteration never changes the tree in any wayIteration starts at the tree's minimum key and ends at the maximumConstruction occurs in worstcase Olog N timeDereferencing executes in worstcase O timeIncrementing executes in worstcase Olog N timeSpace complexity is worstcase Olog NFor simplicity, assume the tree is not changed by an outside source during the iterator's lifetime.Step : Understand requirement implicationsTo satisfy the requirements, the iterator must maintain a collection of node pointers. A node exists in the collection only if that node must be revisited at some point in time.The iterator must visit only the necessary nodes to deliver a key when the iterator is dereferenced. "Visiting" a node means calling any of that node's member functions. Ex: Suppose an iterator is built for the tree below. Then the iterator's operator is invoked to return key then is invoked to advance to key then is invoked to return key then is invoked to advance to key and then is invoked to return key The iterator should have only visited the highlighted nodes tree with nodes and keys. Root node's keys are and Root's left child has keys and Root's middle child has keys and Root's middle child has keys and Node has singlekeyed children: and Node has singlekeyed children: and Node has singlekeyed children: and Step : Implement the TreeIterator classImplement the TreeIterator to satisfy the complexity requirements mentioned above. Code in main.cpp adds random keys to a Tree object, then tests that the iterator properly iterates through all keys in ascending order. But time and space complexity aren't tested by code in main.cpp Rather, main.cpp only ensures that the iterator properly iterates through all keys.Most unit tests will fail if the iterator does not properly iterate through all the tree's keys in the correct order. So run code in develop mode and ensure that the test passes before submitting code.HintsAssume that Trees begin and end member functions return a TreeIterator object.Tree uses a template type, IteratorType, for the iterator type, allowing specialized iterators to be used for grading. So the declared return type for begin and end is actually IteratorType.The conceptual description of an iterator mentions that the iterator "points to a key. In the actual implementation, the "pointer" to a key is not an int The iterator must know if more keys exist in the node, and a direct pointer to the key integer itself does not include such information.
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started