Recursive and iterative handling of a binary search tree, Data Structure & Algorithms

This section prescribes additional exercise with the recursive and iterative handling of a binary search tree.

Adding to the Binary Search Tree Recursively

Add implementations to recursively add to the binary search tree. The public addRecursively method should examine the tree's root, placing the new addition there if the root is zero; otherwise,addRecursively will call the private method addRecursively, passing it the non-zero root of the tree. The recursive method will compare the new addition's data to that located at the current root. If the data is less and the subsequent left pointer is zero, the new addition can be stored there; otherwise, the function calls itself recursively, passing the non-zero left pointer to itself. Data in the new addition greater than that in the current root is handled similarly with the right pointer.

Displaying the Binary Search Tree Iteratively

Add the implementation to iteratively write the binary search tree. The iteration will move down the tree, following successive left pointers. The first node with zero for a left pointer may be written, as there can be no data which comes before it. The iteration which moves down the tree will need to stack each current pointer so that it may unwind the downward traversal of the tree. Use theTemplateNode, TemplateList and TemplateStack implementations from the previous homework for this purpose. Starting with a current pointer initialized to the root of the tree, replace the current pointer with each non-zero left pointer encountered; push current on the stack before each replacement. When a left pointer of zero is encountered, display that node's data and move to the right. When a right pointer of zero is assigned to current, pop to move back up the tree, write a node, then move right again. Become familiar with this behavior in a diagram before coding.

Destroying the Binary Search Tree

Implement a recursive erase method. Add the following prototypes to the tree's class definition.

public:

voideraseRecursively

                  (void);

private:

voideraseRecursively

                  (node* currentRoot);

The bodies of these methods will be identical in form to those for writing recursively.

Add the following code to the else clause in the main function. Note the use of the recursive erase and add methods and the iterative write.

cout<< "Press to continue...\n";

cin.get();

customerTree.eraseRecursively();

cout<< "Recursive Tree Listing After Erase:" <

infile.clear();  // restore stream state so I/O may proceed

infile.seekg (0);  // seek "get" to file start (byte #0)

while (!infile.eof())

customerTree.addRecursively (new node(infile));  // recursive add

cout<< "Iterative Listing of Recursive Additions\n";

customerTree.writeIteratively (cout);

infile.close();

Note that one of the erase methods could be called by the destructor to perform its function as well.

Test the algorithms thoroughly by modifying the data file several times.

Posted Date: 4/2/2013 3:50:13 AM | Location : United States







Related Discussions:- Recursive and iterative handling of a binary search tree, Assignment Help, Ask Question on Recursive and iterative handling of a binary search tree, Get Answer, Expert's Help, Recursive and iterative handling of a binary search tree Discussions

Write discussion on Recursive and iterative handling of a binary search tree
Your posts are moderated
Related Questions
Q. Explain quick sort? Sort the given array using quick sort method. 24 56 47 35 10 90 82 31

DEPTH FIRST SEARCH (DFS) The approach adopted into depth first search is to search deeper whenever possible. This algorithm frequently searches deeper through visiting unvisite

Containers Introduction Simple abstract data types are useful for manipulating simple sets of values, such as integers or real numbers however more complex abstract data t

Q. Using array to execute the queue structure, write down an algorithm/program to (i) Insert an element in the queue. (ii) Delete an element from the queue.

Graphs are data structures which consist of a set of vertices & a set of edges which connect the vertices. A graph where the edges are directed is called directed graph. Or else, i

In the earlier unit, we have discussed about the arrays. Arrays are data structures of fixed size. Insertion & deletion involves reshuffling of array elements. Thus, arraymanipulat

Define null values.  In some cases a particular entity might not have an applicable value for an attribute or if we do not know the value of an attribute for a particular entit

The location of a node in a binary search tree is defined as a string such as LLRRL, which represents the node that you find by starting at the root, and traversing Left, traverse

Construct a B+ tree for the following keys, starting with an empty tree.  Each node in the tree can hold a maximum of 2 entries (i.e., order d = 1). Start with an empty root nod

Worst Case: For running time, Worst case running time is an upper bound with any input. This guarantees that, irrespective of the type of input, the algorithm will not take any lo