终于写完了，以下是完整版的红黑树代码，我就不格式化了，格式化之后代码好像就复制无效了。
　　用截图吧还是……
#include<stdio.h>
#include<stdlib.h>
#define MaxSize 10000
enum{black,red};
typedef struct TreeNode{
int key;
int color;
TreeNode *right;
TreeNode *left;
TreeNode *parent;
}*RedBlackTree;
RedBlackTree T_NIL;
void LeftRotate(RedBlackTree &T,RedBlackTree x)
{
RedBlackTree y;
y=x->right;
x->right=y->left;
if(y->left!=T_NIL){
y->left->parent=x;
}
y->parent=x->parent;
if(x->parent==T_NIL){
T=y;
}
else if(x==x->parent->left){
x->parent->left=y;
}
else x->parent->right=y;
y->left=x;
x->parent=y;
}
void RightRotate(RedBlackTree &T,RedBlackTree x)
{
RedBlackTree y;
y=x->left;
x->left=y->right;
if(y->right!=T_NIL){
y->right->parent=x;
}
y->parent=x->parent;
if(x->parent==T_NIL){
T=y;
}
else if(x==x->parent->right){
x->parent->right=y;
}
else x->parent->left=y;
y->right=x;
x->parent=y;
}
void InsertFixup(RedBlackTree &T,RedBlackTree z)
{
RedBlackTree y;
while(z->parent->color==red){
if(z->parent==z->parent->parent->left){
y=z->parent->parent->right;
if(y->color==red){
z->parent->color=black;
y->color=black;
z->parent->parent->color=red;
z=z->parent->parent;
}
else{
if(z==z->parent->right){
z=z->parent;
LeftRotate(T,z);
}
z->parent->color=black;
z->parent->parent->color=red;
RightRotate(T,z->parent->parent);
}
}
else if(z->parent==z->parent->parent->right){
y=z->parent->parent->left;
if(y->color==red){
z->parent->color=black;
y->color=black;
z->parent->parent->color=red;
z=z->parent->parent;
}
else{
if(z==z->parent->left){
z=z->parent;
RightRotate(T,z);
}
z->parent->color=black;
z->parent->parent->color=red;
LeftRotate(T,z->parent->parent);
}
}
}
T->color=black;
}
void Insert(RedBlackTree &T,int num)
{
RedBlackTree x,y,z;
if(!T){
T_NIL=(RedBlackTree)malloc(sizeof(struct TreeNode));
T=(RedBlackTree)malloc(sizeof(struct TreeNode));
T->parent=T_NIL;
T->color=black;
T->left=T_NIL;
T->right=T_NIL;
T->key=num;
T_NIL->color=black;
}
else{
z=(RedBlackTree)malloc(sizeof(struct TreeNode));
y=T_NIL;
x=T;
while(x!=T_NIL){
y=x;
if(num<x->key)x=x->left;
else if(num>x->key)x=x->right;
else return;
}
if(num<y->key)y->left=z;
else y->right=z;
z->left=T_NIL;
z->right=T_NIL;
z->color=red;
z->parent=y;
z->key=num;
InsertFixup(T,z);
}
return;
}
void Transplant(RedBlackTree &T,RedBlackTree u,RedBlackTree v)
{
if(u->parent==T_NIL){
T=v;
}
else if(u==u->parent->left){
u->parent->left=v;
}
else u->parent->right=v;
v->parent=u->parent;
return;
}
RedBlackTree TreeMinimum(RedBlackTree x){
while(x->left!=T_NIL){
x=x->left;
}
return x;
}
void DeleteFixup(RedBlackTree &T,RedBlackTree x)
{
RedBlackTree w;
while(x!=T&&x->color==black){
if(x==x->parent->left){
w=x->parent->right;
if(w->color==red){
w->color==black;
x->parent->color==red;
LeftRotate(T,x->parent);
w=x->parent->right;
}
if(w->left->color==black&&w->right->color==black){
w->color=red;
x=x->parent;
}
else if(w->right->color==black){
w->left->color=black;
w->color=red;
RightRotate(T,w);
w=x->parent->right;
}
w->color=x->parent->color;
x->parent->color=black;
w->right->color=black;
LeftRotate(T,x->parent);
x=T;
}
else{
w=x->parent->left;
if(w->color==red){
w->color==black;
x->parent->color==red;
RightRotate(T,x->parent);
w=x->parent->left;
}
if(w->right->color==black&&w->left->color==black){
w->color=red;
x=x->parent;
}
else if(w->left->color==black){
w->right->color=black;
w->color=red;
LeftRotate(T,w);
w=x->parent->left;
}
w->color=x->parent->color;
x->parent->color=black;
w->left->color=black;
RightRotate(T,x->parent);
x=T;
}
}
return;
}
RedBlackTree Search(RedBlackTree T,int x)
{
while(x!=T->key&&T!=T_NIL){
if(x>T->key)T=T->right;
else T=T->left;
}
return T;
}
void Delete(RedBlackTree &T,int num)
{
RedBlackTree z=Search(T,num);
RedBlackTree x,y=z;
int y_OriginalColor=y->color;
if(z->left==T_NIL){
x=z->left;
Transplant(T,z,z->left);
}
else if(z->right==T_NIL){
x=z->right;
Transplant(T,z,z->left);
}
else{
y=TreeMinimum(z->right);
x=y->right;
if(y->parent==z)
x->parent=y;
else{
Transplant(T,y,y->right);
y->right=z->right;
y->right->parent=y;
}
Transplant(T,z,y);
y->left=z->left;
y->left->parent=y;
y->color=z->color;
}
if(y_OriginalColor==black)
DeleteFixup(T,x);
return;
}
struct QueueNode{
RedBlackTree data[MaxSize];
int rear;
int front;
}queue;
struct QueueNode *p=&queue;
void Enqueue(RedBlackTree T){
p->rear=(p->rear+1)%MaxSize;
p->data[p->rear]=T;
}
RedBlackTree Dequeue(){
p->front=(p->front+1)%MaxSize;
return p->data[p->front];
}
bool IsEmpty(){
if(p->front==p->rear)return true;
else return false;
}
void InOrderTraversal(RedBlackTree T)
{
if(T!=T_NIL){
InOrderTraversal(T->left);
printf("%d ",T->key);
InOrderTraversal(T->right);
}
return;
}
void LevelOrderTraversal(RedBlackTree T)
{
printf("%d ",T->key);
Enqueue(T);
while(!IsEmpty()){
T=Dequeue();
if(T->left!=T_NIL){
printf("%d ",T->left->key);
Enqueue(T->left);
}
if(T->right!=T_NIL){
printf("%d ",T->right->key);
Enqueue(T->right);
}
}
return;
}
int main()
{
p->front=p->rear=0;
RedBlackTree T=NULL;
Insert(T,1);
Insert(T,2);
Insert(T,14);
Insert(T,5);
Insert(T,11);
Insert(T,8);
Insert(T,5);
Insert(T,15);
Insert(T,7);
InOrderTraversal(T);
printf("\n");
LevelOrderTraversal(T);
Delete(T,8);
Delete(T,1);
printf("\n");
InOrderTraversal(T);
printf("\n");
LevelOrderTraversal(T);
return 0;
}