#include?“stdio.h“
#include?“stdlib.h“
#include?“time.h“
#define??MAXSIZE?1000
#define??true??1
#define??false?0

typedef?struct?anode{
	int?elem;
	int?bf;
	struct?anode?*lchild;
	struct?anode?*rchild;
}AVLNode*AVLTree;
//平衡二叉排序樹的數(shù)據(jù)結(jié)構(gòu)


typedef?struct{
	AVLTree?data[MAXSIZE];
	int?frontrear;
}sepQueue*PsepQueue;
//隊(duì)列元素為指向樹的指針

typedef?struct?node{
	AVLTree?data;
	struct?node?*?next;
}linkstack*Plinkstack;

typedef?struct{
	Plinkstack?top;
}stack*Pstack;
//以上的兩個(gè)數(shù)據(jù)結(jié)構(gòu)是鏈?zhǔn)綏５慕Y(jié)構(gòu)



int?AVLTree_Insert（AVLTree?*tAVLTree?s）;
/*
*平衡二叉排序樹的節(jié)點(diǎn)插入s為要插入的節(jié)點(diǎn)
*
*返回true表示插入數(shù)據(jù)成功false表示插入數(shù)據(jù)失敗
*/


void?levelOrder（AVLTree?t）;
/*
*層次法遍歷一棵二叉樹
*
*此層次法遍歷?<“優(yōu)點(diǎn)“>?在于能夠完全的顯示一棵樹
*/

PsepQueue?Init_sepQueue（）;
//隊(duì)的初始化

int?empty_sepQueue（PsepQueue?Q）;
//判斷隊(duì)是否為空

int?full_sepQueue（PsepQueue?Q）;
//判斷隊(duì)是否滿

int?push_sepQueue（PsepQueue?QAVLTree?data）;
//新隊(duì)員入隊(duì)

int?pop_sepQueue（PsepQueue?Q?AVLTree?*data）;
//隊(duì)員出隊(duì)

void?Destory_sepQueue（PsepQueue?*Q）;
//銷毀隊(duì)列

void?visit（AVLTree?t）;
//訪問(wèn)節(jié)點(diǎn)


AVLTree?LL_Rotate（AVLTree?a）;
/*????????????????????????????????????????A
*對(duì)二叉排序樹進(jìn)行“左左”調(diào)整????????????/?\
*???????????????????????????????????????B???#
*原因在于:a->bf=2b->bf=1??????????????/?\?
*?????????????????????????????????????#???#
*/


AVLTree?LR_Rotate（AVLTree?a）;
/*?????????????????????????????????????A
*對(duì)二叉排序樹進(jìn)行“左右”調(diào)整?????????/?\
*????????????????????????????????????B???#
*原因在于:a->bf=2b->bf=-1??????????/?\
*??????????????????????????????????#???C
*?????????????????????????????????????/?\
*????????????????????????????????????#???#
*/

AVLTree?RL_Rotate（AVLTree?a）;
/*?????????????????????????????????????????A
*對(duì)二叉排序樹進(jìn)行“右左”調(diào)整?????????????/?\
*????????????????????????????????????????#???B
*原因在于:a->bf=-2b->bf=1??????????????????/?\
*??????????????????????????????????????????C???#
*?????????????????????????????????????????/?\
*????????????????????????????????????????#???#
*/????????????????????????????????????????

AVLTree?RR_Rotate（AVLTree?a）;?
/*??????????????????????????????????????A
*對(duì)二叉排序樹進(jìn)行“右右”調(diào)整??????????/?\?
*?????????????????????????????????????#???B
*原因在于:a->bf=-2b->bf=-1??????????????/?\
*???????????????????????????????????????#???#
*/????????????????????????????????????



void?Rotate（AVLTree?*tAVLTree?a）;
/*
*調(diào)整節(jié)點(diǎn)的平衡包括了各種需要調(diào)節(jié)的情況
*
*此算法的優(yōu)點(diǎn)在于?<“屏蔽“>?所有的旋轉(zhuǎn)調(diào)節(jié)的情況
*/


void?InOrder（AVLTree?t）;
/*中序遍歷二叉樹*/


int?locate_AVLNode（AVLTree?*tAVLTree?sAVLTree?*faAVLTree?*a）;
/*
*在平衡二叉排序樹中插入一個(gè)新的節(jié)點(diǎn)
*
*入口參數(shù)a:最小不平衡因子;fa是a的雙親;t是待查樹;s為待插入的節(jié)點(diǎn)
*
*返回true表示查找并且插入成功false表示失敗
*/


void?adjust_AVLTree_bf（AVLTree?*aAVLTree?s）;
/*
*插入數(shù)據(jù)后調(diào)節(jié)最小不平衡路徑上的平衡因子
*
*入口參數(shù)a為最小不平衡因子s用于找路徑
*/


int?TreeHigh（AVLTree?t）;
/*求解樹的高度*/


int?Delete_AVLTree_elem（AVLTree?*tint?kAVLTree?*s）;
/*
*刪除二叉排序樹中的節(jié)點(diǎn)（僅僅只是刪除節(jié)點(diǎn)）
*
*入口參數(shù)s用于存放需要?jiǎng)h除節(jié)點(diǎn)的雙親
*
*返回true表示刪除數(shù)據(jù)成功false表示刪除數(shù)據(jù)失敗;?<“s是輸出型的節(jié)點(diǎn)“>方便以后調(diào)節(jié)不平衡因子
*/


int?AVLTree_Delete（AVLTree?*tint?k）;
/*??????????????????????