毕业设计-数据结构b类红黑二叉树.doc

#include<stdio.h>
#include<malloc.h>
#include<string.h>
#include<windows.h>
#include <stdlib.h>
#define TRUE 1
#define BOOL int
#define FALSE 0
#define Status int

enum color_t
{
RED,BlACK
};

typedef struct RedBlackNode //红黑二叉树结构体
{
int data;
char phone[12];
char name[12]; //数据域
color_t color; //颜色
RedBlackNode *left; //左孩子
RedBlackNode *right; //右孩子
RedBlackNode *parent; //父亲节点
}RedBlackNode,*RBTree;

typedef struct LinkStack
{
RedBlackNode *rbtree;
struct LinkStack *next;
}LinkStack;

LinkStack * InitStack();
Status StackEmpty(LinkStack *L);
Status DestroyStack(LinkStack *L);
Status StackLength(LinkStack *L);
Status PushStack(LinkStack *L,RedBlackNode *r);
RedBlackNode * PopStack(LinkStack *L);
RedBlackNode *RBserach(RedBlackNode *rbtree,int key);
RedBlackNode *RBMinimum(RBTree *T);
RedBlackNode *RBMaximum(RBTree *T);
RedBlackNode *RBpioneer(RedBlackNode *T);
RedBlackNode *RBsucceed(RedBlackNode *T);
void left_rotate(RBTree *rbtree,RedBlackNode *T);
void right_rotate(RBTree *retree,RedBlackNode *T);
BOOL RBInsertNode(RBTree *T,int data);
int RBDeleteNode(RBTree *T, int data);
void RbTreeInsertAdjust(RBTree *T,RedBlackNode *p);
void RbTreeDeleteAdjust(RBTree *T,RedBlackNode *parent,RedBlackNode *x);
void Output(RedBlackNode *p);
void PreorderTraverse(RedBlackNode *T);
void InorderTraverse(RedBlackNode *T);
void PostorderTraverse(RedBlackNode *T);
int prerecursion(RedBlackNode *T);
int inrecursion(RedBlackNode *T);
int postrecursion(RedBlackNode *T);
void menu1();
void menu2();
void logon();

LinkStack * InitStack()
{
LinkStack *L;
L=(LinkStack *)malloc(sizeof(LinkStack));
L->next=NULL;
return L;
}

Status StackEmpty(LinkStack *L)
{
if(L->next)
{
return FALSE;
}
else
{
return TRUE;
}
}

Status DestroyStack(LinkStack *L)
{
LinkStack *p,*r,*q;
p=L->next;
r=L;
if(p==NULL)
{
return FALSE;
}
while(p!=NULL)
{
r->next=p->next;
q=p;
p=p->next;
free(q);
}
free(L);
return TRUE;
}

Status StackLength(LinkStack *L)
{
int i=0;
LinkStack *p;
p=L->next;
if(L==NULL)
{
return FALSE;
}
while(p!=NULL)
{
i++;
p=p->next;
}
return i;
}

RedBlackNode *PopStack(LinkStack *L)
{
LinkStack *p;
RedBlackNode *q;
p=L;
while(p->next&&p->next->next!=NULL)
{
p=p->next;
}
q=p->next->rbtree;
p->next=NULL;
return q;
}

Status PushStack(LinkStack *L,RedBlackNode *r)
{
LinkStack *p,*stacknode=(LinkStack*)malloc(sizeof(LinkStack));
p=L;
while(p->next!=NULL)
{
p=p->next;
}
stacknode->rbtree=r;
stacknode->next=NULL;
p->next=stacknode;
return TRUE;
}

RedBlackNode *RBserach(RBTree *rbtree,int key) //查找值为key的节点
{
RedBlackNode *T;
T=*rbtree;
while(T!=NULL&&T->data!=key)
{
if(key<T->data)
{
T=T->left;
}
else
{
T=T->right;
}
}
Output(T);
return T;
}

RedBlackNode *RBMinimum(RBTree *T) //返回红黑树局部最小值
{
RedBlackNode *curNode, *targetNode;
curNode=*T;
targetNode=NULL;
if(curNode!=NULL)
{
targetNode=curNode;
curNode=curNode->left;
}
return targetNode;
}

