这个东东处理细节问题弄了很久很久~特别是旋转和着色部分~还是终于完成插入部分了~对比过正规版的暂时没有发现出入(不知道~不排除存在bug)~
红黑树的精髓感觉在于删除部分~AVL树删除节点可以先放放~不过红黑树这个最好还是要学学的~~删除节点部分看来又要大涨代码量了~不知道什么时候能弄好呢~
PS:Common.h小改了一下~兼容.cpp顺便在这里发发代码方便参考~
Common.h可以参考这个网址~
https://bbs.bccn.net/thread-478689-1-1.html




07011835更~小改了一下代码~多测试了一组数据没有发现bug~准备构思删除节点工作~

07021357更~有同友反映了.cpp格式不能通过编译~还是数据类型问题~已经改好了~


PS:Common.h里面或许有些编译器不支持_int64那个可以去掉(毕竟64位比较函数比较少用)~

#include"Common.h"
#include<time.h>
typedef enum RB_Tree_Setcolor
{
    RED,
    BLACK,
}RB_Tree_Setcolor;

typedef enum RB_Tree_Location   //记录该节点的位置
{
    NIL,
    LEFT,
    RIGHT,
}RB_Tree_Location;

typedef int ElemType;

typedef struct RB_Tree_Node       //定义红黑树节点
{
    struct RB_Tree_Node* left;
    struct RB_Tree_Node* right;
    struct RB_Tree_Node* parent;

    RB_Tree_Setcolor color;
    RB_Tree_Location location;

    ElemType key;

}RB_Tree_Node;

typedef struct RB_Tree_Root    //定义红黑树
{
    RB_Tree_Node* root;        //根节点
    RB_Tree_Node* nil;         //空节点
    size_t n_size;             //插入节点占用空间的大小
    void (*Visit)(RB_Tree_Node* );
    int (*Comp)(const void* p1,const void* p2);  //插入节点的比较函数 

}RB_Tree_Root;


void RB_Tree_Init(RB_Tree_Root** t,const size_t size,
                  int (*Comp)(const void* ,const void* ),void (*Visit)(RB_Tree_Node* ));   
//初始化红黑树   

RB_Tree_Node* RB_Tree_Insert(RB_Tree_Root* t,ElemType k);  //插入节点
RB_Tree_Node* _RB_Tree_Insert_Set(RB_Tree_Root* t_r,RB_Tree_Node* t,ElemType key,const int kt); //初始化插入节点

RB_Tree_Node* RB_Tree_Find_Node(RB_Tree_Root* t,const ElemType key);   //查找节点
RB_Tree_Node* _RB_Tree_Find_Node(RB_Tree_Root* t,ElemType key,int* kt);
//查找节点并返回该节点的父节点如果是根节点则直接返回本节点

void RB_Tree_Free_All(RB_Tree_Root** t);   //释放红黑树
void _RB_Tree_Free_All(RB_Tree_Node** t);

void _RB_Tree_Left_Rotate(RB_Tree_Root* t_r,RB_Tree_Node* t);   //左旋操作
void _RB_Tree_Right_Rotate(RB_Tree_Root* t_r,RB_Tree_Node* t);  //右旋操作

RB_Tree_Node* _RB_Tree_HandleReorient(RB_Tree_Root* t_r,RB_Tree_Node* t); //进行旋转处理

int RB_Tree_Empty(RB_Tree_Root* t);       //判断该树是否为空

RB_Tree_Node* RB_Tree_Get_Brother(RB_Tree_Node* t);  //获取兄弟节点


int RB_Tree_Del_Node(RB_Tree_Root* t,ElemType key);         //删除节点

void _RB_Tree_Del_Handle1(RB_Tree_Node* t);                       //处理删除情况
void _RB_Tree_Del_Handle2(RB_Tree_Root* t_r,RB_Tree_Node* t_s);
void _RB_Tree_Del_Handle3(RB_Tree_Node* t);
void _RB_Tree_Del_Handle4(RB_Tree_Root* t_r,RB_Tree_Node* t);
void _RB_Tree_Del_Handle5(RB_Tree_Root* t_r,RB_Tree_Node* t);
void _RB_Tree_Del_Handle6(RB_Tree_Root* t_r,RB_Tree_Node* t_f,RB_Tree_Node* t_s);

RB_Tree_Node* _RB_Tree_Find_Substitute(RB_Tree_Node* t);    //寻找替身节点


  //对删除节点进行旋转判断
