-
BST Tree
How can I check to see if my program is building the tree correctly? I eventually want to
add a preOrder() function, inOrder() function, postOrder() function, and a levelOrder()
function transversals.
#include<iostream>
#include<iomanip>
#include<fstream>
#include <cctype> // defines isalpha() function
#include<string>
#include"TreeImplementation.cpp"
using namespace std;
int main()
{
node structnode;
btree bt;
int num=0;
char chr;
int count=0;
ifstream fin("input.txt");
ofstream fout("output1.txt");
fin>>num;
fin>>chr;
while(fin)
{
bt.insert(num);
bt.search(num);
fout<<num;
count++;
fout<<"Step: "<<count<<" "<<"Data Value = "<<num<<" "<<"Activity Signal = "<<chr<<endl;
fout<<"Preorder Transversal = "<<endl<<endl;
fout<<"Inorder Transversal = "<<endl<<endl;
fout<<"Post order Transversal = "<<endl<<endl;
fout<<"Level by Level Transversal = "<<endl<<endl;
fout<<"Total Number of nodes = "<<count<<endl<<endl;
fin>>num;
fin>>chr;
}
return 0;
}
#include"Treeheader.h"
//Constructor
///////////////////////////////////////////////////////////////////////
btree::btree()
{
root=NULL;
}
///////////////////////////////////////////////////////////////////////
/*btree::~btree()
{
destroy_tree(root);
}
*/
//Destriy tree function
//////////////////////////////////////////////////////////////////////
void destroy_tree(node *leaf)
{
if(leaf!=NULL)
{
destroy_tree(leaf->left);
destroy_tree(leaf->right);
delete leaf;
}
}
//Insert Tree
//////////////////////////////////////////////////////////////////////
void btree::insert(int key, node *leaf)
{
if(key< leaf->key_value)
{
if(leaf->left!=NULL)
insert(key, leaf->left);
else
{
leaf->left=new node;
leaf->left->key_value=key;
leaf->left->left=NULL; //Sets the left child of the child node to null
leaf->left->right=NULL; //Sets the right child of the child node to null
}
}
else if(key>=leaf->key_value)
{
if(leaf->right!=NULL)
insert(key, leaf->right);
else
{
leaf->right=new node;
leaf->right->key_value=key;
leaf->right->left=NULL; //Sets the left child of the child node to null
leaf->right->right=NULL; //Sets the right child of the child node to null
}
}
}
///////////////////////////////////////////////////////////////////////
node *btree::search(int key, node *leaf)
{
if(leaf!=NULL)
{
if(key==leaf->key_value)
return leaf;
if(key<leaf->key_value)
return search(key, leaf->left);
else
return search(key, leaf->right);
}
else return NULL;
}
///////////////////////////////////////////////////////////////////////
void btree::insert(int key)
{
if(root!=NULL)
insert(key, root);
else
{
root=new node;
root->key_value=key;
root->left=NULL;
root->right=NULL;
}
}
//////////////////////////////////////////////////////////////////////
node *btree::search(int key)
{
return search(key, root);
}
///////////////////////////////////////////////////////////////////////
/*void btree::destroy_tree(node *root)
{
if(root != NULL)
destroy_tree(
destroy_tree(root);
}
*/
-
Create a counter variable in your node struct or class and increment it as necessary for each child down the tree, then when you print the tree you can see if it was built properly by printing out that variable as well.
-
I have never heard of a counter value in a struct or class.
-
If you just want to know to check it's working properly you could run it through a debugger and watch where it is attaching the nodes.