RedBlackNode *RBMaximum(RBTree *T) //返回红黑树局部最大值
{
RedBlackNode *curNode, *targetNode;
curNode=*T;
targetNode=NULL;
if(curNode!=NULL)
{
targetNode=curNode;
curNode=curNode->right;
}
return targetNode;
}

RedBlackNode *RBpioneer(RedBlackNode *T) //返回T的前驱
{
RedBlackNode *targetNode;
RedBlackNode *P;
P=NULL;
if(T==NULL)
{
return P;
}
if(T->left!=NULL)
{
targetNode=RBMaximum(&(T->left));
}
else
{
while(T->parent!=NULL&&T->parent->right!=T)
{
T=T->parent;
}
targetNode=T->parent;
}
return targetNode;
}

RedBlackNode *RBsucceed(RedBlackNode *T) //后继节点
{
RedBlackNode *targetNode;
RedBlackNode *P;
P=NULL;
if(T==NULL)
{
return P;
}
if(T->right!=NULL)
{
targetNode=RBMinimum(&(T->right));
}
else
{
while(T->parent!=NULL&&T->parent->left!=T)
{
T=T->parent;
}
targetNode=T->parent;
}
return targetNode;
}

void left_rotate(RBTree *rbtree,RedBlackNode *T) //左旋
{
RedBlackNode *p;
p=T->right;
T->right=p->left;
if(p->left!=NULL)
{
p->left->parent=T;
}
p->parent=T->parent;
if(T->parent==NULL)
{
*rbtree=p;
}
else
{
if(T->parent->left==T)
{
T->parent->left=p;
}
else
{
T->parent->right=p;
}
}
p->left=T;
T->parent=p;
}

void right_rotate(RBTree *retree,RedBlackNode *T)
{
RedBlackNode *p;
p=T->left;

T->left=p->right;
if(p->right!=NULL)
{
p->right->parent=T;
}
p->parent=T->parent;
if(T->parent==NULL)
{
*retree=p;
}
else
{
if(T->parent->left==T)
{
T->parent->left=p;
}
else
{
T->parent->right=p;
}
}
p->right=T;
T->parent=p;
}

BOOL RBInsertNode(RBTree *T,int data,char *name,char *phone)
{
RedBlackNode *node,*p,*curNode;
node=(RedBlackNode *)malloc(sizeof(RedBlackNode));
if(node==NULL)
return FALSE;
node->data=data;
strcpy(node->phone,phone);
strcpy(node->name,name);
node->color=RED;
node->left=NULL;
node->right=NULL;
node->parent=NULL;
curNode=*T;
p=NULL;
while(curNode!=NULL)
{
p=curNode;
if(data < curNode->data)
{
curNode=curNode->left;
}
else
{
curNode=curNode->right;
}
}
if(p==NULL)
{
*T=node;
}
else
{
if(data<p->data)
{
p->left=node;
}
else
{
p->right=node;
}
}
node->parent=p;
RbTreeInsertAdjust(T,node);
return TRUE;
}

int RBDeleteNode(RBTree *T, int data,char *name,char *phone)
{
RedBlackNode *child,*target,*realdel;
target= RBserach(T,data);
if(target!=NULL)
{
if(target->left==NULL||target->right==NULL)
{
realdel=target;
}
else
{
realdel=RBsucceed(target);
}
if(realdel->left!=NULL)
{
child=realdel->left;
}
else
{
child=realdel->right;
}
if(child!=NULL)
{
child->parent=realdel->parent;
}
if(realdel->parent==NULL)
{
*T=child;
}
else
{
if(realdel->parent->left==realdel)
{
realdel->parent->left=child;
}
else
{
realdel->parent->right=child;
}
}
if(target!=realdel)
{
target->data=realdel->data;
strcpy(target->phone,phone);
strcpy(target->name,name);
}
if(realdel->color==BlACK)
{
RbTreeDeleteAdjust(T,realdel->parent,child);
}
free(realdel);
return TRUE;
}
else
{
return FALSE;
}
}

