Ad:

C++ Discussion Thread
Unsolved
Views: 5213

May 17th, 2006

Reading a file into a binary search tree

Expand Post »

i know how to get a file and all but how do u go about putting that file into the tree?

my get file

C++ Syntax (Toggle Plain Text)
void BST::loadFile()
{
	cout << "Enter the the file location" << endl;
	cin >> inFileName;
	inFile.open(inFileName.c_str());
	if (!inFile.is_open())  //test for file
	{
		cerr << "Cannot open file: " << inFileName << endl;
		getche();
	}
	while(!inFile.eof()) //loop through untill end of file
	{ 
		inFile >> lastName >> firstName; 
 
		cout << lastName << ", " << firstName <<  endl; 
 
	}// end obtain info 
 
	inFile.close();//close infile
}
void BST::loadFile()
{
	cout << "Enter the the file location" << endl;
	cin >> inFileName;
	inFile.open(inFileName.c_str());
	if (!inFile.is_open())  //test for file
	{
		cerr << "Cannot open file: " << inFileName << endl;
		getche();
	}
	while(!inFile.eof()) //loop through untill end of file
	{ 
		inFile >> lastName >> firstName; 

		cout << lastName << ", " << firstName <<  endl; 
 
	}// end obtain info 

	inFile.close();//close infile
}

do i just go key = inFile
here is my key struct

C++ Syntax (Toggle Plain Text)
struct Key {
	char* data;  // string
 
	Key();
	Key(char* data) { this->data = new char[strlen(data)];
								strcpy(this->data,data);}
	~Key() {delete data;};
	Key(Key& key);
	void print();
 
	Key& operator= (Key& key);
	bool operator== (Key& key) { return 0 == strcmp(this->data,key.data);} // is this == to that key
	bool operator< (Key& key)  { return -1 == strcmp(this->data,key.data);}// is this < that key
	bool operator> (Key& key)  { return 1 == strcmp(this->data,key.data);} // is this > that key
};
 
 
Key::Key()
{
	data = NULL;
}
 
Key::Key(Key& key)
{
	data = key.data;
}
 
Key& Key::operator= (Key& key)
{
	data = key.data;
	return *this;
}
 
void Key::print()
{
	cout << data << endl;
}
struct Key {
	char* data;  // string

	Key();
	Key(char* data) { this->data = new char[strlen(data)];
								strcpy(this->data,data);}
	~Key() {delete data;};
	Key(Key& key);
	void print();

	Key& operator= (Key& key);
	bool operator== (Key& key) { return 0 == strcmp(this->data,key.data);} // is this == to that key
	bool operator< (Key& key)  { return -1 == strcmp(this->data,key.data);}// is this < that key
	bool operator> (Key& key)  { return 1 == strcmp(this->data,key.data);} // is this > that key
};


Key::Key()
{
	data = NULL;
}

Key::Key(Key& key)
{
	data = key.data;
}

Key& Key::operator= (Key& key)
{
	data = key.data;
	return *this;
}

void Key::print()
{
	cout << data << endl;
}

my BST Class

C++ Syntax (Toggle Plain Text)
class BST_Node {
private:
	Key key;         // key holds the data
	BST_Node* left;  // ptr to left subtree
	BST_Node* right; // ptr to right subtree
 
public:
	// Managers
	BST_Node();
	BST_Node(Key key);        // Construct given key-data
	BST_Node(BST_Node& node); // Copy Constructor
	~BST_Node();              // Destruct node
 
	// Operators
	BST_Node& operator= (BST_Node& node); // Assignment
 
	// Accessors
	Key getKey() {return key;};         // get Key Data
	BST_Node* getLeft() {return left;};  // get root of left subtree
	BST_Node* getRight() {return right;}; // get root of right subtree
	void setLeft(BST_Node* node);
	void setRight(BST_Node* node);
};
 
BST_Node::BST_Node()
{
	key.data = NULL;
	left = NULL;
	right = NULL;
}
 
BST_Node::BST_Node(Key key)
{	
 
	cout << "enter key" << endl;
	cin >> key.data;
 
}
 
