AVL tree save file

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
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
#include <iostream>
#include <fstream>
#include <cctype>
#include <stdlib.h>
#include <conio.h>

using namespace std;

struct node
{
	int element;
	node *left;
	node *right;
	int height;
};
typedef struct node *nodeptr;
class bstree{
	public:
		void insert(int,nodeptr &);
		void del(int, nodeptr &);
		int deletemin(nodeptr &);
		void find(int,nodeptr &);
		void makeempty(nodeptr &);
		void copy(nodeptr &,nodeptr &);
		void saveFile( ofstream &, nodeptr &);
		nodeptr nodecopy(nodeptr &);
		void preorder( nodeptr);
		void inorder(nodeptr);
		void postorder(nodeptr);
		int bsheight(nodeptr);
		nodeptr srl(nodeptr &);
		nodeptr drl(nodeptr &);
		nodeptr srr(nodeptr &);
		nodeptr drr(nodeptr &);
		int max(int,int);
		int nonodes(nodeptr);
};
// Inserting a node
void bstree::insert(int x,nodeptr &p)
{
	if (p == NULL)
	{
		p = new node;
		p->element = x;
		p->left=NULL;
		p->right = NULL;
		p->height=0;
		if ( p==NULL ){
			cout<<"Out of Space\n"<<endl;
		}
	}
	else{
		if (x<p->element){
			insert(x,p->left);
			if ((bsheight(p->left) - bsheight(p->right))==2){
				if (x < p->left->element){
					p=srl(p);
				}
				else{
					p = drl(p);
				}
			}
		}
		else if (x>p->element){
			insert(x,p->right);
			if ((bsheight(p->right) - bsheight(p->left))==2){
				if (x > p->right->element){
					p=srr(p);
				}
				else{
					p = drr(p);
				}
			}
		}
		else{
			cout<<"Element Exists\n"<<endl;
		}
	}
	int m,n,d;
	m = bsheight(p->left);
	n = bsheight(p->right);
	d = max(m,n);
	p->height = d + 1;
}

// Finding an element
void bstree::find(int x,nodeptr &p){
	if ( p == NULL ){
		cout<<"Sorry! element not found\n"<<endl;
	}
	else{
		if ( x < p->element ){
			find( x , p->left );
		}
		else{
			if ( x > p->element ){
				find( x , p->right );
			}
			else{
				cout<<"Element found!\n"<<endl;
			}
		}
	}
}
// Copy a tree
void bstree::copy(nodeptr &p,nodeptr &p1){
	makeempty(p1);
	p1 = nodecopy(p);
}
// Make a tree empty
void bstree::makeempty(nodeptr &p){
	nodeptr d;
	if (p != NULL){
		makeempty(p->left);
		makeempty(p->right);
		d=p;
		free(d);
		p=NULL;
	}
}
// Copy the nodes
nodeptr bstree::nodecopy(nodeptr &p){
	nodeptr temp;
	if ( p == NULL ){
		return p;
	}
	else{
		temp = new node;
		temp->element = p->element;
		temp->left = nodecopy(p->left);
		temp->right = nodecopy(p->right);
		return temp;
	}
}
int bstree::deletemin(nodeptr &p)
{
	int c;
	cout<<"inside deltemin\n"<<endl;
	if (p->left == NULL){
		c = p->element;
		p = p->right;
		return c;
	}
	else{
		c = deletemin(p->left);
		return c;
	}
}


// Deleting a node
void bstree::del(int x,nodeptr &p){
	nodeptr d;
	if ( p == NULL ){
		cout<<"Sorry! element not found\n"<<endl;
	}
	else if ( x < p->element){
		del( x, p->left );
	}
	else if ( x > p->element ){
		del( x , p->right );
	}
	else if (( p->left == NULL ) && ( p->right == NULL )){
		d = p;
		free(d);
		p = NULL;
		cout << "Element deleted successfully\n" << endl;
	}
	else if (p->left == NULL){
		d = p;
		free(d);
		p = p->right;
		cout << "Element deleted successfully\n" << endl;
	}
	else if (p->right == NULL){
		d = p;
		p = p->left;
		free(d);
		cout << "Element deleted successfully\n" << endl;
	}
	else{
		p->element = deletemin(p->right);
	}
}

