红黑树源码及错误解析

/* 作者：田帅

学校：**大学

版本：红黑树初始版本

*/

#include"stdio.h"

#include"malloc.h"

#define MIN -99999999 //不要加等号

#define MAX 99999999

struct node

{

long key;

char color;

struct node *p;

struct node *leftChild;

struct node *rightChild;

};

node *nil,*root;//创建根节点和叶子节点

int printnode=0;

node *CreateNode(int key);

void RB_insert_fixUp(node *T,node *z);

void nil_create();//叶子节点创建

void RB_insert(node *T,node *z);//弄算法导论上非递归的吧

void left_rotate(node *T,node *z);//向左旋转

void right_rotate(node *T,node *z);

void PrintRBTree(node *T);//输出树

void nil_create()//叶子节点创建

{

nil=(node *)malloc(sizeof(node));

root=(node *)malloc(sizeof(node));

nil->key=MIN;

nil->color='B';

//nil->p=NULL;//这里注意

nil->leftChild=nil;

nil->rightChild=nil;

root=nil;

}

node *CreateNode(int key)

{

node *x = (node *)malloc(sizeof(node));

x->color ='R';

x->key = key;

x->leftChild = nil;

x->rightChild = nil;

x->p = NULL;

return x;

}

void RB_insert(node *T,node *z)//弄算法导论上非递归的吧

{

node *x,*y;//y用来记录父节点

x=root;//这里应该是 根节点 跟形式参数重复 会造成错误

y=nil;

while(x!=nil)//x为要插入的位置de父节点 y为x的父节点

{

y=x;

if(x->key>z->key)

x=x->leftChild;

else

x=x->rightChild;

}

z->p=y;

if(y==nil)//初始化 插入到空树种

root=z;

else if(z->key<y->key)

y->leftChild=z;

else

y->rightChild=z;

z->leftChild=nil;

z->rightChild=nil;

z->color='R';

RB_insert_fixUp(T,z);

}

void RB_insert_fixUp(node *T,node *z)

{

node *y;

while(z->p->color=='R')//插入节点 是红节点 如果父节点也是红节点 则需要调整

{

if(z->p==z->p->p->leftChild)//插入的节点的父节点 是祖父节点的左孩子

{

y=z->p->p->rightChild;//祖父节点的右孩子

if(y->color=='R')//二叔是 红色的O(∩_∩)O哈哈~

{

z->p->color='B';

y->color='B';

z->p->p->color='R';

z=z->p->p;

}

else

{//这个地方一定要加上 {

if(z==z->p->rightChild)//二叔是黑色 且 要插入的节点是右孩子

{

z=z->p;

left_rotate(T,z);

}

z->p->color='B';//二叔是黑色 且要插入的节点是左孩子

z->p->p->color='R';

// z->p->p->color='R'; //???????????????????????????

right_rotate(T,z->p->p);

}

}

else//插入的节点的父节点 是祖父节点的右孩子

{

y=z->p->p->leftChild;//祖父节点的左孩子

if(y->color=='R')//二叔是 红色的O(∩_∩)O哈哈~

{

z->p->color='B';

y->color='B';

z->p->p->color='R';

z=z->p->p;//???????

}

else

{

if(z==z->p->leftChild)//二叔是黑色 且 要插入的节点是左孩子

{

z=z->p;

right_rotate(T,z);

}

z->p->color='B';//二叔是黑色 且要插入的节点是右孩子

z->p->p->color='R';

left_rotate(T,z->p->p);

}

}

}

root->color='B';//这里不要落下！！！

}

void left_rotate(node *T,node *z)//向左旋转

{

node *y;

y=z->rightChild;//让y 为要旋转的节点的右子树

z->rightChild=y->leftChild;

if(y->leftChild!=nil)

y->leftChild->p=z;

y->p=z->p;//将要旋转节点切下

if(z->p==nil)

root=y;

else if(z==z->p->leftChild)//要旋转节点是 其父节点左孩子

z->p->leftChild=y;

else//要旋转节点是 其父节点右孩子

z->p->rightChild=y;

y->leftChild=z;//将要旋转节点挂到 代替它的孩子的左子树上

z->p=y;

}

void right_rotate(node *T,node *z)

{

node *y;

y=z->leftChild;//让y 为要旋转的节点的左子树

z->leftChild=y->rightChild;

if(y->rightChild!=nil)

y->rightChild->p=z;

y->p=z->p;//将要旋转节点切下

if(z->p==nil)

root=y;

else if(z==z->p->leftChild)//要旋转节点是 其父节点左孩子

z->p->leftChild=y;

else//要旋转节点是 其父节点右孩子

z->p->rightChild=y;

y->rightChild=z;//将要旋转节点挂到 代替它的孩子的左子树上

z->p=y;

}

void PrintRBTree(node *T)

{

int i;

if(T != nil)

{

for(i = 0; i <= printnode;i++)

printf(" ");

printf("(%d",T->key);

if(T->color == 'B')

printf("B,\n");

else

printf("R,\n");

printnode++;

PrintRBTree(T->leftChild);

PrintRBTree(T->rightChild);

printnode--;

for(int j = 0; j <= printnode;j++)

printf(" ");

printf("),\n");

}

else

{

for(int i = 0; i <= printnode;i++)

printf(" ");

printf("Nil,\n");

}

}

void INORDER_TREE_WALK(struct node* x) //中根遍历

{

//printf("%ld %c ",x->key,x->color); //debug 先根遍历

if(x->leftChild!=nil)

INORDER_TREE_WALK(x->leftChild);

printf("%ld %c ",x->key,x->color);

if(x->rightChild!=nil)

INORDER_TREE_WALK(x->rightChild);

}

int main()

{ //long a[11]={4,1,3,2,16,9,10,14,8,7};

//long a[10]={10,9,8,7,6,5,4,3,2,1};

// long a[10]={1,2,3,4,5,6,7,8,9,10};

// long a[]={1,2,3,4,5,6,7,8,9,10};//这个可以

long a[]={4,1,3,2,16,9,10,14,8,7};//这个不可以

node *z[11];

nil_create();

// nil=(node *)malloc(sizeof(node));

// nil=nil_create();

printf(" 1111111");

for(int j = 0; j <10; j++)

{

printf(" 222222 ");

z[j]=CreateNode(a[j]);

RB_insert(root,z[j]);

}

printf(" 222222 ");

INORDER_TREE_WALK(root);

// PrintRBTree(root);

return 0;

}

出现的错误及调试方法：

总是到insert_fix_up时候出现错误；原因是 第三种情况 要写在 if(y.color=='R') else{ if() ; ********} 不要忘记在else 之后加上 大括号