首页 > 代码库 > 平衡二叉树(AVLTREE,双链表实现)
平衡二叉树(AVLTREE,双链表实现)
首先说下好久没更新了，最近打游戏和工作都有点多，o(^▽^)o。
写这个AVL发现自己的代码风格好差，尤其是变量命名这块，后来意识到了，想去改，但是太多了，改了几个就不想改了，做这个是记录下自己的成长吧。
另外说下，调这个AVL真心有点烦了，前面写了一个，但是逻辑有点乱，基本的删除都测差不多ok了，发现一个bug，实在不想去看那代码，太乱了，后来强b这自己去重新写，花了1个多小时（当然是加班的时候理），理清了，晚上9点多回来，大概3个小时，把del这块从新改完了，写代码真的是一个时候一个思想，发现处理节点只有单个分支的时候，还是第一次的思想好，直接指针操作一下，逻辑很精简，具体可以看code708的那2段逻辑处理，在处理删除节点有2个孩子节点时，在思考用指针直接处理，还是用一个临时变量来操作，最后选择了临时变量节点来处理，具体为什么，因为简单，而且仔细想了想这样处理是没错的，node里data基本只是一个keyValue，用在avl里查找，删除，构造做参考的，这个地方也有考虑用指针，也实现了，基本没多大问题，后来出bug的时候在那理了半天，实在受不了，把他改造了。
另外printAVL的函数直接copy BTree的，这个没什么好说的，还有AVL查找，这个真的不用我写了。本文主要就实现任意的一个数组构造AVLTree，删除AVLTree的任意个节点，保证AVLTree的特性。
具体贴代码，如下，测试的例子，都ok的，具体的放开，还有千万一定要吐槽我的变量命名及注释及很多，我在改，下次写的时候一定注意。
/*运行环境QT C */
1 #include <stdio.h> 2 #define DEBUG 0 3 //参考图http://www.cnblogs.com/skywang12345/p/3577360.html 4 #define PRINTTREEINIT(a) 5 printf("------------------init Tree begin-------------\n"); 6 PrintBTree(a); 7 printf("------------------init Tree end-------------\n"); 8 #define PRINTTREEAVL(a) 9 printf("------------------AVL Tree begin-------------\n"); 10 PrintBTree(a); 11 printf("------------------AVL Tree end-------------\n"); 12 13 #define PRINTTREEDEL(a) 14 printf("------------------after del node Tree begin-------------\n"); 15 PrintBTree(a); 16 printf("------------------after del nodeTree end-------------\n"); 17 18 #define PRINTTREEADJ(a) 19 printf("------------------after adjust Tree begin-------------\n"); 20 PrintBTree(a); 21 printf("------------------after adjust Tree end-------------\n"); 22 #define L 1 23 #define R -1 24 #define BTREE AVLTree 25 typedef struct treenode 26 { 27 int data; 28 int hight; 29 struct treenode *parent; 30 struct treenode *lchild; 31 struct treenode *rchild; 32 } TreeNode; 33 typedef enum {LL=0,LR,RR,RL,RLR} TURNFLAG; 34 typedef TreeNode* AVLTree; 35 typedef int DATATYPE; 36 int IsLeafNode(TreeNode* Node); 37 //void DeleteNode(AVLTree* btree, DATATYPE delData); 38 void DeleteNode(AVLTree* btree, DATATYPE delData); 39 40 TreeNode* InitNode(int data); 41 void InitAVLTree(AVLTree *avlTree, TreeNode *root); 42 43 TreeNode *GetFixNode(AVLTree *btree, DATATYPE data); 44 int GetTreeHight(AVLTree *btree); 45 TreeNode *InsertNode(TreeNode* parNode, DATATYPE data); 46 int GetDiffHeight(TreeNode* rootNode); 47 int AdjustNode(TreeNode* posNode, AVLTree *avlTree); 48 int GetSymDiffHeight(TreeNode* rootNode); 49 int IsRoot(TreeNode* rootNode); 50 int IsLChild(TreeNode* rootNode); 51 TreeNode *GetMaxNode(TreeNode* rootNode); 52 TreeNode *GetMinNode(TreeNode* rootNode); 53 TreeNode* AdjustNodeByTurnFlag(TreeNode** Node,TURNFLAG a, AVLTree *avlTree); 54 void PrintNTab(int num); 55 void PrintBTree(BTREE* btree); 56 void PrintViewTreeNode(TreeNode* treeNode, int num); 57 TreeNode* GetPosByKeyValue(TreeNode* rootNode,int key); 58 int GetChildNum(TreeNode* rootNode); 59 int GetChildNum(TreeNode* curNode) 60 { 61 if((NULL != curNode->lchild)&&(NULL != curNode->rchild)) return 2; 62 if((NULL != curNode->lchild)&&(NULL == curNode->rchild)) return 1; 63 if((NULL == curNode->lchild)&&(NULL != curNode->rchild)) return -1; 64 if((NULL == curNode->lchild)&&(NULL == curNode->rchild)) return 0; 65 66 } 67 TreeNode *GetMaxNode(TreeNode* rootNode) 68 { 69 if(rootNode == NULL) return NULL; 70 if(NULL == rootNode->rchild) return rootNode; 71 TreeNode *curNode = rootNode; 72 while((NULL != curNode)&&(NULL != curNode->rchild)) 73 { 74 curNode = curNode->rchild; 75 } 76 return curNode; 77 } 78 79 TreeNode *GetMinNode(TreeNode* rootNode) 80 { 81 if(rootNode == NULL) return NULL; 82 if(NULL == rootNode->lchild) return rootNode; 83 TreeNode *curNode = rootNode; 84 while((NULL != curNode)&&(NULL != curNode->lchild)) 85 { 86 curNode = curNode->lchild; 87 } 88 return curNode; 89 } 90 91 TreeNode* GetPosByKeyValue(TreeNode* rootNode,int data) 92 { 93 if(rootNode == NULL) return NULL; 94 if(data =http://www.mamicode.com/= rootNode->data) return rootNode; 95 96 97 TreeNode* curTreeNode = rootNode; 98 99 while( NULL != curTreeNode ) 100 { 101 if(data > curTreeNode->data) 102 { 103 if(curTreeNode->rchild != NULL) 104 { 105 //printf("curTreeNode->rchild != NULL rchild[%d]\n", curTreeNode->rchild->data); 106 curTreeNode = curTreeNode->rchild; 107 }else{ 108 curTreeNode = NULL; 109 break; 110 } 111 } 112 else if(data < curTreeNode->data) 113 { 114 if(curTreeNode->lchild != NULL) 115 { 116 curTreeNode = curTreeNode->lchild; 117 }else{ 118 curTreeNode = NULL; 119 break; 120 } 121 } 122 else 123 { 124 printf("find key.\n", __LINE__); 125 return curTreeNode; 126 } 127 128 } 129 if(NULL == curTreeNode) 130 { 131 printf("Not find key.\n", __LINE__); 132 return curTreeNode; 133 } 134 135 } 136 void PrintViewTreeNode(TreeNode* treeNode, int num) 137 { 138 if(NULL == treeNode) return ; 139 num++; 140 printf("%d", treeNode->data); 141 if(treeNode->lchild == NULL) 142 { 143 printf("\n"); 144 PrintNTab(num); 145 printf("*"); 146 } 147 else 148 { printf("\n"); 149 PrintNTab(num); 150 PrintViewTreeNode(treeNode->lchild, num); 151 } 152 if(treeNode->rchild == NULL) 153 { 154 printf("\n"); 155 PrintNTab(num); 156 printf("&"); 157 158 } 159 else 160 { 161 printf("\n"); 162 PrintNTab(num); 163 PrintViewTreeNode(treeNode->rchild, num); 164 165 } 166 167 168 } 169 void PrintBTree(BTREE* btree) 170 { 171 int num = 0; 172 if(btree==NULL) 173 { 174 printf("empty tree.\n"); 175 } 176 177 printf("***********TREE View BEGIN***********\n"); 178 //PrintTreeNode((*btree)); 179 PrintViewTreeNode(*btree, num); 180 printf("\n"); 181 printf("***********TREE View END ***********\n"); 182 printf("\n"); 183 184 printf("\n"); 185 186 187 } 188 void PrintNTab(int num) 189 { 190 int i = 0; 191 192 while(i<num) 193 { 194 printf(" "); 195 i++; 196 } 197 } 198 TreeNode* AdjustNodeByTurnFlag(TreeNode** node,TURNFLAG tFlag,AVLTree *avlTree) 199 {//* > ->优先级 200 TreeNode* nodeTmp = (TreeNode* )malloc(sizeof(TreeNode)); 201 TreeNode* freeNode = NULL; 202 int isRootNode = 0; 203 int sdh = 0; 204 int iRet = 0; 205 memset(nodeTmp, 0x00, sizeof(TreeNode)); 206 if(((tFlag>3) ||(tFlag <0)|| ((*node)==NULL))) return NULL; 207 switch (tFlag){ 208 case LL: 209 freeNode = *node; 210 memcpy(nodeTmp,(*node)->lchild,sizeof(TreeNode)); 211 *node = (*node)->lchild; 212 213 (*node)->parent = nodeTmp->parent; 214 iRet = IsLChild(freeNode); 215 if(iRet == -1) 216 { 217 //root 218 isRootNode = 1; 219 } 220 else if(1 == iRet) 221 { 222 //isLchild 223 freeNode->parent->lchild = *node; 224 } 225 else if(0 == iRet) 226 { 227 //isRchild 228 freeNode->parent->rchild = *node; 229 } 230 231 (*node)->rchild = freeNode; 232 freeNode->parent = *node; 233 234 freeNode->lchild = nodeTmp->rchild; 235 if(NULL != nodeTmp->rchild) 236 { 237 freeNode->lchild->parent = freeNode; 238 } 239 if(isRootNode) 240 { 241 *avlTree = *node; 242 } 243 free(nodeTmp); 244 break; 245 case LR: 246 freeNode = *node; 247 memcpy(nodeTmp,(*node)->lchild->rchild,sizeof(TreeNode)); 248 *node = (*node)->lchild->rchild; 249 (*node)->parent = freeNode->parent; 250 iRet = IsLChild(freeNode); 251 if(iRet == -1) 252 { 253 //root 254 isRootNode = 1; 255 } 256 else if(1 == iRet) 257 { 258 //isLchild 259 freeNode->parent->lchild = *node; 260 } 261 else if(0 == iRet) 262 { 263 //isRchild 264 freeNode->parent->rchild = *node; 265 266 } 267 (*node)->lchild = freeNode->lchild; 268 freeNode->lchild->parent = *(node); 269 freeNode->lchild->rchild = NULL; 270 freeNode->lchild = NULL; 271 272 (*node)->rchild = freeNode; 273 freeNode->parent = *(node); 274 275 freeNode->lchild = nodeTmp->rchild; 276 (*node)->lchild->rchild = nodeTmp->lchild; 277 if(NULL != nodeTmp->rchild) 278 { 279 nodeTmp->rchild->parent = freeNode; 280 } 281 if(NULL != nodeTmp->lchild) 282 { 283 nodeTmp->lchild->parent = (*node)->lchild; 284 } 285 286 if(isRootNode) 287 { 288 *avlTree = *node; 289 } 290 free(nodeTmp); 291 break; 292 293 case RR: 294 //直接改变指针，所以入参是二级指针 295 freeNode = *node; 296 memcpy(nodeTmp,*node,sizeof(TreeNode)); 297 *node=(*node)->rchild; 298 299 if(nodeTmp->parent != NULL) 300 { 301 if(IsLChild(nodeTmp)){nodeTmp->parent->lchild = *node;} 302 else {nodeTmp->parent->rchild = *node;} 303 } 304 else 305 { 306 //说明nodeTmp是根节点，要改变树的节点 307 isRootNode = 1; 308 } 309 310 if((*node)->lchild){ 311 nodeTmp->rchild = (*node)->lchild; 312 (*node)->lchild->parent = nodeTmp; 313 } 314 (*node)->parent = nodeTmp->parent; 315 (*node)->lchild = nodeTmp; 316 nodeTmp->parent = *node; 317 if(isRootNode) 318 { 319 *avlTree = *node; 320 } 321 free(freeNode); 322 //树的根节点被改了,这里要注意，刚好玩玩二级指针 323 break; 324 case RL: 325 freeNode = *node; 326 memcpy(nodeTmp,(*node)->rchild->lchild,sizeof(TreeNode)); 327 *node = (*node)->rchild->lchild; 328 (*node)->parent = freeNode->parent; 329 iRet = IsLChild(freeNode); 330 if(iRet == -1) 331 { 332 //root 333 isRootNode = 1; 334 } 335 else if(1 == iRet) 336 { 337 //isLchild 338 freeNode->parent->lchild = *node; 339 } 340 else if(0 == iRet) 341 { 342 //isRchild 343 freeNode->parent->rchild = *node; 344 345 } 346 (*node)->rchild = freeNode->rchild; 347 freeNode->rchild->parent = *(node); 348 freeNode->rchild->lchild = NULL; 349 freeNode->rchild = NULL; 350 351 (*node)->lchild = freeNode; 352 freeNode->parent = *(node); 353 354 freeNode->rchild = nodeTmp->lchild; 355 (*node)->rchild->lchild = nodeTmp->rchild; 356 if(NULL != nodeTmp->lchild) 357 { 358 nodeTmp->lchild->parent = freeNode; 359 } 360 if(NULL != nodeTmp->rchild) 361 { 362 nodeTmp->rchild->parent = (*node)->rchild; 363 } 364 365 if(isRootNode) 366 { 367 *avlTree = *node; 368 } 369 free(nodeTmp); 370 break; 371 default: 372 break; 373 } 374 return *node; 375 376 } 377 378 //1->is 379 int IsLChild(TreeNode* sonNode) 380 { 381 if(sonNode->parent ==NULL)return -1; 382 return ((sonNode->parent->lchild == sonNode)?1:0); 383 } 384 385 386 //1->is 387 int IsRoot(TreeNode* rootNode) 388 { 389 return(rootNode->parent == NULL); 390 } 391 int GetDiffHeight(TreeNode* rootNode) 392 { 393 394 int lh=GetTreeHight((AVLTree*)&(rootNode->lchild));//L 395 int rh=GetTreeHight((AVLTree*)&(rootNode->rchild));//R 396 return ((lh>rh)?(lh-rh):(rh-lh)); 397 } 398 399 int GetSymDiffHeight(TreeNode* rootNode) 400 { 401 int lh=GetTreeHight((AVLTree*)&(rootNode->lchild));//L 402 int rh=GetTreeHight((AVLTree*)&(rootNode->rchild));//L 403 return (lh-rh); 404 } 405 406 int AdjustNode(TreeNode* posNode, AVLTree* avlTree) 407 {//这个函数写的有点问题，如果传入的posNode dh = 2时候，而起父节点平衡了，就会少调整一部分，所以入posNode尽量用son 408 int dh = GetDiffHeight(posNode); 409 int sdh = 0; 410 int sSondh = 0; 411 if(0== dh)return 0; 412 if(2 == dh) 413 { 414 //这个地方后补上去的，感觉这个AVL树写的到处是漏洞啊汗 415 if(NULL != posNode->lchild) 416 { 417 posNode = posNode->lchild; 418 } 419 else if(NULL != posNode->rchild) 420 { 421 posNode = posNode->rchild; 422 } 423 } 424 425 TreeNode *parNode = posNode->parent; 426 if(NULL == parNode ) return 0; 427 dh = GetDiffHeight(parNode); 428 //l-r =0 429 while(parNode&&dh) 430 { 431 if(2==dh) 432 { 433 sdh = GetSymDiffHeight(parNode); 434 if(-2 == sdh) 435 { 436 //in RL 437 sSondh = GetSymDiffHeight((parNode->rchild)); 438 if(1==sSondh) 439 { 440 //RL 441 AdjustNodeByTurnFlag(&parNode,RL,avlTree); 442 PrintBTree(avlTree); 443 } 444 else 445 { 446 //RR 447 AdjustNodeByTurnFlag(&parNode,RR,avlTree); 448 } 449 } 450 else 451 { 452 //in L 453 sSondh = GetSymDiffHeight(parNode->lchild); 454 if(1==sSondh) 455 { 456 //LL 457 AdjustNodeByTurnFlag(&parNode,LL,avlTree); 458 } 459 else 460 { 461 //LR 462 AdjustNodeByTurnFlag(&parNode,LR,avlTree); 463 } 464 } 465 break; 466 } 467 parNode = parNode->parent; 468 if(parNode != NULL) 469 { 470 dh = GetDiffHeight(parNode); 471 472 } 473 } 474 475 } 476 TreeNode *InsertNode(TreeNode* parNode, DATATYPE data) 477 { 478 TreeNode* sonTreeNode = InitNode(data); 479 if((parNode->lchild != NULL)&&(parNode->rchild == NULL)) parNode->rchild = sonTreeNode; 480 if((parNode->rchild != NULL)&&(parNode->lchild == NULL)) parNode->lchild = sonTreeNode; 481 if((parNode->rchild == NULL)&&(parNode->lchild == NULL)) 482 { 483 if(data < parNode->data) 484 { 485 parNode->lchild = sonTreeNode; 486 } 487 else{ 488 parNode->rchild = sonTreeNode; 489 490 } 491 } 492 sonTreeNode->parent = parNode; 493 494 return sonTreeNode; 495 496 } 497 498 int IsLeafNode(TreeNode* Node) 499 { 500 return ((Node->lchild == NULL)&&(Node->rchild == NULL)); 501 } 502 503 int GetTreeHight(AVLTree *btree) 504 {//这里后来处理，空树的高度是0，根节点的高度1 505 TreeNode*curNode = *btree; 506 if((curNode ==NULL)) return 0; 507 if(IsLeafNode(curNode)) return 1; 508 509 510 if(((curNode->lchild != NULL)&&(curNode->rchild ==NULL)&&IsLeafNode(curNode->lchild)) 511 ||((curNode->lchild == NULL)&&(curNode->rchild !=NULL)&&IsLeafNode(curNode->rchild)) 512 ||((curNode->lchild != NULL)&&(curNode->rchild !=NULL)&&IsLeafNode(curNode->rchild)&&IsLeafNode(curNode->lchild)) 513 ) 514 return 2; 515 int leftHeight = GetTreeHight((AVLTree*)&((*btree)->lchild)); 516 int rightHeight = GetTreeHight((AVLTree*)&((*btree)->rchild)); 517 return ((leftHeight>rightHeight)?leftHeight:rightHeight)+1; 518 519 } 520 TreeNode* InitNode(int data) 521 { 522 TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode)); 523 memset(newNode, 0x00, sizeof(TreeNode)); 524 newNode->data =http://www.mamicode.com/ data; 525 newNode->hight = 0; 526 return newNode; 527 } 528 //return rootNode addr 529 void InitAVLTree(AVLTree *avlTree, TreeNode *root) 530 { 531 *avlTree = root; 532 } 533 534 //查找合适的位置来插入新元素(find parent) 535 TreeNode* GetFixNode(AVLTree *AVLTree, DATATYPE data) 536 { 537 if((AVLTree == NULL )) 538 { 539 return NULL; 540 } 541 542 if(((*AVLTree)->lchild == NULL) 543 &&((*AVLTree)->rchild == NULL)) 544 { 545 //InsertNode(*AVLTree ,data); 546 #if DEBUG 547 printf("insert under root \n"); 548 #endif 549 return *AVLTree; 550 } 551 TreeNode* curTreeNode = (TreeNode*)malloc(sizeof(TreeNode)); 552 curTreeNode = *AVLTree; 553 while( (curTreeNode->lchild != NULL) 554 ||(curTreeNode->rchild !=NULL) ) 555 { 556 if(data > curTreeNode->data) 557 { 558 #if DEBUG 559 printf(" data=http://www.mamicode.com/[%d] curData=[%d] insert R /n", data, curTreeNode->data); 560 #endif 561 if(curTreeNode->rchild != NULL) 562 { 563 #if DEBUG 564 printf("curTreeNode->rchild != NULL rchild[%d]\n", curTreeNode->rchild->data); 565 #endif 566 curTreeNode = curTreeNode->rchild; 567 568 }else{ 569 570 break; 571 } 572 } 573 else if(data < curTreeNode->data) 574 { 575 #if DEBUG 576 printf(" data=http://www.mamicode.com/[%d] curData=[%d] insert L /n", data, curTreeNode->data); 577 #endif 578 if(curTreeNode->lchild != NULL) 579 { 580 curTreeNode = curTreeNode->lchild; 581 }else{ 582 583 break; 584 } 585 } 586 else 587 { 588 printf("invaild elem here at line %d.\n", __LINE__); 589 return NULL; 590 } 591 592 } 593 return curTreeNode; 594 595 } 596 597 //contruct tree 598 AVLTree* InitBTree(DATATYPE oriData[], int size) 599 { 600 int iRet = -1; 601 AVLTree* avlTree = NULL; 602 avlTree = (AVLTree*)malloc(sizeof(AVLTree)); 603 //*avlTree = (TreeNode*)malloc(sizeof(TreeNode)); 604 int pos = size; 605 TreeNode* rootNode = InitNode(oriData[0]); 606 InitAVLTree(avlTree, rootNode); 607 608 TreeNode *posNode = (TreeNode*)malloc(sizeof(TreeNode)); 609 while(pos>1) 610 { 611 #if DEBUG 612 printf("********begin one*************\n"); 613 printf("pos = [%d] index =[%d] data[%d]\n", pos, size-pos+1, oriData[size-pos+1]); 614 #endif 615 posNode = GetFixNode(avlTree, oriData[size-pos+1]); 616 #if DEBUG 617 printf("Parent = [%d] Insert data=http://www.mamicode.com/[%d] /n", posNode->data, oriData[size-pos+1] ); 618 #endif 619 InsertNode(posNode, oriData[size-pos+1]); 620 //judge and confit 621 //PrintBTree(avlTree); 622 623 iRet = AdjustNode(posNode, avlTree); 624 pos--; 625 #if DEBUG 626 printf("********end one*************\n\n"); 627 #endif 628 //PrintBTree(avlTree); 629 630 631 } 632 //PrintBTree(avlTree); 633 return avlTree; 634 635 } 636 637 638 void DeleteNode(AVLTree* avlTree, DATATYPE delKey) 639 { 640 TreeNode* posNode = GetPosByKeyValue(*avlTree,delKey); 641 int iIsRootNode = 0; 642 int iIsLchlid = 0; 643 644 int iHight = 0; /*处理传入节点in，freeNode 是 in的直接孩子节点情况，这个最早写的时候考虑不周*/ 645 646 if(posNode == *avlTree) 647 { 648 printf("del root node\n"); 649 iIsRootNode = 1; 650 } 651 /*看到定义的变量没用，感觉好恶心*/ 652 //TreeNode* parNode = NULL;//这个是临时变量，后面写，发现定义parnode是错的，应该定义tmpNode 653 TreeNode* freeNode = NULL;//这个是临时变量，后面写 ，应该定义tmpNode 654 //TreeNode* freeNodePar = NULL;//这个是临时变量，后面写 ，应该定义tmpNode 655 //TreeNode* curNode = NULL;//这个是临时变量，后面写 ，应该定义tmpNode 656 657 //TreeNode* pLeftChildOfPosNode = NULL; 658 //TreeNode* pRightChildOfPosNode = NULL; 659 TreeNode* pParentOfPosNode = NULL; 660 //TreeNode* pCurPosNode = NULL; 661 662 663 //TreeNode* pLeftChildOfFreeNode = NULL; 664 //TreeNode* pRightChildOfFreeNode = NULL; 665 TreeNode* pParentOfFreeNode = NULL; 666 TreeNode stTmpNode; 667 memset(&stTmpNode, 0x00, sizeof(TreeNode)); 668 669 int iFlagLR = 0;//judge isLchild 670 int iTagIsSon = 0;//judge isLchild 671 672 int sdh = 0;//diff LR height of node 673 int iChildNum = 0; 674 int iNum = 0; 675 if(NULL != posNode ) 676 { 677 iChildNum = GetChildNum(posNode); 678 iFlagLR = IsLChild(posNode); 679 680 if(0 == iChildNum) 681 { 682 if(iIsRootNode) 683 { 684 free(posNode); 685 *avlTree = NULL; 686 return; 687 } 688 else 689 { 690 //isLeafNode 691 pParentOfPosNode = posNode->parent; 692 693 if(1 == iFlagLR) 694 { 695 //L 696 pParentOfPosNode->lchild = NULL; 697 698 }else if(0 == iFlagLR) 699 { 700 pParentOfPosNode->rchild = NULL; 701 } 702 free(posNode); 703 AdjustNode(pParentOfPosNode, avlTree); 704 705 } 706 707 } 708 else if(1 == iChildNum) 709 { 710 /*这段逻辑是最早写的，后来重理逻辑，理的很复杂，后来的逻辑基本是处理节点方法*/ 711 pParentOfPosNode = posNode; 712 posNode = posNode->lchild; 713 if(iIsRootNode) 714 { 715 *avlTree = posNode; 716 } 717 else 718 { 719 if(1 == iFlagLR) 720 { 721 //L 722 pParentOfPosNode->parent->lchild = posNode ; 723 }else if(0 == iFlagLR) 724 { 725 pParentOfPosNode->parent->rchild = posNode ; 726 } 727 } 728 posNode->parent = pParentOfPosNode->parent; 729 free(pParentOfPosNode); 730 AdjustNode(posNode, avlTree); 731 } 732 else if(-1 == iChildNum) 733 { 734 pParentOfPosNode = posNode; 735 posNode = posNode->rchild; 736 if(iIsRootNode) 737 { 738 *avlTree = posNode; 739 } 740 else 741 { 742 if(1 == iFlagLR) 743 { 744 //L 745 pParentOfPosNode->parent->lchild = posNode ; 746 } 747 else if(0 == iFlagLR) 748 { 749 pParentOfPosNode->parent->rchild = posNode ; 750 } 751 } 752 posNode->parent = pParentOfPosNode->parent; 753 free(pParentOfPosNode); 754 AdjustNode(posNode, avlTree); 755 } 756 else if(2 == iChildNum) 757 { 758 759 /*********begin**********/ 760 sdh = GetSymDiffHeight(posNode); 761 if((1 == sdh) 762 ||(0 == sdh)) 763 { 764 //左子树比右子树高,调整左子树 765 //pCurPosNode = posNode; 766 freeNode = GetMaxNode(posNode->lchild); 767 iNum = GetChildNum(freeNode); 768 memset(&stTmpNode, 0x00, sizeof(TreeNode)); 769 memcpy(&stTmpNode, freeNode, sizeof(TreeNode)); 770 memcpy(freeNode, posNode, sizeof(TreeNode)); 771 freeNode->data =http://www.mamicode.com/ stTmpNode.data; 772 if(iIsRootNode){ 773 *avlTree = freeNode; 774 } 775 else 776 { 777 if(iFlagLR) 778 { 779 posNode->parent->lchild = freeNode; 780 } 781 else 782 { 783 posNode->parent->rchild = freeNode; 784 } 785 } 786 if(0 == iNum) 787 {/*process*/ 788 789 pParentOfFreeNode = stTmpNode.parent; 790 if(stTmpNode.parent != posNode) 791 { 792 posNode->lchild->parent = freeNode; 793 posNode->rchild->parent = freeNode; 794 pParentOfFreeNode->rchild = NULL; 795 } 796 else 797 { 798 freeNode->lchild = NULL; 799 } 800 801 free(posNode); 802 803 if(stTmpNode.parent != posNode) 804 { 805 AdjustNode(pParentOfFreeNode, avlTree); 806 } 807 else 808 { 809 AdjustNode(freeNode, avlTree); 810 } 811 812 813 } 814 else if(1 == iNum) 815 { 816 /*这个属于异常分支，会指向自己*/ 817 //process posNode 818 if(stTmpNode.parent != posNode) 819 { 820 posNode->lchild->parent = freeNode; 821 posNode->rchild->parent = freeNode; 822 823 } 824 else 825 { 826 stTmpNode.lchild->parent = freeNode; 827 posNode->rchild->parent = freeNode; 828 } 829 //process freeNode 830 if(stTmpNode.parent != posNode) 831 { 832 stTmpNode.lchild->parent = stTmpNode.parent; 833 stTmpNode.parent->rchild = stTmpNode.lchild; 834 } 835 else 836 { 837 stTmpNode.lchild->parent = freeNode; 838 freeNode->lchild = stTmpNode.lchild; 839 } 840 841 free(posNode); 842 //AdjustNode(stTmpNode.parent, avlTree); 843 if(stTmpNode.parent != posNode) 844 { 845 AdjustNode(stTmpNode.parent, avlTree); 846 } 847 else 848 { 849 AdjustNode(freeNode, avlTree); 850 } 851 852 } 853 } 854 else if(-1 == sdh) 855 { 856 //左子树比右子树低,调整右子树 857 //pCurPosNode = posNode; 858 freeNode = GetMinNode(posNode->rchild); 859 iNum = GetChildNum(freeNode); 860 memset(&stTmpNode, 0x00, sizeof(TreeNode)); 861 memcpy(&stTmpNode, freeNode, sizeof(TreeNode)); 862 memcpy(freeNode, posNode, sizeof(TreeNode)); 863 freeNode->data =http://www.mamicode.com/ stTmpNode.data; 864 if(iIsRootNode){ 865 *avlTree = freeNode; 866 } 867 else 868 { 869 if(iFlagLR) 870 { 871 posNode->parent->lchild = freeNode; 872 } 873 else 874 { 875 posNode->parent->rchild = freeNode; 876 } 877 } 878 if(0 == iNum) 879 {/*process*/ 880 pParentOfFreeNode = stTmpNode.parent; 881 if(stTmpNode.parent != posNode) 882 { 883 posNode->lchild->parent = freeNode; 884 posNode->rchild->parent = freeNode; 885 pParentOfFreeNode->lchild = NULL; 886 } 887 else 888 { 889 freeNode->rchild = NULL; 890 } 891 892 free(posNode); 893 894 if(stTmpNode.parent != posNode) 895 { 896 AdjustNode(pParentOfFreeNode, avlTree); 897 } 898 else 899 { 900 AdjustNode(freeNode, avlTree); 901 } 902 #if 0 903 pParentOfFreeNode = stTmpNode.parent; 904 905 posNode->lchild->parent = freeNode; 906 posNode->rchild->parent = freeNode; 907 pParentOfFreeNode->lchild = NULL; 908 free(posNode); 909 AdjustNode(pParentOfFreeNode, avlTree); 910 #endif 911 912 } 913 else if(-1 == iNum) 914 { 915 /*这个属于异常分支，会指向自己*/ 916 //process posNode 917 if(stTmpNode.parent != posNode) 918 { 919 posNode->lchild->parent = freeNode; 920 posNode->rchild->parent = freeNode; 921 922 } 923 else 924 { 925 stTmpNode.rchild->parent = freeNode; 926 posNode->lchild->parent = freeNode; 927 } 928 //process freeNode 929 if(stTmpNode.parent != posNode) 930 { 931 stTmpNode.rchild->parent = stTmpNode.parent; 932 stTmpNode.parent->lchild = stTmpNode.rchild; 933 } 934 else 935 { 936 stTmpNode.rchild->parent = freeNode; 937 freeNode->rchild = stTmpNode.rchild; 938 } 939 940 free(posNode); 941 if(stTmpNode.parent != posNode) 942 { 943 AdjustNode(stTmpNode.parent, avlTree); 944 } 945 else 946 { 947 AdjustNode(freeNode, avlTree); 948 } 949 950 } 951 } 952 } 953 } 954 else 955 { 956 printf("can not find the key .\n"); 957 } 958 } 959 void DelNodeTestCase() 960 { 961 #if 0 962 int arr[5]={10, 8, 14, 12, 15};//del root 963 AVLTree *avlTree = InitBTree(arr, 5); 964 PRINTTREEINIT(avlTree); 965 966 int delKey = 10; 967 DeleteNode(avlTree, delKey); 968 PRINTTREEDEL(avlTree); 969 #endif 970 #if 0 971 int arr[1]={10};//del root 972 AVLTree *avlTree = InitBTree(arr, 1); 973 PRINTTREEINIT(avlTree); 974 975 int delKey = 10; 976 DeleteNode(avlTree, delKey); 977 PRINTTREEDEL(avlTree); 978 #endif 979 #if 0 980 int arr[2]={10,15};//del root 981 AVLTree *avlTree = InitBTree(arr, 2); 982 PRINTTREEINIT(avlTree); 983 984 int delKey = 10; 985 DeleteNode(avlTree, delKey); 986 PRINTTREEDEL(avlTree); 987 #endif 988 #if 0 989 int arr[3]={10,15, 5};//del root 990 AVLTree *avlTree = InitBTree(arr, 3); 991 PRINTTREEINIT(avlTree); 992 993 int delKey = 10; 994 DeleteNode(avlTree, delKey); 995 PRINTTREEDEL(avlTree); 996 #endif 997 998 #if 0 999 int arr[3]={10,15, 5}; 1000 AVLTree *avlTree = InitBTree(arr, 3); 1001 PRINTTREEINIT(avlTree); 1002 1003 int delKey = 5; 1004 DeleteNode(avlTree, delKey); 1005 PRINTTREEDEL(avlTree); 1006 #endif 1007 1008 #if 0 1009 int arr[7]={20,15, 25,7, 18, 22,19}; 1010 AVLTree *avlTree = InitBTree(arr, 7); 1011 PRINTTREEINIT(avlTree); 1012 1013 int delKey = 15; 1014 DeleteNode(avlTree, delKey); 1015 PRINTTREEDEL(avlTree); 1016 #endif 1017 #if 0 1018 int arr[7]={20,15, 25,7, 18, 22,17}; 1019 AVLTree *avlTree = InitBTree(arr, 7); 1020 PRINTTREEINIT(avlTree); 1021 1022 int delKey = 15; 1023 DeleteNode(avlTree, delKey); 1024 PRINTTREEDEL(avlTree); 1025 #endif 1026 #if 0 1027 int arr[7]={20,15, 25,7, 18, 22,17}; 1028 AVLTree *avlTree = InitBTree(arr, 7); 1029 PRINTTREEINIT(avlTree); 1030 1031 int delKey = 18; 1032 DeleteNode(avlTree, delKey); 1033 PRINTTREEDEL(avlTree); 1034 #endif 1035 #if 0 1036 int arr[6]={20,15, 25,7, 18, 22}; 1037 AVLTree *avlTree = InitBTree(arr, sizeof(arr)/sizeof(arr[0])); 1038 PRINTTREEINIT(avlTree); 1039 1040 int delKey = 15; 1041 DeleteNode(avlTree, delKey); 1042 PRINTTREEDEL(avlTree); 1043 #endif 1044 #if 0 1045 int arr[5]={20,15, 25,7, 22}; 1046 AVLTree *avlTree = InitBTree(arr, sizeof(arr)/sizeof(arr[0])); 1047 PRINTTREEINIT(avlTree); 1048 1049 int delKey = 15; 1050 DeleteNode(avlTree, delKey); 1051 PRINTTREEDEL(avlTree); 1052 #endif 1053 #if 0 1054 int arr[13]={20,15, 25,7, 18, 22,30, 5, 9, 16,19,40, 17}; 1055 AVLTree *avlTree = InitBTree(arr, sizeof(arr)/sizeof(arr[0])); 1056 PRINTTREEINIT(avlTree); 1057 1058 int delKey = 15; 1059 DeleteNode(avlTree, delKey); 1060 PRINTTREEDEL(avlTree); 1061 #endif 1062 #if 0 1063 int arr[13]={20,15, 25,7, 18, 22,30, 5, 9, 17,19,40, 16}; 1064 AVLTree *avlTree = InitBTree(arr, sizeof(arr)/sizeof(arr[0])); 1065 PRINTTREEINIT(avlTree); 1066 1067 int delKey = 15; 1068 DeleteNode(avlTree, delKey); 1069 PRINTTREEDEL(avlTree); 1070 #endif 1071 1072 #if 0 1073 /*左子树中max叶子节点*/ 1074 int arr[13]={28,20, 40,18,25,30,50,16,19,22,26,60, 17}; 1075 AVLTree *avlTree = InitBTree(arr, 13); 1076 PRINTTREEINIT(avlTree); 1077 1078 int delKey = 20; 1079 DeleteNode(avlTree, delKey); 1080 PRINTTREEDEL(avlTree); 1081 #endif 1082 1083 #if 0 1084 /*左子树中max叶子节点*/ 1085 int arr[13]={28,20, 40,18,25,30,50,17,19,22,26,60, 16}; 1086 AVLTree *avlTree = InitBTree(arr, sizeof(arr)/sizeof(arr[0])); 1087 PRINTTREEINIT(avlTree); 1088 1089 int delKey = 20; 1090 DeleteNode(avlTree, delKey); 1091 PRINTTREEDEL(avlTree); 1092 #endif 1093 #if 0 1094 int arr[13]={20,15, 25,7, 18, 22,30, 5, 9, 16,19,40, 11}; 1095 AVLTree *avlTree = InitBTree(arr, sizeof(arr)/sizeof(arr[0])); 1096 PRINTTREEINIT(avlTree); 1097 1098 int delKey = 15; 1099 DeleteNode(avlTree, delKey); 1100 PRINTTREEDEL(avlTree); 1101 #endif 1102 /*这个地方调整影响到其他的地方了*/ 1103 #if 0 1104 int arr[13]={20,15, 25,7, 18, 22,30, 5, 11, 16,19,40, 9}; 1105 AVLTree *avlTree = InitBTree(arr, sizeof(arr)/sizeof(arr[0])); 1106 PRINTTREEINIT(avlTree); 1107 1108 int delKey = 15; 1109 DeleteNode(avlTree, delKey); 1110 PRINTTREEDEL(avlTree); 1111 #endif 1112 1113 #if 0 1114 /*左子树中max非叶子节点*/ 1115 int arr[13]={28,21, 40,18,25,30,50,16,20,22,26,60, 19}; 1116 AVLTree *avlTree = InitBTree(arr, 13); 1117 PRINTTREEINIT(avlTree); 1118 1119 int delKey = 21; 1120 DeleteNode(avlTree, delKey); 1121 PRINTTREEDEL(avlTree); 1122 #endif 1123 1124 #if 0 1125 /*左子树中max非叶子节点*/ 1126 int arr[7]={28,21, 40,20,25,30,18}; 1127 AVLTree *avlTree = InitBTree(arr, 7); 1128 PRINTTREEINIT(avlTree); 1129 1130 int delKey = 21; 1131 DeleteNode(avlTree, delKey); 1132 PRINTTREEDEL(avlTree); 1133 #endif 1134 #if 1 1135 /*左子树中max非叶子节点3个节点情况*/ 1136 int arr[6]={28,21, 40,18,25,30}; 1137 AVLTree *avlTree = InitBTree(arr, 7); 1138 PRINTTREEINIT(avlTree); 1139 1140 int delKey = 21; 1141 DeleteNode(avlTree, delKey); 1142 PRINTTREEDEL(avlTree); 1143 #endif 1144 } 1145 void ConstAVLTree() 1146 { 1147 #if 1 1148 //int arr[6]={10, 8, 14, 12, 15, 16};//RR 1149 //int arr[6]={10, 8, 18, 12, 25, 19};//RR 1150 //int arr[6]={10, 8, 14, 12, 15, 11};//RL(L) 1151 //int arr[6]={10, 8, 14, 12, 15, 13};//RL(R) 1152 //int arr[6]={20, 17, 25, 14, 18, 15};//LL(L) 1153 //int arr[6]={20, 17, 25, 14, 18, 16};//LL(R) 1154 //int arr[6]={20, 16, 25, 14, 18, 17};//LR(L) 1155 int arr[6]={20, 16, 25, 14, 18, 19};//LR(R) 1156 AVLTree *avlTree = InitBTree(arr, sizeof(arr)/sizeof(arr[0])); 1157 PRINTTREEAVL(avlTree); 1158 //int arr[12]={25, 14, 30, 8, 20, 28, 39, 7, 9, 18, 22, 19};//LR(R) 1159 //int arr[12]={25, 14, 30, 8, 20, 28, 39, 7, 9, 18, 22, 17};//LR(L) 1160 //int arr[12]={25, 14, 30, 8, 20, 28, 39, 7, 9, 18, 22, 6};//LL(L) 1161 //int arr[12]={25, 10, 35, 8, 15, 29, 40, 27, 33, 38, 45, 26};//RL(L) 1162 //int arr[12]={25, 10, 35, 8, 15, 29, 40, 27, 33, 38, 45, 50};//RR(L) 1163 1164 //AVLTree *avlTree = InitBTree(arr, 12); 1165 #endif 1166 } 1167 int main(void) 1168 { 1169 ConstAVLTree(); 1170 DelNodeTestCase(); 1171 return 0; 1172 }
运行结果：------------------AVL Tree begin-------------
***********TREE View BEGIN***********
18
16
14
*
&
&
20
19
*
&
25
*
&
***********TREE View END ***********
------------------AVL Tree end-------------
------------------init Tree begin-------------
***********TREE View BEGIN***********
28
21
18
*
19
*
&
25
*
&
40
30
*
&
&
***********TREE View END ***********
------------------init Tree end-------------
要写的数据结构又少一个哈哈哈哈哈哈
平衡二叉树(AVLTREE,双链表实现)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。