（1）任務為：抽象數據類型的實現；本次任務用了devcpp程序作為開發軟件，編寫語言為C語言。
（2）二叉樹是一種遞歸數據結構。二叉樹是含有n(n>=0)個節點的有限集合。當n=0時稱為空二叉樹。在非空二叉樹中：（1）有且僅有一個稱為根的節點（2）當n>1時，其余節點劃分為兩個互不相交的子集L和R,其中L和R也是一課二叉樹，分別稱為左子樹和右子樹，且其次序不能顛倒。
二叉樹的基本操作有：
1、Status InitBiTree(BiTree &T)即創建一棵空二叉樹
2、BiTree MakeBiTree(TElemType e,BiTree L,BiTree R)即創建一棵二叉樹T,其中根節點的值為e，L和R分別作為左子樹和右子樹
3、void DestoryBiTree(BiTree &T)即銷毀二叉樹
4、Status BiTreeEmpty(BiTree &T)二叉樹判空，若為空返回TRUE,否則FALSE
5、Status BreakBitree(BiTree &T,BiTree &L,BiTree &R)將一棵二叉樹T分解成根、左子樹和右子樹三個部分
6、Status ReplaceLeft(BiTree &T,BiTree <)替換左子樹。若T非空，則用LT替換T的左子樹，並用LT返回T的原有左子樹
7、Status ReplaceRight(BiTree &T,BiTree &RT)替換右子樹。若T非空，則用RT替換T的左子樹，並用RT返回T的原有左子樹
8、Status CutLeft(BiTree &T,BiTree <)剪除左子樹，若T非空，則剪除T的左子樹，並用LT返回
9、Status CutRight(BiTree &T,BiTree &RT)剪除右子樹，若T非空，則剪除T的右子樹，並用RT返回
10、Status PreTraverse(BiTree T,Status(*visit)(TElemType e))先序遍歷
11、Status MidTraverse(BiTree T,Status(*visit)(TElemType e))中序遍歷
12、void AfterTraverse(BiTree T)後序遍歷
13、int BiTreeDepth(BiTree T)求樹的深度
14、BiTree CreatBT ()建立二叉樹
（3）所選的存儲結構為鏈式存儲，其中包含一個數據域和兩個左右孩子指針。各基本操作的實現：
1、Status InitBiTree(BiTree &T)操作中通過T=(BiTree)malloc(sizeof(BiTNode));給樹開辟一塊空間實現創建一棵空二叉樹
2、BiTree MakeBiTree(TElemType e,BiTree L,BiTree R)中，通過t->data = e;t->lchild = L;t->rchild = R;實現令L、R成為t的左右子樹
3、void DestoryBiTree(BiTree &T)則直接通過free(T);釋放內存空間來達到銷毀樹
4、Status BiTreeEmpty(BiTree &T)中如果NULL==T,即樹中沒有內容，則判斷為空樹
5、Status BreakBitree(BiTree &T,BiTree &L,BiTree &R)通過 L = T->lchild;R = T->rchild;來將結構體T所指向的左右子樹分別賦給L和R樹。
6、Status ReplaceLeft(BiTree &T,BiTree <)通過t = T->lchild;T->lchild = LT;LT = t使T的左子樹變為指向LT,即LT成為T的左子樹，從而達到替換作用
7、Status ReplaceRight(BiTree &T,BiTree &RT)原理與上一步相同
8、Status CutLeft(BiTree &T,BiTree <)通過LT = T->lchild;T->lchild = NULL使LT的存儲位置變為T->lchild，而T->lchild 的存儲位置變為NULL
9、Status CutRight(BiTree &T,BiTree &RT)原理與上一步相同
10、Status PreTraverse(BiTree T,Status(*visit)(TElemType e))先序遍歷通過遞歸的方法，每進入一層遞歸 先visit(T->data)即先訪問根節點，再進入PreTraverse(T->lchild,visit)左子樹的一層遞歸訪問，再進入PreTraverse(T->rchild,visit)右子樹
11、Status MidTraverse(BiTree T,Status(*visit)(TElemType e))中序遍歷，先進入左子樹的最底層MidTraverse(T->lchild,visit)訪問，接著回訪問根節點visit(T->data)，再進入右子樹最底層MidTraverse(T->rchild,visit)訪問，再逐層上升訪問。
12、void AfterTraverse(BiTree T)後序遍歷則先進入左子樹最底層 AfterTraverse (T->lchild);訪問，再進入右子樹最底層AfterTraverse (T->rchild);訪問，然後再訪問根節點，再逐層上升訪問。
15、int BiTreeDepth(BiTree T)求樹的深度，根節點獨占一層，所以二叉樹的深度為其左右子樹深度的最大值加1，判斷到達最底層時NULL == T就返回上一層，逐層上升加1
16、BiTree CreatBT ()建立二叉樹。用戶先輸入根節點信息，此時如果用戶輸入0，則令t=NULL,即不存儲任何信息，當輸入非0時，鏈表中t->data的信息域即存儲為該用戶輸入的信息，接著用戶輸入左子樹信息，進入一層遞歸，此時該信息為t->lchild信息域的內容，當輸入為0則返回上一層，問右子樹的信息，此時該信息為t->rchild信息域的內容,以此類推。
以下為源碼：
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
typedef int TElemType;
typedef bool Status;
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
Status InitBiTree(BiTree &T){
T = (BiTree)malloc(sizeof(BiTNode));
if(!T) return ERROR;
return OK;
}
BiTree MakeBiTree(TElemType e,BiTree L,BiTree R){
BiTree t;
t = (BiTree)malloc(sizeof(BiTNode));
if(NULL == t) return NULL;
t->data = e;
t->lchild = L;
t->rchild = R;
return t;
}
void DestoryBiTree(BiTree &T){
free(T);
}
Status BiTreeEmpty(BiTree &T){
if(NULL == T) return TRUE;
else return FALSE;
}
Status BreakBitree(BiTree &T,BiTree &L,BiTree &R){
if(NULL == T) return FALSE;
L = T->lchild;
R = T->rchild;
T->lchild = NULL;
T->rchild = NULL;
return TRUE;
}
Status ReplaceLeft(BiTree &T,BiTree <){
if(NULL == T) return FALSE;
BiTree t;
t = T->lchild;
T->lchild = LT;
LT = t;
return TRUE;
}
Status ReplaceRight(BiTree &T,BiTree &RT){
if(NULL == T) return FALSE;
BiTree t;
t = T->rchild;
T->rchild = RT;
RT = t;
return TRUE;
}
Status CutLeft(BiTree &T,BiTree <){
if(NULL == T) {
LT = NULL;
return FALSE;
}
LT = T->lchild;
T->lchild = NULL;
return TRUE;
}
Status CutRight(BiTree &T,BiTree &RT){
if(NULL == T) {
RT = NULL;
return FALSE;
}
RT = T->lchild;
T->lchild = NULL;
return TRUE;
}
//先序遍歷
Status PreTraverse(BiTree T,Status(*visit)(TElemType e)){
if(NULL == T) return OK;
if(ERROR == visit(T->data)) return ERROR;
if(ERROR == PreTraverse(T->lchild,visit))
return ERROR;
return PreTraverse(T->rchild,visit);
}
//中序遍歷
Status MidTraverse(BiTree T,Status(*visit)(TElemType e)){
if(NULL == T) return OK;
if(ERROR == MidTraverse(T->lchild,visit))
return ERROR;
if(ERROR == visit(T->data))
return ERROR;
return MidTraverse(T->rchild,visit);
}
//後序遍歷
void AfterTraverse(BiTree T){
if (T == NULL)
return ;
else
{
AfterTraverse (T->lchild);
AfterTraverse (T->rchild);
printf ("%d", T->data);
}
}
Status visit(TElemType e) {
printf("%d",e);
}
//求深度
int BiTreeDepth(BiTree T){
int dL = 0,dR = 0;
if(NULL == T) return 0;
else{
dL = BiTreeDepth(T->lchild);
dR = BiTreeDepth(T->rchild);
return 1+(dL > dR ? dL : dR);
}
}
//建立二叉樹
BiTree CreatBT ()
{
BiTree t;
int x;
scanf ("%d", &x);
if (x == 0)
{
t = NULL;
}
else
{
t = (BiTree) malloc (sizeof (BiTNode));
t->data = x;
printf ("\n請輸入%d結點的左子結點:", t->data);
t->lchild = CreatBT ();
printf ("\n請輸入%d結點的右子結點:", t->data);
t->rchild = CreatBT ();
}
return t;
}
int main(){
BiTree T;
int i,k;
InitBiTree(T);
printf("正在為您建立二叉樹，請以輸入'0'表示值為空\n");
printf ("請輸入根結點：\n");
//建立一顆二叉樹
T = CreatBT ();
//對用戶輸入的樹判空
i = BiTreeEmpty(T);
if(1 == i){
printf ("該樹為空樹\n");
}else{
printf(" ----------先序遍歷二叉樹 ----------\n");
PreTraverse(T,visit);
printf("\n ----------中序遍歷二叉樹 ----------\n");
MidTraverse(T,visit);
printf("\n ----------後序遍歷二叉樹 ----------\n");
AfterTraverse(T);
printf("\n ----------二叉樹的深度----------\n");
k = BiTreeDepth(T);
printf("%d",k);
BiTree T1,T2;
T1 = T;
printf("\n ----------為您剪掉左子樹----------\n");
CutLeft(T1,T2);
printf("\n ----------剪掉左子樹的先序遍歷二叉樹 ----------\n");
PreTraverse(T1,visit);
printf("\n ----------為您將左子樹接回----------\n");
ReplaceLeft(T1,T2);
printf("\n ----------接回左子樹的先序遍歷二叉樹 ----------\n");
PreTraverse(T1,visit);
printf("\n ----------為您拆散這課二叉樹 ----------\n");
BreakBitree(T,T1,T2);
printf("\n ----------拆散後根節點的先序遍歷二叉樹 ----------\n");
PreTraverse(T,visit);
printf("\n ----------拆散後左子樹的先序遍歷二叉樹 ----------\n");
PreTraverse(T1,visit);
printf("\n ----------拆散後右子樹的先序遍歷二叉樹 ----------\n");
PreTraverse(T2,visit);
printf("\n ----------為您重新組裝這課二叉樹 ----------\n");
BiTree t = MakeBiTree(T->data,T1,T2);
printf("\n ----------組裝後的先序遍歷二叉樹 ----------\n");
PreTraverse(t,visit);
DestoryBiTree(T);
}
while(1){//設置一個死循環，為了不讓程序結束而關閉窗口
}
return 0;
}
測試數據：
預期子樹為：
測試結果為：
