插入就写了一天 基本在调试 先把插入放出来再说 删除操作就要看缘分了

#include<bits/stdc++.h>
using namespace std;
enum{black,red};
/*红黑树的五个属性*/
typedef struct node{
　　 int key;
　　 int color;
　　 node *right;
　　node *left;
　　node *parent;
}*RedBlackTree;
RedBlackTree T_NIL;
/*哨兵，叶结点的左右子树指针都指向它，根结点的父结点指针也指向它，可以方便后续的操作，所有的结点共用这一结点作为NULL的标志，可以节约空间*/
/*左旋操作，传入红黑树和待旋结点*/
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 Fixup(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 traversal(RedBlackTree T)
{
　　if(T!=T_NIL){
　　traversal(T->left);
　　printf("%d\n",T->key);
　　traversal(T->right);
}
　　return;
}
/*普通插入操作，最后调用了fixup函数*/
void Insert(RedBlackTree &T,int num)
{
　　RedBlackTree x,y,z;
　　if(!T){
　　　　T_NIL=(RedBlackTree)malloc(sizeof(struct node));
　　　　T=(RedBlackTree)malloc(sizeof(struct node));
　　　　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 node));
　　　　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;
　　　　Fixup(T,z);
　　}
　　return;
}
/*不要看着我，我只是一个调试的代码*/
int main()
{
　　RedBlackTree T=NULL;
　　Insert(T,4);
　　Insert(T,2);
　　Insert(T,1);
　　Insert(T,11);
　　Insert(T,8);
　　Insert(T,14);
　　Insert(T,5);
　　Insert(T,15);
　　Insert(T,7);
　　traversal(T);
　　return 0;
}

orz完全不会

　　 终于写完了，以下是完整版的红黑树代码，我就不格式化了，格式化之后代码好像就复制无效了。
　　用截图吧还是……
#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;
}