void _RB_Tree_Del_HandleReorient1(RB_Tree_Root* t_r,RB_Tree_Node* t_s);
void _RB_Tree_Del_HandleReorient2(RB_Tree_Root* t_r,RB_Tree_Node* t_s);  
void _RB_Tree_Del_HandleReorient3(RB_Tree_Root* t_r,RB_Tree_Node* t_s);
void _RB_Tree_Del_HandleReorient4(RB_Tree_Root* t_r,RB_Tree_Node* t_s);

int RB_Tree_Single_Node(RB_Tree_Root* t);            //判断是否为单节点
int _RB_Tree_Childnode_State(RB_Tree_Node* t);       //判断孩子节点状态

void RB_Tree_Print(RB_Tree_Root* t,
                   void (*_RB_Tree_Print)(RB_Tree_Node* t,void (*Visit)(RB_Tree_Node* t)));  //遍历函数

void RB_Tree_PreTravel(RB_Tree_Node* t,void (*Visit)(RB_Tree_Node* t));             //前序遍历
void RB_Tree_InTravel(RB_Tree_Node* t,void (*Visit)(RB_Tree_Node* t));              //中序遍历
void RB_Tree_PostTravel(RB_Tree_Node* t,void (*Visit)(RB_Tree_Node* t));            //后序遍历

void RB_Tree_Visit(RB_Tree_Node* t);                 //具体遍历函数


int main()
{
    RB_Tree_Root* t=NULL;
    int i=0;
    int k=0;
    //int a[]={100,25,200,400,150,125};
    int a[]={100,200,300,400,500,600,700,800,900,1000,1100,1200};
//    int a[]={985,321,436,596,805,178,398,26,506,770};

//    int a[]={652,195,100,364,599,781,515};
//   int a[]={376,170,795,585,240,307,736,61,191,825};
//    int a[]={170,61,736,585,795,825};
//    int a[]={736,61,795,585,825};
//    int a[]={585,61,795,825};

    srand((unsigned)time(NULL));

    RB_Tree_Init(&t,sizeof(ElemType),COMMON_Comp_Max_Int,RB_Tree_Visit);

    for (i=0;i<sizeof(a)/sizeof(*a);++i)
    {
    //    printf("即将插入的数为:%d\n",k=rand()%1000);
    //    RB_Tree_Insert(t,k);
        printf("即将插入的数为:%d\n",a[i]);
        RB_Tree_Insert(t,a[i]);
    }

    while (1)
    {
        puts("前序遍历结果为:");
        RB_Tree_Print(t,RB_Tree_PreTravel);

        puts("中序遍历结果为:");
        RB_Tree_Print(t,RB_Tree_InTravel);

      //  puts("后序遍历结果为:");
     //   RB_Tree_Print(t,RB_Tree_PostTravel);

        puts("请输入要删除的节点:");

        if (scanf("%d",&k)==EOF)
            break;

        RB_Tree_Del_Node(t,k);

    }

    RB_Tree_Free_All(&t);

    return 0;
}

void RB_Tree_Init(RB_Tree_Root** t,const size_t n_size,
                  int (*Comp)(const void* ,const void* ),void (*Visit)(RB_Tree_Node* ))
{
    COMMON_Creat_Node((void** )t,sizeof(RB_Tree_Root));
    (*t)->n_size=n_size;
    (*t)->Comp=Comp;
    (*t)->Visit=Visit;

    COMMON_Creat_Node((void** )&(*t)->nil,sizeof(RB_Tree_Node));

    (*t)->nil->color=BLACK;
    (*t)->nil->location=NIL;

    (*t)->root=(*t)->nil;
}

void RB_Tree_Free_All(RB_Tree_Root** t)
{
    COMMON_Free_Node((void** )&(*t)->root);
    COMMON_Free_Node((void** )t);
}

void _RB_Tree_Free_All(RB_Tree_Node** t)
{
    if ((*t)->left==NULL)
        return ;

    _RB_Tree_Free_All(&(*t)->left);    //递归删除节点
    _RB_Tree_Free_All(&(*t)->right);

    COMMON_Free_Node((void** )t);
}

RB_Tree_Node* RB_Tree_Get_Brother(RB_Tree_Node* t)  //获取兄弟节点
{
    if (t==NULL)
        return NULL;

    if (t->location==LEFT)
        return t->parent->right;

    if (t->location==RIGHT)
        return t->parent->left;

    return t->parent;  //返回空叶子节点
}

