红黑树的代码实现.doc

《红黑树的代码实现.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、//bysvking//2012.5#include#include#include#defineMAXSIZE1000typedefintElemType;#defineRED0#defineBLACK1typedefstructRBTNode{charcolor;ElemTypedata;structRBTNode*p;structRBTNode*left;structRBTNode*right;}RBTNode,*PRBTNode;typedefstructRBTree{PRBTNoderoot;PRBTNodenil;//统

2、一的空节点，该节点是黑的}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("请输入数据的个数：");scanf("%d",&n);printf("随机生成的%d个数据是：",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指向为父母节点，left和right赋值为NULL。PRBTNodet=NULL;PRBTNodep=NULL;intflag=0;//用来表示插入在左边的树还是右边的树t=tree-