Thursday, July 28, 2011

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!!!

No comments:

Post a Comment

Your Comment is Our Order, Your Majesty