C语言红黑树，增加，删除

#include 
#include 
#include 

#define LEN 30
#define RED 1				//红色 
#define BLACK 0				//黑色	

typedef struct tree{
	int key;			//关键字 
	int color;			//结点颜色	
	struct tree *parent;	//指向父亲的指针 
	struct tree *lchild;	//指向左孩子 
	struct tree *rchild;	//指向右孩子 
}Node, *RBtree;

typedef struct{
	RBtree pt[LEN];
	int rear;
	int front;
}Queue;

Node * Insert(RBtree * t, int data);	//插入结点 
Node * CreateNode(int data);		//建立结点 
void CreateRBtree(RBtree * t, Node *node);		//建立调整红黑树 
bool FindNode(RBtree *t, int data);		//找到要删除的结点 

Node * RedDelete(RBtree *t, Node *node);				//删除红结点 
void BlackDelete(RBtree *t, Node *node, Node *fat);				//删除黑结点



void Lsp(Node **root, Node *node);		//左旋 
void Rsp(Node **root, Node *node);		//右旋 
Node * PriorNode(Node *node);			//返回该结点的 前驱结点 
Node * NextNode(Node *node);		//返回该结点的 后继结点

void Clear(RBtree *t);		//销毁 

void Traverse(RBtree *t);		//中序遍历 

void TraColor(RBtree *t);		//层序遍历 颜色 

Node *pnode(RBtree *t, int data);		//返回数据结点的指针 


void InitQueue(Queue *q);	//初始化 
bool DeQueue(Queue *q, Node ** t); //出队
bool EnQueue(Queue *q, Node ** t); //入队 
bool Full(Queue *q);		//队满
bool Empty(Queue *q);		//队空 



int main(void)
{
	RBtree root = NULL;
	int i;
	Node * temp;
	int num[18] = {6,1,4,2,10,13,16,8,9,17,19,15,14,21,28,22,12,18};
	
	for(int i = 0; i <18;++i)
	{
		temp = Insert(&root, num[i]);
		CreateRBtree(&root, temp);
		
	}


	TraColor(&root);		//层序遍历 颜色 
//	Traverse(&root);		//中序遍历 
	
	printf("输入要删除的数据: ");
	while(scanf("%d", &i) == 1)
	{
		while(getchar() !='n')
			continue;
		if(FindNode(&root, i))			//找到要删除的结点 
		{
	    	printf("n");
	    	TraColor(&root);		//层序遍历 颜色 
	    	printf("n");	
		}
		else
		{
			printf("数据不存在n");
		}

		printf("输入要删除的数据: ");	
	}


	Clear(&root);
	
	return 0;
}

bool FindNode(RBtree *t, int data)		//找到要删除的结点 
{
	Node *del;
	Node *fat;   //父亲结点 
	Node *gra; //爷爷结点
	Node *tp; 
	Node *node;
	
	int temp;

	if(*t == NULL)
		return false;
	
	del=pnode(t, data);	//返回数据结点的指针 
	if(del == NULL)
		return false;

	if(del->lchild != NULL)
	{
		node = PriorNode(del);			//返回该结点的 前驱结点
		temp = node->key;
		node->key = del->key;
		del->key = temp;
		
	}
	else if(del->rchild != NULL)
	{
		node = NextNode(del);		//返回该结点的 后继结点
		temp = node->key;
		node->key = del->key;
		del->key = temp;
	}
	else	
	{
		node = del;
	}
	
	if(node->parent == NULL)	//如果删除的是根节点直接删除 
		*t = NULL;
	else
	{
		fat = node->parent;
		tp = RedDelete(t, node);				//删除红结点 ，返回删除后从新连接改位置的结点 
		if(node->color == BLACK)
		{
			BlackDelete(t, tp, fat);		//删除黑结点 
		}
		
	}	
			
	free(node);
	
	return true;
}

