Introvertuism: project

Showing posts with label project. Show all posts

Thursday, July 28, 2011

Height Balance Tree with coord

//compiled with Code:Block 10.05
#include<iostream>
#include<cmath>
#include<conio.h>
#include<windows.h>
using namespace std;

struct Node{
int data;
int height;
Node *left;
Node *right;};
typedef Node* ptr;

ptr Insert(int x, ptr p);
ptr findMin(ptr root);
ptr Delete(int x, ptr p);
int GetMaxDepth(ptr root, int depth);
void GoToXY(int x,int y);
void Print(ptr root,int d,int c,int swing);
ptr RotateLeft(ptr x);
ptr RotateRight(ptr x);
int BalanceFactor(ptr x);
ptr RebalanceTree(ptr x);
template<class T>
void tempStore(T* R);

int main()
{
char j = '1';
ptr Root = 0;
int h;
char in[8];
in[0] = 'C' ;
//cout<<"1.Input\n2.Delete\n Type answer : ";
do
{
cout<<"1.Input\n2.Delete\n Type answer : ";
cin>>j;
if (j == '1')
{
system("cls");
while (true)
{
system("cls");
cout<<"Enter integer number, X or x for select menu: ";
cin>>in;
if (in[0] == 'x' || in[0] == 'X')
break;
h= atoi(in);
Root = Insert(h,Root);
tempStore(Root );
getch();
}
}
else
{
if (j =='2')
{
while(true)
{
system("cls");
cout<<"Enter Value to Delete, X or x for select menu: ";
cin>>in;
if (in[0] == 'x' || in[0] == 'X')
break;
h= atoi(in);
Root = Delete(h,Root);
tempStore(Root );
getch();
system("cls");
}
}

}
}while(j>= 'a' || j<='z' || j>='A' || j<='Z' );
}

ptr Insert (int x, ptr p)
{
ptr temp;
if (!p)
{
temp = new Node;
temp->data = x;
temp->left = temp->right = 0;
temp->height= 0;
return temp;
}
else
{
if( x < p->data)
p->left=Insert(x,p->left);
else
{
if( x > p->data)
p->right=Insert(x,p->right);
}
}
p->height = BalanceFactor(p);
if (abs(p->height) >1 )
p = RebalanceTree(p);
return p;
}

ptr findMin(ptr root)
{
if (root->left)
return findMin(root->left);
else
return root;
}

ptr Delete(int x, ptr p)
{
ptr temp;
if (!p)
return 0;
else
{
if ( x > p->data)
{
temp = Delete(x,p->right);
p->right = temp;
}
else
{
if ( x < p->data)
{
temp = Delete(x,p->left);
p->left= temp;
}
else
{
if (p->left && p->right)
{
ptr swap = findMin(p->right);
p->data = swap->data;
temp = Delete(swap->data,p->right);
p->right = temp;
}
else
{
ptr a = (p->right)?p->right:p->left;
p = 0;
delete p;
return a;

}
}
}
}
p->height = BalanceFactor(p);
if (abs(p->height) >1 )
p = RebalanceTree(p);
return p;
}

int GetMaxDepth(ptr root, int depth)
{
if (!root)
return depth -1;
else
{
int a,b;
a = GetMaxDepth(root->left,depth+1);
b = GetMaxDepth(root->right,depth +1);
return (a>b)?a:b;
}
}

void GoToXY(int x,int y)
{
COORD coord;
coord.X = x ;coord.Y = y;
SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),coord);
}

void Print(ptr root,int d,int c,int swing)
{
if (root)
{
if (root->left)
{
GoToXY(swing + pow(2,d-c-1),(c+1)*2);
cout<<'|';

GoToXY(swing + pow(2,d-c-1),(c+1)*2-1);
for(int i = pow(2,d-c-1);i< pow(2,d-c);i++)
cout<<'_';
}
if (root->right)
{
GoToXY(swing + pow(2,d-c-1) + pow(2,d-c),(c+1)*2);
cout<<'|';

GoToXY(swing + pow(2,d-c-1) + pow(2,d-c),(c+1)*2-1);
for(int i = pow(2,d-c-1);i<= pow(2,d-c);i++)
{
cout<<'_';GoToXY(swing + pow(2,d-c-1) + pow(2,d-c)-(i-pow(2,d-c-1)),(c+1)*2-1);
}
}
GoToXY(swing + pow(2,d-c),(c+1)*2 -1);
cout<<root->data;
Print(root->left,d,c+1,swing);
Print(root->right,d,c+1,swing + pow(2,d-c));
}
}

