Binary search tree class - output to file

closed account (zwA4jE8b)
I have made a BST class. It has all the regular tree functions, add leaf, inorder, preorder, and postorder traversal.

Currently the traversals simply use 'cout' to output the nodes of the tree and are void functions.

How can I make them output the nodes information to a file?

I need to return values to the calling program as the traversal runs.

If I use 'return' in the traversal then it will break.

1
2
3
4
5
6
7
 
template <class dType>
void tree<dType>::inorderR(leaf<dType>* _l) const
{
	if (_l->_left != NULL) inorderR(_l->_left);
	cout << _l->_id << " ";                     //Here, needs to 'give' value to calling program.
	if (_l->_right != NULL) inorderR(_l->_right);
}



I am new to classes. I have written a stack class and when pop is called it return one value. That was easy.

Please let me know if you need to see any more of the classes code!
Last edited on
PanGalactic (1658)
Can you do that external to the BST?

1
2
 
for node in BST:
    print node

naraku9333 (2163)
You can overload operator<< then you can output to file or cout.
closed account (zwA4jE8b)
PanGalactic:
I'm sorry, I do not quite understand what you are saying.

Are you asking if I can do the search outside the class by calling nodes? If so, then no, the class is self contained. I could just use the functions in my 'main.cpp' , which I might just have to do, but I just wanted to see if I could do it from the class. One thought of mine was to just add the nodes to an array and return the array from the class.

naraku9333:
Can you give me an example?

heres is the class...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
 
//Michael Ervin - Tree ADT

#ifndef H_TREE
#define H_TREE

#include <iostream>
#include "stack.h"

template <class dType>
struct leaf
	{
		dType _id;
		leaf<dType> *_left, *_right;
	};

template <class dType>
class tree
{
protected:
	leaf<dType>* _root;
public:
	tree();
	bool isEmpty() const;
	void grow(dType _water);
	void prune(dType _todel);
	void inordertraversalR() const;
	void preordertraversalR() const;
	void postordertraversalR() const;
	void inordertraversalI() const;
	void preordertraversalI() const;
	void postordertraversalI() const;
	void killtree();
	~tree();
private:
	void delete_zero(leaf<dType>* _p, leaf<dType>* _c);
	void delete_one(leaf<dType>* _p, leaf<dType>* _c);
	void delete_two(leaf<dType>* _c);
	void inorderR(leaf<dType>* _l) const;
	void preorderR(leaf<dType>* _l) const;
	void postorderR(leaf<dType>* _l) const;
	void inorderI(leaf<dType>* _l) const;
	void preorderI(leaf<dType>* _l) const;
	void postorderI(leaf<dType>* _l) const;
	void hexxus(leaf<dType>*& _d);
};

template <class dType>
tree<dType>::tree(){_root = NULL;}

template <class dType>
bool tree<dType>::isEmpty() const{return (_root == NULL);}

template <class dType>
void tree<dType>::grow(dType _water)
{
	leaf<dType> *_c, *_t, *_n;
	_n = new leaf<dType>;

	_n->_id = _water;
	_n->_left = NULL;
	_n->_right = NULL;

	if (!isEmpty())
	{
		_c = _root;
		while (_c != NULL)
		{
			_t = _c;
			if (_water < _c->_id)
				_c = _c->_left;
			else if (_water > _c->_id)
				_c = _c->_right;
		}
		if (_t->_id > _water)
			_t->_left = _n;
		else
			_t->_right = _n;
	}
	else
		_root = _n;
}

template <class dType>
void tree<dType>::prune(dType _todel)
{
	leaf<dType> *_c, *_p;
	_p = NULL;
	_c = _root;
	
	while (_c != NULL && _c->_id != _todel)
	{
		_p = _c;
		if (_todel < _c->_id)
			_c = _c->_left;
		else
			_c = _c->_right;
	}
	if (_c != NULL)
	{
		if (_c->_left == NULL && _c->_right == NULL)
			delete_zero(_p, _c);
		else if (_c->_left != NULL && _c->_right != NULL)
			delete_two(_c);
		else
			delete_one(_p, _c);
	}
	else
		cout << "Node w/ id: " << _todel << " is not in the tree...";
}

