请高手帮忙修改
#include<stdio.h>#include<stdlib.h>
#define red 0
#define black 1
struct note
{
int data;
struct note *left,*right,*parent;
bool colour;
};
struct note T={0,0,0,0,black};
struct note *NIL=&T;
//左旋转
void Left_Rotate(struct note *root,struct note *x)
{
struct note *y;
y=x->right;
if(y==NIL)
return;
x->right=y->left;//put right[x] to left[y]
if(y->left!=NIL)
y->left->parent=x;
y->parent=x->parent;//put x->parent connect to y
if(x->parent==NIL)
root=y;
else if(x==x->parent->left)
x->parent->left=y;
else
x->parent->right=y;
y->left=x;//put x to y->left
x->parent=y;
}
//右旋转
void Right_Rotate(struct note *root,struct note *x)
{
struct note *y;
y=x->left;
if(y==NIL)
return;
x->left=y->right;
if(y->right!=NIL)
y->left->parent=x;
y->parent=x->parent;
if(x->parent=NIL)
root=y;
else if(x==x->parent->left)
x->parent->left=y;
else
x->parent->right=y;
y->right=x;
x->parent=y;
}
//二叉树插入z
struct note* Tree_Insert(struct note *root,struct note *z)
{
struct note *x,*y;
x=root;
y=NIL;
while(x!=NIL)
{
y=x;
if(x->data>z->data)
x=x->left;
else x=x->right;
}
z->parent=y;
if(y==NIL)
root=z;
else
{
if(z->data<y->data)
y->left=z;
else
y->right=z;
}
z->left=NIL;
z->right=NIL;
return root;
}
//红黑树插入x后，进行着色修正
struct note* RB_Tree(struct note *root,struct note *x)
{
root=Tree_Insert(root,x);
struct note *y;
x->colour=red;
x->left=NIL;
x->right=NIL;
while((x!=root)&&(x->parent->colour=red))
{
if(x->parent==x->parent->parent->left)
{
y=x->parent->parent->right;
if(y->colour==red)
{
x->parent->colour=black;
y->colour=black;
x->parent->parent->colour=red;
x=x->parent->parent;
}
else
{
if(x==x->parent->right)
{
x=x->parent;
Left_Rotate(root,x);
}
x->parent->colour=black;
x->parent->parent->colour=red;
Right_Rotate(root,x->parent->parent);
}
}
else
{
y=x->parent->parent->left;
if((y->colour==red)&&(y!=NIL))
{
x->parent->colour=black;
y->colour=black;
x->parent->parent->colour=red;
x=x->parent->parent;
}
else
{
if(x==x->parent->left)
{
x=x->parent;
Right_Rotate(root,x);
}
x->parent->colour=black;
x->parent->parent->colour=red;
Left_Rotate(root,x->parent->parent);
}
}
}
root->colour=black;
return root;
}
//输出
void Print(struct note *x)
{
if(x!=NIL)
{
Print(x->left);
printf("%4d,%4d\n",x->data,x->colour);
Print(x->right);
}
}
//求树中的最小值
struct note * Tree_Min(struct note *x)
{
while(x->left!=NULL)
{
x=x->left;
}
return x;
}
//后继（也就是大于key[X]的最小值）
struct note* Tree_Successor(struct note *x)
{
struct note *y;
if(x->right!=NIL)
return Tree_Min(x->right);
y=x->parent;
while((y!=NIL)&&(x==y->right))
{
x=y;
y=y->parent;
}
return y;
}
//删除后修复红黑树
void RB_Delete_Fixup(struct note *root,struct note *x)
{
struct note *w;
while((x!=root)&&(x->colour==black))
{
//===============x在左边的============================
if(x==x->parent->left)
{
w=x->parent->right;
//==============第一种情况======================
if(w->colour==red)
{
w->colour=black;
x->parent->colour=red;
Left_Rotate(root,x->parent);
w=x->parent->right;
}
//=============第二种情况=======================
if((w->left->colour=black)&&(w->right->colour=black))
{
w->colour=red;
x=x->parent;
}
else
{
//=============第三种情况=====================
if(w->right->colour=black)
{
w->left->colour=black;
w->colour=red;
Right_Rotate(root,w);
w=x->parent->right;
}
//=============第四种情况=====================
w->colour=x->parent->colour;
x->parent->colour=black;
w->right->colour=black;
Left_Rotate(root,x->parent);
x=root;
}
}
//======================================================
else
{
w=x->parent->left;
if(w->colour==red)
{
w->colour=black;
x->parent->colour=red;
Right_Rotate(root,x->parent);
w=x->parent->left;
}
if((w->left->colour=black)&&(w->right->colour=black))
{
w->colour=red;
x=x->parent;
}
else
{
if(w->left->colour=black)
{
w->right->colour=black;
w->colour=red;
Left_Rotate(root,w);
w=x->parent->left;
}
w->colour=x->parent->colour;
x->parent->colour=black;
w->right->colour=black;
Right_Rotate(root,x->parent);
x=root;
}
}
x->colour=black;
}
//红黑树删去z
struct note* Tree_Delete(struct note *root,struct note *z)
{
struct note *y,*x;
//==========z的儿女情况=================
if((z->left==NIL)||(z->right==NIL))
y=z;
else
y=Tree_Successor(z);
//======================================
//======此时的y有一子女或没有子女=======
if(y->left!=NIL)
x=y->left;
else
x=y->right;
//if(x!=NULL)
x->parent=y->parent;
if(y->parent==NIL)
root=x;
else
{
if(y=y->parent->left)
y->parent->left=x;
else
y->parent->right;
}
//=====z有两个子女的情况===============
if(y!=z)
z->data=y->data;
if(y->colour=black)
RB_Delete_Fixup(root,x);
return y;
}
//查找删除的节点
struct note* find_key(struct note *root,int key)
{
struct note *x;
x=root;
if((x==NULL)||(key==x->data))
return x;
if(key<x->data)
return find_key(x->left,key)
else
return find_key(x->right,key);
}
void main()
{
struct note *root,*key,*k;
int dat;
root=NIL;
key=(struct note*)malloc(sizeof(struct note));
printf("输入数据：\n");
scanf("%d",&key->data);
while(key->data!=0)
{
root=RB_Tree(root, key);
key=(struct note*)malloc(sizeof(struct note));
scanf("%d",&key->data);
}
printf("root:%d,%d\n",root->data,root->colour);
printf("从小到大输出数据：\n");
Print(root);
printf("输入删除的节点：\n");
scanf("%d",k->data);
k=find_key(root,dat);
k=Tree_Delete(root,k);
RB_Delete_Fixup(root,k);
Print(root);
}