void bstree::preorder(nodeptr p){
	if (p!=NULL){
		cout<<p->element<<"\t";
		preorder(p->left);
		preorder(p->right);
	}
}

// Inorder Printing
void bstree::inorder(nodeptr p){
	if (p!=NULL){
		inorder(p->left);
		cout<<p->element<<"\t";
		inorder(p->right);
	}
}

// PostOrder Printing
void bstree::postorder(nodeptr p){
	if (p!=NULL){
		postorder(p->left);
		postorder(p->right);
		cout<<p->element<<"\t";
	}
}

int bstree::max(int value1, int value2){
	return ((value1 > value2) ? value1 : value2);
}

int bstree::bsheight(nodeptr p){
	int t;
	if (p == NULL){
		return -1;
	}
	else{
		t = p->height;
		return t;
	}
}

nodeptr bstree:: srl(nodeptr &p1){
	nodeptr p2;
	p2 = p1->left;
	p1->left = p2->right;
	p2->right = p1;
	p1->height = max(bsheight(p1->left),bsheight(p1->right)) + 1;
	p2->height = max(bsheight(p2->left),p1->height) + 1;
	return p2;
}
nodeptr bstree:: srr(nodeptr &p1){
	nodeptr p2;
	p2 = p1->right;
	p1->right = p2->left;
	p2->left = p1;
	p1->height = max(bsheight(p1->left),bsheight(p1->right)) + 1;
	p2->height = max(p1->height,bsheight(p2->right)) + 1;
	return p2;
}
nodeptr bstree:: drl(nodeptr &p1){
	p1->left=srr(p1->left);
	return srl(p1);
}
nodeptr bstree::drr(nodeptr &p1){
	p1->right = srl(p1->right);
	return srr(p1);
}

int bstree::nonodes(nodeptr p){
	int count=0;
	if ( p != NULL ){
		nonodes(p->left);
		nonodes(p->right);
		count++;
	}
	return count;
}

void readTextFile( ifstream &inFile , bstree &bst , nodeptr &root ){
	node *leaf;
	while( !inFile.eof() ){
		leaf = new node;
		inFile >> leaf->element;
		leaf->height = 0;
		leaf->left = leaf->right = NULL;
		if( root == NULL )
			root = leaf;
		bst.insert( leaf->element , root );
	}
}

void bstree::saveFile( ofstream &outFile , nodeptr &p ){
	outFile << p->element << endl;
	saveFile( p->left );
	saveFile( p->right);
}

int main(){
	//clrscr();
	nodeptr root,root1,min,max;//,flag;
	root = NULL;
	root1 = NULL;
	int a,choice,findele,delele;
	char ch='y';
	bstree bst;
	ifstream inFile( "tree.txt" );
	ofstream outFile( "try.txt" );
	readTextFile( inFile , bst , root );

	system("cls");
	
	do{
		cout<<"\n\t\t\t\tWELCOME TO AVL TREE"<<endl;
		cout<<"\t\t\t\t:::::::::::::::::::\n"<<endl;
		cout << "\t\t::::::::::::::::::::::::::::::::::::::::::::::::"   << endl;
		cout << "\t\t::::Enter 1 to insert a new node::::::::::::::::"   << endl;
		cout << "\t\t::::Enter 2 to search a value:::::::::::::::::::"   << endl;
		cout << "\t\t::::Enter 3 to delete a value:::::::::::::::::::"   << endl;
		cout << "\t\t::::Enter 4 to display Preorder:::::::::::::::::"   << endl;
		cout << "\t\t::::Enter 5 to display Inorder::::::::::::::::::"   << endl;
		cout << "\t\t::::Enter 6 to display Postorder::::::::::::::::"   << endl;
		cout << "\t\t::::Enter 7 to display the height of the tree:::"   << endl;
		cout << "\t\t::::Enter 8 to save File::::::::::::::::::::::::"   << endl;
		cout << "\t\t::::Enter 0 to exit:::::::::::::::::::::::::::::"   << endl;
		cout << "\t\t::::::::::::::::::::::::::::::::::::::::::::::::\n" << endl;
		
		cout<<"\nEnter the choice: ";
		cin>>choice;
		
		switch(choice){
		case 1:
			cout << "\n\t\tADDING NEW NODE"<<endl;
			cout << "\t\t:::::::::::::\n"<<endl;
			cout << "Enter a new value: ";
			cin  >> a;
			bst.insert(a,root);
			cout << "\nThe new value have been added to your tree successfully\n"<<endl;
			break;
		case 2:
			cout << "\nEnter node to search: ";
			cin  >> findele;
			if (root != NULL){
				bst.find(findele,root);
			}
			break;
		case 3:
			cout << "\nEnter node to delete: ";
			cin  >> delele;
			bst.del(delele,root);
			bst.inorder(root);
			cout << endl;
			break;
		case 4:
			cout << "\n\t\tPRE-ORDER TRAVERSAL"<<endl;
			bst.preorder(root);
			cout << endl;
			break;
		case 5:
			cout << "\n\t\tIN-ORDER TRAVERSAL"<<endl;
			bst.inorder(root);
			cout << endl;
			break;
		case 6:
			cout << "\n\t\tPOST ORDER TRAVERSAL"<<endl;
			bst.postorder(root);
			cout << endl;
			break;
		case 7:
			cout << "\n\t\tHEIGHT\n"<<endl;
			cout << "The height of the tree is: "<<bst.bsheight(root) << endl;
			break;
		case 8:
			bst.saveFile( outFile , root );
			cout << "Save successful ! " << endl;
			system( "pause" );
			break;
		case 0:
			cout << "\n\tThank your for using AVL tree program\n" << endl;
			break;
		default:
			cout << "Sorry! wrong input\n" << endl;
			break;
		}
		system("pause");//Pause window
		system("cls");//Clear screen
	}while(choice != 0);
	return 0;
}


