#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;
//平衡二叉排序樹的數據結構


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

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

typedef?struct{
	Plinkstack?top;
}stack*Pstack;
//以上的兩個數據結構是鏈式棧的結構



int?AVLTree_Insert（AVLTree?*tAVLTree?s）;
/*
*平衡二叉排序樹的節點插入s為要插入的節點
*
*返回true表示插入數據成功false表示插入數據失敗
*/


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

PsepQueue?Init_sepQueue（）;
//隊的初始化

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

int?full_sepQueue（PsepQueue?Q）;
//判斷隊是否滿

int?push_sepQueue（PsepQueue?QAVLTree?data）;
//新隊員入隊

int?pop_sepQueue（PsepQueue?Q?AVLTree?*data）;
//隊員出隊

void?Destory_sepQueue（PsepQueue?*Q）;
//銷毀隊列

void?visit（AVLTree?t）;
//訪問節點


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


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

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

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



void?Rotate（AVLTree?*tAVLTree?a）;
/*
*調整節點的平衡包括了各種需要調節的情況
*
*此算法的優點在于?<“屏蔽“>?所有的旋轉調節的情況
*/


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


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


void?adjust_AVLTree_bf（AVLTree?*aAVLTree?s）;
/*
*插入數據后調節最小不平衡路徑上的平衡因子
*
*入口參數a為最小不平衡因子s用于找路徑
*/


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


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


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