#include
#include

#define?OVERFLOW?-1
#define?OK?1
#define?ERROR?0
#define?TRUE?1
#define?FALSE?0

#define?LH?+1??//左高
#define?EH?0???//等高
#define?RH?-1??//右高

typedef?int?RcdType;
typedef?int?Status;

//存放輸入數據的數組結構體
typedef?struct?ArrayNode{
????RcdType?data;
????ArrayNode?*next;
}ArrayNode?*Array;

//平衡二叉樹結構體
typedef?struct?BBSTNode{
????RcdType?data;
????int?bf;
????BBSTNode?*lchild?*rchild;
}BBSTNode*BBSTree;

//鏈隊列結構體
typedef?struct?LQNode{
????BBSTree?elem;
????struct?LQNode?*next;
}LQNode?*QueuePtr;

//隊列結點結構體
typedef?struct{
????QueuePtr?front;
????QueuePtr?rear;
}LQueue;

//棧結點結構體
typedef?struct?LSNode{
????BBSTree?data;?????????//數據域
????struct?LSNode?*next;???//指針域
}LSNode?*LStack;??????????//結點和鏈棧類型


/*初始化一個鏈棧*/
Status?InitStack_LS（LStack?&S）{
????S?=?NULL;
}


/*進棧操作*/
Status?Push_LS（LStack?&S?BBSTree?e）{
????LSNode?*t;
????t?=?（LSNode*）malloc（sizeof（LSNode））;
????if（NULL==t）?return?OVERFLOW;
????t->data?=?e;
????t->next?=?S;
????S?=?t;
????return?OK;
}

/*出棧操作*/
Status?Pop_LS（LStack?&S?BBSTree?&e）{
????LSNode?*t;
????if（S==NULL）?return?ERROR;
????t?=?S;
????e?=?t->data;
????S?=?S->next;
????return?OK;
}


/*獲得棧頂元素*/
Status?GetTop_LS（LStack?S?BBSTree?&e）{
????if（NULL==S）?return?ERROR;
????else{
????????e?=?S->data;
????????return?OK;
????}
}

/*判斷棧是否為空*/
Status?StackEmpty_LS（LStack?S）{
????if（NULL==S）?return?TRUE;
????else?return?FALSE;
}

/*初始化鏈隊列*/
void?InitQueue_LQ（LQueue?&Q）{
????Q.front?=?NULL;
????Q.rear=?NULL;
}

/*鏈隊列進隊操作*/
Status?EnQueue_LQ（LQueue?&Q?BBSTree?e）{
????LQNode?*p;
????p?=?（LQNode*）malloc（sizeof（LQNode））;
????if（NULL==p）?return?OVERFLOW;
????p->elem?=?e;
????p->next?=?NULL;
????if（NULL==Q.front）?Q.front?=?p;??//e插入空隊列
????else?Q.rear->next?=?p;??//e插入非空隊列
????Q.rear?=?p;??//隊尾指針指向新的隊尾
????return?OK;
}

/*鏈隊列出棧操作*/
Status?DeQueue_LQ（LQueue?&Q?BBSTree?&e）{
????LQNode?*p;
????if（NULL==Q.front）?return?ERROR;
????p?=?Q.front;
????e?=?p->elem;
????Q.front?=?p->next;
????if（Q.rear==p）?Q.rear?=?NULL;
????free（p）;
????return?OK;
}


/*求平衡二叉樹的深度*/
int?BBSTreeDepth（BBSTree?T）{
????int?depthLeft?depthRight;
????if（NULL==T）?return?0;
????else{
????????depthLeft?=?BBSTreeDepth（T->lchild）;
????????depthRight?=?BBSTreeDepth（T->rchild）;
????????return?1+（depthLeft?>?depthRight???depthLeft?:?depthRight）;
????}
}

/*交換二叉樹所有結點的左右子樹*/
void?ExchangeSubTree（BBSTree?&T）{
????BBSTree?temp;
????if（NULL!=T）{
????????ExchangeSubTree（T->lchild）;???//使用遞歸交換左子樹
????????ExchangeSubTree（T->rchild）;???//使用遞歸交換右子樹
????????if（（T->lchild!=NULL）||（T->rchild!=NULL））{????//如果T的子樹有一個不為空，則交換左右子樹
????????????temp?=?T->lchild;
????????????T->lchild?=?T->rchild;
????????????T->rchild?=?temp;
????????}
????}

}

/*左旋調整*/
void?L_Rotate（BBSTree?&p）{
????BBSTree?rc?=?p->rchild;
????p->rchild?=?rc->lchild;
????rc->lchild?=?p;
????p?=?rc;
}

/*右旋調整*/
void?R_Rotate（BBSTree?&p）{

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件??????15467??2017-01-03?23:39??數據結構課設\Tree?head.cpp

?????文件???????8374??2017-01-03?23:39??數據結構課設\Tree?head.o

?????文件?????434132??2017-01-04?00:12??數據結構課設\平衡二叉樹--課程設計.doc

?????文件???????8556??2017-01-04?00:05??數據結構課設\平衡二叉樹.cpp

?????文件?????147542??2017-01-04?00:05??數據結構課設\平衡二叉樹.exe

?????文件??????17445??2017-01-04?00:05??數據結構課設\平衡二叉樹.o

?????文件?????235516??2016-12-29?22:40??數據結構課設\數據結構實驗指導書（2015春）.doc

?????文件?????738304??2017-01-03?12:28??數據結構課設\樹--設計性實驗.doc

?????文件??????16571??2017-01-03?13:27??數據結構課設\題目12??平衡二叉樹操作的演示.docx

?????目錄??????????0??2017-12-28?23:57??數據結構課設

-----------?---------??----------?-----??----

??????????????1621907????????????????????10