#include
#include
#include
#define SIZE 3
struct node_{
struct node_ *leftChild;
struct node_ *rightChild;
int number;
int t;
};
struct stack_{
int size;
int top;
int * value;
};
typedef struct node_ Node;
typedef struct stack_ stack;
stack * theStack=NULL;
Node * root=NULL;
Node *holder;
int a;
Node *tempRoot=NULL,*tempParent=NULL,*tempAccess=NULL;
int calculate_T(Node *parentNode);
Node * CON_ROT_Optimized(Node *record,int number);
void initStack();
int isOverFlow();
void push(Node *path);
int pop();
Node * InsertTree(Node *node,int number);
void println_Infix(Node *node);
void println_Prefix(Node *node);
void println_Postfix(Node *node);
void instruction();
Node * entry_Con();
Node * CON_ROT_Optimized(Node *record,int number);
void rotation(Node **root,Node **parent,Node **access);
void right_Rotation(Node **root,Node **parent,Node **access);
void left_Rotation(Node **root,Node **parent,Node **access);
void addNode();
int getT(Node *node);
void read();
FILE *file=NULL;
FILE *file2=NULL;
/*We define a stack to hold address of node in the tree.Our stack is circle stack.
It can take only three address of path on the search key.Adress of search key,address of parent of search key and address of grandparent
Initialize the Stack
*/
void initStack()
{
theStack=(stack *)calloc(1,sizeof(stack));
theStack->value=(int *)calloc(3,sizeof(int));
//theStack->top=-1;
}
//Make a circle if is OverFlow.
int isOverFlow()
{
if(theStack->top==-1)
return 1;
else
return 0;
}
//Push the address of nodes
void push(Node *path)
{
theStack->top%=3;
theStack->value[theStack->top++]=(int)path;
}
//Take address of node from stack.
int pop()
{
int k;
k=--theStack->top;
if(isOverFlow())
{
theStack->top=2;
k=theStack->top;
}
return theStack->value[k];
}
//Insert a node to the tree but we don't put same numbers in the tree
Node * InsertTree(Node *node,int number)
{
if(node==NULL)
{
node=(Node *)calloc(1,sizeof(Node));
node->number=number;
return node;
}
else if(number
{
node->leftChild=InsertTree(node->leftChild,number);
}
else if(number>node->number)
{
node->rightChild=InsertTree(node->rightChild,number);
}
return node;
}
//Infix Printer
void println_Infix(Node *node)
{
if(node!=NULL)
{
println_Infix(node->leftChild);
printf("number --> %d t: %d \n",node->number,node->t);
println_Infix(node->rightChild);
}
}
//Prefix Printer
void println_Prefix(Node *node)
{
if(node!=NULL)
{
println_Prefix(node->leftChild);
println_Prefix(node->rightChild);
printf("number --> %d t: %d \n",node->number,node->t);
}
}
//Postfix Printer
void println_Postfix(Node *node)
{
if(node!=NULL)
{
printf("number --> %d t: %d \n",node->number,node->t);
println_Postfix(node->leftChild);
println_Postfix(node->rightChild);
}
}
//We have got prepared tree first and we initalize it.
void initializeTree(){
root=(Node *)InsertTree(root,54);
root=(Node *)InsertTree(root,83);
root=(Node *)InsertTree(root,92);
root=(Node *)InsertTree(root,72);
root=(Node *)InsertTree(root,81);
root=(Node *)InsertTree(root,65);
root=(Node *)InsertTree(root,18);
root=(Node *)InsertTree(root,12);
root=(Node *)InsertTree(root,10);
root=(Node *)InsertTree(root,14);
root=(Node *)InsertTree(root,28);
root=(Node *)InsertTree(root,20);
root=(Node *)InsertTree(root,37);
}
//Choice of println.The user can make a choice to print tree on console(Infix,Prefix,Postfix)
void println()
{
int a;
printf("1 :Infix\n2 :Prefix\n3 :Postfix");
printf("\nEntry :");
scanf("%d",&a);
switch(a){
case 1: printf("-----Infix-------\n");
println_Infix(root); break;
case 2 :printf("-----Prefix------\n");
println_Prefix(root); break;
case 3:printf("-----Postfix-----\n");
println_Postfix(root); break;
}
}
int result(Node * node){
return node->number;
}
//Entry of CON_ROT program, Choose one of them
void instruction()
{
int chose;
printf("\nWhat do you want to do?\n1:Addition a node to the tree\n2:Conditional Rotation\n3:Print Tree\n4:Exit");
printf("\nEntry :");
scanf("%d",&chose);
switch(chose){
case 1:addNode(); break;
case 2:result(entry_Con()); break;
case 3:println(); break;
case 4:exit(1); break;
}
instruction();
}
//Add node to the tree
void addNode()
{
int a;
printf("Enter a integer : ");
scanf("%d",&a);
root=(Node *)InsertTree(root,a);
}
//We want a search key from the user..
Node * entry_Con()
{
printf("Enter a search key in the tree :");
scanf("%d",&a);
initStack();
return CON_ROT_Optimized(root,a);
}
Node * CON_ROT_Optimized(Node *record,int number)
{
int w=0;
record->t++;
push(record);
if(record->number==number)
{
tempAccess=(Node *)pop();
tempParent=(Node *)pop();
tempRoot=(Node *)pop();
if(tempParent==NULL)
w=0;
else if(tempParent->leftChild==tempAccess)
{
w=2*getT(tempAccess)-getT(tempAccess->rightChild)-getT(tempParent);
}
else if(tempParent->rightChild==tempAccess)
{
w=2*getT(tempAccess)-getT(tempAccess->leftChild)-getT(tempParent);
}
printf("W (Condition for Rotation) %d\n",w);
if(w>0)
{
if(tempRoot==NULL)
{
rotation(&tempRoot,&tempParent,&tempAccess);
root=tempRoot;
}
else
{
rotation(&tempRoot,&tempParent,&tempAccess);
}
tempParent->t=calculate_T(tempParent);
tempAccess->t=calculate_T(tempAccess);
}
return tempAccess;
}
else
{
if(number
{
if(record->leftChild!=NULL){
CON_ROT_Optimized(record->leftChild,number);
}
else{
printf("\nThe search key %d is not found in the tree \n\n",a);
}
}else
{
if(record->rightChild!=NULL){
CON_ROT_Optimized(record->rightChild,number);
}
else{
printf("\nThe search key %d is not found in the tree \n\n",a);
}
}
}
}//End method
//End Algorithm Oprimized_CON_ROT
int calculate_T(Node *parentNode)
{
//right Rotation
if(tempAccess->leftChild==tempParent)
{
if(parentNode==tempParent){
if(parentNode->rightChild)
return parentNode->t-tempAccess->t+parentNode->rightChild->t;
else
return parentNode->t-tempAccess->t;
}else if(parentNode==tempAccess){
if(parentNode->rightChild)
return parentNode->t+tempParent->t-parentNode->rightChild->t;
else
return parentNode->t+tempParent->t;
}
}
//left Rotation
else if(tempAccess->rightChild==tempParent)
{
if(parentNode==tempParent){
if(parentNode->leftChild)
return parentNode->t-tempAccess->t+parentNode->leftChild->t;
else
return parentNode->t-tempAccess->t;
}
else if(parentNode==tempAccess){
if(parentNode->rightChild)
return parentNode->t+tempParent->t-parentNode->rightChild->t;
else
return parentNode->t+tempParent->t;
}
}
return -1;
}
int getT(Node *node){
if(node==NULL)
return 0;
else
return node->t;
}
void left_Rotation(Node **root,Node **parent,Node **access)
{
holder=*parent;
printf("\nLeft Rotation\n\n");
if(*root==NULL)
{
*root=(*parent)->leftChild;
(*parent)->leftChild=(*access)->rightChild;
(*root)->rightChild=*parent;
}
else if((*root)->leftChild==*parent)
{
(*root)->leftChild=*access;
(*parent)->leftChild=(*access)->rightChild;
(*access)->rightChild=holder;
}
else if((*root)->rightChild==*parent)
{
(*root)->rightChild=*access;
(*parent)->leftChild=(*access)->rightChild;
(*access)->rightChild=holder;
}
}
void right_Rotation(Node **root,Node **parent,Node **access)
{
holder=*parent;
printf("\nRight Rotation\n\n");
if(*root==NULL)
{
*root=(*parent)->rightChild;
(*parent)->rightChild=(*access)->leftChild;
(*root)->leftChild=*parent;
}
else if((*root)->leftChild==*parent)
{
(*root)->leftChild=*access;
(*parent)->rightChild=(*access)->leftChild;
(*access)->leftChild=holder;
}
else if((*root)->rightChild==*parent)
{
(*root)->rightChild=*access;
(*parent)->rightChild=(*access)->leftChild;
(*access)->leftChild=holder;
}
}
//Rotation function,We decide which rotation will perform in the tree, left rotation or right rotation.....
void rotation(Node **tempRoot,Node **tempParent,Node **tempAccess)
{
/*We evaulate tempRoot and tempParent to perform rotation..
If tempRoot is null then we rotate root's children to be root but
if not then make a rotation according to the tempParent->children
*/
if(*tempRoot==NULL)
{
if((*tempParent)->rightChild!=NULL)
{
if((*tempParent)->rightChild->number==(*tempAccess)->number)
right_Rotation(tempRoot,tempParent,tempAccess);
}
if((*tempParent)->leftChild!=NULL)
{
if((*tempParent)->leftChild->number==(*tempAccess)->number)
left_Rotation(tempRoot,tempParent,tempAccess);
}
}else
if((*tempParent)->leftChild!=NULL){
if((*tempParent)->leftChild->number==(*tempAccess)->number)
{
left_Rotation(tempRoot,tempParent,tempAccess);
}
}
if((*tempParent)->rightChild!=NULL){
if((*tempParent)->rightChild->number==(*tempAccess)->number)
{
right_Rotation(tempRoot,tempParent,tempAccess);
}
}
}
int main()
{
initializeTree();
println_Postfix(root);
instruction();
system("PAUSE");
return 0;
}
Hiç yorum yok:
Yorum Gönder