BST_Node::BST_Node(BST_Node& node)
{
	right = node.right;
	left = node.left;
	//key = node.key;
}
 
BST_Node::~BST_Node()
{
	delete left;
	delete right;
}
 
BST_Node& BST_Node::operator= (BST_Node& node)
{
	right = node.right;
	left = node.left;
	//key = node.key;
	return *this;
}
 
void BST_Node::setLeft(BST_Node* node)
{
	this->left = node;
}
 
void BST_Node::setRight(BST_Node* node)
{
	this->right = node;
}
class BST_Node {
private:
	Key key;         // key holds the data
	BST_Node* left;  // ptr to left subtree
	BST_Node* right; // ptr to right subtree

public:
	// Managers
	BST_Node();
	BST_Node(Key key);        // Construct given key-data
	BST_Node(BST_Node& node); // Copy Constructor
	~BST_Node();              // Destruct node

	// Operators
	BST_Node& operator= (BST_Node& node); // Assignment

	// Accessors
	Key getKey() {return key;};         // get Key Data
	BST_Node* getLeft() {return left;};  // get root of left subtree
	BST_Node* getRight() {return right;}; // get root of right subtree
	void setLeft(BST_Node* node);
	void setRight(BST_Node* node);
};

BST_Node::BST_Node()
{
	key.data = NULL;
	left = NULL;
	right = NULL;
}

BST_Node::BST_Node(Key key)
{	
	
	cout << "enter key" << endl;
	cin >> key.data;

}

BST_Node::BST_Node(BST_Node& node)
{
	right = node.right;
	left = node.left;
	//key = node.key;
}

BST_Node::~BST_Node()
{
	delete left;
	delete right;
}

BST_Node& BST_Node::operator= (BST_Node& node)
{
	right = node.right;
	left = node.left;
	//key = node.key;
	return *this;
}

void BST_Node::setLeft(BST_Node* node)
{
	this->left = node;
}

void BST_Node::setRight(BST_Node* node)
{
	this->right = node;
}

Similar Threads

Help with binary search tree insertion in C++
Binary Search Tree in C++
searching and inserting node in a binary search tree in C
recursive findaverage function for Binary search tree in C
Binary search tree removal in C++

tyczj

Reputation Points: 10

Solved Threads: 1

Junior Poster in Training

Offline

91 posts
since Mar 2005

Permalink

May 17th, 2006

Re: Reading a file into a binary search tree

http://eternallyconfuzzled.com/tuts/bst1.html#insert

Dave Sinkula

Team Colleague

Reputation Points: 2780

Solved Threads: 312

long time no c

Offline

4,790 posts
since Apr 2004

Permalink

May 18th, 2006

Re: Reading a file into a binary search tree

yea i have an insert function already

C++ Syntax (Toggle Plain Text)
bool BST::insert(BST_Node* &subRoot, Key key)
{
	BST_Node* node = new BST_Node(key);
	if(!subRoot)
	{
		subRoot = node;
		return true;
	}
	if(key == root->getKey())
	{
		return false;
		delete node;
	}
	if(key < subRoot->getKey())
	{
		if(subRoot->getLeft() == NULL)
		{
			root->setLeft(new BST_Node(key));
		}
		else
		{
			insert(subRoot->getRight(), key.data);
		}
	}
}
bool BST::insert(BST_Node* &subRoot, Key key)
{
	BST_Node* node = new BST_Node(key);
	if(!subRoot)
	{
		subRoot = node;
		return true;
	}
	if(key == root->getKey())
	{
		return false;
		delete node;
	}
	if(key < subRoot->getKey())
	{
		if(subRoot->getLeft() == NULL)
		{
			root->setLeft(new BST_Node(key));
		}
		else
		{
			insert(subRoot->getRight(), key.data);
		}
	}
}

tyczj

Reputation Points: 10

Solved Threads: 1

Junior Poster in Training

Offline

91 posts
since Mar 2005

Permalink

May 18th, 2006

Re: Reading a file into a binary search tree