void RbTreeInsertAdjust(RBTree *T,RedBlackNode *p)
{
RedBlackNode *q,*uncle,*grandparent;
while((q=p->parent)!=NULL&&q->color==RED)
{
grandparent=q->parent;
if(q==grandparent->left)
{
uncle=grandparent->right;
if(uncle!=NULL&&uncle->color==RED)
{
grandparent->color=RED;
q->color=BlACK;
uncle->color=BlACK;
p=grandparent;
}
else
{
if(p==q->right)
{
p=q;
left_rotate(T,p);
q=p->parent;
}
else
{
q->color=BlACK;
grandparent->color=RED;
right_rotate(T,grandparent);
}
}
}
else
{
uncle=grandparent->left;
if(uncle!=NULL&&uncle->color==RED)
{
grandparent->color=RED;
q->color=BlACK;
uncle->color=BlACK;
p=grandparent;
}
else
{
if(p==q->left)
{
p=q;
right_rotate(T,p);
q=p->parent;
}
else
{
q->color=BlACK;
grandparent->color=RED;
left_rotate(T,grandparent);
}
}
}
}
(*T)->color=BlACK;
}

void RbTreeDeleteAdjust(RBTree *T,RedBlackNode *parent,RedBlackNode *x)
{
RedBlackNode *brother;
while((x==NULL||x->color==BlACK)&&x!=*T)
{
if(x==parent->left)
{
brother=parent->right;
if(brother->color==RED)
{
brother->color=BlACK;
parent->color=RED;
left_rotate(T,parent);
brother=parent->right;
}
if((brother->left==NULL||brother->left->color==BlACK)&&
(brother->right==NULL||brother->right->color==BlACK))
{
brother->color=RED;
x=parent;
parent=parent->parent;
}
else
{
if(brother->right==NULL||brother->color==BlACK)
{
brother->left->color=BlACK;
brother->color=RED;
right_rotate(T,brother);
brother=parent->right;
}
brother->color=parent->color;
parent->color=BlACK;
brother->right->color=BlACK;
left_rotate(T,parent);
x=*T;
}
}
else
{
brother=parent->left;
if(brother->color==RED)
{
brother->color=BlACK;
parent->color=RED;
right_rotate(T,parent);
brother=parent->left;
}
if((brother->right==NULL||brother->right->color==BlACK)&&
(brother->left==NULL||brother->left->color==BlACK))
{
brother->color=RED;
x=parent;
parent=parent->parent;
}
else
{
if(brother->left==NULL||brother->left->color==BlACK)
{
brother->right->color=BlACK;
brother->color=RED;
left_rotate(T,brother);
brother=parent->left;
}
brother->color=parent->color;
parent->color=BlACK;
brother->left->color=BlACK;
right_rotate(T,parent);
x=*T;
}
}
}
if(x!=NULL)
{
x->color=BlACK;
}
}

void Output(RedBlackNode *p)
{
printf("data: %d, color: %s, parent: %d，name:%s,phone:%s\n",
p->data, (p->color == RED ? "RED" : "BlACK"),
(p->parent != NULL) ? p->parent->data : -1,p->name,p->phone);

}

void PreorderTraverse(RedBlackNode *T)
{
LinkStack *L=InitStack();
RedBlackNode *p;
p=T;
while (p || !StackEmpty(L))
{
while (p) //遍历左子树
{
Output(p);
PushStack(L,p);
p=p->left;
}
if (!StackEmpty(L)) //通过下一次循环中的内嵌while实现右子树遍历
{
p=PopStack(L);
p=p->right;
}
}
}

void InorderTraverse(RedBlackNode *T)
{
LinkStack *L;
L=InitStack();
RedBlackNode *p;
p=T;
while (p!=NULL || !StackEmpty(L))
{
while (p!=NULL) //遍历左子树
{
PushStack(L,p);
p=p->left;
}

if (!StackEmpty(L))
{
p=PopStack(L);
Output(p); //访问根结点
p=p->right; //通过下一次循环实现右子树遍历
}
}
DestroyStack(L);
}

