#include?
#define?LH?+1
#define?EH?0
#define?RH?-1
#define?TRUE?1
#define?FALSE?0

using?namespace?std;

const?int?SIZE?=?1002;

int?preOrder[SIZE]?inOrder[SIZE];

struct?Node
{
????int?data;
????Node?*lson;
????Node?*rson;
};

typedef?struct?BSTnode
{
????int?data;
????int?bf;
????struct?BSTnode?*lchild*rchild;
}BSTnode*bstree;

int?Delete（bstree?&Tint?e）//刪除結(jié)點
{
????bstree?pq;
????int?shorter;
????e=0;
????p=T;
????if?（!T->rchild）?//右子數(shù)為空需要重接它的左子數(shù)
????{
????????T=T->lchild;
????????free（p）;
????????shorter=true;
????}
????else?if?（!T->lchild）?//重接它的右子數(shù)
????{
????????T=T->rchild;
????????free（p）;
????????shorter=true;
????}
????else??//左右子數(shù)均不空
????{
????????q=T->lchild;
????????while?（q->rchild!=NULL）?//轉(zhuǎn)左，然后向右到盡頭
????????{
????????????q=q->rchild;
????????}
????????e=q->data;
????}
????return?e;
}

void?Delete_Rightbalance（bstree?&T）//刪除在左子樹上的，相當于插入在右子樹
{
????bstree?rc=T->rchildld;
????int?shorter;
????switch?（rc->bf）
????{
????case?LH://雙旋?，先右旋后左旋
????????ld=rc->lchild;
????????rc->lchild=ld->rchild;
????????ld->rchild=rc;
????????T->rchild=rc->lchild;
????????rc->lchild=T;
????????switch?（ld->bf）
????????{
????????case?LH:
????????????T->bf=EH;
????????????rc->bf=RH;
????????????break;
????????case?EH:
????????????T->bf=rc->bf=EH;
????????????break;
????????case?RH:
????????????T->bf=LH;
????????????rc->bf=EH;
????????????break;
????????}
????????ld->bf=EH;
????????T=rc;
????????shorter=true;
????????break;
????case?EH:///////刪除在左子樹，相當于插入在右子樹，左單旋
????????T->rchild=rc->lchild;
????????rc->lchild=T;
????????rc->bf=LH;
????????T->bf=RH;
????????T=rc;
????????shorter=EH;
????????break;
????case?RH:///////刪除在左子樹，相當于插入在右子樹，左單旋
????????T->rchild=rc->lchild;
????????rc->lchild=T;
????????rc->bf=T->bf=EH;
????????T=rc;
????????shorter=true;
????????break;
????}
}

void?Delete_Leftbalance（bstree?&T）//刪除右子樹上的，相當于插入在左子樹上
{
????bstree?p1p2;
????int?shorter;
????p1=T->lchild;
????switch?（p1->bf）
????{
????case?LH:
????????T->lchild=p1->rchild;//右旋
????????p1->rchild=T;
????????p1->bf=T->bf=EH;
????????T=p1;
????????shorter=true;
????????break;
????case?EH:
????????T->lchild=p1->rchild;//右旋
????????p1->rchild=T;
????????p1->bf=RH;
????????T->bf=LH;
????????T=p1;
????????shorter=false;
????????break;
????case?RH:
????????p2=p1->rchild;//右雙旋
????????p1->rchild=p2->lchild;
????????p2->lchild=p1;
????????T->lchild=p2->rchild;
????????p2->rchild=T;
????????switch?（p2->bf）
????????{
????????case?LH:
????????????T->bf=RH;
????????????p1->bf=EH;
????????????break;
????????case?EH:
????????????T->bf=EH;
????????????p1->bf=EH;
????????????break;
????????case?RH:
????????????T->bf=EH;
????????????p1->bf=LH;
????????????break;
????????}
????????p2->bf=EH;
????????T=p2;
????????shorter=true;
????????break;
????}
}

bstree?DeleteAVL（bstree?&Tint?e）//刪除后要保證該二叉樹還是平衡的
{
????int?nm=0;//標記
????int?shor