RB_Tree_Node* RB_Tree_Insert(RB_Tree_Root* t,ElemType k)     //插入节点
{
    RB_Tree_Node* p=NULL;
    int kt=0;

    if (t==NULL)
        return NULL;

    p=_RB_Tree_Find_Node(t,k,&kt);

    if (kt==0&&!RB_Tree_Empty(t))
        return NULL;

     return  _RB_Tree_HandleReorient(t,_RB_Tree_Insert_Set(t,p,k,kt));
}

RB_Tree_Node* RB_Tree_Find_Node(RB_Tree_Root* t,const ElemType key)   //查找节点
{
    RB_Tree_Node* p=NULL;
    int (*Comp)(const void* ,const void* )=NULL;
    int k=0;

    if (RB_Tree_Empty(t)==1)
        return NULL;

    p=t->root;
    Comp=t->Comp;

    while (p!=t->nil)
    {
        k=Comp(&key,&p->key);

        if (k==-1)
            p=p->left;
        else if (k==1)
            p=p->right;
        else 
            return p;
    }

    return NULL;   //没有找到
}

RB_Tree_Node* _RB_Tree_Find_Node(RB_Tree_Root* t,ElemType key,int* kt)
{
    RB_Tree_Node* p=NULL;
    RB_Tree_Node* pt=NULL;

    int (*Comp)(const void* ,const void* )=NULL;
    int k=0;

    if (t==NULL)
        return NULL;

    p=t->root;
    pt=p;

    Comp=t->Comp;

    while (p!=t->nil)
    {

        pt=p;

        k=Comp(&key,&p->key);

        if (k==-1)
            p=p->left;
        else if (k==1)
            p=p->right;
        else
        {
            *kt=0;

            return p;
        }
    }

 
    *kt=k;

    return pt;
}



RB_Tree_Node* _RB_Tree_Insert_Set(RB_Tree_Root* t_r,RB_Tree_Node* t,ElemType k,const int kt) //初始化插入节点
{
    RB_Tree_Node* t_new=NULL;

    COMMON_Creat_Node((void** )&t_new,sizeof(RB_Tree_Node));

    t_new->color=RED;
    t_new->left=t_r->nil;
    t_new->right=t_r->nil;
    t_new->parent=t;

    memmove(&t_new->key,&k,t_r->n_size);

    if (kt==-1)
    {
        t->left=t_new;
        t_new->location=LEFT;
    }
    else if (kt==1)
    {
        t->right=t_new;
        t_new->location=RIGHT;
    }
    else  //如果插入的是根节点
    {
        t_r->root=t_new;
        t_new->location=NIL;
    }

    return t_new;
}

void _RB_Tree_Left_Rotate(RB_Tree_Root* t_r,RB_Tree_Node* t)   //左旋操作
{
    RB_Tree_Node* t_n=t->right;

    t->right=t_n->left;

    if (t->right!=t_r->nil)
        t->right->parent=t;

    t_n->parent=t->parent;

    if (t_n->left->location!=NIL)
        t_n->left->location=RIGHT;


    if (t->location==NIL)
    {
        t_r->root=t_n;
        t_n->location=NIL;
    }
    else if (t->location==RIGHT)
        t_n->parent->right=t_n;
    else if (t->location==LEFT)
    {
        t_n->parent->left=t_n;
        t_n->location=LEFT;
    }

    t_n->left=t;
    t->parent=t_n;
    t->location=LEFT;

}
void _RB_Tree_Right_Rotate(RB_Tree_Root* t_r,RB_Tree_Node* t)  //右旋操作
{
    RB_Tree_Node* t_n=t->left;

    t->left=t_n->right;

    if (t->left!=t_r->nil)
        t->left->parent=t;

    t_n->parent=t->parent;

    if (t_n->right->location!=NIL)
        t_n->right->location=LEFT;

    if (t->location==NIL)
    {
        t_r->root=t_n;
        t_n->location=NIL;
    }
    else if (t->location==LEFT)
        t_n->parent->left=t_n;
    else if (t->location==RIGHT)
    {
        t_n->parent->right=t_n;
        t_n->location=RIGHT;
    }

    t_n->right=t;
    t->parent=t_n;

    t->location=RIGHT;

}

