毕业设计-数据结构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 intenum color_tRED,BlACK;typedef struct RedBlackNode /红黑二叉树结构体 int data; char phone12;char name12; /数据域 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;elseT=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);elsewhile(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;elseT->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;elseT->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; elsep->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;elserealdel=RBsucceed(target);if(realdel->left!=NULL)child=realdel->left;elsechild=realdel->right;if(child!=NULL)child->parent=realdel->parent;if(realdel->parent=NULL)*T=child;elseif(realdel->parent->left=realdel)realdel->parent->left=child;elserealdel->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;elsereturn 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;elseif(p=q->right)p=q;left_rotate(T,p);q=p->parent;elseq->color=BlACK;grandparent->color=RED;right_rotate(T,grandparent);elseuncle=grandparent->left;if(uncle!=NULL&&uncle->color=RED)grandparent->color=RED;q->color=BlACK;uncle->color=BlACK;p=grandparent;elseif(p=q->left) p=q;right_rotate(T,p);q=p->parent;elseq->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;elseif(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;elseif(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:%sn",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("nnnttt 红黑二叉树n"); printf("ttt 版本号：1.0nn"); printf("nnnnnttt 2015年1月12日nn"); printf("ttt组长：范伟佳n"); printf("ttt组员：张航斌n"); printf("ttt组员：张艺峰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 name12;char phone12;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按任意键继