- #include <stdio.h>
- #include <stdlib.h>
- typedef struct Node{
- int data;
- int bf;
- struct Node *lchild;
- struct Node *rchild;
- }Node;
- #define LH 1
- #define EH 0
- #define RH -1
- void L_Rotate(Node **p){
- Node *rc=(*p)->rchild;
- (*p)->rchild=rc->lchild;
- rc->lchild=*p;
- *p=rc;
- }
- void R_Rotate(Node **p){
- Node *lc=(*p)->lchild;
- (*p)->lchild=lc->rchild;
- lc->rchild=*p;
- *p=lc;
- }
- void LeftBalance(Node **p){
- Node *lc=(*p)->lchild,*rd;
- switch(lc->bf){
- case LH:
- (*p)->bf=lc->bf=EH;
- R_Rotate(p);
- break;
- case RH:
- rd=lc->rchild;
- switch(rd->bf){
- case LH:
- (*p)->bf=RH;
- lc->bf=EH;
- break;
- case EH:
- (*p)->bf=lc->bf=EH;
- break;
- case RH:
- (*p)->bf=EH;
- lc->bf=LH;
- break;
- }//end switch(lc->bf)
- rd->bf=EH;
- L_Rotate(&((*p)->lchild));
- R_Rotate(p);
- break;
- }//end switch(lc->bf)
- }//end LeftBalance()
- void RightBalance(Node **p){
- Node *rc=(*p)->rchild,*ld;
- switch(rc->bf){
- case RH:
- (*p)->bf=rc->bf=EH;
- L_Rotate(p);
- break;
- case LH:
- ld=rc->lchild;
- switch(ld->bf){
- case RH:
- (*p)->bf=LH;
- rc->bf=EH;
- break;
- case EH:
- (*p)->bf=rc->bf=EH;
- break;
- case LH:
- (*p)->bf=EH;
- rc->bf=RH;
- break;
- }
- ld->bf=EH;
- R_Rotate(&(*p)->rchild);
- L_Rotate(p);
- break;
- }
- }
- int InsertAVL(Node **t,int data,int *isTaller){
- if(!(*t)){
- *t=(Node*)malloc(sizeof(Node));
- (*t)->data=data;
- (*t)->lchild=(*t)->rchild=NULL;
- (*t)->bf=EH;
- *isTaller=1;
- }//end if(!(*t))
- else{
- if(data==(*t)->data) {
- *isTaller=0;
- return 0;
- }
- if(data<(*t)->data){
- if(!InsertAVL(&((*t)->lchild),data,isTaller)) return 0;
- if(*isTaller){
- switch((*t)->bf){
- case LH:
- LeftBalance(t);
- *isTaller=0;
- break;
- case EH:
- (*t)->bf=LH;
- *isTaller=1;
- break;
- case RH:
- (*t)->bf=EH;
- *isTaller=0;
- break;
- }//end switch((*t)->bf)
- }//end if(*isTaller)
- }//end if(data<(*t)->data)
- else{
- if(!InsertAVL(&((*t)->rchild),data,isTaller)) return 0;
- if(*isTaller){
- switch((*t)->bf){
- case LH:
- (*t)->bf=EH;
- *isTaller=0;
- break;
- case EH:
- (*t)->bf=RH;
- *isTaller=1;
- break;
- case RH:
- RightBalance(t);
- *isTaller=0;
- break;
- }//end switch((*t)->bf)
- }//end if(*isTaller)
- }////end else---(data>(*t)->data)---
- }//end else-----(*t)-----
- return 1;
- }
- void inOrder(Node *root){
- if(root){
- inOrder(root->lchild);
- printf("%d \\t",root->data);
- inOrder(root->rchild);
- }
- }
- void DotOrder(Node *root, FILE *fp) /*先序遍历二叉树, root为指向二叉树根结点的指针*/
- {
- if(root==NULL || !(root->lchild || root->rchild))
- return;
- if(root->lchild)
- fprintf(fp,"%d -> %d;\\n",root->data,root->lchild->data);
- else
- {
- fprintf(fp,"NULL%dL[label=\\"NULL\\",shape=none];\\n",root->data);
- fprintf(fp,"%d -> NULL%dL;\\n",root->data,root->data);
- }
- if(root->rchild)
- fprintf(fp,"%d -> %d;\\n",root->data,root->rchild->data);
- else
- {
- fprintf(fp,"NULL%dR[label=\\"NULL\\",shape=none];\\n",root->data);
- fprintf(fp,"%d -> NULL%dR;\\n",root->data,root->data);
- }
- DotOrder(root->lchild,fp);
- DotOrder(root->rchild,fp);
- }
- void MakeDot(Node *root)
- {
- FILE *fp=fopen("AVL.gv","w+");
- fprintf(fp,"digraph AVL {\\n");
- DotOrder(root,fp);
- fprintf(fp,"}\\n\\n");
- fclose(fp);
- }
- int main(int argc,char *argv[]){
- if(argc>1){
- Node *root=NULL;
- int i;
- int taller=1;
- for(i=1;i<argc;i++){
- InsertAVL(&root,atoi(argv[i]),&taller);
- }
- MakeDot(root);
- printf("该平衡二叉树的中序序列为:\\n");
- inOrder(root);
- system("dot.exe -Tpng AVL.gv -o AVL.png && AVL.png");
- }
- else{
- int data;
- Node *root=NULL;
- int taller=1;
- printf("请输入数据,以\\"-1\\"结束:\\n");
- scanf("%d",&data);
- if(data!=-1){
- do{
- InsertAVL(&root,data,&taller);
- scanf("%d",&data);
- }while(data!=-1);
- MakeDot(root);
- printf("该平衡二叉树的中序序列为:\\n");
- inOrder(root);
- system("dot.exe -Tpng AVL.gv -o AVL.png && AVL.png");
- }
- else{
- printf("一颗空树!\\n");
- }
- }
- printf("\\n");
- system("pause");
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/020720149897.html
来源: http://www.codesnippet.cn/detail/020720149897.html