數(shù)據(jù)結(jié)構(gòu)B類紅黑二叉樹

1、#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 /紅黑二叉樹結(jié)構(gòu)體 int data; char phone12;char name12; /數(shù)據(jù)域 color_t color;

2、/顏色 RedBlackNode *left; /左孩子 RedBlackNode *right; /右孩子 RedBlackNode *parent; /父親節(jié)點(diǎn) RedBlackNode,*RBTree;typedef struct LinkStack RedBlackNode *rbtree; struct LinkStack *next;LinkStack;LinkStack * InitStack();Status StackEmpty(LinkStack *L);Status DestroyStack(LinkStack *L);Status StackLength(LinkSta

3、ck *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);voi

4、d 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

5、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 * InitSt

6、ack()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-&g

7、t;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->n

8、ext; 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;RedBlackNo

9、de *RBserach(RBTree *rbtree,int key) /查找值為key的節(jié)點(diǎn) 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(cur

10、Node!=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 *

11、T) /返回T的前驅(qū) 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(RedBlac

12、kNode *T) /后繼節(jié)點(diǎn) 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,RedB

13、lackNode *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_rota

14、te(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->paren

15、t=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=NU

16、LL;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

17、;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->

18、;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(

19、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->pa

20、rent;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

21、(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,grandpare

22、nt); (*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,

23、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=BlA

24、CK;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; rig

25、ht_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-&g

26、t;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, colo

27、r: %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(

28、L) while (p) /遍歷左子樹 Output(p); PushStack(L,p); p=p->left; if (!StackEmpty(L) /通過下一次循環(huán)中的內(nèi)嵌while實(shí)現(xiàn)右子樹遍歷 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-&

29、gt;left; if (!StackEmpty(L) p=PopStack(L); Output(p); /訪問根結(jié)點(diǎn) p=p->right; /通過下一次循環(huán)實(shí)現(xiàn)右子樹遍歷 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

30、 = node->left | last = node->right)/左右子樹已訪問完，訪問根節(jié)點(diǎn) Output(node); last = node; else if(node->left | node->right) /左右子樹未訪問，當(dāng)前節(jié)點(diǎn)入棧，左右節(jié)點(diǎn)入棧 PushStack(L,node); if(node->right) PushStack(L,node->right); if(node->left) PushStack(L,node->left); else /當(dāng)前節(jié)點(diǎn)為葉節(jié)點(diǎn)，訪問 Output(node); last = n

31、ode; 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); O

32、utput(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"

33、;);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+)B

34、eep(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(&q

35、uot; - 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");

36、 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=

37、0;char name12;char phone12;logon();while(1)menu1();printf("請輸入1-6:");scanf("%d",&i);switch(i)case 1:printf("請輸入添加個數(shù):");scanf("%d",&k);for(a=0;a<k;a+) printf("請輸入學(xué)號:"); scanf("%d",&data); printf("請輸入姓名:"); scanf(&quo

38、t;%s",&name); printf("請輸入電話:"); scanf("%s",&phone); RBInsertNode(&root,data,name,phone); j=1; printf("n按任意鍵繼續(xù)."); getchar(); getchar(); system("cls");break;case 2:if(j=1) printf("請輸入查找學(xué)號:"); scanf("%d",&q); printf("

39、;請輸入姓名:"); scanf("%s",&name); printf("請輸入電話:"); scanf("%s",&phone); RBserach(&root,q); printf("n按任意鍵繼續(xù)."); getchar(); getchar(); system("cls"); break;else printf("請初始化n"); printf("n按任意鍵繼續(xù)."); getchar(); getchar(); system("cls");break; case 3: if(j=1) printf("請輸入插入學(xué)號：");scanf("%d",&b); printf("請輸入姓名:"); scanf("%s",&n