void BlackDelete(RBtree *t, Node *node, Node *fat)				//删除黑结点， 红黑树中，空节点属于黑节点  
{
	Node * bro;	  //兄弟结点 
	Node **pf;   //指向父亲结点地址的指针 
	Node *temp;
	
	if(node != NULL && node->color == RED)		//如果连接后的结点是红结点， 直接改黑 
		node->color = BLACK;
	else if(node != NULL && node->parent == NULL)		//如果节点是根节点，直接改黑 
	{
		node->color = BLACK;
	}
	else							//红黑树中，空节点属于黑节点 
	{
		if(fat->parent != NULL && fat == fat->parent->lchild)		//存放父节点的地址 
			pf = &(fat->parent->lchild);
		else if(fat->parent != NULL && fat == fat->parent->rchild)
			pf = &(fat->parent->rchild);
		else
			pf = t;	
			
		if(node == fat->lchild)		//该节点是父节点的左孩子 
		{
			bro = fat->rchild;		//兄弟节点
			if(bro->color == RED)		//1. 如果兄弟是红色 
			{
				bro->color = BLACK;
				fat->color = RED;
				Lsp(pf, fat);		//以父节点为支点 左旋 
				BlackDelete(t, node, fat);	//向上递归, 主要是把 node的兄弟节点该为黑色 
			} 
			else if(bro->color == BLACK)	//如果兄弟是黑节点 
			{
				if((bro->lchild == NULL && bro->rchild == NULL) || (bro->lchild == NULL && bro->rchild != NULL && bro->rchild->color == BLACK) 		//2. 兄弟的两个孩子都是黑色 
				  || (bro->rchild == NULL && bro->lchild != NULL && bro->lchild->color == BLACK) || (bro->lchild != NULL && bro->lchild->color == BLACK && bro->rchild != NULL && bro->rchild->color == BLACK))
				{
					bro->color = RED;			//把兄弟改为红色 
					if(fat->color == RED)
						fat->color = BLACK;		//父亲改为黑色 
					else
						BlackDelete(t, fat, fat->parent);	//如果父亲以前就是黑色，以父亲节点向上递归		
				}
				else if((bro->lchild != NULL && bro->lchild->color == RED) && (bro->rchild == NULL || bro->rchild->color == BLACK))		//3. 兄弟的左孩子是红色，右孩子是黑色 
				{
					temp = bro->lchild;				//右旋后，新的兄弟节点 
					bro->lchild->color = BLACK;		//兄弟的左孩子改为黑色 
					bro->color = RED;				//兄弟改为红色 
					
					Rsp(&fat->rchild, bro);		//以兄弟为支点 右旋	
					bro = temp; 
					
					//主要是把第 3 种情况变为 第 4 种情况处理 
					bro->color = fat->color;	//父亲的颜色给兄弟 
					fat->color = BLACK;			//父亲变黑 
					bro->rchild->color = BLACK;	//兄弟的右孩子变黑 
					Lsp(pf, fat);		//以父节点为支点 左旋 	
				}
				else if(bro->rchild != NULL && bro->rchild->color == RED)		//4. 兄弟的右孩子是红色 
				{
					bro->color = fat->color;	//父亲的颜色给兄弟 
					fat->color = BLACK;			//父亲变黑 
					bro->rchild->color = BLACK;	//兄弟的右孩子变黑 
					Lsp(pf, fat);		//以父节点为支点 左旋 
				}
			}
			
		}
		else						//该节点是父节点的右孩子 
		{
			bro = fat->lchild;		//兄弟节点 
			if(bro->color == RED)		//1. 如果兄弟是红色 
			{
				bro->color = BLACK;
				fat->color = RED;
				Rsp(pf, fat);		//以父节点为支点 右旋 
				BlackDelete(t, node, fat);	//向上递归, 主要是把 node的兄弟节点该为黑色 
			} 
			else if(bro->color == BLACK)	//如果兄弟是黑节点 
			{
				if((bro->lchild == NULL && bro->rchild == NULL) || (bro->lchild == NULL && bro->rchild != NULL && bro->rchild->color == BLACK) 		//2. 兄弟的两个孩子都是黑色 
				  || (bro->rchild == NULL && bro->lchild != NULL && bro->lchild->color == BLACK) || (bro->lchild != NULL && bro->lchild->color == BLACK && bro->rchild != NULL && bro->rchild->color == BLACK))
				{
					bro->color = RED;			//把兄弟改为红色 
					if(fat->color == RED)
						fat->color = BLACK;		//父亲改为黑色 
					else
						BlackDelete(t, fat, fat->parent);	//如果父亲以前就是黑色，以父亲节点向上递归		
				}
				else if((bro->rchild != NULL && bro->rchild->color == RED) && (bro->lchild == NULL || bro->lchild->color == BLACK))		//3. 兄弟的右孩子是红色，左孩子是黑色 
				{
					temp = bro->rchild;				//左旋后，新的兄弟节点 
					bro->rchild->color = BLACK;		//兄弟的右孩子改为黑色 
					bro->color = RED;				//兄弟改为红色 
					
					Lsp(&fat->lchild, bro);		//以兄弟为支点 左旋	
					bro = temp; 
					
					//主要是把第 3 种情况变为 第 4 种情况处理 
					bro->color = fat->color;	//父亲的颜色给兄弟 
					fat->color = BLACK;			//父亲变黑 
					bro->lchild->color = BLACK;	//兄弟的左孩子变黑 
					Rsp(pf, fat);		//以父节点为支点 右旋 	
				}
				else if(bro->lchild != NULL && bro->lchild->color == RED)		//4. 兄弟的左孩子是红色 
				{
					bro->color = fat->color;	//父亲的颜色给兄弟 
					fat->color = BLACK;			//父亲变黑 
					bro->lchild->color = BLACK;	//兄弟的左孩子变黑 
					Rsp(pf, fat);		//以父节点为支点 右旋 
				}
			}
		
		}
	}
	
}

