AVL DSPS

#include<iostream.h>
#include<string.h> 
#include<fstream.h>
#include<conio.h>
//using namespace std;

class tnode
{
	public:
	char data[10];
	tnode *llink,*rlink;
	int ht;
};

class avl
{
	public:
	tnode *root;
	int lh,rh;
        int b;
	public:
	avl()
	{
		root=NULL;
		lh=0;
		rh=0;
		b=0;
	}
        tnode *insert(tnode *,tnode *);
	void create();
	int BF(tnode *);
	int height(tnode *);
	tnode *RR(tnode *);
	tnode *LL(tnode *);
	tnode *LR(tnode *);
	tnode *RL(tnode *);
	void preorder(tnode*);
	void inorder(tnode*);
};

	void avl::create()
	{	
		tnode *temp;
		fstream f1;
	     //	int ch=1;
		char x[10];
		char str[30];
  		f1.open("abc.txt",ios::in);
  		 while(f1)
   		{
     			f1.getline(str,30);
       			cout<data=str;			
			if(f1)
                       {
                        strcpy(temp->data,str);
			temp->llink=NULL;
			temp->rlink=NULL;
			temp->ht=0;
			if(root==NULL)
			{
				root=temp;
			}
			else	
			{
			root=insert(temp,root);
			}
                      }
		}
	}


	tnode * avl::insert(tnode *t,tnode *r)
	{
		//int b=0;
		if(strcmp(t->data,r->data)>0)
		{
			if(r->rlink==NULL)
			{
				r->rlink=t;
				r->ht=t->ht+1;
			}
			else
			r->rlink=insert(t,r->rlink);
		}
		else
		{
			if(r->llink==NULL)
			{
				r->llink=t;
				r->ht=t->ht+1;
			}
			else
			r->llink=insert(t,r->llink);
		}

		if(BF(r)==2)
		{
			//cout<<"hi"<data;
			if(t->datallink->data)
			{
				r=LL(r);
			}
			else
				r=LR(r);
		}
		if(BF(r)==-2)
		{
			//cout<<"hi";
			if(strcmp(t->data,r->rlink->data)>0)
			{
				r=RR(r);
			}
			else
				{
				r=RL(r);
				}
		}

		return(r);
	}



	int avl::BF(tnode *r)
	{
		
		if(r==NULL)
		return 0;
	
		if(r->llink==NULL)
		lh=0;
		else    
		lh=1+r->llink->ht;
		
		if(r->rlink==NULL)
		rh=0;
		else
		rh=1+r->rlink->ht;


	      /*	cout<<"height of"<data;
		cout<<"lh===="<llink==NULL)
		lh=0;
		else
		lh=1+height(r->llink);
		
		if(r->rlink==NULL)
		rh=0;
		else
		rh=1+height(r->rlink);
	
		if(lh>rh)
		return(lh);
		else
		return(rh);
		
	//	return(-1);
	}
	
	tnode * avl::LL(tnode *r)
	{
		tnode *y=new tnode;
		y=r->llink;
		r->llink=y->rlink;
		y->rlink=r;
		return(y);
	}
	tnode * avl::RR(tnode *r)
	{
		tnode *y=new tnode;
		y=r->rlink;
		r->rlink=y->llink;
		y->llink=r;
		return(y);
	
	}
	tnode *avl::LR(tnode *r)
	{
		tnode *x=new tnode,*t=new tnode;
		x=r->llink;
		t=x->rlink;
		x->rlink=t->llink;
		t->llink=x;
		r->llink=t;
		r=LL(r);
		return(r);
	}


	tnode * avl::RL(tnode *r)
	{
		tnode *x,*t;
		x=r->rlink;
		t=x->llink;	
		x->llink=t->rlink;
		t->rlink=x;
		r->rlink=t;
		r=RR(r);
		return(r);
	}

	void avl::preorder(tnode *r)
	{
		if(r!=NULL)
		{
			cout<data<<"->";
			preorder(r->llink);
			preorder(r->rlink);
		}
	}

	void avl::inorder(tnode *r)
	{
		if(r!=NULL)
		{

			inorder(r->llink);
			cout<data<<"->";
			inorder(r->rlink);
		}
	}



	void main()
	{
		avl a1;
		clrscr();
		a1.create();
		a1.preorder(a1.root);
		a1.inorder(a1.root);
	      //	return (0);
		getch();
	}

SHARE SHARE SHARE