void PostorderTraverse(RedBlackNode *T)
{
RedBlackNode *node = NULL,*last = NULL;
LinkStack *L=InitStack();
RedBlackNode *p;
p=T;
PushStack(L,p);
while(!StackEmpty(L))
{
node = PopStack(L);
if(last == node->left || last == node->right)//左右子树已访问完，访问根节点
{
Output(node);
last = node;
}
else if(node->left || node->right) //左右子树未访问，当前节点入栈，左右节点入栈
{
PushStack(L,node);
if(node->right)
PushStack(L,node->right);
if(node->left)
PushStack(L,node->left);
}
else //当前节点为叶节点，访问
{
Output(node);
last = node;
}
}
DestroyStack(L);
}

int prerecursion(RedBlackNode *T)
{
RedBlackNode *p;
p=T;
if(p)
{
Output(p);
if(p->left)
prerecursion(p->left);
if(p->right)
prerecursion(p->right);
return TRUE;
}
return FALSE;
}

int inrecursion(RedBlackNode *T)
{
RedBlackNode *p;
p=T;
if(p)
{
if(p->left)
inrecursion(p->left);
Output(p);
if(p->right)
inrecursion(p->right);
return TRUE;
}
return FALSE;
}

int postrecursion(RedBlackNode *T)
{
RedBlackNode *p;
p=T;
if(p)
{
if(p->left)
postrecursion(p->left);
if(p->right)
postrecursion(p->right);
Output(p);
return TRUE;
}
return FALSE;
}

void menu1()
{
int i;
printf(" --------------------------------------------------------------\n");
printf(" --------------------------------------------------------------\n");
printf(" -- 1.初始化 --\n");
printf(" -- 2.查找 --\n");
printf(" -- 3.插入 --\n");
printf(" -- 4.删除 --\n");
printf(" -- 5.遍历 --\n");
printf(" -- 6.退出 --\n");
for(i=0;i<30;i++)
{
int j;
printf(" >");
Sleep(5);
for(j=0;j<10;j++)
{
Beep(40000,2);
}
}
printf("\n");
printf(" --------------------------------------------------------------\n");
printf(" --------------------------------------------------------------\n");
}

void menu2()
{
int i,j;
printf(" --------------------------------------------------------------\n");
printf(" --------------------------------------------------------------\n");
printf(" -- 1.前序遍历 --\n");
printf(" -- 2.中序遍历 --\n");
printf(" -- 3.后序遍历 --\n");
printf(" -- 4.前序遍历非递归 --\n");
printf(" -- 5.中序遍历非递归 --\n");
printf(" -- 6.后序遍历非递归 --\n");
printf(" -- 7.返回 --\n");
for(i=0;i<40;i++)
{
printf(" >");
Sleep(5);
for(j=0;j<20;j++)
{
Beep(40000,2);
}
}
printf("\n");
printf(" --------------------------------------------------------------\n");
printf(" --------------------------------------------------------------\n");
}

void logon()
{
printf("\n\n\n\t\t\t 红黑二叉树\n");
printf("\t\t\t 版本号：1.0\n\n");
printf("\n\n\n\n\n\t\t\t 2015年1月12日\n\n");
printf("\t\t\t组长：范伟佳\n");
printf("\t\t\t组员：张航斌\n");
printf("\t\t\t组员：张艺峰\n");
system("pause");
system("cls");
}

main(void)
{
RedBlackNode *root;
root=NULL;
int data;
int i,j,k,q,a,b,c,d;
j=0;
char name[12];
char phone[12];
logon();
while(1)
{
menu1();
printf("请输入[1-6]:");
scanf("%d",&i);
switch(i)
{
case 1:
printf("请输入添加个数:");
scanf("%d",&k);
for(a=0;a<k;a++)
{
printf("请输入学号:");
scanf("%d",&data);
printf("请输入姓名:");
scanf("%s",&name);
printf("请输入电话:");
scanf("%s",&phone);
RBInsertNode(&root,data,name,phone);
}
j=1;
printf("\n按任意键继