RB_Tree_Node* _RB_Tree_HandleReorient(RB_Tree_Root* t_r,RB_Tree_Node* t) //进行旋转处理
{
    RB_Tree_Node* t_b=NULL; 
    RB_Tree_Node* t_p=t;

    if (t->location==NIL)   //如果是空树或者只有一个节点
    {
        t_r->root->color=BLACK;
        return t;
    }

    while (t->parent->color==RED)
    {
        t_p=t->parent;
        t_b=RB_Tree_Get_Brother(t_p);  //获取兄弟节点的颜色

        if (t_b->color==RED)  //处理双红情况
        {
            t_p->color=BLACK;
            t_p->parent->color=RED;
            t_b->color=BLACK;

            t=t_p=t_p->parent;

        }
        else if (t->location==RIGHT&&t_p->parent->left==t_b)  
        {
            _RB_Tree_Left_Rotate(t_r,t_p->parent);
            t_p->left->color=RED;
            t_p->color=BLACK;
            break;


        }
        else if (t->location==LEFT&&t_p->parent->right==t_b)
        {
            _RB_Tree_Right_Rotate(t_r,t_p->parent);
            t_p->right->color=RED;
            t_p->color=BLACK;
            break;
        }
        else if (t_p->parent->right==t_b)
        {
            _RB_Tree_Left_Rotate(t_r,t_p);
            t_p=t_p->parent;

            _RB_Tree_Right_Rotate(t_r,t_p->parent);
            t_p->right->color=RED;
            t_p->color=BLACK;
            break;

        }
        else
        {
            _RB_Tree_Right_Rotate(t_r,t_p);
            t_p=t_p->parent;

            _RB_Tree_Left_Rotate(t_r,t_p->parent);
            t_p->left->color=RED;
            t_p->color=BLACK;
            break;
        }
    }

    t_r->root->color=BLACK;   //重置头节点着色

    return t;
}


int RB_Tree_Empty(RB_Tree_Root* t)       //判断该树是否为空
{
    if (t==NULL)
        return -1;
    
    return t->root==t->nil;
}

int RB_Tree_Del_Node(RB_Tree_Root* t,ElemType key)  //删除节点
{
    RB_Tree_Node* t_f=RB_Tree_Find_Node(t,key);   //查找要删除的节点
    RB_Tree_Node* t_s=NULL;                       //替身节点
    RB_Tree_Node* t_sp=NULL;                      //替身节点的父节点

    int k=0;

    if (t_f==NULL)  
        return 0;  //找不到就返回空

    k=_RB_Tree_Childnode_State(t_f);

    if (k==0&&t_f==t->root)   //头节点是单节点
    {
        t_s=t->root;
        t->root=t->nil;
        COMMON_Free_Node((void** )&t_s);

        return 1;
    }

    if (k==1&&t_f==t->root)    //当只有根-左两个节点时,要调整根节点的位置 以及节点状态
    {
        t->root=t->root->left;
        _RB_Tree_Del_Handle1(t->root);

        return 1;
    }

    if (k==-1&&t_f==t->root)   //当只有根-右两个节点时,要调整根节点的位置 以及节点状态
    {
        t->root=t->root->right;
        _RB_Tree_Del_Handle1(t->root);

        return 1;
    }

    if (k==0)                      //如果该节点是非头节点的叶子节点
    {
        _RB_Tree_Del_Handle2(t,t_f);   //进行删除并判断是否需要重新调整平衡

        return 1;
    }

    if (k!=2)                      //如果找到的节点只有一个孩子(不用旋转)
    {
        _RB_Tree_Del_Handle3(t_f);

        return 1;
    }

    t_s=_RB_Tree_Find_Substitute(t_f);          //查找替身节点

    k=_RB_Tree_Childnode_State(t_s);             //获取替身节点的孩子节点信息

    //如果替身节点是叶子节点并且替身节点刚好是要删节点的左孩子并且该节点是黑色,则需要判断是否重新调整平衡
    if (k==0&&t_s->color==BLACK&&t_f->left==t_s)
    {
        _RB_Tree_Del_Handle5(t,t_f);
        _RB_Tree_Del_HandleReorient1(t,t_s->right);

        return 1;

    }

    if (t_s->color==BLACK&&t_f->left==t_s)  //直接处理替身节点是刚好是左孩子并且替身节点的颜色是黑色并且替身节点是非空节点
    {
        _RB_Tree_Del_Handle4(t,t_s);
        return 1;
    }

    //如果替身节点的左节点是空节点或者替身节点是红色并且替身节点刚好是要删节点的左孩子,不用旋转
    if ((k==1||t_s->color==RED)&&t_f->left==t_s) 
    {
        _RB_Tree_Del_Handle5(t,t_f);
        return 1;
    }

    //删除的左节点为非空节点
    _RB_Tree_Del_Handle6(t,t_f,t_s);

    return 1;
}