template <class dType>
void tree<dType>::delete_zero(leaf<dType>* _p, leaf<dType>* _c)
{
	if (_p->_left == NULL)
		_p->_right = NULL;
	else
		_p->_left = NULL;
	delete _c;
}

template <class dType>
void tree<dType>::delete_one(leaf<dType>* _p, leaf<dType>* _c)
{
	if (_p->_left == _c)
		if (_c->_left != NULL)
			_p->_left = _c->_left;
		else
			_p->_left = _c->_right;
	else if (_p->_right == _c)
		if (_c->_left != NULL)
			_p->_right = _c->_left;
		else
			_p->_right = _c->_right;
}

template <class dType>
void tree<dType>::delete_two(leaf<dType>* _c)
{
	leaf<dType> *_s;
	dType _holder;

	_s = _c->_left;
	while (_s->_right != NULL)
	{
		if (_s->_right != NULL)	
			_s = _s->_right;
		else
			_s = _s->_left;
	}
	_holder = _s->_id;
	prune(_s->_id);
	_c->_id = _holder;
}

template <class dType>
void tree<dType>::inordertraversalR() const{inorderR(_root);}

template <class dType>
void tree<dType>::inorderR(leaf<dType>* _l) const
{
	if (_l->_left != NULL) inorderR(_l->_left);
	cout << _l->_id << " ";
	if (_l->_right != NULL) inorderR(_l->_right);
}

template <class dType>
void tree<dType>::preordertraversalR() const{preorderR(_root);}

template <class dType>
void tree<dType>::preorderR(leaf<dType>* _l) const
{
	cout << _l->_id << " ";
	if (_l->_left != NULL) preorderR(_l->_left);
	if (_l->_right != NULL) preorderR(_l->_right);
}

template <class dType>
void tree<dType>::postordertraversalR() const{postorderR(_root);}

template <class dType>
void tree<dType>::postorderR(leaf<dType>* _l) const
{
		if (_l->_left != NULL) postorderR(_l->_left);
		if (_l->_right != NULL) postorderR(_l->_right);
		cout << _l->_id << " ";
}

template <class dType>
void tree<dType>::inordertraversalI() const{inorderI(_root);}

template <class dType>
void tree<dType>::inorderI(leaf<dType>* _l) const
{
	if (!isEmpty())
	{
		stack<leaf<dType>*> _logs(15, NULL);
		leaf<dType> *_c = _root;

		while (!_logs.isEmpty() || _c != NULL)
			if ( _c != NULL)
			{
				_logs.push(_c);
				_c = _c->_left;
			}
			else
			{
				_c = _logs.pop();
				cout << _c->_id << " ";
				_c = _c->_right;
			}
	}
	else
		cout << "The tree has not grown yet...";
}

template <class dType>
void tree<dType>::preordertraversalI() const{preorderI(_root);}


template <class dType>
void tree<dType>::preorderI(leaf<dType>* _l) const
{
	if (!isEmpty())
	{
		stack<leaf<dType>*> _logs(15, NULL);
		leaf<dType> *_c = _root;

		while (!_logs.isEmpty() || _c != NULL)
			if ( _c != NULL)
			{
				cout << _c->_id << " ";
				_logs.push(_c);
				_c = _c->_left;
			}
			else
			{
				_c = _logs.pop();
				_c = _c->_right;
			}
	}
	else
		cout << "The tree has not grown yet...";
}
Last edited on
naraku9333 (2163)
This is from my Binary Tree
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
 
template <class T>
std::ostream& operator<<(std::ostream& ostr, const BinaryTree<T>& tree)
{	
	if(tree.root != NULL)
		tree.PrintTree(ostr, tree.root);
	else
		ostr<<"ERROR: Tree Is Empty"<<endl;//throw BinaryTree<T>::BinaryTreeError(3);
	return ostr;
}

template <class T>
void BinaryTree<T>::PrintTree(std::ostream& ostr, Node* r)const
{
	//output the left tree if exists
	if(r->lchild != NULL)
	{
		PrintTree(ostr, r->lchild);
	}
	if(Debug == 0)
		ostr << r->data;//calling nodes data
	if(Debug == 1)
	{
		ostr <<"This node: "<<r->data<<"Left child: ";
		if(r->lchild != NULL)
			ostr << r->lchild->data<<"Right child: ";
		else
			ostr<< "NULL\nRight child: ";
		if(r->rchild != NULL)
			ostr << r->rchild->data<<endl;
		else
			ostr << "NULL\n"<< endl;
	}

	//output the right tree
	if(r->rchild != NULL)
	{
		PrintTree(ostr, r->rchild);
	}
}


