叉平衡樹過程分析doc

1、./* Note:Your choice is C IDE */平衡二叉樹。#include "stdio.h"#include "stdlib.h"typedef struct Nodeint key;struct Node*pLeft;struct Node*pRight;int bf;Node;void RightRotate(Node*pNode)Node*pAxis=(*pNode)->pLeft;(*pNode)->pLeft=pAxis->pRight;pAxis->pRight=*pNode;*pNode=pAxi

2、s;void LeftRotate(Node*pNode)Node*pAxis=(*pNode)->pRight;(*pNode)->pRight=pAxis->pLeft;pAxis->pLeft=*pNode;*pNode=pAxis;void LL_LR_Balance(Node*pNode)Node*pLeft=(*pNode)->pLeft;Node*pRight;switch(pLeft->bf)case 1:(*pNode)->bf=pLeft->bf=0;RightRotate(pNode);break;case -1:pRigh

3、t=pLeft->pRight;switch(pRight->bf)case 0:(*pNode)->bf=pLeft->bf=0;break;case 1: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;void RR_RL_Balance(Node*pNode)Nod

4、e*pRight=(*pNode)->pRight;Node*pLeft;switch(pRight->bf)case -1:(*pNode)->bf=pRight->bf=0;LeftRotate(pNode);break;case 1:pLeft=pRight->pLeft;switch(pLeft->bf)case 0:(*pNode)->bf=pRight->bf=0;break;case 1:(*pNode)->bf=pLeft->bf=0;pRight->bf=-1;break;case -1:pRight->

5、bf=pLeft->bf=0;(*pNode)->bf=1;break;RightRotate(&(*pNode)->pRight);LeftRotate(pNode);break;int InsertBST(Node*pRoot,int key,int*chain) if(*pRoot)=NULL) *pRoot=(Node*)malloc(sizeof(Node);(*pRoot)->bf=0;(*pRoot)->pLeft=(*pRoot)->pRight=NULL;(*pRoot)->key=key;*chain=1;elseif(ke

6、y=(*pRoot)->key)*chain=0;return 0;if(key<(*pRoot)->key)if(!InsertBST(&(*pRoot)->pLeft,key,chain)return 0;if(*chain) switch(*pRoot)->bf)case 0:(*pRoot)->bf=1;*chain=1;break;case 1:LL_LR_Balance(pRoot);*chain=0;break;case -1:(*pRoot)->bf=0;*chain=0;break; elseif(!InsertBST(&am

7、p;(*pRoot)->pRight,key,chain)return 0;if(*chain) switch(*pRoot)->bf)case 0:(*pRoot)->bf=-1;*chain=1;break;case 1:(*pRoot)->bf=0;*chain=0;break;case -1:RR_RL_Balance(pRoot);*chain=0;break; return 1;void PintTree(Node *bt,int n)/屏幕顯示二叉樹!int i;if(bt=NULL)return ;PintTree(bt->pLeft,n+1);f

8、or(i=0;i<n-1;+i)printf(" ");if(n>=1)printf(" -");printf("%dn",bt->key);PintTree(bt->pRight,n+1);void main()Node*pRoot=NULL;int a=0,*chain=&a,n=0; InsertBST(&pRoot,3,chain); InsertBST(&pRoot,8,chain); InsertBST(&pRoot,16,chain); InsertBST(&pRoot,7,chain); Inser