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

Assignment Help:

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.


Related Discussions:- Recursive and iterative handling of a binary search tree

Sorted list using binary search technique, Write an algorithm for searching...

Write an algorithm for searching a key from a sorted list using binary search technique 1.   if (low > high) 2.     return (-1) 3.    mid = (low +high)/2; 4    .if ( X

Representation of a sparse matrix, Let us assume a sparse matrix from stora...

Let us assume a sparse matrix from storage view point. Assume that the entire sparse matrix is stored. Then, a significant amount of memory that stores the matrix consists of zeroe

What is a linear array, What is a linear array? An array is a way to re...

What is a linear array? An array is a way to reference a series of memory locations using the similar name. Every memory location is shown by an array element. An  array elemen

Addressing modes, Compare zero-address, one-address, two-address, and three...

Compare zero-address, one-address, two-address, and three-address machines by writing programs to compute: Y = (A – B X C) / (D + E X F) for each of the four machines. The inst

Applications of binary trees, In computer programming, Trees are utilized ...

In computer programming, Trees are utilized enormously. These can be utilized for developing database search times (binary search trees, AVL trees, 2-3 trees, red-black trees), Gam

Array implementation of a multiqueue, Program gives the program segment by ...

Program gives the program segment by using arrays for the insertion of an element to a queue into the multiqueue. Program: Program segment for the insertion of any element to t

Example which cause problems for hidden-surface algorithms, Example which c...

Example which cause problems for some hidden-surface algorithms Some special cases, which cause problems for some hidden-surface algorithms, are penetrating faces and cyclic ov

Numerical - algorithm, Q. What is the smallest value of n such that an algo...

Q. What is the smallest value of n such that an algorithm whose running time is 100n2 runs faster than an algorithm whose running time is 2n on the same machine.    A n

State about the bit string, State about the Bit String Carrier set of...

State about the Bit String Carrier set of the Bit String ADT is the set of all finite sequences of bits, including empty strings of bits, which we denote λ. This set is {λ, 0

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd