（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

#include

#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;