code run perfectly.

just for my
 
saveFile(.. )

function. how to save it? i'm using recursive function of preorder and try to save into my txt but it's fail. any suggesstion?
Last edited on
anyone?
err. I had left this thread for quite long. any people help?
so you have still that kind of annoying habit to pass everything as a non const reference? you should really stop that.

typedef struct node *nodeptr; is not a good idea either. That rather veils that it is a pointer.

In case of saveFile() you stepped in this trap. you simply need to check the pointer whether it's null:
1
2
3
4
5
6
7
8
void bstree::saveFile( ofstream &outFile , nodeptr &p ){
if(p) // this will prevent the program from crashing!
{
	outFile << p->element << endl;
	saveFile( p->left );
	saveFile( p->right);
}
}
It will crash because it's guaranteed that at p will be null at the end.

For readTextFile(). Why isn't it a member function too?
The function itself is rather easy:
1
2
3
4
5
6
void readTextFile( ifstream &inFile , bstree &bst , nodeptr &root ){
	int element;
	while(inFile >> leaf->element){
		bst.insert( element , root );
	}
}


It seems that you have a hard time to grasp the programming logic generally and oop particularly:

bstree has member function but no member variables.
node has no member function but member variables.

For OOP you need both variables as member and functions as members that work with the afore mentioned variables.
@coder777 . ya. u helped me alot.
but if i not pass with reference.
any idea that can like what i'm doing with another way with good practice ?
can u provide it for my code ? with certain line that i can no need pass with non const reference..
i change the code based on this
1
2
3
4
5
6
7
8
void bstree::saveFile( ofstream &outFile , nodeptr &p ){
if(p) // this will prevent the program from crashing!
{
	outFile << p->element << endl;
	saveFile( p->left );
	saveFile( p->right);
}
}

it's fail to save.
it say ofstream & reference what cannot with node * . bla bla

what error is this?
can u provide it for my code ?


what error is this?
Well, outFile is the first parameter for saveFile, hence you need to pass it:

1
2
3
4
5
6
7
8
void bstree::saveFile( ofstream &outFile , node *p ){
if(p)
{
	outFile << p->element << endl;
	saveFile( outFile, p->left );
	saveFile( outFile, p->right);
}
}


Since the content of node is not changed you can make it const:
1
2
3
4
5
6
7
8
void bstree::saveFile( ofstream &outFile , const node *p ){
if(p)
{
	outFile << p->element << endl;
	saveFile( outFile, p->left );
	saveFile( outFile, p->right);
}
}
adding const is a good practice since it raises the safety of your code
sorry . made a stupid mistake at my
 
saveFile

function . i didn't notice it. hahaha.

