紅黑樹(shù)的代碼實(shí)現(xiàn).doc

《紅黑樹(shù)的代碼實(shí)現(xiàn).doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、//bysvking//2012.5#include#include#include#defineMAXSIZE1000typedefintElemType;#defineRED0#defineBLACK1typedefstructRBTNode{charcolor;ElemTypedata;structRBTNode*p;structRBTNode*left;structRBTNode*right;}RBTNode,*PRBTNode;typedefstructRBTree{PRBTNoderoot;PRBTNodenil;//統(tǒng)

2、一的空節(jié)點(diǎn)，該節(jié)點(diǎn)是黑的}RBTree,*PRBTree;intleftRotate(PRBTreetree,PRBTNodet);intrightRotate(PRBTreetree,PRBTNodet);PRBTNodeinsertRB(PRBTreetree,ElemTyped);intinsertRB_fixup(PRBTreetree,PRBTNodet);intcreateRBTree(PRBTreetree,ElemTyped[],intn);intinitRB(PRBTreetree);PRBTNodemaximum(PRBTreetree,PRBTNodet);PRB

3、TNodeminimum(PRBTreetree,PRBTNodet);PRBTNodenext(PRBTreetree,PRBTNodet);PRBTNodeprecursor(PRBTreetree,PRBTNodet);intwalkNext(PRBTreetree);intinOrderWalk(PRBTreetree,PRBTNodet);intdeleteRB_fixup(PRBTreetree,PRBTNodec);PRBTNodedeleteRB(PRBTreetree,PRBTNodet);intmain(){PRBTNodep;intd[MAXSIZE];intn=

4、0;inti;RBTreetree;initRB(&tree);/*insertRB(&tree,11);insertRB(&tree,2);insertRB(&tree,14);insertRB(&tree,1);insertRB(&tree,7);insertRB(&tree,15);insertRB(&tree,5);insertRB(&tree,8);insertRB(&tree,4);*/p=insertRB(&tree,26);insertRB(&tree,17);insertRB(&tree,41);insertRB(&tree,14);insertRB(&tree,21

5、);insertRB(&tree,30);insertRB(&tree,47);insertRB(&tree,10);insertRB(&tree,16);insertRB(&tree,19);insertRB(&tree,23);insertRB(&tree,28);insertRB(&tree,38);insertRB(&tree,7);insertRB(&tree,12);insertRB(&tree,15);insertRB(&tree,20);insertRB(&tree,3);insertRB(&tree,35);insertRB(&tree,39);srand(time(

6、NULL));/*puts("請(qǐng)輸入數(shù)據(jù)的個(gè)數(shù)：");scanf("%d",&n);printf("隨機(jī)生成的%d個(gè)數(shù)據(jù)是：",n);for(i=0;idata);printf("刪除%d后：",p->data);deleteRB(&tree,p);inOrderWalk(

7、&tree,tree.root);puts("");printf("根是%d",tree.root->data);return0;}PRBTNodeinsertRB(PRBTreetree,ElemTyped){//插入元素//!!!記得插入的元素的初始化，p指向?yàn)楦改腹?jié)點(diǎn)，left和right賦值為NULL。PRBTNodet=NULL;PRBTNodep=NULL;intflag=0;//用來(lái)表示插入在左邊的樹(shù)還是右邊的樹(shù)t=tree-