【數(shù)據(jù)結(jié)構(gòu)】b類-紅黑二叉樹正文終稿

#include<stdio.h>#include<malloc.h>#include<string.h>#include<windows.h>#include<stdlib.h>#defineTRUE1#defineBOOLint#defineFALSE0#defineStatusintenumcolor_t{ RED,BlACK};typedefstructRedBlackNode//紅黑二叉樹結(jié)構(gòu)體{ intdata; charphone[12]; charname[12];//數(shù)據(jù)域 color_tcolor;//顏色 RedBlackNode*left;//左孩子 RedBlackNode*right;//右孩子 RedBlackNode*parent;//父親節(jié)點}RedBlackNode,*RBTree;typedefstructLinkStack{RedBlackNode*rbtree; structLinkStack*next;}LinkStack;LinkStack*InitStack();StatusStackEmpty(LinkStack*L);StatusDestroyStack(LinkStack*L);StatusStackLength(LinkStack*L);StatusPushStack(LinkStack*L,RedBlackNode*r);RedBlackNode*PopStack(LinkStack*L);RedBlackNode*RBserach(RedBlackNode*rbtree,intkey);RedBlackNode*RBMinimum(RBTree*T);RedBlackNode*RBMaximum(RBTree*T);RedBlackNode*RBpioneer(RedBlackNode*T);RedBlackNode*RBsucceed(RedBlackNode*T);voidleft_rotate(RBTree*rbtree,RedBlackNode*T);voidright_rotate(RBTree*retree,RedBlackNode*T);BOOLRBInsertNode(RBTree*T,intdata);intRBDeleteNode(RBTree*T,intdata);voidRbTreeInsertAdjust(RBTree*T,RedBlackNode*p);voidRbTreeDeleteAdjust(RBTree*T,RedBlackNode*parent,RedBlackNode*x);voidOutput(RedBlackNode*p);voidPreorderTraverse(RedBlackNode*T);voidInorderTraverse(RedBlackNode*T);voidPostorderTraverse(RedBlackNode*T);intprerecursion(RedBlackNode*T);intinrecursion(RedBlackNode*T);intpostrecursion(RedBlackNode*T);voidmenu1();voidmenu2();voidlogon();LinkStack*InitStack(){ LinkStack*L; L=(LinkStack*)malloc(sizeof(LinkStack));L->next=NULL;returnL;}StatusStackEmpty(LinkStack*L){ if(L->next) { returnFALSE; } else { returnTRUE;}}StatusDestroyStack(LinkStack*L){ LinkStack*p,*r,*q; p=L->next; r=L; if(p==NULL) { returnFALSE; } while(p!=NULL) { r->next=p->next; q=p; p=p->next; free(q); } free(L); returnTRUE;}StatusStackLength(LinkStack*L){ inti=0; LinkStack*p; p=L->next; if(L==NULL) { returnFALSE; } while(p!=NULL) { i++; p=p->next; } returni;}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;returnq;}StatusPushStack(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;returnTRUE;}RedBlackNode*RBserach(RBTree*rbtree,intkey)//查找值為key的節(jié)點{ RedBlackNode*T; T=*rbtree; while(T!=NULL&&T->data!=key) { if(key<T->data) { T=T->left; } else { T=T->right; } } Output(T); returnT;}RedBlackNode*RBMinimum(RBTree*T)//返回紅黑樹局部最小值{ RedBlackNode*curNode,*targetNode; curNode=*T; targetNode=NULL; if(curNode!=NULL) { targetNode=curNode; curNode=curNode->left; } returntargetNode;}RedBlackNode*RBMaximum(RBTree*T)//返回紅黑樹局部最大值{ RedBlackNode*curNode,*targetNode; curNode=*T; targetNode=NULL; if(curNode!=NULL) { targetNode=curNode; curNode=curNode->right; } returntargetNode;}RedBlackNode*RBpioneer(RedBlackNode*T)//返回T的前驅(qū){RedBlackNode*targetNode;RedBlackNode*P;P=NULL;if(T==NULL){ returnP;}if(T->left!=NULL){ targetNode=RBMaximum(&(T->left));}else{ while(T->parent!=NULL&&T->parent->right!=T) { T=T->parent; } targetNode=T->parent;}returntargetNode;}RedBlackNode*RBsucceed(RedBlackNode*T)//后繼節(jié)點{ RedBlackNode*targetNode; RedBlackNode*P; P=NULL; if(T==NULL) { returnP; } if(T->right!=NULL) { targetNode=RBMinimum(&(T->right)); } else { while(T->parent!=NULL&&T->parent->left!=T) { T=T->parent; } targetNode=T->parent; } returntargetNode;}voidleft_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;}voidright_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;}BOOLRBInsertNode(RBTree*T,intdata,char*name,char*phone){ RedBlackNode*node,*p,*curNode; node=(RedBlackNode*)malloc(sizeof(RedBlackNode)); if(node==NULL) returnFALSE; 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); returnTRUE;}intRBDeleteNode(RBTree*T,intdata,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);returnTRUE; } else { returnFALSE; }}voidRbTreeInsertAdjust(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;}voidRbTreeDeleteAdjust(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;} }voidOutput(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);}voidPreorderTraverse(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))//通過下一次循環(huán)中的內(nèi)嵌while實現(xiàn)右子樹遍歷 { p=PopStack(L); p=p->right; }}}voidInorderTraverse(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);//訪問根結(jié)點p=p->right;//通過下一次循環(huán)實現(xiàn)右子樹遍歷}}DestroyStack(L);}voidPostorderTraverse(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)//左右子樹已訪問完，訪問根節(jié)點{Output(node);last=node;}elseif(node->left||node->right)//左右子樹未訪問，當(dāng)前節(jié)點入棧，左右節(jié)點入棧{PushStack(L,node);if(node->right)PushStack(L,node->right);if(node->left)PushStack(L,node->left);}else//當(dāng)前節(jié)點為葉節(jié)點，訪問{Output(node);last=node;}}DestroyStack(L);}intprerecursion(RedBlackNode*T){RedBlackNode*p;p=T; if(p) { Output(p); if(p->left) prerecursion(p->left);if(p->right) prerecursion(p->right); returnTRUE; } returnFALSE;}intinrecursion(RedBlackNode*T){RedBlackNode*p;p=T; if(p) { if(p->left) inrecursion(p->left); Output(p);if(p->right) inrecursion(p->right); returnTRUE; } returnFALSE; }intpostrecursion(RedBlackNode*T){RedBlackNode*p;p=T; if(p) { if(p->left) postrecursion(p->left);if(p->right) postrecursion(p->right); Output(p); returnTRUE; } returnFALSE; }voidmenu1(){inti; 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++) { intj; printf(">"); Sleep(5); for(j=0;j<10;j++) { Beep(40000,2); } } printf("\n"); printf("--------------------------------------------------------------\n"); printf("--------------------------------------------------------------\n");}voidmenu2(){inti,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");}voidlogon(){printf("\n\n\n\t\t\t紅黑二叉樹\n");printf("\t\t\t版本號：1.0\n\n");printf("\n\n\n\n\n\t\t\t2015年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; intdata;inti,j,k,q,a,b,c,d; j=0; charname[12]; charphone[12]; logon(); while(1) { menu1(); printf("請輸入[1-6]:"); scanf("%d",&i); switch(i) { case1: printf("請輸入添加個數(shù):"); scanf("%d",&k); for(a=0;a<k;a++) { printf("請輸入學(xué)號:");scanf("%d",&data);printf("請輸入姓名:");scanf("%s",&name);printf("請輸入電話:");scanf("%s",&phone); RBInsertNode(&root,data,name,phone); } j=1; printf("\n按任意鍵繼續(xù)..."); getchar(); getchar(); system("cls"); break; case2: if(j==1) { printf("請輸入查找學(xué)號:"); scanf("%d",&q); printf("請輸入姓名:");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; } case3: if(j==1) { printf("請輸入插入學(xué)號："); scanf("%d",&b); printf("請輸入姓名:");scanf("%s",&name);printf("請輸入電話:");scanf("%s",&phone); RBInsertNode(&root,b,name,phone); printf("\n按任意鍵繼續(xù)..."); getchar(); getchar(); system("cls"); break; } else { printf("請初始化\n"); printf("\n按任意鍵繼續(xù)..."); getchar(); getchar(); system("cls"); break; } case4: if(j==1){ printf("請輸入刪除學(xué)號："); scanf("%d",&c);printf("請輸入姓名:");scanf("%s",&name);printf("請輸入電話:");scanf("%s",&phone); RBDeleteNode(&root,c,name,phone); printf("\n按任意鍵繼續(xù)..."); getchar(); getchar();system("cls"); break;}else{ printf("請初始化\n"); printf("\n按任意鍵繼續(xù)..."); getchar(); getchar(); system("cls"); break;} case5: menu2(); printf("請輸入[1-7]:");scanf("%d",&d);switch(d){ case1: prerecursion(root); break; case2: inrecursion(root); break; case3: postrecursion(root); break; case4: PreorderTraverse(root); break; case5: InorderTraverse(root); break; case6: PostorderTraverse(root); break; case7: break; default: printf("輸入錯誤，請重新輸入\n"); break; }printf("\n按任意鍵繼續(xù)..."); getchar(); getchar(); system("cls");break;case6: exit(0);default: printf("輸入錯誤，請重新輸入\n按任意鍵繼續(xù)..."); getchar(); getchar();system("cls"); } } }基于C8051F單片機直流電動機反饋控制系統(tǒng)的設(shè)計與研究基于單片機的嵌入式Web服務(wù)器的研究MOTOROLA單片機MC68HC（8）05PV8/A內(nèi)嵌EEPROM的工藝和制程方法及對良率的影響研究基于模糊控制的電阻釬焊單片機溫度控制系統(tǒng)的研制基于MCS-51系列單片機的通用控制模塊的研究基于單片機實現(xiàn)的供暖系統(tǒng)最佳啟停自校正（STR）調(diào)節(jié)器單片機控制的二級倒立擺系統(tǒng)的研究基于增強型51系列單片機的TCP/IP協(xié)議棧的實現(xiàn)基于單片機的蓄電池自動監(jiān)測系統(tǒng)基于32位嵌入式單片機系統(tǒng)的圖像采集與處理技術(shù)的研究基于單片機的作物營養(yǎng)診斷專家系統(tǒng)的研究基于單片機的交流伺服電機運動控制系統(tǒng)研究與開發(fā)基于單片機的泵管內(nèi)壁硬度測試儀的研制基于單片機的自動找平控制系統(tǒng)研究基于C8051F040單片機的嵌入式系統(tǒng)開發(fā)基于單片機的液壓動力系統(tǒng)狀態(tài)監(jiān)測儀開發(fā)模糊Smith智能控制方法的研究及其單片機實現(xiàn)一種基于單片機的軸快流CO〈,2〉激光器的手持控制面板的研制基于雙單片機沖床數(shù)控系統(tǒng)的研究基于CYGNAL單片機的在線間歇式濁度儀的研制基于單片機的噴油泵試驗臺控制器的研制基于單片機的軟起動器的研究和設(shè)計基于單片機控制的高速快走絲電火花線切割機床短循環(huán)走絲方式研究基于單片機的機電產(chǎn)品控制系統(tǒng)開發(fā)基于PIC單片機的智能手機充電器基于單片機的實時內(nèi)核設(shè)計及其應(yīng)用研究基于單片機的遠(yuǎn)程抄表系統(tǒng)的設(shè)計與研究基于單片機的煙氣二氧化硫濃度檢測儀的研制基于微型光譜儀的單片機系統(tǒng)單片機系統(tǒng)軟件構(gòu)件開發(fā)的技術(shù)研究基于單片機的液體點滴速度自動檢測儀的研制基于單片機系統(tǒng)的多功能溫度測量儀的研制基于PIC單片機的電能采集終端的設(shè)計和應(yīng)用基于單片機的光纖光柵解調(diào)儀的研制氣壓式線性摩擦焊機單片機控制系統(tǒng)的研制基于單片機的數(shù)字磁通門傳感器基于單片機的旋轉(zhuǎn)變壓器-數(shù)字轉(zhuǎn)換器的研究基于單片機的光纖Bragg光柵解調(diào)系統(tǒng)的研究單片機控制的便攜式多功能乳腺治療儀的研制基于C8051F020單片機的多生理信號檢測儀基于單片機的電機運動控制系統(tǒng)設(shè)計Pico專用單片機核的可測性設(shè)計研究基于MCS-51單片機的熱量計基于雙單片機的智能遙測微型氣象站MCS-51單片機構(gòu)建機器人的實踐研究基于單片機的輪軌力檢測基于單片機的GPS定位儀的研究與實現(xiàn)基于單片機的電液伺服控制系統(tǒng)用于單片機系統(tǒng)的MMC卡文件系統(tǒng)研制基于單片機的時控和計數(shù)系統(tǒng)性能優(yōu)化的研究基于單片機和CPLD的粗光柵位移測量系統(tǒng)研究單片機控制的后備式方波UPS提升高職學(xué)生單片機應(yīng)用能力的探究基于單片機控制的自動低頻減載裝置研究基于單片機控制的水下焊接電源的研究基于單片機的多通道數(shù)據(jù)采集系統(tǒng)基于uPSD3234單片機的氚表面污染測量儀的研制基于單片機的紅外測油儀的研究96系列單片機仿真器研究與設(shè)計基于單片機的單晶金剛石刀具刃磨設(shè)備的數(shù)控改造基于單片機的溫度智能控制系統(tǒng)的設(shè)計與實現(xiàn)基于MSP430單片機的電梯門機控制器的研制基于單片機的氣體測漏儀的研究基于三菱M16C/6N系列單片機的CAN/USB協(xié)議轉(zhuǎn)換器基于單片機和DSP的變壓器油色譜在線監(jiān)測技術(shù)研究基于單片機的膛壁溫度報警系統(tǒng)設(shè)計基于AVR單片機的低壓無功補償控制器的設(shè)計基于單片機船舶電力推進(jìn)電機監(jiān)測系統(tǒng)基于單片機網(wǎng)絡(luò)的振動信號的采集系統(tǒng)基于單片機的大容量數(shù)據(jù)存儲技術(shù)的應(yīng)用研究基于單片機的疊圖機研究與教學(xué)方法實踐基于單片機嵌入式Web服務(wù)器技術(shù)的研究及實現(xiàn)基于AT89S52單片機的通用數(shù)據(jù)采集系統(tǒng)基于單片機的多道脈沖幅度分析儀研究機器人旋轉(zhuǎn)電弧傳感角焊縫跟蹤單片機控制系統(tǒng)基于單片機的控制系統(tǒng)在PLC虛擬教學(xué)實驗中的應(yīng)用研究基于單片機系統(tǒng)的網(wǎng)絡(luò)通信研究與應(yīng)用基于PIC16F877單片機的莫爾斯碼自動譯碼系統(tǒng)設(shè)計與研究基于單片機的模糊控制器在工業(yè)電阻爐上的應(yīng)用研究基于雙單片機沖床數(shù)控系統(tǒng)的研究與開發(fā)基于Cygnal單片機的μC/OS-Ⅱ的研究基于單片機的一體化智能差示掃描量熱儀系統(tǒng)