Iterative Methods
This section looks at the functions that are implemented iteratively (or the iterative version of the functions)
Constructor
When we create our tree, we are going to start with an empty tree. Thus, our constructor simply needs to initialize the data member to nullptr.
Insert - Iterative version
This function will insert data into the tree. There are two ways to implement this function, either iteratively or recursively. We will start by looking at the iterative solution. In this situation, we begin by taking care of the empty tree situation. If the tree is empty we simply create a node and make root_ point to that only node. Otherwise, we need to go down our tree until we find the place where we must do the insertion and then create the node.
Search - Iterative version
The key operation that is supported by a binary search tree is search. For our purposes we will simply look at finding out whether or not a value is in the tree or not. The search operation should never look at the entire tree. The whole point of the binary search tree is to make this operation fast. We should search it so that we can eliminate a portion of the tree with every search operation.
To do this we start at the root and compare that node's data against what we want. If it matches, we have found it. If not, we go either left or right depending on how data relates to the current node. If at any point we have an empty tree (ie the pointer we are using for iterating through the tree becomes nullptr) we stop the search and return false. If we find a node that matches we stop and return true.
Breadth First Print
Writing a breadth-first traversal involves using the queue data structure to order what nodes to deal with next. You want to deal with the nodes from top to bottom left to right, and thus you use the queue to order the nodes. Here is an example of how we will do this.
We begin by declaring a queue (initially empty)
Prime the Queue
We start prime the queue by putting the root into the queue. In this example, we always check to ensure no nullptrs are ever added to the queue. Alternatively we allow the addition of nullptrs and decide how to deal with them when we dequeue.
Dequeue front of node and process it by adding its non-nullptr children into the queue, print the node
Continue by dequeuing front node and processing it in same manner
Repeat again as 25 only has a right child only it is added
Repeat once again with 5 which has no children thus nothing is added to queue
Repeat again with 15 (also no children)
Repeat with 35 and add its children
Continue by removing 30
And one more time with 40
At this point queue is empty and thus, we have completed our breadthfirst print of the tree.
In code form, this is how we will write our code (we assume we have a template queue available:
Last updated