Node * RedDelete(RBtree *t, Node *node)				//删除红结点 
{
	Node *fat;
	Node *temp;
	
	if(node->lchild != NULL && node->rchild == NULL)		//前驱结点一定没有右孩子 
	{
		fat = node->parent;
		temp = node->lchild;
		if(node == fat->rchild)
		{
			fat->rchild = node->lchild;
			node->lchild->parent = fat;
		}
		else
		{
			fat->lchild = node->lchild;
			node->lchild->parent = fat;
		}
		
	}
	else if(node->lchild == NULL && node->rchild != NULL)	//后继结点一定没有左孩子 
	{
		fat = node->parent;
		temp = node->rchild;
		if(node == fat->lchild)
		{
			fat->lchild  = node->rchild;
			node->rchild->parent = fat;
		}
		else
		{
			fat->rchild = node->rchild;
			node->rchild->parent = fat;
		}
	}
	else							//叶子结点 
	{
		fat = node->parent;
		
		if(fat->lchild == node)
			fat->lchild = NULL;
		else
			fat->rchild = NULL;
		
		temp = NULL;	
		
	}
	
	return temp;	//返回连接后的结点 
}



void CreateRBtree(RBtree * t, Node *node)		//建立调整红黑树 
{
	Node * fat;   //父亲结点 
	Node * gra;	  //爷爷结点
	Node **pg;   //指向爷爷结点地址的指针 
	Node *temp;	
	if(node->parent == NULL)
		node->color = BLACK;
	else 
	{
		if(node->parent->color == BLACK)
			return;		
		else if(node->parent->color == RED)
		{
			fat = node->parent;		//父亲结点 	
			gra = fat->parent;		//爷爷结点
			if(gra->parent == NULL)
				pg = t;
			else
			{
				temp = gra->parent;
				if(temp->lchild == gra)
					pg = &temp->lchild;
				else
					pg = &temp->rchild;
			}
			
			
			if(gra != NULL && fat == gra->lchild)						//父结点是，爷爷结点的左孩子 
			{
				if(fat->color == RED && gra->rchild != NULL && gra->rchild->color == RED)		//1.父结点是红色，叔叔结点是红色 
				{
					fat->color = BLACK;										//父结点变黑 
					gra->rchild->color = BLACK;								//叔叔结点变黑	
					gra->color = RED;										//爷爷变红 
					CreateRBtree(t, gra);								//向上递归 
				}
	        	else if(node == fat->rchild && (gra->rchild == NULL || gra->rchild->color == BLACK))		//2.node 是父结点的右孩子，并且叔叔结点是黑色（空结点表示黑色） 
				{																					//以父节点为支点 左旋 
					Lsp(&gra->lchild, fat);		//左旋 														//主要是把第二种情况转化为第 3 种情况 		
					temp = node;										
					node = fat;
					fat = temp;
					
					fat->color = BLACK;																//父结点改黑 
					gra->color = RED;																//爷爷变红	
					Rsp(pg, gra);		//右旋 	
				}
		    	else if(node == fat->lchild && (gra->rchild == NULL || gra->rchild->color == BLACK))		//3. node 是父结点的左孩子，并且叔叔结点是黑色（空结点表示黑色）
				{																					
					fat->color = BLACK;																//父结点改黑 
					gra->color = RED;																//爷爷变红					
					Rsp(pg, gra);		//右旋 														//以爷爷节点为支点 右旋	
				}
			}
			else if(gra != NULL && fat == gra->rchild)		//父结点是，爷爷结点的右孩子 
			{
				fat = node->parent;		//父亲结点 	
				gra = fat->parent;		//爷爷结点
				
				if(fat->color == RED && gra->lchild != NULL && gra->lchild->color == RED)		//1.父结点是红色，叔叔结点是红色 
				{
					fat->color = BLACK;										//父结点变黑 
					gra->lchild->color = BLACK;								//叔叔结点变黑	
					gra->color = RED;										//爷爷变红 
					CreateRBtree(t, gra);								//向上递归 
				}
				else if(node == fat->lchild && (gra->lchild == NULL || gra->lchild->color == BLACK))		//2.node 是父结点的左孩子，并且叔叔结点是黑色（空结点表示黑色）
				{																					//以父节点为支点 右旋	
					Rsp(&gra->rchild, fat);		//右旋 														//主要是把第二种情况转化为第 3 种情况
					temp = node;										
					node = fat;
					fat = temp;	
					
					fat->color = BLACK;																//父结点改黑 
					gra->color = RED;																//爷爷变红
					Lsp(pg, gra);		//左旋 	
				}
				else if(node == fat->rchild && (gra->lchild == NULL || gra->lchild->color == BLACK))
				{
					fat->color = BLACK;																//父结点改黑 
					gra->color = RED;																//爷爷变红					
					Lsp(pg, gra);		//左旋 														//以爷爷节点为支点 左旋	
				}
				
				
			}
		}
	}	
}

