Bst Tree

**Drew** · 10-02-2001

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:

reOrderTranverse(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);
{

}*/

**zen** · 10-02-2001

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.

**Drew** · 10-02-2001

In a BST, do you really need a destructor or a destroy tree?

**zen** · 10-03-2001

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.

Thread: Bst Tree

Thread Tools

Search Thread

Display

Bst Tree

Zen or anyone else.

Similar Threads

Interpreter.c

BST delete again, but this time I think I'm close

Binary Search Trees Part III

Request for comments

BST/Red and Black Tree