So just use the insert function in main.

The only thing I would do different is to use ofstream and ifstream for file i/o. And avoid anything with (EOF) like the plague.

Depending how your file is structured, will determine how you read it in. I'm assuming it looks something like this:

file.txt

C++ Syntax (Toggle Plain Text)

Smith Chris
Jones Antony
Anderson Clive

Therefore you could read in each line into the binary search tree, using the getline command?

iamthwee

Featured Poster

Reputation Points: 1536

Solved Threads: 431

Posting Expert

Offline

5,865 posts
since Aug 2005

Permalink

Nov 16th, 2010

Re: Reading a file into a binary search tree

I need some help to read data from file to BST

C++ Syntax (Toggle Plain Text)
/*
Name: Nguyen Ngoc Hoang
Student COde: 08020167
K53D- UET- VNU
Assigment 01
DSA
*/
#include<iostream>
#include<string>
#include<fstream>
#include<algorithm>
#include<iomanip>
 
using namespace std;
 
struct Data  // Data include keyword and number of occurrences
{
  string key;
  int count;
};
 
struct Node //A Node inclues Data, left and right
{
	Data data;
	Node* left;
	Node* right;
	Node(Data d,Node* l,Node* r)
    {
        data=d;
        left=l;
        right=r;
    }
};
 
class BSTree
{
private:
    static const int N = 100;
	Node *root;
public:
	//Construct an empty BSTree
	BSTree()
	{
		root=NULL;
	}
	//Create a BSTree from a file
	BSTree(BSTree &T , char *input)
	{
		ifstream fin;
		fin.open(input);
		if(!fin.good())
		{
		    cout<<"Error!File wordcount.in is not exits!"<<endl;
		    cout<<"Please check again !"<<endl;
		}
		Data getdata;
		getdata.count=1;
		string keyword;
		while(fin.good())
		{
		    fin>>keyword;
		    strcpy(keyword,getdata.key);
			T.InsertData(getdata);
		}
		fin.close();
	}
	//Destruct the BSTree
//	~BSTree();
	int IsEmpty();
	//Print all values of nodes inoder traversal
	void PrintTree(char* output);
	void Print_Tree(Node*,char* output);
	//Insert a value to BSTree
	void InsertData(Data DataInsert);
	void AddNode(Node *v,Data DataInsert);
};
int BSTree::IsEmpty()
{
    return root==NULL;
}
void BSTree::PrintTree(char* output)
{
    Print_Tree(root,output);
}
void BSTree::Print_Tree(Node* p,char* output)
{
    ofstream fout;
    fout.open(output);
    if(p!=NULL)
    {
        Print_Tree(p->left,output);
        fout<<p->data.key<<"\t";
        fout<<p->data.count<<endl;
        //fout<<"hoang huong";
        Print_Tree(p->right,output);
    }
    fout.close();
}
 
void BSTree::InsertData(Data DataInsert)
{
    if(root==NULL)  root=new Node(DataInsert,NULL,NULL );
    else    AddNode(root,DataInsert);
}
void BSTree::AddNode(Node *v,Data ValueInsert)
{
 
    if(v->data.key==ValueInsert.key)
    {
        ValueInsert.count++;
        return;
    }
    else
    {
        if(v->data.key > ValueInsert.key)
        {
            if(v->left!=NULL)   AddNode(v->left,ValueInsert);
            else    v->left=new Node(ValueInsert,NULL,NULL);
        }
        else
        {
            if(v->right!=NULL)  AddNode(v->right,ValueInsert);
            else    v->right=new Node(ValueInsert,NULL,NULL);
        }
    }
}
//main function
int main()
{
    BSTree T;
    BSTree Tree = BSTree(T ,"wordcount.in");
    T.PrintTree("wordcount.out");
}
 
 
 
 
 
 
//count the number of Node
int CountNode(Node* root)
{
    if(root=NULL)   return 0;
    else
    {
        int count=1;
        return CountNode(root->left)+CountNode(root->right);
    }
}
//Compare key of Node with a string
bool Compare(Node* n, string s)
{
    while(true)
    {
        if (n==NULL)    return false;
        else if(s==(n->data).key)    return true;
        else if(s<n->data.key)  n=n->left;
        else    n=n->right;
 
    }
}
/*
Name: Nguyen Ngoc Hoang
Student COde: 08020167
K53D- UET- VNU
Assigment 01
DSA
*/
#include<iostream>
#include<string>
#include<fstream>
#include<algorithm>
#include<iomanip>

