二叉树数据结构的实现
（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;
}
测试数据：
预期子树为：
测试结果为：