Side comment, you have alot of traversal funcs but I dont see any store.

EDIT: The Debug ==1 block was specific to the assignment and should be ignored.
Last edited on
closed account (zwA4jE8b)
This is a work in progress. My assignment was not to make a class but just a program that created a tree from an input file and output it to a file. I did that already, now I want to make it into a class.

Thank you for the example.
That gives me a lot of direction!

did you #include <fstream> in your class?
Last edited on
naraku9333 (2163)
Nope, just iostream, you'll include fstream from main or where ever you open the file. As far as the class is concerned its just a stream.

I would add some comments and maybe more descriptive var names, I'm having a hard time understanding what your doing.
closed account (zwA4jE8b)
This is what I have so far... but when I compile there is a LINK error

Trees.obj : error LNK2019: unresolved external symbol "class std::basic_ostream<char,struct std::char_traits<char> > & __cdecl operator<<(class std::basic_ostream<char,struct std::char_traits<char> > &,class tree<int> const &)" (??6@YAAAV?$basic_ostream@DU?$char_traits@D@std@@@std@@AAV01@ABV?$tree@H@@@Z) referenced in function "void __cdecl readin(void)" (?readin@@YAXXZ)
1>C:\Visual Studio 2010\C++\1 - School Projects\Trees\Debug\Trees.exe : fatal error LNK1120: 1 unresolved externals


This error happens when i write
cout << 'treename';
'treename' is the instance of the class, there are not actually quotes around it in the code...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
 
//Michael Ervin - Tree ADT

#ifndef H_TREE
#define H_TREE

#include <iostream>
#include "stack.h"

using namespace std;

template <class dType>
struct leaf
	{
		dType _id;
		leaf<dType> *_left, *_right;
	};

template <class dType>
class tree
{
	friend ostream& operator<< (ostream& , const tree<dType>&);
protected:
	leaf<dType>* _root;
public:
	tree();
	bool isEmpty() const;
	void grow(dType _water);
	void prune(dType _todel);
	void inordertraversalR() const;
	void preordertraversalR() const;
	void postordertraversalR() const;
	void inordertraversalI() const;
	void preordertraversalI() const;
	void postordertraversalI() const;
	void killtree();
	~tree();
private:
	void delete_zero(leaf<dType>* _p, leaf<dType>* _c);
	void delete_one(leaf<dType>* _p, leaf<dType>* _c);
	void delete_two(leaf<dType>* _c);
	void inorderR(leaf<dType>* _l) const;
	void preorderR(leaf<dType>* _l) const;
	void postorderR(leaf<dType>* _l) const;
	void hexxus(leaf<dType>*& _d);
};

template <class dType>
tree<dType>::tree(){_root = NULL;}

template <class dType>
bool tree<dType>::isEmpty() const{return (_root == NULL);}

template <class dType>
ostream& operator<< (ostream& ostr, const tree<dType>& me)
{
	ostr << "trial";
	return ostr;
}
Last edited on
naraku9333 (2163)
Add the template arg to ostream overload declaration

1
2
 
template <class dType>
friend ostream& operator<< (ostream& , const tree<dType>&);
Last edited on
closed account (zwA4jE8b)
Thanks for the help naraku9333

I found this on msdn..
template <class dType> friend ostream& operator<< (ostream& ostr, const tree<dType>& me);

resolved the issue and now it works.

I should now be able to implement it,
Thanks a lot.
closed account (zwA4jE8b)
just a note to anyone else who reads this who has trouble in this area...

I found out that you can pass (ostream& output) as a parameter to a function in a class.

1
2
3
4
5
6
7
8
 
void output(tree<int>& aspen)
{
	ofstream outs;
	outs.open("output.out");
	//outs << aspen;
	aspen.inordertraversalI(outs);  //Outputs to the ofstream!!!!
	outs.close();
}


Topic archived. No new replies allowed.