Add a function member called levelByLevel() to traverse a tree level by level; t

Question

Add a function member called levelByLevel() to traverse a tree level by level; that is, first visit
the root, then all nodes on level 1 (children of the root), then all nodes on level2, and so on. Nodes on the same level should be visited in order from left to right. (Hint: Write a nonrecursive function, and use a queue of pointers.) In this problem, you can assume that the maximum number of nodes in a tree is less than 30. Note that you have to display the value of the visiting nodes for the grading purpose. The following shows the function prototype.

void BST::levelByLevel()

For the following sample tree, the result of the level by level traversal will be 10 5 15 2 9 20 17 30.


---------------------------------------------------------------
BST.cpp

#include
#include

using namespace std;

#include "BST.h"

//--- Definition of constructor
BST::BST()
: myRoot(0)
{}

bool BST::empty() const
{ return myRoot == 0; }


bool BST::search(const int & item) const
{
BinNode * locptr = myRoot;
bool found = false;
while (!found && locptr != 0)
{
if (item < locptr->data) // descend left
locptr = locptr->left;
else if (locptr->data < item) // descend right
locptr = locptr->right;
else // item found
found = true;
}
return found;
}


void BST::insert(const int & item)
{
BinNode * locptr = myRoot; // search pointer
BinNode * parent = 0; // pointer to parent of current node
bool found = false; // indicates if item already in BST
while (!found && locptr != 0)
{
parent = locptr;
if (item < locptr->data) // descend left
locptr = locptr->left;
else if (locptr->data < item) // descend right
locptr = locptr->right;
else // item found
found = true;
}
if (!found)
{ // construct node containing item
locptr = new BinNode(item);
if (parent == 0) // empty tree
myRoot = locptr;
else if (item < parent->data ) // insert to left of parent
parent->left = locptr;
else // insert to right of parent
parent->right = locptr;
}
else
cout << "Item already in the tree ";
}

-----------------------------------------------------------------------

BST.h


#include
using namespace std;

#ifndef BINARY_SEARCH_TREE
#define BINARY_SEARCH_TREE

class BST
{
public:
/***** Function Members *****/
BST();
bool empty() const;
bool search(const int & item) const;
void insert(const int & item);

private:
/***** Node class *****/
class BinNode
{
public:
int data;
BinNode * left;
BinNode * right;

// BinNode constructors
// Default -- data part is default int value; both links are null.
BinNode()
: left(0), right(0)
{}

// Explicit Value -- data part contains item; both links are null.
BinNode(int item)
: data(item), left(0), right(0)
{}

};// end of class BinNode declaration

/***** Data Members *****/
BinNode * myRoot;

}; // end of class declaration

#endif

------------------------------------------------------------------------

Tester.cpp

/

*----- treetester.cpp -----------------------------------------------------
Program for testing BST.
------------------------------------------------------------------------*/
#include
using namespace std;

#include "BST.h"

int main()
{
// Testing Constructor and empty()
BST intBST; // test the class constructor
cout << "Constructing empty BST ";
cout << "BST " << (intBST.empty() ? "is" : "is not") << " empty ";

// Testing insert
cout << " Now insert a bunch of integers into the BST."
" Try items not in the BST and some that are in it: ";
int number;
for (;;)
{
cout << "Item to insert (-999 to stop): ";
cin >> number;
if (number == -999) break;
intBST.insert(number);
}
cout << "BST " << (intBST.empty() ? "is" : "is not") << " empty ";

// Testing search()
cout << " Now testing the search() operation."
" Try both items in the BST and some not in it: ";
for (;;)
{
cout << "Item to find (-999 to stop): ";
cin >> number;
if (number == -999) break;
cout << (intBST.search(number) ? "Found" : "Not found") << endl;
}

Explanation / Answer

#include //As stated in the problem you will need a queue. The STL queue should work fine. #include //queue //List is more efficient #include void BST::levelByLevel() { cout right);//and this will continue until all nodes have been visited } } //I didn't test this, so if there are any problems, let me know

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.