::::|| VU ||:::: SOLUTION FILE CS 301

#include <iostream.h>
#include <stdlib.h>

enum {TRUE = 1,FALSE = 0};

typedef struct _node
{
int info;
struct _node *left;
struct _node *right;
}node;
class btree
{
private:
node *root;
void InsertLeft(node* & ,node*);
void InsertRight(node* &,node*);
void deltree(node*);
public:
btree();
~btree();
node* GetRoot(void);
void MakeTree(void);
void DeleteNode(node *,node *,int);
int Searchnode(node*,int);
void DisplayTree(node*,int);
void Inorder(node* );
void Preorder(node*);
void Postorder(node*);

btree::btree()
{
char create='Y';
root = new node;
cout<<"Enter a number which will become a root"<<endl;
cin>>root->info;
root->left = NULL;
root->right = NULL;
}

btree::~btree()
{
deltree(root);
}

void btree::deltree(node *root)
{
if(root)
{
deltree(root->left);
deltree(root->right);
delete root;
}
}

node* btree::GetRoot(void)
{
return(root);
}

void btree::MakeTree(void)
{
node *newnode;
char create;

do
{
newnode = new node;
cout<<"Enter your number"<<endl;
cin>>newnode->info;

newnode->left=NULL;
newnode->right=NULL;
if(newnode->info < root->info)
InsertLeft(newnode,root);
else
InsertRight(newnode,root);
cout<<"Create another node[Y/N]"<<endl;
cin>>create;
}while(create=='Y' || create=='Y');
}

void btree::InsertLeft(node* &newnode,node* current)
{
if(current->left==NULL)
current->left=newnode;
else
{
current = current->left;
if(newnode->info < current->info)
InsertLeft(newnode,current);
else
InsertRight(newnode,current);
}
}

void btree::InsertRight(node* &newnode,node* current)
{
if(current->right==NULL)
current->right=newnode;
else
{
current = current->right;
if(newnode->info < current->info)
InsertLeft(newnode,current);
else
InsertRight(newnode,current);
}
}

void btree::DeleteNode(node *current,node *parent,int delnode)
{
if(delnode < current->info)
DeleteNode(current->left,current,delnode);
else if(delnode > current->info)
DeleteNode(current->right,current,delnode);
else if(delnode == current->info)
{
if(current->left == NULL)
{
if(parent->info > current->info)
parent->left = current->right;
else
parent->right = current->right;
}
else if(current->right == NULL)
{
if(parent->info > current->info)
parent->left = current->left;
else
parent->right = current->left;
}
else
{
node *temp;
int flag = 0;

parent = current;
current = current->left;
temp = current;
while(current->right != NULL)
{
current = current->right;
if(flag == 0)
flag = 1;
else
temp = temp->right;
}
parent->info = current->info;
if(flag == 0)

parent->left = current->left;
else
temp->right = current->left;
}
delete current;
}
}

int btree::Searchnode(node *current,int num)
{
if(num<current->info && current->left!=NULL)
Searchnode(current->left,num);
else if(num>current->info && current->right!=NULL)
Searchnode(current->right,num);
else
{
if(num==current->info)
return TRUE;
else
return FALSE;
}
return FALSE;
}

void btree::DisplayTree(node *current,int Level)
{
if(current)
{
DisplayTree(current->right,Level+1);
cout<<endl;
for(int i=0;i<Level;i++)
cout<<" ";
cout<<current->info;
DisplayTree(current->left,Level+1);
}
}

void btree::Inorder(node *current)
{
if(current!=NULL)
{
Inorder(current->left);
cout<<current->info;
Inorder(current->right);
}
}

void btree::Preorder(node *current)
{
if(current!=NULL)
{
cout<<current->info;
Preorder(current->left);
Preorder(current->right);
}
}

void btree::Postorder(node *current)
{
if(current!=NULL)
{
Postorder(current->left);
Postorder(current->right);
cout<<current->info;
}
}

int main()
{
char in[] = {18,95,41,29,52,74,86,33,57,17,20};
char pre[] = {41,95,74,52,29,18,86,57,17,33,20,-1};
int len = sizeof(in)/sizeof(in[0]);


int opt;
int num;
char ch='y';
btree bt;
do
{
cout<<"\nEnter your option\n";
cout<<"1. Make a Tree\n";
cout<<"2. Delete a node\n";
cout<<"3. search a node\n";
cout<<"4. display the tree\n";
cout<<"5. Inorder traversal\n";
cout<<"6. preorder traversal\n";
cout<<"7. postorder traversal\n";
cout<<"8. Exit\n";
cin>>opt;
switch(opt)
{
case 1:
bt.MakeTree();
break;
case 2:
int delnode;
cout<<"\nEnter an information to be deleted\n";
cin>>delnode;
bt.DeleteNode(bt.GetRoot(),NULL,delnode);
break;
case 3:
cout<<"\nEnter a number to search in the tree\n";
cin>>num;
if(bt.Searchnode(bt.GetRoot(),num))
cout<<"The number is present"<<endl;
else
cout<<"The number is not present"<<endl;
break;
case 4:
bt.DisplayTree(bt.GetRoot(),1);
break;
case 5:
bt.Inorder(bt.GetRoot());
break;
case 6:
bt.Preorder(bt.GetRoot());
break;
case 7:
bt.Postorder(bt.GetRoot());
break;
case 8:
exit(0);
default:
cout<<"\nInvalid Entry\n";
}
}while(ch=='Y' || ch=='y');
}

--

    

Join Vu_Bahawalur
http://groups.google.com/group/vu_Bahawalpur?hl=en&pli=1

   

-- 

     

--
For study materials, past papers and assignments,
Join VU School at www.vuscool.com
 
Facebook Group link
http://www.facebook.com/groups/vuCoooL
 
CoooL Virtual University Students Google Group.
To post to this group, send email to coool_vu_students@googlegroups.com
 
home page
http://groups.google.com/group/coool_vu_students?hl=en