using namespace std;

struct Data  // Data include keyword and number of occurrences
{
  string key;
  int count;
};

struct Node //A Node inclues Data, left and right
{
	Data data;
	Node* left;
	Node* right;
	Node(Data d,Node* l,Node* r)
    {
        data=d;
        left=l;
        right=r;
    }
};

class BSTree
{
private:
    static const int N = 100;
	Node *root;
public:
	//Construct an empty BSTree
	BSTree()
	{
		root=NULL;
	}
	//Create a BSTree from a file
	BSTree(BSTree &T , char *input)
	{
		ifstream fin;
		fin.open(input);
		if(!fin.good())
		{
		    cout<<"Error!File wordcount.in is not exits!"<<endl;
		    cout<<"Please check again !"<<endl;
		}
		Data getdata;
		getdata.count=1;
		string keyword;
		while(fin.good())
		{
		    fin>>keyword;
		    strcpy(keyword,getdata.key);
			T.InsertData(getdata);
		}
		fin.close();
	}
	//Destruct the BSTree
//	~BSTree();
	int IsEmpty();
	//Print all values of nodes inoder traversal
	void PrintTree(char* output);
	void Print_Tree(Node*,char* output);
	//Insert a value to BSTree
	void InsertData(Data DataInsert);
	void AddNode(Node *v,Data DataInsert);
};
int BSTree::IsEmpty()
{
    return root==NULL;
}
void BSTree::PrintTree(char* output)
{
    Print_Tree(root,output);
}
void BSTree::Print_Tree(Node* p,char* output)
{
    ofstream fout;
    fout.open(output);
    if(p!=NULL)
    {
        Print_Tree(p->left,output);
        fout<<p->data.key<<"\t";
        fout<<p->data.count<<endl;
        //fout<<"hoang huong";
        Print_Tree(p->right,output);
    }
    fout.close();
}

void BSTree::InsertData(Data DataInsert)
{
    if(root==NULL)  root=new Node(DataInsert,NULL,NULL );
    else    AddNode(root,DataInsert);
}
void BSTree::AddNode(Node *v,Data ValueInsert)
{

    if(v->data.key==ValueInsert.key)
    {
        ValueInsert.count++;
        return;
    }
    else
    {
        if(v->data.key > ValueInsert.key)
        {
            if(v->left!=NULL)   AddNode(v->left,ValueInsert);
            else    v->left=new Node(ValueInsert,NULL,NULL);
        }
        else
        {
            if(v->right!=NULL)  AddNode(v->right,ValueInsert);
            else    v->right=new Node(ValueInsert,NULL,NULL);
        }
    }
}
//main function
int main()
{
    BSTree T;
    BSTree Tree = BSTree(T ,"wordcount.in");
    T.PrintTree("wordcount.out");
}






//count the number of Node
int CountNode(Node* root)
{
    if(root=NULL)   return 0;
    else
    {
        int count=1;
        return CountNode(root->left)+CountNode(root->right);
    }
}
//Compare key of Node with a string
bool Compare(Node* n, string s)
{
    while(true)
    {
        if (n==NULL)    return false;
        else if(s==(n->data).key)    return true;
        else if(s<n->data.key)  n=n->left;
        else    n=n->right;

    }
}

hoangnn90

Reputation Points: 10

Solved Threads: 0

Newbie Poster

Offline

1 posts
since Nov 2010

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.

Previous Thread in C++ Forum Timeline: Classes

Next Thread in C++ Forum Timeline: getline not reading in the last line in a file

DaniWeb Message

Cancel Changes

User Name
Password