okay.
so you mean everytime i use like
 
const node *p


rather than use
 
node *&p
right?

besides that need your help about save file thing
last time what i did is
1
2
3
4
5
6
7
//txt file data
5 // node index
50
43
24
45
65

so i use
1
2
3
4
inFile >> nodeIndex;
for(  int i = 0 ; i < nodeIndex ; i++ ){
   ...
}

now i change to while ( !inFile.eof() )
but when i read the text file without the nodeIndex
1
2
3
4
5
6
7
//without node index
50
43
23
45
65
     // <--- Enter the space 

when the result come out
it print something like
23 45 -8181291 .. ..
the negative value is mean the enter data in txt . how to prevent this??
so you mean everytime i use like

rather than use
It depends. if you really want to modify the pointer (i.e. allocate memory for it) you need the reference (&) to the pointer.

now i change to while ( !inFile.eof() )

The problem with the eof() is that you check it too late. This is correct:
1
2
3
4
5
6
void readTextFile( ifstream &inFile , bstree &bst , nodeptr &root ){
	int element;
	while(inFile >> element){ // This sets the eof flag and leaves element unchanged, but it's ok since then bst.insert( element , root ); is not called
		bst.insert( element , root );
	}
}
if you do this
1
2
3
4
5
6
7
void readTextFile( ifstream &inFile , bstree &bst , nodeptr &root ){
	int element;
	while( !inFile.eof() ){ // Too late for the check! The damage is done.
		inFile >> element; // This sets the eof flag
		bst.insert( element , root ); // because the prevous line deteced an eof it leaves element unchanged (=invalid). Nevertheless the invalid value is stored!
	}
}


you have another problem: on line 293 you pass an uninitalized root to readTextFile() which leads to undefined behavior
i thought i already initialized the
root to NULL first at start?

how should i initialize it then?
root to NULL first at start?
yes, sorry, I overlooked. I expected something like

nodeptr root = NULL;

so did you check
1
2
3
4
5
6
void readTextFile( ifstream &inFile , bstree &bst , nodeptr &root ){
	int element;
	while(inFile >> element){
		bst.insert( element , root );
	}
}
?
1
2
3
4
5
void bstree::readTextFile( ifstream &inFile, nodeptr &root) {
	int element;
	while( inFile >> element )
		insert( element , root );
}

it's work successful .

now i have a little bit problem about my last option
 
–	Calculating balances after a rotation

how did i return calculate balances ? isn't return number of height?
getting confuse for this option
The program then should have an option to calculate balances after rotation.

i think i done all those option alreayd.
but i left this last option.
i don't know how to count the balance after rotation
the balance is the difference of the height between the right and the left node
for my thinking i also think like this

right subtree compare with left subtree . correct?

this the problem that i not really know how to compare the subtree only.
because if do the function.
will do the recursive again. but i don't know how to really fix that recursive to count oni right subtree and left subtree.
any suggesstion?
generally a balance is found the following way:

you have a function that take the left and right node as the parameter.

the recursion ends if both nodes have no succeeding left/right node.
You can calculate the balance from both

if right has right succeeding: pass that as the right parameter to the next recursion
else: pass the already passed parameter to the next recursion

if right has left succeeding: pass that as the left parameter to the next recursion
else if left has right succeeding: pass the right of the left as the left parameter to the next recursion
else if left has left succeeding: pass the left of the left as the left parameter to the next recursion
else if left has no successor: pass the already passed left parameter to the next recursion


this is roughly the algorithm to find the balance between two neighboring nodes
i thought i already did it with mine
 
bsheight

function isn't?

if i just want to check the right balance and left balance. isnt
1
2
3
int balance = 0;
balance = bsheight(p->right) - bsheight(p->left);
cout << "Balance : " << balance << endl;

isn't right for this way>
what happens if p->right or p->left is null?
err if p->right is null of course it's -1?
because in my bsheightfunction
if it's null and it's return -1 value...
yes it does, but it's plain wrong.

if the height of left is 4 I'd be:

balance = -1 - 4 -> -5

That's not a balance.

you need to implement the the algorithm I suggested above. It's only for one branch. You need to do the recursion for all need within the (sub) tree. print out the balance when there's no successor. start the recursion at the top you the modified recursion
Topic archived. No new replies allowed.