二叉树的实现数据结构

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

}

测试数据：预期子树为：

测试结果为：