Node * CreateNode(int data)		//建立结点 
{
	Node * node = (Node *)malloc(sizeof(Node));
	node->key = data;
	node->color = RED;
	node->parent = NULL;
	node->lchild = NULL;
	node->rchild = NULL;
	
	return node;
}

Node * Insert(RBtree * t, int data)	//插入结点 
{
	Node *node;
	Node *temp;
	
	Node *p;
	
	if(*t == NULL)
	{
		node = CreateNode(data);
		*t = node;	
	}
	else
	{
		p = *t;
		while(p)
		{
			if(p->key > data)
			{
				temp = p;
				p = p->lchild;
				if(p == NULL)
				{
					node = CreateNode(data);
					temp->lchild = node;
					node->parent = temp;
				}
			}
			else
			{
				temp = p;
				p = p->rchild;
				if(p == NULL)
				{
					node = CreateNode(data);
					temp->rchild = node;
					node->parent = temp;
				}
			}
		}
		
	}
	return node;
}

Node * PriorNode(Node *node)			//返回该结点的 前驱结点 
{
	Node *temp;
	temp = node->lchild;

	while(temp->rchild != NULL)
		temp = temp->rchild;
		
	return temp;
}

Node * NextNode(Node *node)		//返回该结点的 后继结点
{
	Node *temp;
	temp = temp->rchild;
	
	while(temp->lchild != NULL)
		temp = temp->lchild;
	
	return temp;	
} 