ptr RotateLeft(ptr x)
{
ptr temp = x->right;
x->right = x->right->left;
temp->left = x;
return temp;
}

ptr RotateRight(ptr x)
{
ptr temp = x->left;
x->left = x->left->right;
temp->right = x;
return temp;
}

int BalanceFactor(ptr x)
{
return GetMaxDepth(x->left,1) - GetMaxDepth(x->right,1);
}
ptr RebalanceTree(ptr x)
{
if (x->height == 2)
{
if (x->left->height ==1)
return RotateRight(x);
else
{
x->left = RotateLeft(x->left);
return RotateRight(x);
}
}
else
{
if (x->right->height ==-1)
return RotateLeft(x);
else
{
x->right = RotateRight(x->right);
return RotateLeft(x);
}
}
}

template<class T>
void tempStore(T* R)
{
Print(R,GetMaxDepth(R,1),0,0);
GoToXY(0,GetMaxDepth(R,1)+1);
}

//L

//Jangan cumacopy-paste doang!!pelajari!!

//Project ini dibuat semata-mata untuk pembelajaran

Height Balance Tree with coord

Binary Search Tree with Coord

//Compiled with CodeBlock 10.05
#include<iostream>
#include<cmath>
#include<conio.h>
#include<windows.h>
#include<cstdlib>
using namespace std;

struct Node{
int data;
Node* left;
Node* right;};
typedef Node* ptr;

ptr Insert(int dat, ptr root);
ptr findMin(ptr root);
ptr Delete(int value, ptr root);
int GetMaxDepth(ptr root, int depth);
void GoToXY(int x,int y);
void Print(ptr root,int d,int c,int swing);
template<class T>
void tempStore(T* R);

