数据结构B类红黑二叉树.doc

#include#include#include#include#include #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(keydata)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 data) curNode=curNode-left;else curNode=curNode-right;if(p=NULL) *T=node;else if(datadata)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); Sleep(5);for(j=0;j10;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); Sleep(5);for(j=0;j20;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;ak;a+) printf(请输入学号:); scanf(%d,&data); printf(请输入姓名:); scanf(%s,&name); printf(请输入电话:); scanf(%s,&phone); RBInsertNode(&root,data,name,phone); j=1; printf(n按任意键继续.); getchar(); getchar(); system(cls);break;case 2:if(j=1) printf(请输入查找学号:); scanf(%d,&q); printf(请输入姓名:); scanf(%s,&name); printf(请输入电话:); scanf(%s,&phone); RBserach(&root,q); printf(n按任意键继续.); getchar(); getchar(); system(cls); break;else printf(请初始化n); printf(n按任意键继续.)