平衡二叉树的建立 From: http://www.oschina.net/code/snippet_1167407_27146

AVL.c

#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;
}