/*binary tree structure*/
typedef struct _btree{
int value;
struct _btree* left;
struct _btree* right;
}btree;
/*insert node into tree*/
void insert(btree** root,int nv)
{
btree* p=*root,*pre=*root;
while(p != 0){
pre=p;
if(p->value == nv){
return;
}
else if(p->value < nv){
p=p->right;
}
else{
p=p->left;
}
}
p=malloc(sizeof(btree));
memset(p,0,sizeof(p));
p->value=nv;
p->left=0;
p->right=0;
if(*root == 0){
*root=p;
}
else if(pre->value < nv){
pre->right=p;
}
else if(pre->value > nv){
pre->left=p;
}
}
/*print binary tree*/
void _print(btree* p,int level)
{
int i=0;
if(p != 0){
_print(p->right,level+1);
for(i=0;i<level*3;i++){
printf(" ");
}
printf("%d\n",p->value);
_print(p->left,level+1);
}
}
void print(btree* root)
{
_print(root,0);
}
/*destroy binary tree*/
void destroy(btree** root)
{
if(*root != 0){
destroy(&(*root)->left);
destroy(&(*root)->right);
free(*root);
/*printf("destroy:0x%x\n",*root);*/
*root=0;
}
}
/*find node in binary tree*/
btree* find(btree* root,int nv)
{
while(root != 0 && root->value != nv){
if(root->value < nv){
root=root->right;
}
else{
root=root->left;
}
}
return root;
}
/*delete a node by merging*/
void deleteMerge(btree** root,int nv)
{
btree* c=*root,*pre=*root,*tmp=*root;
/*first,find it*/
while(c != 0 && c->value != nv){
pre=c;
c=(c->value<nv)? c->right:c->left;
}
/*delete if found*/
if(c == 0){
return;
}
/*delete root*/
if(c == pre){
if(c->left ==0 && c->right == 0){
*root=0;
}
else if(c->left == 0){
*root=c->right;
}
else if(c->right ==0){
*root=c->left;
}
else{
tmp=c->left;
while(tmp->right != 0){
tmp=tmp->right;
}
tmp->right=c->right;
*root=c->left;
}
}
/*delete node*/
else{
if(c->left == 0 && c->right == 0){
pre->left=(pre->left==c)? 0:pre->left;
pre->right=(pre->right==c)? 0:pre->right;
}
else if(c->left == 0){
pre->left=(pre->left==c)? c->right:pre->left;
pre->right=(pre->right==c)? c->right:pre->right;
}
else if(c->right == 0){
pre->left=(pre->left==c)? c->left:pre->left;
pre->right=(pre->right==c)? c->left:pre->right;
}
else{
tmp=c->left;
while(tmp->right != 0){
tmp=tmp->right;
}
tmp->right=c->right;
pre->left=(pre->left==c)? c->left:pre->left;
pre->right=(pre->right==c)? c->left:pre->right;
}
}
free(c);
}
/*delete by copying*/
void deleteCopy(btree** root,int nv)
{
btree *c=*root,*pre=*root,*tmp=*root,*tPre=*root;
/*first,find it*/
while(c != 0 && c->value != nv){
pre=c;
c=(c->value<nv)? c->right:c->left;
}
/*then,delete it*/
if(c == 0){
return;
}
/*the node is root?*/
if(c == pre){
if(c->left == 0 && c->right == 0){
*root=0;
}
else if(c->left == 0){
*root=c->right;
}
else if(c->right == 0){
*root=c->left;
}
else{
tPre=tmp=c->left;
while(tmp->right != 0){
tPre=tmp;
tmp=tmp->right;
}
if(tmp == tPre){
c->value=tmp->value;
c->left=tmp->left;
c=tmp;
}
else{
c->value=tmp->value;
tPre->right=tmp->left;
c=tmp;
}
}
}
/*common node*/
else{
if(c->left == 0 && c->right == 0){
pre->left=(pre->left==c)? 0:pre->left;
pre->right=(pre->right==c)? 0:pre->right;
}
else if(c->left == 0){
pre->left=(pre->left==c)? c->right:pre->left;
pre->right=(pre->right==c)? c->right:pre->right;
}
else if(c->right == 0){
pre->left=(pre->left==c)? c->left:pre->left;
pre->right=(pre->right==c)? c->left:pre->right;
}
else{
tPre=tmp=c->left;
while(tmp->right != 0){
tPre=tmp;
tmp=tmp->right;
}
if(tPre == tmp){
c->value=tmp->value;
c->left=tmp->left;
c=tmp;
}
else{
c->value=tmp->value;
tPre->right=tmp->left;
c=tmp;
}
}
}
free(c);
}
/*delete by copying in right hand*/
void deleteCopyRight(btree** root,int nv)
{
btree *c=*root,*pre=*root,*tmp=*root,*tPre=*root;
/*first,find it*/
while(c != 0 && c->value != nv){
pre=c;
c=(c->value<nv)? c->right:c->left;
}
/*then,delete it*/
if(c == 0){
return;
}
/*the node is root?*/
if(c == pre){
if(c->left == 0 && c->right == 0){
*root=0;
}
else if(c->left == 0){
*root=c->right;
}
else if(c->right == 0){
*root=c->left;
}
else{
tPre=tmp=c->right;
while(tmp->left != 0){
tPre=tmp;
tmp=tmp->left;
}
if(tmp == tPre){
c->value=tmp->value;
c->right=tmp->right;
c=tmp;
}
else{
c->value=tmp->value;
tPre->left=tmp->right;
c=tmp;
}
}
}
/*common node*/
else{
if(c->left == 0 && c->right == 0){
pre->left=(pre->left==c)? 0:pre->left;
pre->right=(pre->right==c)? 0:pre->right;
}
else if(c->left == 0){
pre->left=(pre->left==c)? c->right:pre->left;
pre->right=(pre->right==c)? c->right:pre->right;
}
else if(c->right == 0){
pre->left=(pre->left==c)? c->left:pre->left;
pre->right=(pre->right==c)? c->left:pre->right;
}
else{
tPre=tmp=c->right;
while(tmp->left != 0){
tPre=tmp;
tmp=tmp->left;
}
if(tPre == tmp){
c->value=tmp->value;
c->right=tmp->right;
c=tmp;
}
else{
c->value=tmp->value;
tPre->left=tmp->right;
c=tmp;
}
}
}
free(c);
}
/*rotate right*/
void rotateRight(btree** root,btree* gr,btree* par,btree* ch)
{
if(ch == *root || ch == 0)
return;
par->left=ch->right;
ch->right=par;
if(par != *root){
gr->left=(gr->left==par)? ch:gr->left;
gr->right=(gr->right==par)? ch:gr->right;
}
else{
*root=ch;
}
}
/*rotate left*/
void rotateLeft(btree** root,btree* gr,btree* par,btree* ch)
{
if(ch == *root || ch == 0)
return;
par->right=ch->left;
ch->left=par;
if(par != *root){
gr->left=(gr->left==par)? ch:gr->left;
gr->right=(gr->right==par)? ch:gr->right;
}
else{
*root=ch;
}
}
/*dsw perfect tree*/
void dswTree(btree** root)
{
btree *cur=*root,*tmp=*root,*gr=*root;
int cnt=0,m=0,level=0,tn=0;
double dm=0;
/*first,create main chain*/
while(cur != 0){
if(cur->left != 0){
tmp=cur->left;
rotateRight(root,gr,cur,cur->left);
cur=tmp;
if(cur->right == gr){
gr=cur;
}
}
else{
gr=cur;
cur=cur->right;
}
}
/*count number of tree*/
for(cur=*root;cur!=0;cur=cur->right,cnt++){
}
/*calculate the special number*/
dm=log10(cnt+1)/log10(2);
m=(int)dm;
m=(dm-m>=0.5)? m+1:m;
level=m;
m=pow(2,m)-1;
m=cnt-m;
cnt=cnt-m;
/*process the special numbers*/
cur=gr=*root;
while(m-->0){
tmp=cur->right;
rotateLeft(root,gr,cur,tmp);
gr=tmp;
cur=tmp->right;
tmp=tmp->right;
}
/*process the next number*/
gr=cur=*root;
tmp=cur->right;
while(level-- > 1){
gr=cur=*root;
tmp=cur->right;
cnt=cnt/2;
tn=0;
while(tmp != 0 && tmp->right != 0 && tn++ < cnt){
rotateLeft(root,gr,cur,tmp);
gr=tmp;
cur=tmp->right;
tmp=cur->right;
}
}
}
/*main and some other functions*/
void clearscreen();
char mainMenu();
void insertDefault(btree**root);
void printTree(btree*root);
void insertUI(btree**root);
void deleteMergeUI(btree**root);
void deleteCopyUI(btree**root);
void deleteCopyRightUI(btree**root);
void insertContinous(btree**root);
void rotateRightUI(btree**root);
void rotateLeftUI(btree**root);
void dswTreeUI(btree**root);
void main()
{
btree *root=0;
char ch=0;
printf("binary tree start.\n");
while(ch != 'f'){
clearscreen();
ch=mainMenu();
switch(ch){
case 'a':insertUI(&root);break;
case 'b':insertDefault(&root);break;
case 'c':deleteMergeUI(&root);break;
case 'd':deleteCopyUI(&root);break;
case 'e':deleteCopyRightUI(&root);break;
case 'f':break;/*exit*/
case 'g':printTree(root);break;
case 'h':insertContinous(&root);break;
case 'i':rotateRightUI(&root);break;
case 'j':rotateLeftUI(&root);break;
case 'k':dswTreeUI(&root);break;
default:break;
}
}
destroy(&root);
printf("Press any key to continue.\n");
getch();
return;
}
void dswTreeUI(btree**root)
{
clearscreen();
printf("befor dsw transform:\n");
print(*root);
printf("after dsw transform:\n");
dswTree(root);
print(*root);
printf("Press any key to continue\n");
getch();
}
void rotateLeftUI(btree**root)
{
int nv=0;
btree *gr=*root,*par=*root,*ch=*root;
clearscreen();
print(*root);
printf("Please input a node to rotate left:\n");
scanf("%d",&nv);
while(ch !=0 && ch->value != nv){
gr=par;
par=ch;
if(ch->value < nv){
ch=ch->right;
}
else{
ch=ch->left;
}
}
rotateLeft(root,gr,par,ch);
}
void rotateRightUI(btree**root)
{
int nv=0;
btree *gr=*root,*par=*root,*ch=*root;
clearscreen();
print(*root);
printf("Please input a node to rotate right:\n");
scanf("%d",&nv);
while(ch !=0 && ch->value != nv){
gr=par;
par=ch;
if(ch->value < nv){
ch=ch->right;
}
else{
ch=ch->left;
}
}
rotateRight(root,gr,par,ch);
}
void insertContinous(btree**root)
{
int i=0,cnt=0;
printf("please input the max num:\n");
scanf("%d",&cnt);
for(i=0;i<cnt;i++){
insert(root,i);
}
}
void clearscreen()
{
int i=0;
for(i=0;i<30;i++){
printf("\n");
}
}
char mainMenu()
{
char ch=0;
printf("a.insert\tb.insert default\th.insert continous\n");
printf("c.delete merge\td.delete copy\te.delete copy right\n");
printf("g.print\n");
printf("i.rotate right\tj.rotate left\tk.dsw perfect tree\n");
printf("f.exit\n");
printf("please enter your choice:\n");
ch=getch();
return ch;
}
void insertDefault(btree** root)
{
insert(root,5);
insert(root,10);
insert(root,20);
insert(root,15);
insert(root,30);
insert(root,25);
insert(root,40);
insert(root,23);
insert(root,28);
insert(root,25);
insert(root,20);
insert(root,30);
insert(root,10);
insert(root,23);
insert(root,28);
insert(root,40);
insert(root,5);
insert(root,6);
insert(root,15);
insert(root,2);
insert(root,4);
insert(root,1);
insert(root,0);
insert(root,26);
insert(root,29);
insert(root,38);
insert(root,42);
}
void printTree(btree* root)
{
clearscreen();
print(root);
printf("Press any key to continue\n");
getch();
}
void insertUI(btree** root)
{
int nv=0;
clearscreen();
print(*root);
printf("Please input a new node:\n");
scanf("%d",&nv);
insert(root,nv);
}
void deleteMergeUI(btree**root)
{
int nv=0;
clearscreen();
print(*root);
printf("Please input a node to delete by merging:\n");
scanf("%d",&nv);
deleteMerge(root,nv);
}
void deleteCopyUI(btree**root)
{
int nv=0;
clearscreen();
print(*root);
printf("Please input a node to delete by coping:\n");
scanf("%d",&nv);
deleteCopy(root,nv);
}
void deleteCopyRightUI(btree**root)
{
int nv=0;
clearscreen();
print(*root);
printf("Please input a node to delete by coping:\n");
scanf("%d",&nv);
deleteCopyRight(root,nv);
}
