首页 > 代码库 > 红黑树(RBTREE)之上-------构造红黑树
红黑树(RBTREE)之上-------构造红黑树
该怎么说呢，现在写代码的速度还是很快的，很高兴，o(^▽^)o。
光棍节到了，早上没忍住，手贱了一般，看到*D的优惠，买了个机械键盘，晚上就到了，敲着还是很舒服的，和老婆炫耀了一把哈哈。
光棍节再去*mall买个，带着上班用。
正题，构造红黑树，就是节点的插入与调整，具体的理论我就不说了，图我也不画了，别人画的很好，我在纸上画的我自己都不想看。
贴几个网址作为参考吧：
参考的文档：1.http://www.cnblogs.com/zhb-php/p/5504481.html (推荐)
2.http://www.cnblogs.com/skywang12345/p/3245399.html 参考，写的太详细了，反而不适合当文档
3.http://blog.csdn.net/v_july_v/article/details/6284050 这个刚好作为测试的参考图
这次的变量命名基本注意了，不过有些以前写的拿过来改改，懒得去把所有的都改了，写这个好像没有什么收获，好像数据结构基本的一些常用的都写了，还有个hash表下次写。
最近工作应该算是忙吧，但是做的都是偏测试的，更希望去写代码来锻炼自己。另一方面，解决问题感觉啥事都要靠自己啊，别人还是不靠谱的，以后尽量能不问别人就别去问了，感觉自己都烦了，问了别人解决不了,浪费大家的时间最后还是要靠自己去解决。不爽。。。
环境：qt5
语言：c
代码：head_file：rb_func.h
1 #ifndef RB_MAIN 2 #define RB_MAIN 3 4 #define DEBUG 1 5 #define RED 1 6 #define BLACK 0 7 #define R RED 8 #define B BLACK 9 #define OK 0 10 #define ERR -1 11 12 #if 1 13 #define Left 1 14 #define Right -1 15 #endif 16 #ifndef NULL 17 #define NULL 0 18 #endif 19 #define PRINTTREEINIT(a)20 printf("------------------init Tree begin-------------\n");21 PrintBTree(a);22 printf("------------------init Tree end-------------\n"); 23 #define PRINTTREEAVL(a)24 printf("------------------AVL Tree begin-------------\n");25 PrintBTree(a);26 printf("------------------AVL Tree end-------------\n"); 27 28 #define PRINTTREEDEL(a)29 printf("------------------after del node Tree begin-------------\n");30 PrintBTree(a);31 printf("------------------after del nodeTree end-------------\n"); 32 33 #define PRINTTREEADJ(a)34 printf("------------------after adjust Tree begin-------------\n");35 PrintBTree(a);36 printf("------------------after adjust Tree end-------------\n"); 37 typedef int DATATYPE; 38 39 typedef struct treenode 40 { 41 DATATYPE data; 42 struct treenode *parent; 43 struct treenode *lchild; 44 struct treenode *rchild; 45 unsigned int color; 46 }TreeNode; 47 48 49 typedef TreeNode* RBTREE; 50 void PrintBTree(RBTREE* btree); 51 void PrintTreeNode(TreeNode* ); 52 void PrintViewTreeNode(TreeNode* treeNode, int num); 53 void PrintNTab(int i); 54 /* 55 TreeNode* InitRBTree(DATATYPE oriData[], int size); 56 */ 57 RBTREE* InitRBTree(DATATYPE oriData[], int size); 58 59 TreeNode *GetFixNode(RBTREE *pRBTree, DATATYPE data); 60 TreeNode * InitRootNode(DATATYPE data, TreeNode* pNewTreeNode); 61 TreeNode *InsertNode(TreeNode* pParNode, DATATYPE data); 62 int AdjustNode(TreeNode* pParNode, RBTREE* pRBTree); 63 int IsLChild(TreeNode* pSonNode); 64 TreeNode* Spinning(TreeNode *pCurNode,unsigned int iOp, RBTREE* pRBTree); 65 66 67 68 69 70 71 72 73 74 #endif // RB_MAIN
process_file:rb_func.c
1 #include "rb_func.h" 2 3 4 5 void PrintNTab(int num) 6 { 7 int i = 0; 8 9 while(i<num) 10 { 11 printf(" "); 12 i++; 13 } 14 } 15 16 void PrintViewTreeNode(TreeNode* treeNode, int num) 17 { 18 num++; 19 char cColor; 20 if(RED == treeNode->color ) cColor = ‘R‘; 21 if(BLACK == treeNode->color ) cColor = ‘B‘; 22 printf("%d %c", treeNode->data, cColor); 23 if(treeNode->lchild == NULL) 24 { 25 printf("\n"); 26 PrintNTab(num); 27 printf("*"); 28 } 29 else 30 { printf("\n"); 31 PrintNTab(num); 32 PrintViewTreeNode(treeNode->lchild, num); 33 } 34 if(treeNode->rchild == NULL) 35 { 36 printf("\n"); 37 PrintNTab(num); 38 printf("&"); 39 40 } 41 else 42 { 43 printf("\n"); 44 PrintNTab(num); 45 PrintViewTreeNode(treeNode->rchild, num); 46 47 } 48 49 50 } 51 52 /*这个看不出来树的结构了，需要重新写打印方法。*/ 53 void PrintTreeNode(TreeNode* treeNode) 54 { 55 if((treeNode->lchild == NULL) 56 &&(treeNode->rchild == NULL)) 57 { 58 printf("%d\n", treeNode->data); 59 } 60 else 61 { 62 if((treeNode->lchild != NULL) 63 || (treeNode->rchild != NULL)) 64 { 65 printf("%d ", treeNode->data); 66 if(treeNode->lchild != NULL) 67 { 68 printf("--->"); 69 PrintTreeNode(treeNode->lchild); 70 } 71 printf("%d ", treeNode->data); 72 if(treeNode->rchild != NULL) 73 { 74 printf("===>"); 75 PrintTreeNode(treeNode->rchild); 76 } 77 } 78 } 79 return ; 80 } 81 82 void PrintBTree(RBTREE* btree) 83 { 84 int num = 0; 85 if(btree==NULL) 86 { 87 printf("empty tree.\n"); 88 } 89 #if 0 90 printf("TreeView Rule---若一个节点有左右孩子节点,则父节点一行一列，左右孩子不同行同一列，若无做孩子，则打印的数据用*代替，如果无有孩子则打印的数据用&代替" 91 "另外树的层次用4个空格来体现，比如第1列代表第一层，第5列代表第二层。\n" 92 ); 93 #endif 94 printf("***********TREE View BEGIN***********\n"); 95 PrintViewTreeNode(*btree, num); 96 printf("\n"); 97 printf("***********TREE View END ***********\n"); 98 printf("\n"); 99 } 100 101 102 TreeNode * InitRootNode(DATATYPE data, TreeNode* pNewTreeNode) 103 { 104 pNewTreeNode->data =http://www.mamicode.com/ data; 105 pNewTreeNode->parent = NULL; 106 pNewTreeNode->lchild = NULL; 107 pNewTreeNode->rchild = NULL; 108 pNewTreeNode->color = B; 109 return pNewTreeNode; 110 } 111 112 113 //查找合适的位置来插入新元素(find parent) 114 TreeNode *GetFixNode(RBTREE *pRBTree, DATATYPE data) 115 { 116 if((pRBTree == NULL )) 117 { 118 return NULL; 119 } 120 121 if(((*pRBTree)->lchild == NULL) 122 &&((*pRBTree)->rchild == NULL)) 123 { 124 printf("insert under root \n"); 125 return *pRBTree; 126 } 127 TreeNode* pCurTreeNode = *pRBTree; 128 while( (pCurTreeNode->lchild != NULL) 129 ||(pCurTreeNode->rchild !=NULL) ) 130 { 131 if(data > pCurTreeNode->data) 132 { 133 //printf("insert R \n"); 134 printf(" data=http://www.mamicode.com/[%d] curData=[%d] insert R /n", data, pCurTreeNode->data); 135 if(pCurTreeNode->rchild != NULL) 136 { 137 printf("pCurTreeNode->rchild != NULL rchild[%d]\n", pCurTreeNode->rchild->data); 138 pCurTreeNode = pCurTreeNode->rchild; 139 140 }else{ 141 142 break; 143 } 144 } 145 else if(data < pCurTreeNode->data) 146 { 147 printf(" data=http://www.mamicode.com/[%d] curData=[%d] insert L /n", data, pCurTreeNode->data); 148 if(pCurTreeNode->lchild != NULL) 149 { 150 pCurTreeNode = pCurTreeNode->lchild; 151 }else{ 152 break; 153 } 154 } 155 else 156 { 157 printf("invaild elem here at line %d.\n", __LINE__); 158 return NULL; 159 } 160 } 161 return pCurTreeNode; 162 } 163 164 //将一个值插入节点的L/R子树上 165 TreeNode *InsertNode(TreeNode* pParNode, DATATYPE data) 166 { 167 #if DEBUG 168 /*这里要处理相等的情况*/ 169 if(data =http://www.mamicode.com/= pParNode->data) 170 { 171 printf("invaild data %d\n", data); 172 printf("invaild para here at line %d.\n", __LINE__); 173 return NULL; 174 } 175 #endif 176 TreeNode* pSonTreeNode = (TreeNode*)malloc(sizeof(TreeNode)); 177 pSonTreeNode->data =http://www.mamicode.com/ data; 178 pSonTreeNode->lchild = NULL; 179 pSonTreeNode->rchild = NULL; 180 pSonTreeNode->color = RED; 181 pSonTreeNode->parent = pParNode; 182 if(data < pParNode->data) 183 { 184 pParNode->lchild = pSonTreeNode; 185 } 186 else{ 187 pParNode->rchild = pSonTreeNode; 188 } 189 return pSonTreeNode; 190 } 191 TreeNode* Spinning(TreeNode *pCurNode,unsigned int iOp, RBTREE* pRBTree) 192 { 193 TreeNode *pLChild = NULL; 194 TreeNode *pRChild = NULL; 195 TreeNode *pParent = NULL; 196 197 //TreeNode *pA = NULL; 198 int iIsLChild = IsLChild(pCurNode); 199 if(NULL == pCurNode) return NULL; 200 if(Left == iOp) 201 { 202 //左旋 203 if(NULL == pCurNode->rchild) return NULL; 204 pLChild = pCurNode->rchild->lchild;/*z的左孩子*/ 205 pRChild = pCurNode->rchild; 206 if(-1 != iIsLChild){ 207 pParent = pCurNode->parent; 208 } 209 else 210 { 211 *pRBTree = pRChild; 212 } 213 if(NULL != pLChild) 214 { 215 pLChild->parent = pCurNode; 216 } 217 pCurNode->rchild = pLChild; 218 219 pRChild->lchild = pCurNode; 220 pCurNode->parent = pRChild; 221 222 pRChild->parent = pParent; 223 if(-1 != iIsLChild) 224 { 225 if(1 == iIsLChild) 226 { 227 pParent->lchild = pRChild; 228 } 229 else 230 { 231 pParent->rchild = pRChild; 232 } 233 } 234 return pRChild; 235 } 236 else if(Right == iOp) 237 { 238 //右旋 239 if(NULL == pCurNode->lchild) return NULL; 240 pRChild = pCurNode->lchild->rchild;/*z的左孩子*/ 241 pLChild = pCurNode->lchild; 242 if(-1 != iIsLChild){ 243 pParent = pCurNode->parent; 244 } 245 else 246 { 247 *pRBTree = pLChild; 248 } 249 if(NULL != pRChild) 250 { 251 pRChild->parent = pCurNode; 252 } 253 pCurNode->lchild = pRChild; 254 255 pLChild->rchild = pCurNode; 256 pCurNode->parent = pLChild; 257 258 pLChild->parent = pParent; 259 if(-1 != iIsLChild) 260 { 261 if(1 == iIsLChild) 262 { 263 pParent->lchild = pLChild; 264 } 265 else 266 { 267 pParent->rchild = pLChild; 268 } 269 } 270 return pLChild; 271 272 } 273 } 274 int AdjustNode(TreeNode* pCurNode, RBTREE* pRBTree) 275 { 276 if(NULL == pRBTree) goto err; 277 int LRFlag = 0; 278 int CurLRFlag = 0; 279 280 if(BLACK == pCurNode->parent->color) return OK; 281 unsigned int iCase = 0; 282 TreeNode *pParNode = pCurNode->parent; 283 LRFlag = IsLChild(pParNode); 284 CurLRFlag = IsLChild(pCurNode); 285 if(LRFlag) 286 { 287 /*tsb*/ 288 if((NULL != pParNode->parent->rchild)&& 289 (RED == pParNode->parent->rchild->color)) 290 { 291 iCase = 1; 292 }else 293 { 294 if(CurLRFlag) 295 { /*case 2:父节点是左孩子当前节点的父节点是红色,叔叔节点是黑色，当前节点是其父节点的左孩子； */ 296 /*cur in L*/ 297 iCase = 2; 298 299 } 300 else 301 { /*case 3:当前节点的父节点是红色,叔叔节点是黑色，当前节点是其父节点的右子； */ 302 iCase = 3; 303 } 304 305 } 306 /*tse*/ 307 #if 0 308 if(NULL != pParNode->parent->rchild) 309 { 310 if(//(RED == pParNode->color)&& 311 (RED == pParNode->parent->rchild->color)) 312 { /*case 1:父节点是左孩子 如果当前结点的父结点是红色且祖父结点的另一个子结点（叔叔结点）是红色； */ 313 iCase = 1; 314 } 315 else if(//(RED == pParNode->color)&& 316 (B == pParNode->parent->rchild->color)) 317 { 318 if(CurLRFlag) 319 { /*case 2:父节点是左孩子当前节点的父节点是红色,叔叔节点是黑色，当前节点是其父节点的左孩子； */ 320 /*cur in L*/ 321 iCase = 2; 322 323 } 324 else 325 { /*case 3:当前节点的父节点是红色,叔叔节点是黑色，当前节点是其父节点的右子； */ 326 iCase = 3; 327 } 328 } 329 } 330 else 331 { 332 if(CurLRFlag) 333 { /*case 2:父节点是左孩子当前节点的父节点是红色,叔叔节点是黑色，当前节点是其父节点的左孩子； */ 334 /*cur in L*/ 335 iCase = 2; 336 337 } 338 else 339 { /*case 3:当前节点的父节点是红色,叔叔节点是黑色，当前节点是其父节点的右子； */ 340 iCase = 3; 341 } 342 } 343 #endif 344 } 345 else 346 { 347 if(NULL != pParNode->parent->lchild) 348 { 349 if(//(RED == pParNode->color)&& 350 (RED == pParNode->parent->rchild->color)) 351 { /*case 1:父节点是R孩子 如果当前结点的父结点是红色且祖父结点的另一个子结点（叔叔结点）是红色； */ 352 iCase = 4; 353 } 354 else if(//(RED == pParNode->color)&& 355 (B == pParNode->parent->rchild->color)) 356 { 357 if(CurLRFlag) 358 { /*case 2:父节点是R孩子当前节点的父节点是红色,叔叔节点是黑色，当前节点是其父节点的左孩子； */ 359 /*cur in L*/ 360 iCase = 5; 361 } 362 else 363 { /*case 3:当前节点的父节点是红色,叔叔节点是黑色，当前节点是其父节点的右子； */ 364 iCase = 6; 365 } 366 } 367 } 368 else { 369 if(CurLRFlag) 370 { /*case 2:父节点是R孩子当前节点的父节点是红色,叔叔节点是黑色，当前节点是其父节点的左孩子； */ 371 /*cur in L*/ 372 iCase = 5; 373 } 374 else 375 { /*case 3:当前节点的父节点是红色,叔叔节点是黑色，当前节点是其父节点的右子； */ 376 iCase = 6; 377 } 378 } 379 } 380 381 switch (iCase) { 382 case 1: 383 pParNode->color = B; 384 pParNode->parent->rchild->color = B; 385 pParNode->parent->color = R; 386 387 pCurNode = pParNode->parent;/*this cur is Red*/ 388 if(pCurNode == *pRBTree) 389 {/*process the pCurNode is rootNode.*/ 390 pCurNode->color = BLACK; 391 }else 392 { 393 AdjustNode(pCurNode, pRBTree); 394 } 395 break; 396 case 2: 397 pParNode->color = B; 398 pParNode->parent->color = R; 399 pCurNode = Spinning(pParNode->parent,Right, pRBTree);/*this cur is Black*/ 400 401 break; 402 case 3: 403 pCurNode= pParNode; 404 pCurNode = Spinning(pCurNode,Left, pRBTree); 405 #if 0 406 pParNode = pCurNode; 407 pCurNode = pCurNode->lchild; 408 iCase = 2; 409 #endif 410 pCurNode = pCurNode->lchild; 411 AdjustNode(pCurNode, pRBTree); 412 413 414 break; 415 case 4: 416 pParNode->color = B; 417 pParNode->parent->lchild->color = B; 418 pParNode->parent->color = R; 419 pCurNode = pParNode->parent; 420 if(pCurNode == *pRBTree) 421 {/*process the pCurNode is rootNode.*/ 422 pCurNode->color = BLACK; 423 }else 424 { 425 AdjustNode(pCurNode, pRBTree); 426 } 427 break; 428 case 5: 429 430 pCurNode= pParNode; 431 pCurNode =Spinning(pCurNode,Right,pRBTree); 432 #if 0 433 pParNode = pCurNode; 434 pCurNode = pCurNode->rchild; 435 iCase = 6; 436 437 #endif 438 pCurNode = pCurNode->rchild; 439 AdjustNode(pCurNode, pRBTree); 440 441 break; 442 case 6: 443 pParNode->color = B; 444 pParNode->parent->color = R; 445 pCurNode = Spinning(pParNode->parent,Left, pRBTree); 446 447 break; 448 default: 449 goto err; 450 break; 451 } 452 return OK; 453 454 err: 455 printf("in para err.\n"); 456 return ERR; 457 458 } 459 /*1---------->is*/ 460 int IsLChild(TreeNode* pSonNode) 461 { 462 if(pSonNode->parent ==NULL)return -1; 463 return ((pSonNode->parent->lchild == pSonNode)?1:0); 464 } 465 466 /* 这个返回值不好，改掉哈哈 467 * TreeNode* InitRBTree(DATATYPE oriData[], int size) 468 */ 469 RBTREE* InitRBTree(DATATYPE oriData[], int size) 470 { 471 RBTREE* pRBTree = NULL; 472 pRBTree = (RBTREE*)malloc(sizeof(RBTREE)); 473 *pRBTree = (TreeNode*)malloc(sizeof(TreeNode)); 474 int pos = size; 475 int iRet = 0; 476 InitRootNode(oriData[0], *pRBTree); 477 TreeNode *pParentPosNode = NULL; 478 TreeNode *pCurNode = NULL; 479 480 while(pos>1) 481 { 482 #if DEBUG 483 printf("********begin one*************\n"); 484 printf("pos = [%d] index =[%d] insert_data[%d]\n", pos, size-pos+1, oriData[size-pos+1]); 485 #endif 486 pParentPosNode = GetFixNode(pRBTree, oriData[size-pos+1]); 487 #if DEBUG 488 printf("Parent = [%d] Insert data=http://www.mamicode.com/[%d] /n", pParentPosNode->data, oriData[size-pos+1] ); 489 #endif 490 pCurNode = InsertNode(pParentPosNode, oriData[size-pos+1]); 491 492 iRet = AdjustNode(pCurNode, pRBTree); 493 PrintBTree(pRBTree); 494 pos--; 495 #if DEBUG 496 printf("********end one*************\n\n"); 497 #endif 498 499 } 500 501 printf("********pRBTree data %d*************\n\n", (*pRBTree)->data); 502 503 return pRBTree; 504 505 }
main_file:main.c
1 #include <stdio.h> 2 #include "rb_func.h" 3 4 int testcase_1() 5 { 6 /* 7 * int iArr[]= {12,1,9,2,0,11,7}; 8 */ 9 int iArr[]= {12,1,9,2,0,11,7,19,4,15,18,5,14,13,10,16,6,3,8,17}; 10 11 #if 0 12 /*这里写的不好，initRBTree原先返回的是TreeNode* ,现在改为指向返回RBTREE*的指针*/ 13 RBTREE *avlTree = NULL; 14 TreeNode *rootNode = NULL; 15 rootNode= InitRBTree(iArr, sizeof(iArr)/sizeof(iArr[0])); 16 avlTree = (RBTREE*)malloc(sizeof(TreeNode*)); 17 *avlTree = (TreeNode*)malloc(sizeof(TreeNode)); 18 *avlTree = rootNode; 19 #endif 20 RBTREE *pRBTree = InitRBTree(iArr, sizeof(iArr)/sizeof(iArr[0])); 21 PRINTTREEINIT(pRBTree); 22 return 0; 23 } 24 int main(void) 25 { 26 testcase_1(); 27 return 0; 28 }
运行的demo数据（数组）是从一个网站上copy的，这里贴上我的运行结果：
1 ********begin one************* 2 pos = [20] index =[1] insert_data[1] 3 insert under root 4 Parent = [12] Insert data=http://www.mamicode.com/[1] 5 ***********TREE View BEGIN*********** 6 12 B 7 1 R 8 * 9 & 10 & 11 ***********TREE View END *********** 12 13 ********end one************* 14 15 ********begin one************* 16 pos = [19] index =[2] insert_data[9] 17 data=http://www.mamicode.com/[9] curData=http://www.mamicode.com/[12] insert L 18 Parent = [1] Insert data=http://www.mamicode.com/[9] 19 ***********TREE View BEGIN*********** 20 9 B 21 1 R 22 * 23 & 24 12 R 25 * 26 & 27 ***********TREE View END *********** 28 29 ********end one************* 30 31 ********begin one************* 32 pos = [18] index =[3] insert_data[2] 33 data=http://www.mamicode.com/[2] curData=http://www.mamicode.com/[9] insert L 34 Parent = [1] Insert data=http://www.mamicode.com/[2] 35 ***********TREE View BEGIN*********** 36 9 B 37 1 B 38 * 39 2 R 40 * 41 & 42 12 B 43 * 44 & 45 ***********TREE View END *********** 46 47 ********end one************* 48 49 ********begin one************* 50 pos = [17] index =[4] insert_data[0] 51 data=http://www.mamicode.com/[0] curData=http://www.mamicode.com/[9] insert L 52 data=http://www.mamicode.com/[0] curData=http://www.mamicode.com/[1] insert L 53 Parent = [1] Insert data=http://www.mamicode.com/[0] 54 ***********TREE View BEGIN*********** 55 9 B 56 1 B 57 0 R 58 * 59 & 60 2 R 61 * 62 & 63 12 B 64 * 65 & 66 ***********TREE View END *********** 67 68 ********end one************* 69 70 ********begin one************* 71 pos = [16] index =[5] insert_data[11] 72 data=http://www.mamicode.com/[11] curData=http://www.mamicode.com/[9] insert R 73 pCurTreeNode->rchild != NULL rchild[12] 74 Parent = [12] Insert data=http://www.mamicode.com/[11] 75 ***********TREE View BEGIN*********** 76 9 B 77 1 B 78 0 R 79 * 80 & 81 2 R 82 * 83 & 84 12 B 85 11 R 86 * 87 & 88 & 89 ***********TREE View END *********** 90 91 ********end one************* 92 93 ********begin one************* 94 pos = [15] index =[6] insert_data[7] 95 data=http://www.mamicode.com/[7] curData=http://www.mamicode.com/[9] insert L 96 data=http://www.mamicode.com/[7] curData=http://www.mamicode.com/[1] insert R 97 pCurTreeNode->rchild != NULL rchild[2] 98 Parent = [2] Insert data=http://www.mamicode.com/[7] 99 ***********TREE View BEGIN*********** 100 9 B 101 1 R 102 0 B 103 * 104 & 105 2 B 106 * 107 7 R 108 * 109 & 110 12 B 111 11 R 112 * 113 & 114 & 115 ***********TREE View END *********** 116 117 ********end one************* 118 119 ********begin one************* 120 pos = [14] index =[7] insert_data[19] 121 data=http://www.mamicode.com/[19] curData=http://www.mamicode.com/[9] insert R 122 pCurTreeNode->rchild != NULL rchild[12] 123 data=http://www.mamicode.com/[19] curData=http://www.mamicode.com/[12] insert R 124 Parent = [12] Insert data=http://www.mamicode.com/[19] 125 ***********TREE View BEGIN*********** 126 9 B 127 1 R 128 0 B 129 * 130 & 131 2 B 132 * 133 7 R 134 * 135 & 136 12 B 137 11 R 138 * 139 & 140 19 R 141 * 142 & 143 ***********TREE View END *********** 144 145 ********end one************* 146 147 ********begin one************* 148 pos = [13] index =[8] insert_data[4] 149 data=http://www.mamicode.com/[4] curData=http://www.mamicode.com/[9] insert L 150 data=http://www.mamicode.com/[4] curData=http://www.mamicode.com/[1] insert R 151 pCurTreeNode->rchild != NULL rchild[2] 152 data=http://www.mamicode.com/[4] curData=http://www.mamicode.com/[2] insert R 153 pCurTreeNode->rchild != NULL rchild[7] 154 Parent = [7] Insert data=http://www.mamicode.com/[4] 155 ***********TREE View BEGIN*********** 156 9 B 157 1 R 158 0 B 159 * 160 & 161 4 B 162 2 R 163 * 164 & 165 7 R 166 * 167 & 168 12 B 169 11 R 170 * 171 & 172 19 R 173 * 174 & 175 ***********TREE View END *********** 176 177 ********end one************* 178 179 ********begin one************* 180 pos = [12] index =[9] insert_data[15] 181 data=http://www.mamicode.com/[15] curData=http://www.mamicode.com/[9] insert R 182 pCurTreeNode->rchild != NULL rchild[12] 183 data=http://www.mamicode.com/[15] curData=http://www.mamicode.com/[12] insert R 184 pCurTreeNode->rchild != NULL rchild[19] 185 Parent = [19] Insert data=http://www.mamicode.com/[15] 186 ***********TREE View BEGIN*********** 187 9 B 188 1 R 189 0 B 190 * 191 & 192 4 B 193 2 R 194 * 195 & 196 7 R 197 * 198 & 199 12 R 200 11 B 201 * 202 & 203 19 B 204 15 R 205 * 206 & 207 & 208 ***********TREE View END *********** 209 210 ********end one************* 211 212 ********begin one************* 213 pos = [11] index =[10] insert_data[18] 214 data=http://www.mamicode.com/[18] curData=http://www.mamicode.com/[9] insert R 215 pCurTreeNode->rchild != NULL rchild[12] 216 data=http://www.mamicode.com/[18] curData=http://www.mamicode.com/[12] insert R 217 pCurTreeNode->rchild != NULL rchild[19] 218 data=http://www.mamicode.com/[18] curData=http://www.mamicode.com/[19] insert L 219 Parent = [15] Insert data=http://www.mamicode.com/[18] 220 ***********TREE View BEGIN*********** 221 9 B 222 1 R 223 0 B 224 * 225 & 226 4 B 227 2 R 228 * 229 & 230 7 R 231 * 232 & 233 12 R 234 11 B 235 * 236 & 237 18 B 238 15 R 239 * 240 & 241 19 R 242 * 243 & 244 ***********TREE View END *********** 245 246 ********end one************* 247 248 ********begin one************* 249 pos = [10] index =[11] insert_data[5] 250 data=http://www.mamicode.com/[5] curData=http://www.mamicode.com/[9] insert L 251 data=http://www.mamicode.com/[5] curData=http://www.mamicode.com/[1] insert R 252 pCurTreeNode->rchild != NULL rchild[4] 253 data=http://www.mamicode.com/[5] curData=http://www.mamicode.com/[4] insert R 254 pCurTreeNode->rchild != NULL rchild[7] 255 Parent = [7] Insert data=http://www.mamicode.com/[5] 256 ***********TREE View BEGIN*********** 257 9 B 258 1 B 259 0 B 260 * 261 & 262 4 R 263 2 B 264 * 265 & 266 7 B 267 5 R 268 * 269 & 270 & 271 12 B 272 11 B 273 * 274 & 275 18 B 276 15 R 277 * 278 & 279 19 R 280 * 281 & 282 ***********TREE View END *********** 283 284 ********end one************* 285 286 ********begin one************* 287 pos = [9] index =[12] insert_data[14] 288 data=http://www.mamicode.com/[14] curData=http://www.mamicode.com/[9] insert R 289 pCurTreeNode->rchild != NULL rchild[12] 290 data=http://www.mamicode.com/[14] curData=http://www.mamicode.com/[12] insert R 291 pCurTreeNode->rchild != NULL rchild[18] 292 data=http://www.mamicode.com/[14] curData=http://www.mamicode.com/[18] insert L 293 Parent = [15] Insert data=http://www.mamicode.com/[14] 294 ***********TREE View BEGIN*********** 295 9 B 296 1 B 297 0 B 298 * 299 & 300 4 R 301 2 B 302 * 303 & 304 7 B 305 5 R 306 * 307 & 308 & 309 12 B 310 11 B 311 * 312 & 313 18 R 314 15 B 315 14 R 316 * 317 & 318 & 319 19 B 320 * 321 & 322 ***********TREE View END *********** 323 324 ********end one************* 325 326 ********begin one************* 327 pos = [8] index =[13] insert_data[13] 328 data=http://www.mamicode.com/[13] curData=http://www.mamicode.com/[9] insert R 329 pCurTreeNode->rchild != NULL rchild[12] 330 data=http://www.mamicode.com/[13] curData=http://www.mamicode.com/[12] insert R 331 pCurTreeNode->rchild != NULL rchild[18] 332 data=http://www.mamicode.com/[13] curData=http://www.mamicode.com/[18] insert L 333 data=http://www.mamicode.com/[13] curData=http://www.mamicode.com/[15] insert L 334 Parent = [14] Insert data=http://www.mamicode.com/[13] 335 ***********TREE View BEGIN*********** 336 9 B 337 1 B 338 0 B 339 * 340 & 341 4 R 342 2 B 343 * 344 & 345 7 B 346 5 R 347 * 348 & 349 & 350 12 B 351 11 B 352 * 353 & 354 18 R 355 14 B 356 13 R 357 * 358 & 359 15 R 360 * 361 & 362 19 B 363 * 364 & 365 ***********TREE View END *********** 366 367 ********end one************* 368 369 ********begin one************* 370 pos = [7] index =[14] insert_data[10] 371 data=http://www.mamicode.com/[10] curData=http://www.mamicode.com/[9] insert R 372 pCurTreeNode->rchild != NULL rchild[12] 373 data=http://www.mamicode.com/[10] curData=http://www.mamicode.com/[12] insert L 374 Parent = [11] Insert data=http://www.mamicode.com/[10] 375 ***********TREE View BEGIN*********** 376 9 B 377 1 B 378 0 B 379 * 380 & 381 4 R 382 2 B 383 * 384 & 385 7 B 386 5 R 387 * 388 & 389 & 390 12 B 391 11 B 392 10 R 393 * 394 & 395 & 396 18 R 397 14 B 398 13 R 399 * 400 & 401 15 R 402 * 403 & 404 19 B 405 * 406 & 407 ***********TREE View END *********** 408 409 ********end one************* 410 411 ********begin one************* 412 pos = [6] index =[15] insert_data[16] 413 data=http://www.mamicode.com/[16] curData=http://www.mamicode.com/[9] insert R 414 pCurTreeNode->rchild != NULL rchild[12] 415 data=http://www.mamicode.com/[16] curData=http://www.mamicode.com/[12] insert R 416 pCurTreeNode->rchild != NULL rchild[18] 417 data=http://www.mamicode.com/[16] curData=http://www.mamicode.com/[18] insert L 418 data=http://www.mamicode.com/[16] curData=http://www.mamicode.com/[14] insert R 419 pCurTreeNode->rchild != NULL rchild[15] 420 Parent = [15] Insert data=http://www.mamicode.com/[16] 421 ***********TREE View BEGIN*********** 422 9 B 423 1 B 424 0 B 425 * 426 & 427 4 R 428 2 B 429 * 430 & 431 7 B 432 5 R 433 * 434 & 435 & 436 12 R 437 11 B 438 10 R 439 * 440 & 441 & 442 18 B 443 14 R 444 13 B 445 * 446 & 447 15 B 448 * 449 16 R 450 * 451 & 452 19 B 453 * 454 & 455 ***********TREE View END *********** 456 457 ********end one************* 458 459 ********begin one************* 460 pos = [5] index =[16] insert_data[6] 461 data=http://www.mamicode.com/[6] curData=http://www.mamicode.com/[9] insert L 462 data=http://www.mamicode.com/[6] curData=http://www.mamicode.com/[1] insert R 463 pCurTreeNode->rchild != NULL rchild[4] 464 data=http://www.mamicode.com/[6] curData=http://www.mamicode.com/[4] insert R 465 pCurTreeNode->rchild != NULL rchild[7] 466 data=http://www.mamicode.com/[6] curData=http://www.mamicode.com/[7] insert L 467 Parent = [5] Insert data=http://www.mamicode.com/[6] 468 ***********TREE View BEGIN*********** 469 9 B 470 1 B 471 0 B 472 * 473 & 474 4 R 475 2 B 476 * 477 & 478 6 B 479 5 R 480 * 481 & 482 7 R 483 * 484 & 485 12 R 486 11 B 487 10 R 488 * 489 & 490 & 491 18 B 492 14 R 493 13 B 494 * 495 & 496 15 B 497 * 498 16 R 499 * 500 & 501 19 B 502 * 503 & 504 ***********TREE View END *********** 505 506 ********end one************* 507 508 ********begin one************* 509 pos = [4] index =[17] insert_data[3] 510 data=http://www.mamicode.com/[3] curData=http://www.mamicode.com/[9] insert L 511 data=http://www.mamicode.com/[3] curData=http://www.mamicode.com/[1] insert R 512 pCurTreeNode->rchild != NULL rchild[4] 513 data=http://www.mamicode.com/[3] curData=http://www.mamicode.com/[4] insert L 514 Parent = [2] Insert data=http://www.mamicode.com/[3] 515 ***********TREE View BEGIN*********** 516 9 B 517 1 B 518 0 B 519 * 520 & 521 4 R 522 2 B 523 * 524 3 R 525 * 526 & 527 6 B 528 5 R 529 * 530 & 531 7 R 532 * 533 & 534 12 R 535 11 B 536 10 R 537 * 538 & 539 & 540 18 B 541 14 R 542 13 B 543 * 544 & 545 15 B 546 * 547 16 R 548 * 549 & 550 19 B 551 * 552 & 553 ***********TREE View END *********** 554 555 ********end one************* 556 557 ********begin one************* 558 pos = [3] index =[18] insert_data[8] 559 data=http://www.mamicode.com/[8] curData=http://www.mamicode.com/[9] insert L 560 data=http://www.mamicode.com/[8] curData=http://www.mamicode.com/[1] insert R 561 pCurTreeNode->rchild != NULL rchild[4] 562 data=http://www.mamicode.com/[8] curData=http://www.mamicode.com/[4] insert R 563 pCurTreeNode->rchild != NULL rchild[6] 564 data=http://www.mamicode.com/[8] curData=http://www.mamicode.com/[6] insert R 565 pCurTreeNode->rchild != NULL rchild[7] 566 Parent = [7] Insert data=http://www.mamicode.com/[8] 567 ***********TREE View BEGIN*********** 568 9 B 569 1 R 570 0 B 571 * 572 & 573 4 B 574 2 B 575 * 576 3 R 577 * 578 & 579 6 R 580 5 B 581 * 582 & 583 7 B 584 * 585 8 R 586 * 587 & 588 12 R 589 11 B 590 10 R 591 * 592 & 593 & 594 18 B 595 14 R 596 13 B 597 * 598 & 599 15 B 600 * 601 16 R 602 * 603 & 604 19 B 605 * 606 & 607 ***********TREE View END *********** 608 609 ********end one************* 610 611 ********begin one************* 612 pos = [2] index =[19] insert_data[17] 613 data=http://www.mamicode.com/[17] curData=http://www.mamicode.com/[9] insert R 614 pCurTreeNode->rchild != NULL rchild[12] 615 data=http://www.mamicode.com/[17] curData=http://www.mamicode.com/[12] insert R 616 pCurTreeNode->rchild != NULL rchild[18] 617 data=http://www.mamicode.com/[17] curData=http://www.mamicode.com/[18] insert L 618 data=http://www.mamicode.com/[17] curData=http://www.mamicode.com/[14] insert R 619 pCurTreeNode->rchild != NULL rchild[15] 620 data=http://www.mamicode.com/[17] curData=http://www.mamicode.com/[15] insert R 621 pCurTreeNode->rchild != NULL rchild[16] 622 Parent = [16] Insert data=http://www.mamicode.com/[17] 623 ***********TREE View BEGIN*********** 624 9 B 625 1 R 626 0 B 627 * 628 & 629 4 B 630 2 B 631 * 632 3 R 633 * 634 & 635 6 R 636 5 B 637 * 638 & 639 7 B 640 * 641 8 R 642 * 643 & 644 12 R 645 11 B 646 10 R 647 * 648 & 649 & 650 18 B 651 14 R 652 13 B 653 * 654 & 655 16 B 656 15 R 657 * 658 & 659 17 R 660 * 661 & 662 19 B 663 * 664 & 665 ***********TREE View END *********** 666 667 ********end one************* 668 669 ********pRBTree data 9************* 670 671 ------------------init Tree begin------------- 672 ***********TREE View BEGIN*********** 673 9 B 674 1 R 675 0 B 676 * 677 & 678 4 B 679 2 B 680 * 681 3 R 682 * 683 & 684 6 R 685 5 B 686 * 687 & 688 7 B 689 * 690 8 R 691 * 692 & 693 12 R 694 11 B 695 10 R 696 * 697 & 698 & 699 18 B 700 14 R 701 13 B 702 * 703 & 704 16 B 705 15 R 706 * 707 & 708 17 R 709 * 710 & 711 19 B 712 * 713 & 714 ***********TREE View END *********** 715 716 ------------------init Tree end-------------
删除节点估计要等光棍节后才能写。o(^▽^)o
红黑树(RBTREE)之上-------构造红黑树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。