AVL tree save file

[Lim Boon Jye]

#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?

[Lim Boon Jye]

anyone?

[Lim Boon Jye]

err. I had left this thread for quite long. any people help?

[coder777]

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:

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:

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.

[Lim Boon Jye]

@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..

[Lim Boon Jye]

i change the code based on this

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?

[coder777]

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:

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:

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

[Lim Boon Jye]

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

//txt file data
5 // node index
50
43
24
45
65

so i use

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

//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??

[coder777]

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:

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

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

[Lim Boon Jye]

i thought i already initialized the
root to NULL first at start?

how should i initialize it then?

[coder777]

root to NULL first at start?

yes, sorry, I overlooked. I expected something like

nodeptr root = NULL;

so did you check

void readTextFile( ifstream &inFile , bstree &bst , nodeptr &root ){
	int element;
	while(inFile >> element){
		bst.insert( element , root );
	}
}

?

[Lim Boon Jye]

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

[Lim Boon Jye]

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

[coder777]

the balance is the difference of the height between the right and the left node

[Lim Boon Jye]

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?

[coder777]

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

[Lim Boon Jye]

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

int balance = 0;
balance = bsheight(p->right) - bsheight(p->left);
cout << "Balance : " << balance << endl;

isn't right for this way>

[coder777]

what happens if p->right or p->left is null?

[Lim Boon Jye]

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...

[coder777]

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