void Lsp(Node **root, Node *node)		//左旋 
{
	Node *temp = node->rchild;
	Node *pnode = node->parent;
	
	node->rchild = temp->lchild;
	
	if(temp->lchild != NULL)
		temp->lchild->parent = node;
		
	temp->lchild = node;
	node->parent = temp;
	
	temp->parent = pnode;
	*root = temp;
}
void Rsp(Node **root, Node *node)		//右旋 
{
	Node *temp = node->lchild;
	Node *pnode = node->parent;
	
	node->lchild = temp->rchild;
	
	if(temp->rchild != NULL)
		temp->rchild->parent = node;
	
	temp->rchild = node;
	node->parent = temp;
	
	temp->parent = pnode;
	*root = temp;
}

void Traverse(RBtree *t)		//中序遍历 
{
	if(*t == NULL)
		return;
	else
	{
		Traverse(&(*t)->lchild);
		printf("%d  ", (*t)->key);
		Traverse(&(*t)->rchild);
		
	}
	
}

void Clear(RBtree *t)		//销毁 
{
	if(*t == NULL)
		return;
	else
	{
		Clear(&(*t)->lchild);
		Clear(&(*t)->rchild);
		free(*t);
		*t = NULL;
	}
	
}

Node * pnode(RBtree *t, int data)		//返回数据结点的指针 
{
	Node *p;
	if(*t == NULL)
		return NULL;
	else
	{
		p = *t;
		while(p != NULL)
		{
			if(p->key == data)
				return p;
			else if(p->key > data)
				p = p->lchild;
			else
				p = p->rchild;
		}
	}
	
	return p;
}

void TraColor(RBtree *t)		//层序遍历 颜色 
{
	Node * pt = *t;
	int x = 0;
	int y = 0;
	int z = 0;
	Node *temp;
	Queue q;
	InitQueue(&q);
	if(pt == NULL)
		return;
	else
	{
		
			
		if(pt->color == RED)
			printf("%d红  ",pt->key);
		else
			printf("%d黑  ",pt->key);
		printf("n");
		
		if(pt->lchild != NULL)
		{
			EnQueue(&q,&pt->lchild);
				x++;
		}
		if(pt->rchild != NULL)
		{
			EnQueue(&q,&pt->rchild);
				x++;
		}
			
		while(!Empty(&q))
		{
			DeQueue(&q, &temp);
				y++;
			if(temp->color == RED)
				printf("%d红  ",temp->key);
			else
				printf("%d黑  ",temp->key);
		 
			if(temp->lchild != NULL)
			{
				EnQueue(&q,&temp->lchild);
				z++;
			}
			if(temp->rchild != NULL)
			{
				EnQueue(&q,&temp->rchild);
				z++;
			}
			
			if(x == y)
			{
				printf("n");
				x = z;
				y = 0;
				z = 0;
				
			}	
			
		}
		
	}
}

void InitQueue(Queue *q)	//初始化
{
	q->front = q->rear = 0;
}
bool DeQueue(Queue *q, Node ** t) //出队
{
	if(Empty(q))
		return false;
	else
	{
		*t = q->pt[q->front];
		q->front = (q->front+1)%LEN;
		
	}
	return true;
}
bool EnQueue(Queue *q, Node ** t) //入队 
{
	if(Full(q))
		return false;
	else
	{
		q->pt[q->rear] = *t;
		q->rear = (q->rear+1)%LEN;
	}
	return true;
}
bool Full(Queue *q)		//队满
{
	if((q->rear+1)%LEN == q->front)
		return true;
	else
		return false;
}
bool Empty(Queue *q)		//队空 
{
	return q->front == q->rear ? true : false;
}