Please send questions to
st10@humboldt.edu .
//---------------------------------------------------------------
// File: test_binary_tree.cpp
// Name: Sharon M. Tuttle
// last modified: 4-7-04
//
// Purpose: tester for template class binary_tree<Item>
//--------------------------------------------------------------
#include <iostream>
#include "binary_tree.h"
using namespace std;
int main()
{
// set-up declarations
binary_tree<int> numTree;
binary_tree<string> nameTree;
// tests and associated cout's
cout << endl;
cout << "Testing template class binary_tree..." << endl;
cout << endl;
nameTree.create_root("Sharon");
nameTree.add_left("Katherine");
nameTree.add_right("Thomas");
nameTree.print_tree(1);
cout << "1's mean test passed, 0's mean test failed:" << endl;
cout << "-------------------------------------------" << endl;
cout << (numTree.get_size( ) == 0) << endl;
cout << (nameTree.get_size( ) == 3) << endl;
cout << endl;
cout << (numTree.is_empty( ) == true) << endl;
cout << (nameTree.is_empty( ) == false) << endl;
numTree.create_root(5);
cout << endl;
cout << (numTree.get_size( ) == 1) << endl;
cout << (numTree.is_empty( ) == false) << endl;
cout << (numTree.retrieve( ) == 5) << endl;
cout << (numTree.is_root( ) == true) << endl;
cout << (numTree.is_leaf( ) == true) << endl;
cout << (numTree.has_parent( ) == false) << endl;
cout << (numTree.has_left_child( ) == false) << endl;
cout << (numTree.has_right_child( ) == false) << endl;
char dummy;
cout << "TEST SET 1 COMPLETE; root added " << endl
<< " type any character to continue: " << endl;
cin >> dummy;
numTree.add_left(13);
cout << endl;
cout << (numTree.get_size( ) == 2) << endl;
cout << (numTree.is_empty( ) == false) << endl;
cout << (numTree.retrieve( ) == 5) << endl;
cout << (numTree.is_root( ) == true) << endl;
cout << (numTree.is_leaf( ) == false) << endl;
cout << (numTree.has_parent( ) == false) << endl;
cout << (numTree.has_left_child( ) == true) << endl;
cout << (numTree.has_right_child( ) == false) << endl;
cout << "TEST SET 2 COMPLETE; left child added" << endl
<< " type any character to continue: " << endl;
cin >> dummy;
numTree.add_right(20);
cout << endl;
cout << (numTree.get_size( ) == 3) << endl;
cout << (numTree.is_empty( ) == false) << endl;
cout << (numTree.retrieve( ) == 5) << endl;
cout << (numTree.is_root( ) == true) << endl;
cout << (numTree.is_leaf( ) == false) << endl;
cout << (numTree.has_parent( ) == false) << endl;
cout << (numTree.has_left_child( ) == true) << endl;
cout << (numTree.has_right_child( ) == true) << endl;
cout << "TEST SET 3 COMPLETE; right child added" << endl
<< " type any character to continue: " << endl;
cin >> dummy;
numTree.shift_left( );
cout << endl;
cout << (numTree.get_size( ) == 3) << endl;
cout << (numTree.is_empty( ) == false) << endl;
cout << (numTree.retrieve( ) == 13) << endl;
cout << (numTree.is_root( ) == false) << endl;
cout << (numTree.is_leaf( ) == true) << endl;
cout << (numTree.has_parent( ) == true) << endl;
cout << (numTree.has_left_child( ) == false) << endl;
cout << (numTree.has_right_child( ) == false) << endl;
cout << "TEST SET 4 COMPLETE; tried to shift left" << endl
<< " type any character to continue: " << endl;
cin >> dummy;
numTree.shift_to_root( );
cout << endl;
cout << (numTree.get_size( ) == 3) << endl;
cout << (numTree.is_empty( ) == false) << endl;
cout << (numTree.retrieve( ) == 5) << endl;
cout << (numTree.is_root( ) == true) << endl;
cout << (numTree.is_leaf( ) == false) << endl;
cout << (numTree.has_parent( ) == false) << endl;
cout << (numTree.has_left_child( ) == true) << endl;
cout << (numTree.has_right_child( ) == true) << endl;
cout << "TEST SET 5 COMPLETE; shifted up to root" << endl
<< " type any character to continue: " << endl;
cin >> dummy;
numTree.shift_right( );
cout << endl;
cout << (numTree.get_size( ) == 3) << endl;
cout << (numTree.is_empty( ) == false) << endl;
cout << (numTree.retrieve( ) == 20) << endl;
cout << (numTree.is_root( ) == false) << endl;
cout << (numTree.is_leaf( ) == true) << endl;
cout << (numTree.has_parent( ) == true) << endl;
cout << (numTree.has_left_child( ) == false) << endl;
cout << (numTree.has_right_child( ) == false) << endl;
cout << "TEST SET 6 COMPLETE; tried to shift rightt" << endl
<< " type any character to continue: " << endl;
cin >> dummy;
numTree.change(21);
cout << endl;
cout << (numTree.get_size( ) == 3) << endl;
cout << (numTree.is_empty( ) == false) << endl;
cout << (numTree.retrieve( ) == 21) << endl;
cout << (numTree.is_root( ) == false) << endl;
cout << (numTree.is_leaf( ) == true) << endl;
cout << (numTree.has_parent( ) == true) << endl;
cout << (numTree.has_left_child( ) == false) << endl;
cout << (numTree.has_right_child( ) == false) << endl;
cout << "TEST SET 7 COMPLETE; tried to change node's data" << endl
<< " type any character to continue: " << endl;
cin >> dummy;
numTree.add_left(17);
numTree.add_right(25);
cout << endl;
cout << (numTree.get_size( ) == 5) << endl;
cout << (numTree.is_empty( ) == false) << endl;
cout << (numTree.retrieve( ) == 21) << endl;
cout << (numTree.is_root( ) == false) << endl;
cout << (numTree.is_leaf( ) == false) << endl;
cout << (numTree.has_parent( ) == true) << endl;
cout << (numTree.has_left_child( ) == true) << endl;
cout << (numTree.has_right_child( ) == true) << endl;
cout << "TEST SET 8 COMPLETE; added 2 kids to child" << endl
<< " type any character to continue: " << endl;
cin >> dummy;
numTree.shift_to_root( );
numTree.remove_right_subtree( );
cout << endl;
cout << (numTree.get_size( ) == 2) << endl;
cout << (numTree.is_empty( ) == false) << endl;
cout << (numTree.retrieve( ) == 5) << endl;
cout << (numTree.is_root( ) == true) << endl;
cout << (numTree.is_leaf( ) == false) << endl;
cout << (numTree.has_parent( ) == false) << endl;
cout << (numTree.has_left_child( ) == true) << endl;
cout << (numTree.has_right_child( ) == false) << endl;
cout << "TEST SET 8 COMPLETE; tried to delete rt subtree" << endl
<< " type any character to continue: " << endl;
cin >> dummy;
numTree.remove_left_subtree( );
cout << endl;
cout << (numTree.get_size( ) == 1) << endl;
cout << (numTree.is_empty( ) == false) << endl;
cout << (numTree.retrieve( ) == 5) << endl;
cout << (numTree.is_root( ) == true) << endl;
cout << (numTree.is_leaf( ) == true) << endl;
cout << (numTree.has_parent( ) == false) << endl;
cout << (numTree.has_left_child( ) == false) << endl;
cout << (numTree.has_right_child( ) == false) << endl;
cout << "TEST SET 10 COMPLETE; tried to rm left subtree" << endl
<< " type any character to continue: " << endl;
cin >> dummy;
numTree.add_left(3);
numTree.shift_left( );
numTree.add_left(1);
numTree.add_right(4);
numTree.shift_to_root( );
numTree.add_right(7);
numTree.shift_right( );
numTree.add_left(6);
numTree.add_right(9);
numTree.shift_to_root( );
cout << endl;
cout << (numTree.get_size( ) == 7) << endl;
cout << (numTree.is_empty( ) == false) << endl;
cout << (numTree.retrieve( ) == 5) << endl;
cout << (numTree.is_root( ) == true) << endl;
cout << (numTree.is_leaf( ) == false) << endl;
cout << (numTree.has_parent( ) == false) << endl;
cout << (numTree.has_left_child( ) == true) << endl;
cout << (numTree.has_right_child( ) == true) << endl;
cout << "TEST SET 11 COMPLETE; tried to add many nodes" << endl
<< " type any character to continue: " << endl;
cin >> dummy;
numTree.clear_tree( );
cout << endl;
cout << (numTree.get_size( ) == 0) << endl;
cout << (numTree.is_empty( ) == true) << endl;
cout << (numTree.has_parent( ) == false) << endl;
cout << (numTree.has_left_child( ) == false) << endl;
cout << (numTree.has_right_child( ) == false) << endl;
cout << "TEST SET 12 COMPLETE; tried to clear tree" << endl
<< " type any character to continue: " << endl;
cin >> dummy;
numTree.create_root(5);
numTree.add_left(3);
numTree.shift_left( );
numTree.add_left(1);
numTree.add_right(4);
numTree.shift_to_root( );
numTree.add_right(7);
numTree.shift_right( );
numTree.add_left(6);
numTree.add_right(9);
numTree.shift_to_root( );
cout << endl;
cout << (numTree.get_size( ) == 7) << endl;
cout << (numTree.is_empty( ) == false) << endl;
cout << (numTree.retrieve( ) == 5) << endl;
cout << (numTree.is_root( ) == true) << endl;
cout << (numTree.is_leaf( ) == false) << endl;
cout << (numTree.has_parent( ) == false) << endl;
cout << (numTree.has_left_child( ) == true) << endl;
cout << (numTree.has_right_child( ) == true) << endl;
cout << "TEST SET 13 COMPLETE; filled tree UP again" << endl
<< " type any character to continue: " << endl;
cin >> dummy;
numTree.print_tree(3);
// OK, I CAN build a tree this way. But can I TRAVERSE it?
// (and can the students?)
// can get to root, no problem:
numTree.shift_to_root();
// IF this were a binary search tree...?
cout << endl;
cout << "can I binary-search this tree? YES!" << endl;
int target;
cout << "what number would you like to search for?: " << endl;
cin >> target;
numTree.shift_to_root( );
while ( (!numTree.is_leaf( )) && (numTree.retrieve( ) != target) )
{
if (target < numTree.retrieve())
{
numTree.shift_left( );
}
else
{
numTree.shift_right( );
}
}
// IF get here --- have either FOUND item or are AT a leaf.
// (or, target may be AT a leaf...!)
if (numTree.retrieve( ) == target)
{
cout << target << " IS in tree!" << endl;
}
else
{
cout << target << " is NOT in tree!" << endl;
}
cout << "TEST SET 14 COMPLETE; searched tree" << endl
<< " type any character to continue: " << endl;
cin >> dummy;
numTree.shift_to_root( );
numTree.shift_right( );
numTree.shift_right( );
binary_tree<int> numTree2, numTree3;
numTree2.create_root(100);
numTree2.add_left(101);
numTree2.add_right(102);
cout << endl;
cout << (numTree2.get_size( ) == 3) << endl;
numTree3.create_root(200);
numTree3.add_left(201);
numTree3.add_right(202);
cout << (numTree3.get_size( ) == 3) << endl;
// ARE at a leaf in numTree...
numTree.add_left_subtree(numTree2);
numTree.add_right_subtree(numTree3);
cout << endl;
cout << (numTree.get_size( ) == 13) << endl;
cout << (numTree.is_empty( ) == false) << endl;
cout << (numTree.is_root( ) == false) << endl;
cout << (numTree.is_leaf( ) == false) << endl;
cout << (numTree.has_parent( ) == true) << endl;
cout << (numTree.has_left_child( ) == true) << endl;
cout << (numTree.has_right_child( ) == true) << endl;
numTree.shift_left( );
cout << (numTree.retrieve( ) == 100) << endl;
numTree.shift_to_root( );
numTree.shift_right( );
numTree.shift_right( );
numTree.shift_right( );
cout << (numTree.retrieve( ) == 200) << endl;
cout << "BEFORE final print_tree call..." << endl;
numTree.print_tree(4);
cout << "SHOULD be finished!" << endl;
return EXIT_SUCCESS;
}