RB_Tree_Node* _RB_Tree_Find_Substitute(RB_Tree_Node* t)  //寻找替身节点
{
    if (t->left->parent==NULL)
        return t;

    for (t=t->left;t->right->parent!=NULL;t=t->right);

    return t;
}

void _RB_Tree_Del_Handle1(RB_Tree_Node* t)  
{
    RB_Tree_Node* t_f=t->parent;

    t->parent=t_f->parent;
    t->location=NIL;
    t->color=BLACK;

    COMMON_Free_Node((void** )&t_f);
}

void _RB_Tree_Del_Handle2(RB_Tree_Root* t_r,RB_Tree_Node* t)
{
    RB_Tree_Node* t_p=t->parent;
    RB_Tree_Setcolor color=t->color;
    RB_Tree_Node* t_b=RB_Tree_Get_Brother(t);

    if (t->location==LEFT)
    {
        COMMON_Free_Node((void** )&t_p->left);
        t_p->left=t_r->nil;
    }
    else
    {
        COMMON_Free_Node((void** )&t_p->right);
        t_p->right=t_r->nil;
    }

    if (color==RED)         //如果删除的叶子节点是红色则返回
        return ;

    _RB_Tree_Del_HandleReorient1(t_r,t_b);
}


void _RB_Tree_Del_Handle3(RB_Tree_Node* t)
{
    RB_Tree_Node* t_p=t->parent;
    RB_Tree_Node* t_s=t->left->parent!=NULL?t->left:t->right;
    RB_Tree_Node* t_t=NULL;

    t_s->parent=t_p;
    t_s->location=t->location;

    if (t->location==LEFT)
    {
        COMMON_Free_Node((void** )&t_p->left);
        t_p->left=t_s;
    }
    else
    {
        COMMON_Free_Node((void** )&t_p->right);
        t_p->right=t_s;
    }

    t_s->color=BLACK;

}

void _RB_Tree_Del_Handle4(RB_Tree_Root* t_r,RB_Tree_Node* t)
{
    RB_Tree_Node* t_p=t->parent;
    RB_Tree_Node* t_b=t->parent->right;
    RB_Tree_Setcolor color=t->parent->color;

    t->right=t_b;
    t_b->parent=t;
    t->parent=t_p->parent;

    t->location=t_p->location;

    if (t->location==LEFT)
    {
        COMMON_Free_Node((void** )&t->parent->left);
        t->parent->left=t;
    }
    else if (t->location==RIGHT)
    {
        COMMON_Free_Node((void** )&t->parent->right);
        t->parent->right=t;
    }
    else
    {
        COMMON_Free_Node((void** )&t_r->root);
        t_r->root=t;
    }

    t->left->color=BLACK;
}

void _RB_Tree_Del_Handle5(RB_Tree_Root* t_r,RB_Tree_Node* t)
{
    RB_Tree_Node* t_s=t->left;
    RB_Tree_Node* t_p=t->parent;
    RB_Tree_Setcolor color=t->color;

    t_s->right=t->right;
    t->right->parent=t_s;

    t_s->location=t->location;
    t_s->parent=t->parent;

    if (t->location==LEFT)
    {
        COMMON_Free_Node((void** )&t->parent->left);
        t_p->left=t_s;  
    }
    else if (t->location==RIGHT)
    {
        COMMON_Free_Node((void** )&t->parent->right);
        t_p->right=t_s;
    }
    else
    {
        COMMON_Free_Node((void** )&t_r->root);
        t_r->root=t_s;
    }

    t_s->color=color;
    t_s->left->color=BLACK;
}

