/***************************************
APPLICATION : A Complete Tree Program
CODED BY : Ankit Pokhrel
COMPILED ON : Borland C++ Ver 5.02
DATE : 2010 - July - 27
***************************************/
#include "iostream.h"
#include "conio.h"
struct TREE //structure to represent a tree
{
int data;
struct TREE *right,*left,*root;
};
typedef TREE tree;
tree *New;
void create() //function to create a node
{
New = new tree;
New -> left = NULL;
New -> right = NULL;
}
tree *par; //parent node
tree* find(tree *t,int item)
{
tree *loc,*ptr,*save;
if(t == NULL) //tree doesn't exist
{
loc = NULL;
par = NULL;
return loc;
}
if(t -> data == item) //if root node
{
loc = t -> root; //set loc to root
par = NULL; //no parent
return loc; //return location
}
if(item < t -> data)
{
ptr = t -> left; //move to left
save = t -> root; //save parent node
}
else
{
ptr = t -> right; //move to right
save = t -> root; //save parent node
}
while(ptr != NULL)
{
if(item == ptr -> data)
{
loc = ptr; //set loc
par = save; //set parent
return loc; //return location
}
if(item < ptr -> data)
{
save = ptr; //save parent
ptr = ptr -> left; //move to left
}
else
{
save = ptr; //save parent
ptr = ptr -> right; //move to right
}
}
loc = NULL; //data not found
par = save; //save parent
return loc; //return location
}
void caseA(int Item,tree *&tr) //if node has no or one child
{
tree *child;
tree *loc = find(tr,Item); //find location of the item
if(loc -> left == NULL && loc -> right == NULL) //if no children
child = NULL;
else if(loc -> left != NULL) //if left child
child = loc -> left;
else
child = loc -> right;
if(par != NULL)
{
if(loc == par -> left) //if node to be deleted is left of parent
par -> left = child;
else
par -> right = child;
}
else
{
tr -> root = child; //replace root
tr = child;
}
}
void caseB(int Item,tree *&tr) //if node has both children
{
tree *suc,*loc,*parTemp;
loc = find(tr,Item); //find location of item
parTemp = par; //save parent of Item
suc = loc -> right; //go to right
while(suc -> left != NULL)
suc = suc -> left; //go to left
caseA(suc -> data,tr); //Delete successor using caseA
par = parTemp; //set parent
if(par != NULL)
{
if(loc == par -> left) //if node to be deleted is left of parent
par -> left = suc;
else
par -> right = suc;
}
else
{
tr -> root = suc; //replace root
tr = suc;
}
suc -> left = loc -> left; //set left of successor
suc -> right = loc -> right; //set right of successor
}
tree* remove(int Item,tree *&t)
{
tree *loc = find(t,Item); //find location
if(loc == NULL)
{
cout << "Item not Found.";
return loc;
}
if(loc -> right != NULL && loc -> left != NULL) //if node has both child
caseB(Item,t); //call caseB
else
caseA(Item,t); //call caseA
return loc;
}
void insert(tree *&t,int Item)
{
if(t == NULL) //if tree doesn't exists
{
t = new tree; //create a tree
t -> data = Item; //insert data
t -> left = NULL;
t -> right = NULL;
t -> root = t; //initialize root
return;
}
tree *trav = t;
if(Item < trav -> data)
{
if(trav -> left == NULL)
{
create();
New -> data = Item;
trav -> left = New;
}
else
insert(trav -> left,Item); //go to left
}
else
{
if(trav -> right == NULL)
{
create();
New -> data = Item;
trav -> right = New;
}
else
insert(trav -> right,Item); //go to right
}
}
void preorder(tree *t)
{
if(t != NULL)
{
cout << t -> data << ' ';
preorder(t -> left);
preorder(t -> right);
}
}
void inorder(tree *t)
{
if(t != NULL)
{
inorder(t -> left);
cout << t -> data << ' ';
inorder(t -> right);
}
}
void postorder(tree *t)
{
if(t != NULL)
{
postorder(t -> left);
postorder(t -> right);
cout << t -> data << ' ';
}
}
int main()
{
tree *tr1 = NULL;
int n = 0;
cout << "Enter Numbers :\n";
while(n != -999) //create a tree
{
cin >> n;
if(n != -999)
insert(tr1,n);
}
inorder(tr1);
cout << "\nDelete : ";
cin >> n;
tree *temp = remove(n,tr1);
cout << endl;
inorder(tr1);
if(temp != NULL)
cout << "\nDeleted Item : " << temp -> data;
getch();
return 0;
}
......................
Labels:
Tree
No comments:
Post a Comment