#include
#include
#include
#include
#include
#include
#define?LH?1//左高?
#define?EH?0//等高?
#define?RH?-1//右高?
#define?FALSE?0
#define?TRUE?1
#define?OK?1
#define?ERROR?0
#define?MAXSIZE?20
char?filename[30];
FILE?*fp;

typedef?struct{
	int?number;
	char?name[10];
	float?wage;
	int?age;
}worker;


typedef?struct?tree
{
	worker?data;
	int?bf;//節點平衡因子
	struct?tree?*rchild*lchild;
}node*bitree;

int?insert（bitree?&tworker?xbool?&taller）;
int??input（）
{
	int?jn=0;
	worker?wor[MAXSIZE];
	printf（“輸入文件名\n“）;
	scanf（“%s“filename）;
	if（（fp=fopen（“filename““w+“））==NULL）
	{
		printf（“the?file?error!\n“）;
		exit（0）;
	}
	printf（“輸入要錄入的職工個數\n“）;
	scanf（“%d“&n）;
	printf（“輸入%d個職工信息?職工號?姓名，工資，年齡?\n“n）;
	for（j=0;j	{
		scanf（“%d%s%f%d“&wor[j].numberwor[j].name&wor[j].wage&wor[j].age）;
		getchar（）;
	}
	for（j=0;j		fprintf（fp“%-3d?%-10s?%-8f?%-5d\n“wor[j].numberwor[j].namewor[j].wagewor[j].age）;
	fclose（fp）;
	return?n;
}



void?creat（int?nbitree?&t）
{//構建平衡排序樹
	int?i;
	bool?taller=FALSE;
	t=NULL;
	worker?wor;
	if（n==0）
		exit（0）;
	if（（fp=fopen（“filename““r“））==NULL）
	{
		printf（“the?file?error\n“）;
		exit（0）;
	}
	fscanf（fp“%d%s%f%d“&wor.numberwor.name&wor.wage&wor.age）;
	for（i=0;i	{
		insert（twortaller）;
		fscanf（fp“%d%s%f%d“&wor.numberwor.name&wor.wage&wor.age）;
	}
	fclose（fp）;
}



void?r_rotate（bitree?&t）
{//對以*t為根的二叉排序樹作右旋轉處理，處理之后t指向新的樹根節點
//?即旋轉之前的左子樹的根節點
	bitree?lc=t->lchild;
	t->lchild=lc->rchild;
	lc->rchild=t;
	t=lc;
}

void?l_rotate（bitree?&t）
{//對以*p為跟的二叉排序樹作左旋轉處理，處理之后p指向新的樹根節點
//?即旋轉之前的右子樹的根節點
	bitree?rc=t->rchild;
	t->rchild=rc->lchild;
	rc->lchild=t;
	t=rc;
}


void?leftbalance（bitree?&t）
{//對以指針t所指節點為根的二叉樹作左平衡旋轉處理，本算法結束時，指針t指向新的根節點
	bitree?lc=t->lchild;
	switch（lc->bf）
	{
	case?LH:?//新節點插入在*t的左孩子的左子樹上，要作單右旋處理?
		t->bf?=?lc->bf?=?EH;
		r_rotate（t）;
		break;
	case?RH:?//新節點插入在*t的左孩子的右子樹上，要作雙旋處理?
		bitree?rd?=?lc->rchild;
		switch（rd->bf）
		{//修改*T及其孩子的平衡因子?
		case?LH:
			t->bf?=?RH;?
			lc->bf?=?EH;
			break;
		case?EH:
			t->bf?=?lc->bf?=?EH;?
			break;
		case?RH:
			t->bf?=?EH;?
			lc->bf?=?LH;?
			break;
		}
		rd->bf?=?EH;
		l_rotate（t->lchild）;//對*t的左子樹作左平衡處理?
		r_rotate（t）;//對*t作右旋平衡處理?
		break;
	}
}


void?rightbalance（bitree?&t）
{//對以指針t所指節點為根的二叉樹作右平衡旋轉處理，本算法結束時，指針t指向新的根節點?
????bitree?rc?=?t->rchild;
????switch（rc->bf）//檢查*T的右子樹的平衡度，并作相應的平衡處理?
????{
????????case?RH:
????????????//新節點插入在*t的右孩子的右子樹上，要作單左旋處理?
????????????t->bf?=?rc->bf?=?EH;
????????????l_rotate（t）;?
			break;
????????case?LH:?
????????????//新節點插入在*t的右孩子的左子樹上，要作雙旋處理?
????????????bitree?ld?=?rc->lchild;
????????????switch（ld->bf）
????????????{//修改*t及其孩子的平衡因子?
????????????????case?RH:
					t->bf?=?LH;
					rc->bf?=?EH;?
					break;
????????????????case?EH:
					t->bf?=?rc->bf?=?EH;?
					break;
????????????????case?LH: