叉平衡树过程分析doc

《叉平衡树过程分析doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、/*Note:YourchoiceisCIDE*///平衡二叉树。#include"stdio.h"#include"stdlib.h"typedefstructNode{intkey;structNode*pLeft;structNode*pRight;intbf;}Node;voidRightRotate(Node**pNode){Node*pAxis=(*pNode)->pLeft;(*pNode)->pLeft=pAxis->pRight;pAxis->pRight=*pNode;*pNode=pAxis;}void

2、LeftRotate(Node**pNode){Node*pAxis=(*pNode)->pRight;(*pNode)->pRight=pAxis->pLeft;pAxis->pLeft=*pNode;*pNode=pAxis;}voidLL_LR_Balance(Node**pNode){Node*pLeft=(*pNode)->pLeft;Node*pRight;switch(pLeft->bf){case1:(*pNode)->bf=pLeft->bf=0;RightRotate(pNode);break;case-

3、1:pRight=pLeft->pRight;switch(pRight->bf){case0:(*pNode)->bf=pLeft->bf=0;break;case1:pRight->bf=pLeft->bf=0;(*pNode)->bf=-1;break;case-1:(*pNode)->bf=pRight->bf=0;pLeft->bf=1;break;}LeftRotate(&(*pNode)->pLeft);RightRotate(pNode);break;}}voidRR_RL_Balance(Node**pNo

4、de){Node*pRight=(*pNode)->pRight;Node*pLeft;switch(pRight->bf){case-1:(*pNode)->bf=pRight->bf=0;LeftRotate(pNode);break;case1:pLeft=pRight->pLeft;switch(pLeft->bf){case0:(*pNode)->bf=pRight->bf=0;break;case1:(*pNode)->bf=pLeft->bf=0;pRight->bf=-1;break;case-1:pRigh

5、t->bf=pLeft->bf=0;(*pNode)->bf=1;break;}RightRotate(&(*pNode)->pRight);LeftRotate(pNode);break;}}intInsertBST(Node**pRoot,intkey,int*chain){if((*pRoot)==NULL){*pRoot=(Node*)malloc(sizeof(Node));(*pRoot)->bf=0;(*pRoot)->pLeft=(*pRoot)->pRight=NULL;(*pRoot)->key=key;

6、*chain=1;}else{if(key==(*pRoot)->key){*chain=0;return0;}if(key<(*pRoot)->key){if(!InsertBST(&(*pRoot)->pLeft,key,chain))return0;if(*chain){switch((*pRoot)->bf){case0:(*pRoot)->bf=1;*chain=1;break;case1:LL_LR_Balance(pRoot);*chain=0;break;case-1:(*pRoot)->bf=0;*chai

7、n=0;break;}}}else{if(!InsertBST(&(*pRoot)->pRight,key,chain))return0;if(*chain){switch((*pRoot)->bf){case0:(*pRoot)->bf=-1;*chain=1;break;case1:(*pRoot)->bf=0;*chain=0;break;case-1:RR_RL_Balance(pRoot);*chain=0;break;}}}}return1;}voidPintTree(Node*bt,intn)//屏幕显示二叉树

8、!{inti;if(bt==NULL)return;PintTree(bt->pLeft,n+1);for(i=0;i=1)printf("---");printf("%d",bt->key);PintTree(bt->pRight,n