二叉樹(shù)實(shí)驗(yàn)報(bào)告

1、實(shí)驗(yàn)題目：實(shí)驗(yàn)九二叉樹(shù)實(shí)驗(yàn)算法設(shè)計(jì)（3）問(wèn)題分析：1、題目要求：編寫(xiě)算法交換二叉樹(shù)中所有結(jié)點(diǎn)的左右子樹(shù)2、設(shè)計(jì)思路：首先定義一個(gè)二叉樹(shù)的數(shù)據(jù)類(lèi)型，使用先序遍歷建立該二叉樹(shù)，遍歷二叉樹(shù)，設(shè)計(jì)左右子樹(shù)交換的函數(shù)，再次遍歷交換之后的二叉樹(shù)，與先前二叉樹(shù)進(jìn)行比較。遍歷算法與交換算法使用遞歸設(shè)計(jì)更加簡(jiǎn)潔。3、測(cè)試數(shù)據(jù)：A、輸入：1 2 4 0 0 5 0 0 3 0 0交換前中序遍歷：4 2 5 1 3 交換后中序遍歷：3 1 5 2 41234513254交換前：交換后：B、輸入：3 7 11 0 0 18 17 0 0 19 0 0 6 13 0 0 16 0 0交換前中序遍歷：11 7 17 18

2、 19 3 13 6 16 交換后中序遍歷：16 6 13 3 19 18 17 7 11交換前：交換后：376111618131719367161113181917概要設(shè)計(jì)：1、為了實(shí)現(xiàn)上述功能：構(gòu)造一個(gè)空的二叉樹(shù)；應(yīng)用先序遍歷輸入，建立二叉樹(shù)；中序遍歷二叉樹(shù)；調(diào)用左右子樹(shù)交換函數(shù)；中序遍歷交換過(guò)后的二叉樹(shù)。2、本程序包括 4 個(gè)函數(shù)： 主函數(shù) main（） 先序遍歷二叉樹(shù)建立函數(shù) creat_bt（） 中序遍歷二叉樹(shù)函數(shù) inorder（） 左右子樹(shù)交換函數(shù) exchange（）1各函數(shù)間關(guān)系如下：creat_bt（）main（）inorder（）exchange（）詳細(xì)設(shè)計(jì)： 1、結(jié)點(diǎn)類(lèi)

3、型typedef struct binode/定義二叉樹(shù)int data;/數(shù)據(jù)域struct binode *lchild,*rchild;/左孩子、右孩子binode,*bitree; 2、各函數(shù)操作 先序遍歷建二叉樹(shù)函數(shù)bitree creat_bt()輸入結(jié)點(diǎn)數(shù)據(jù)； 判斷是否為 0若是，為空； 不是，遞歸；返回二叉樹(shù)； 左右子樹(shù)交換函數(shù)void exchange(bitree t)判斷結(jié)點(diǎn)是否為空否，交換左右子樹(shù)； 遞歸； 中序遍歷函數(shù)void inorder(bitree bt)判斷是否為空遞歸左子樹(shù)； 輸出；遞歸右子樹(shù)；源 代 碼 ： #include<stdio.h>

4、 #include<malloc.h>typedef struct binode/定義二叉樹(shù)int data;/數(shù)據(jù)域struct binode *lchild,*rchild;/左孩子、右孩子binode,*bitree;bitree creat_bt()/按先序遍歷建二叉樹(shù)bitree t;scanf("%d",&x);if(x=0)t=NULL;/0 表示空結(jié)點(diǎn)elseinode);t->data=x;t->lchild=creat_bt();/遞歸t->rchild=creat_bt();int x;t=(bitree)mall

5、oc(sizeof(breturn t;void exchange(bitree t)/左、右子樹(shù)交換bitree p;if(t!=NULL)/不是空樹(shù)t->rchild=p;/左右交換exchange(t->lchild);/遞歸exchange(t->rchild);p=t->lchild;t->lchild=t->rchild;void inorder(bitree bt)/遞歸的中序遍歷if(bt)inorder(bt->lchild); printf("%d ",bt->data); inorder(bt->r

6、child);void main()bitree root;printf("先序遍歷建立二叉樹(shù)，輸入元素(0 表示空）：n"); root=creat_bt();printf("交換前的中序序列是："); inorder(root);exchange(root);printf("n 交換后的中序序列是："); inorder(root);printf("n");測(cè)試結(jié)果:調(diào)試分析：1、函數(shù)多以遞歸設(shè)計(jì)，雖然大大減輕了代碼上的復(fù)雜度，是思路更加明了， 但也更加容易出錯(cuò)，尤其要注意遞歸函數(shù)出口的設(shè)計(jì)，否則程序難以執(zhí)行。如：If（t!=NULL）即為遞歸函數(shù)出口，當(dāng)結(jié)點(diǎn)為空時(shí)，遞歸函數(shù)結(jié)束；If（bt）為函數(shù)出口，當(dāng) bt 為真時(shí)，執(zhí)