-
Bst Tree
I still can't get this to work I tried some of the early suggestions but I still can't either get the client file correct or my functions are not correct.
This locks up. I am not sure how I should cll my functions in the client
file to make the BST and do the different functions.PreOrder()etc...
#include<iostream>
#include<iomanip>
#include<fstream>
#include <cctype> // defines isalpha() function
#include"TreeImplementation.cpp"
using namespace std;
int main()
{
btree bt;
int num=0;
char chr;
int count=0;
int *leaf1;
ifstream fin("input.txt");
ofstream fout("output1.txt");
fin>>num;
fin>>chr;
while(fin)
{
bt.insert(num);
//bt.search(num);
bt.InorderTranverse(leaf1);
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;
}
header
struct node
{
int key_value;
node *left;
node *right;
};
class btree
{
public:
// node *root;
btree();
// ~btree();
void destroy_tree(node *leaf);
void insert(int key, node *leaf);
node *search(int key, node *leaf);
//node *GetRoot(); {return (root);
//public:
void insert(int key);
node *search(int key);
//void destroy_tree();
void InorderTranverse(node *leaf);
//void preOrderTranverse(node *leaf);
//void PostOrderTranverse(node *leaf);
private:
node *root;
};
node *RChild(node *leaf);
node *LChild(node *leaf);
Implementation
#include<iostream.h>
#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);
}
*/
//////////////////////////////////////////////////////////////////////
void btree::InorderTranverse(node *leaf)
{
if(leaf != NULL)
InorderTranverse(LChild(leaf));
cout<<leaf;
InorderTranverse(RChild(leaf));
}
//////////////////////////////////////////////////////////////////////
node *LChild(node *leaf)
{
return (leaf==NULL) ? NULL : leaf->left;
}
//////////////////////////////////////////////////////////////////////
node *RChild(node *leaf)
{
return (leaf==NULL) ? NULL : leaf->right;
}
//PreOrder Tranverse
///////////////////////////////////////////////////////////////////////
/*void btree::preOrderTranverse(node *leaf)
{
if(leaf != NULL){
cout<<leaf;
preOrderTranverse(LChild(leaf));
preOrderTranverse(RChild(leaf));
}
}
//PostOrderTranverse
///////////////////////////////////////////////////////////////////////
void btree::PostOrderTranverse(node *leaf)
{
if(leaf != NULL){
PostOrderTranverse(LChild(leaf));
PostOrderTranverse(RChild(leaf));
}
}
//////////////////////////////////////////////////////////////////////
node *GetRoot(); {return (root);
{
}*/
-
OK, here's a cut down version of your tree that just inserts and does an InOrderTransversal (the other traversal functions can be done in the same manner) -
Code:
#include<iostream>
#include<iomanip>
#include<fstream>
#include <cctype> // defines isalpha() function
using namespace std;
struct node
{
int key_value;
node *left;
node *right;
};
class btree
{
public:
btree();
void insert(int key);
void InOrderTranverse();
private:
void insert(int key, node *leaf);
void InOrderTranverse(node *leaf);
node *root;
};
int main()
{
btree bt;
int num=0;
char chr;
cin>>num;
cin>>chr;
while(cin)
{
bt.insert(num);
cout << "InOrderTranverse: ";
bt.InOrderTranverse();
cout << endl;
cout<<"Step: "<<count<<" "<<"Data Value = "<<num<<" "<<"Activity Signal = "<<chr<<endl;
cin>>num;
cin>>chr;
}
return 0;
}
//Constructor
///////////////////////////////////////////////////////////////////////
btree::btree()
{
root=NULL;
}
//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
}
}
}
///////////////////////////////////////////////////////////////////////
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;
}
}
//////////////////////////////////////////////////////////////////////
void btree::InOrderTranverse(node *leaf)
{
if(leaf->left != NULL)
InOrderTranverse(leaf->left);
cout<<leaf->key_value<< " ";
if(leaf->right !=NULL)
InOrderTranverse(leaf->right);
}
//////////////////////////////////////////////////////////////////////
void btree::InOrderTranverse()
{
if(root!=NULL)
InOrderTranverse(root);
else
return;
}
If you are unsure on anything post a reply instead of waiting a few days and then reposting the same question again.
-
Zen or anyone else.
In a BST, do you really need a destructor or a destroy tree?
-
If your tree is put into a class then you'll get a destructor whether you want one or not, so this would seem the logical place to delete all the nodes. If you don't delete them you'll get a memory leak.