（1）任務(wù)為：抽象數(shù)據(jù)類型的實(shí)現(xiàn)；本次任務(wù)用了devcpp程序作為開發(fā)軟件，編寫語言為C語言。

成都創(chuàng)新互聯(lián)公司主要從事成都網(wǎng)站設(shè)計(jì)、網(wǎng)站建設(shè)、網(wǎng)頁設(shè)計(jì)、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務(wù)。立足成都服務(wù)博山,十載網(wǎng)站建設(shè)經(jīng)驗(yàn),價(jià)格優(yōu)惠、服務(wù)專業(yè),歡迎來電咨詢建站服務(wù):18982081108

（2）二叉樹是一種遞歸數(shù)據(jù)結(jié)構(gòu)。二叉樹是含有n(n>=0)個(gè)節(jié)點(diǎn)的有限集合。當(dāng)n=0時(shí)稱為空二叉樹。在非空二叉樹中：（1）有且僅有一個(gè)稱為根的節(jié)點(diǎn)（2）當(dāng)n>1時(shí)，其余節(jié)點(diǎn)劃分為兩個(gè)互不相交的子集L和R,其中L和R也是一課二叉樹，分別稱為左子樹和右子樹，且其次序不能顛倒。

二叉樹的基本操作有：

1、Status InitBiTree(BiTree &T)即創(chuàng)建一棵空二叉樹

2、BiTree MakeBiTree(TElemType e,BiTree L,BiTree R)即創(chuàng)建一棵二叉樹T,其中根節(jié)點(diǎn)的值為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分解成根、左子樹和右子樹三個(gè)部分

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）所選的存儲結(jié)構(gòu)為鏈?zhǔn)酱鎯?，其中包含一個(gè)數(shù)據(jù)域和兩個(gè)左右孩子指針。各基本操作的實(shí)現(xiàn)：

1、Status InitBiTree(BiTree &T)操作中通過T=(BiTree)malloc(sizeof(BiTNode));給樹開辟一塊空間實(shí)現(xiàn)創(chuàng)建一棵空二叉樹

2、BiTree MakeBiTree(TElemType e,BiTree L,BiTree R)中，通過t->data = e;t->lchild = L;t->rchild = R;實(shí)現(xiàn)令L、R成為t的左右子樹

3、void DestoryBiTree(BiTree &T)則直接通過free(T);釋放內(nèi)存空間來達(dá)到銷毀樹

4、Status BiTreeEmpty(BiTree &T)中如果NULL==T,即樹中沒有內(nèi)容，則判斷為空樹

5、Status BreakBitree(BiTree &T,BiTree &L,BiTree &R)通過        L = T->lchild;R = T->rchild;來將結(jié)構(gòu)體T所指向的左右子樹分別賦給L和R樹。

6、Status ReplaceLeft(BiTree &T,BiTree <)通過t = T->lchild;T->lchild = LT;LT = t使T的左子樹變?yōu)橹赶騆T,即LT成為T的左子樹，從而達(dá)到替換作用

7、Status ReplaceRight(BiTree &T,BiTree &RT)原理與上一步相同

8、Status CutLeft(BiTree &T,BiTree <)通過LT = T->lchild;T->lchild = NULL使LT的存儲位置變?yōu)門->lchild，而T->lchild 的存儲位置變?yōu)镹ULL

9、Status CutRight(BiTree &T,BiTree &RT)原理與上一步相同

10、Status PreTraverse(BiTree T,Status(*visit)(TElemType e))先序遍歷通過遞歸的方法，每進(jìn)入一層遞歸 先visit(T->data)即先訪問根節(jié)點(diǎn)，再進(jìn)入PreTraverse(T->lchild,visit)左子樹的一層遞歸訪問，再進(jìn)入PreTraverse(T->rchild,visit)右子樹

11、Status MidTraverse(BiTree T,Status(*visit)(TElemType e))中序遍歷，先進(jìn)入左子樹的最底層MidTraverse(T->lchild,visit)訪問，接著回訪問根節(jié)點(diǎn)visit(T->data)，再進(jìn)入右子樹最底層MidTraverse(T->rchild,visit)訪問，再逐層上升訪問。

12、void AfterTraverse(BiTree T)后序遍歷則先進(jìn)入左子樹最底層 AfterTraverse (T->lchild);訪問，再進(jìn)入右子樹最底層AfterTraverse (T->rchild);訪問，然后再訪問根節(jié)點(diǎn)，再逐層上升訪問。

15、int BiTreeDepth(BiTree T)求樹的深度，根節(jié)點(diǎn)獨(dú)占一層，所以二叉樹的深度為其左右子樹深度的大值加1，判斷到達(dá)最底層時(shí)NULL == T就返回上一層，逐層上升加1

16、BiTree CreatBT ()建立二叉樹。用戶先輸入根節(jié)點(diǎn)信息，此時(shí)如果用戶輸入0，則令t=NULL,即不存儲任何信息，當(dāng)輸入非0時(shí)，鏈表中t->data的信息域即存儲為該用戶輸入的信息，接著用戶輸入左子樹信息，進(jìn)入一層遞歸，此時(shí)該信息為t->lchild信息域的內(nèi)容，當(dāng)輸入為0則返回上一層，問右子樹的信息，此時(shí)該信息為t->rchild信息域的內(nèi)容,以此類推。

以下為源碼：

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

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結(jié)點(diǎn)的左子結(jié)點(diǎn):", t->data);

      t->lchild = CreatBT ();

      printf ("\n請輸入%d結(jié)點(diǎn)的右子結(jié)點(diǎn):", t->data);

      t->rchild = CreatBT ();

    }

  return t;

}

int main(){

BiTree T;

int i,k;

    InitBiTree(T);

    printf("正在為您建立二叉樹，請以輸入'0'表示值為空\n");

    printf ("請輸入根結(jié)點(diǎn)：\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 ----------拆散后根節(jié)點(diǎ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){//設(shè)置一個(gè)死循環(huán)，為了不讓程序結(jié)束而關(guān)閉窗口

}

return 0;

}

測試數(shù)據(jù)：預(yù)期子樹為：

測試結(jié)果為：

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

新聞名稱：二叉樹的實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)-創(chuàng)新互聯(lián)
URL標(biāo)題：http://weahome.cn/article/codddo.html