int main()
{
char j = \'1\';
ptr Root = 0;
int h;
char in[8];
in[0] = \'C\' ;
//cout<<\"1.Input\\n2.Delete\\n   Type answer : \";
do
{
cout<<\"1.Input\\n2.Delete\\n Type answer : \";
cin>>j;
if (j == \'1\')
{
system(\"cls\");
while (true)
{
system(\"cls\");
cout<<\"Enter integer number, X or x for select menu: \";
cin>>in;
if (in[0] == \'x\' || in[0] == \'X\')
break;
h= atoi(in);
Root = Insert(h,Root);
tempStore(Root );
getch();
}
}
else
{
if (j ==\'2\')
{
while(true)
{
system(\"cls\");
cout<<\"Enter Value to Delete, X or x for select menu: \";
cin>>in;
if (in[0] == \'x\' || in[0] == \'X\')
break;
h= atoi(in);
Root = Delete(h,Root);
tempStore(Root );
//               cout<<\"Successfull deletion\";
getch();
system(\"cls\");
}
}

}
}while(j>= \'a\' || j<=\'z\' || j>=\'A\' || j<=\'Z\' );
return EXIT_SUCCESS;
}

ptr Insert(int dat, ptr root)
{
ptr temp1;
ptr temp2;
ptr current;
current = new Node;
current->data = dat;
current->left = NULL;
current->right = NULL;
if(root==NULL)
{
root = current;
}
else
{
temp1 = root;
while(temp1 != NULL)
{
temp2 = temp1;
if(current->data < temp1->data)
temp1 = temp1->left;
else
if(current->data > temp1->data)
temp1 = temp1->right;
else
{
//cout<<\"Duplicate value!!\";
delete current;
break;
}
}
if(temp1==NULL)
{
if(current->data<temp2->data)
temp2->left = current;
else
temp2->right = current;
}
//     cout<<\"Insert data success\";
}
return (root);
}

ptr findMin(ptr root)
{
ptr prev = root;
ptr cur = root->right;
if (root->left)
{
prev = cur;
cur = cur->left;
}
if( prev == root )
return prev->right = cur->right;
else
prev->left = cur->right;
root->data = cur->data;
delete cur;
}

int isLeft(ptr parent, ptr cur)
{
int ans;
if(parent->left == cur)
ans = 0;
else
ans=1;
return ans;
}

int isRight(ptr parent, ptr cur)
{
int ans;
if(parent->right==cur)
ans = 0;
else
ans =1;
return ans;
}

ptr Delete(int value,ptr root)
{
ptr temp1=NULL;
ptr temp2=NULL;
ptr current=NULL;
int val;
int ans;
temp1=root;
while(value!= temp1->data)
{
temp2=temp1;
if(value<temp1->data)
temp1=temp1->left;
else
temp1=temp1->right;
if(temp1==NULL)
break;
}

if(temp1==NULL)
{
//cout<<\"\\nThere is no value in Tree\";
}
else
{
current= temp1;
if(current->left==NULL && current->right==NULL)
{
//cout<<\"\\ndeleting data\"<<current->data;
if(temp2==NULL)
{
//cout<<\"\\nDeleting leaf node in tree\";
}
else
{
ans=isLeft(temp2,current);
if(ans==0)
temp2->left=NULL;
ans=isRight(temp2,current);
if(ans==0)
temp2->right=NULL;
}
delete current;
}
else
if(current->left==NULL || current->right==NULL)
{
//cout<<\"\\nDelete one node with one child: \"<<current->data;
if(current->left !=NULL)
{
if(temp2==0)
{
//   cout<<\"Delete root with one left subtree\";
root=current->left;
}
else
{
ans=isLeft(temp2,current);
if(ans==0)
temp2->left=current->left;
ans=isRight(temp2,current);
if(ans==0)
temp2->right=current->left;
}
}
if(current->right !=NULL)
{
if(temp2==0)
{
// cout<<\"\\nDelete root with right subtree\";
root=current->right;
}//end of if
else
{
ans=isLeft(temp2,current);

if(ans==0)
temp2->left=current->right;
ans=isRight(temp2,current);

if(ans==0)
temp2->right=current->right;
}
}
delete current;
}
else if(current->left!=NULL && current->right!=NULL)
{
//cout<<\"\\nDelete node with two children\";
//cout<<\"\\nMinimum value\";
temp1=current->right;
while(temp1->left !=NULL)
temp1=temp1->left;
//cout<<\"deleting and reconstruct\";
val=temp1->data;
Delete(val,root);
current->data=val;
}
}
return(root);
}

int GetMaxDepth(ptr root, int depth)
{
if (!root)
return depth -1;
else
{
int a,b;
a = GetMaxDepth(root->left,depth+1);
b = GetMaxDepth(root->right,depth +1);
return (a>b)?a:b;
}
}

void GoToXY(int x,int y)
{
COORD coord;
coord.X = x ;
coord.Y = y;
SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),coord);
}

void Print(ptr root,int d,int c,int swing)
{
if (root)
{
if (root->left)
{
GoToXY(swing + pow(2,d-c-1),(c+1)*2);
cout<<\'|\';

GoToXY(swing + pow(2,d-c-1),(c+1)*2-1);
for(int i = pow(2,d-c-1);i< pow(2,d-c);i++)
cout<<\'_\';
}
if (root->right)
{
GoToXY(swing + pow(2,d-c-1) + pow(2,d-c),(c+1)*2);
cout<<\'|\';

GoToXY(swing + pow(2,d-c-1) + pow(2,d-c),(c+1)*2-1);
for(int i = pow(2,d-c-1);i<= pow(2,d-c);i++)
{
cout<<\'_\';GoToXY(swing + pow(2,d-c-1) + pow(2,d-c)-(i-pow(2,d-c-1)),(c+1)*2-1);
}
}
GoToXY(swing + pow(2,d-c),(c+1)*2 -1);
cout<<root->data;
Print(root->left,d,c+1,swing);
Print(root->right,d,c+1,swing + pow(2,d-c));
}
}

template<class T>
void tempStore(T* R)
{
Print(R,GetMaxDepth(R,1),0,0);
GoToXY(0,GetMaxDepth(R,1)+1);
}

//L

//Jangan cuma copy-paste doang! Majukan negeri ini!!!