void _RB_Tree_Del_Handle6(RB_Tree_Root* t_r,RB_Tree_Node* t_f,RB_Tree_Node* t_s)
{
    RB_Tree_Node* t_p=t_s->parent;
    RB_Tree_Node* t_fp=t_f->parent;
    RB_Tree_Setcolor color=t_f->color;
    RB_Tree_Setcolor color_t=t_s->color;

    t_p->right=t_s->left;

    if (t_s->left->location!=NIL)  
    {
        t_s->left->parent=t_p;
        t_s->left->location=RIGHT;
        t_s->left->color=BLACK;
    }

    t_s->left=t_f->left;
    t_s->left->parent=t_s;

    t_s->right=t_f->right;
    t_s->right->parent=t_s;

    t_s->parent=t_f->parent;

    t_s->location=t_f->location;

    if (t_f->location==LEFT)  
    {
        COMMON_Free_Node((void** )&t_f->parent->left);
        t_fp->left=t_s;
    }
    else if (t_f->location==RIGHT)
    {
        COMMON_Free_Node((void** )&t_f->parent->right);
        t_fp->right=t_s;
    }
    else
    {
        COMMON_Free_Node((void** )&t_r->root);
        t_r->root=t_s;
    }

    t_s->color=color;

    if (color_t==RED)
        return ;

    if (t_p->right->location!=NIL)
    {
        t_p->right->color=BLACK;
        return ;
    }

    _RB_Tree_Del_HandleReorient1(t_r,t_p->left);
}

void _RB_Tree_Del_HandleReorient1(RB_Tree_Root* t_r,RB_Tree_Node* t_s)
{
    RB_Tree_Node* t_p=t_s->parent;

    if (t_s->color==BLACK)  //如果是黑色节点
    {
        _RB_Tree_Del_HandleReorient2(t_r,t_s); 
        t_r->root->color=BLACK;
        return ;
    }

    if (t_s->location==LEFT)
    {
        _RB_Tree_Right_Rotate(t_r,t_p);
        t_p->color=BLACK;
        t_s->color=RED;
    }
    else
    {
        _RB_Tree_Left_Rotate(t_r,t_p);
        t_p->color=BLACK;
        t_s->color=RED;
    }


    if (t_p->location==LEFT)
        _RB_Tree_Del_HandleReorient2(t_r,t_p->right);
    else
        _RB_Tree_Del_HandleReorient2(t_r,t_p->left);
    
    t_r->root->color=BLACK;
}

void _RB_Tree_Del_HandleReorient2(RB_Tree_Root* t_r,RB_Tree_Node* t_s)
{
    if (_RB_Tree_Childnode_State(t_s)==0)  //t_s为叶子节点
    {
        t_s->color=RED;
        t_s->parent->color=BLACK;
    }
    else if (t_s->location==LEFT)
        _RB_Tree_Del_HandleReorient3(t_r,t_s);
    else
        _RB_Tree_Del_HandleReorient4(t_r,t_s);

}

void _RB_Tree_Del_HandleReorient3(RB_Tree_Root* t_r,RB_Tree_Node* t_s)
{
    RB_Tree_Node* t_p=t_s->parent;

    if (t_s->left->color==BLACK)
    {
        _RB_Tree_Left_Rotate(t_r,t_s);
        _RB_Tree_Right_Rotate(t_r,t_p);

        t_p->color=BLACK;
        t_p->parent->color=RED;
    }
    else if (t_s->right->color==BLACK)
    {
        _RB_Tree_Right_Rotate(t_r,t_p);
        t_s->left->color=BLACK;
        t_s->right->color=BLACK;
        t_s->color=RED;
    }
    else  //双红
    {
        _RB_Tree_Right_Rotate(t_r,t_p);
        t_p->color=BLACK;
        t_s->color=RED;
        t_s->left->color=BLACK;
    }
}

void _RB_Tree_Del_HandleReorient4(RB_Tree_Root* t_r,RB_Tree_Node* t_s)
{
    RB_Tree_Node* t_p=t_s->parent;

    if (t_s->right->color==BLACK)
    {
        _RB_Tree_Right_Rotate(t_r,t_s);
        _RB_Tree_Left_Rotate(t_r,t_p);

        t_p->color=BLACK;
        t_p->parent->color=RED;

    }
    else if (t_s->left->color==BLACK)
    {
        _RB_Tree_Left_Rotate(t_r,t_p);
        t_s->right->color=BLACK;
        t_s->left->color=BLACK;
        t_s->color=RED;
    }
    else
    {
        _RB_Tree_Left_Rotate(t_r,t_p);
        t_p->color=BLACK;
        t_s->color=RED;
        t_s->right->color=BLACK;
    }
}

int RB_Tree_Single_Node(RB_Tree_Root* t)  //判断是否只有一个节点
{
    return RB_Tree_Empty(t)&&t->root->left==t->root->right;  
}

int _RB_Tree_Childnode_State(RB_Tree_Node* t)       //判断孩子节点状态
{
    if (t==NULL)  //没有申请空间
        return -3;

    if (t->parent==NULL)  //空节点
        return -2;

    if (t->left->parent==NULL&&t->right->parent==NULL)  //单节点
        return 0;

    if (t->left->parent==NULL)   //左空右非空
        return -1;

    if (t->right->parent==NULL)  //右空左非空
        return 1;

    return 2;                    //有两个孩子节点
}

void RB_Tree_Print(RB_Tree_Root* t,
                   void (*_RB_Tree_Print)(RB_Tree_Node* t,void (*Visit)(RB_Tree_Node* t)))  //遍历函数
{
    if (RB_Tree_Empty(t))
        return ;

    _RB_Tree_Print(t->root,t->Visit);

    puts("");
}

void RB_Tree_PreTravel(RB_Tree_Node* t,void (*Visit)(RB_Tree_Node* t))             //前序遍历
{
    if (t->parent==NULL)   //判断是否是叶子节点
         return ;

    Visit(t);

    RB_Tree_PreTravel(t->left,Visit);            //递归遍历
    RB_Tree_PreTravel(t->right,Visit);
}

void RB_Tree_InTravel(RB_Tree_Node* t,void (*Visit)(RB_Tree_Node* t))             //中序遍历
{
    if (t->parent==NULL)   //判断是否是叶子节点
         return ;

    RB_Tree_InTravel(t->left,Visit);            //递归遍历

    Visit(t);

    RB_Tree_InTravel(t->right,Visit);
}

void RB_Tree_PostTravel(RB_Tree_Node* t,void (*Visit)(RB_Tree_Node* t))             //后序遍历
{
    if (t->parent==NULL)   //判断是否是叶子节点
         return ;

    RB_Tree_PostTravel(t->left,Visit);            //递归遍历
    RB_Tree_PostTravel(t->right,Visit);

    Visit(t);
}

void RB_Tree_Visit(RB_Tree_Node* t)
{
    if (t->color==RED)
        printf("%-8d%-8s",t->key,"RED");
    else
        printf("%-8d%-8s",t->key,"BLACK");

    if (t->location==LEFT)
        printf("%-8s","LEFT");
    else if (t->location==RIGHT)
        printf("%-8s","RIGHT");
    else
        printf("%-8s","ROOT");

    puts("");
}

[此贴子已经被作者于2017-7-4 20:28编辑过]

主要还是.cpp格式存在强制转型问题~刚刚把代码改成.cpp兼容格式~

现在我还在整理删除节点的思路~那个删除节点弄了很久很久~当然还是有进展了~到时我吃透后再具体说说~

PS:上网搜搜资料~有很多这方面详细的资料~就是这样~~

红黑树删除节点操作基本完成~不过代码感觉比较多或许会有很多BUG~还需后期维护~~~
070500008更~添加了就那么一行代码~更正了bug~还要继续测试~
070500020更~删除节点发现bug~

[此贴子已经被作者于2017-7-4 00:14编辑过]

07041056更~修复删除节点bug~~~~
第一次写感觉代码有点长且形式不怎么简洁~后期还需要看看怎么简化一下~

红黑树是一种平衡树~和AVL有相似的地方~不同的是红黑树是用标记节点颜色来记录平衡状态~而AVL树则标记高度信息~
它的最大深度不会超过最短深度的两倍~
插入节点操作和AVL树都是最多旋转两次~不过在删除节点AVL树最多要从叶子节点旋转到根节点(为0(log(n)))次~红黑树最多旋转3次~进行频繁的插入和删除节点的动态处理通常红黑树效率比较高~然而查找方面则AVL树比较高~不过资料上总的来说统计性能还是红黑树高一点~~

07041946更~
删除节点再次发现bug~

  int a[]={985,321,436,596,805,178,398,26,506,770};
//Del 398 596 bug!!!
好像还是忽略了情况~
07042023更~
已经修正了bug~

[此贴子已经被作者于2017-7-4 20:39编辑过]

一楼有个Common.h的链接~不知道我没有修改过……如果那个出现编译不通过的bug(.cpp可能会出现~如果我没有完善的话)……可以来说一下~

就在论坛主界面今日帖子(后面跟红色数字)的左下方有个蓝框~叫"发布新帖"~点击它就是了~