二叉樹實驗報告

1、實驗題目：實驗九二叉樹實驗算法設(shè)計（3）問題分析：1、題目要求：編寫算法交換二叉樹中所有結(jié)點的左右子樹2、設(shè)計思路：首先定義一個二叉樹的數(shù)據(jù)類型，使用先序遍歷建立該二叉樹，遍歷二叉樹，設(shè)計左右子樹交換的函數(shù)，再次遍歷交換之后的二叉樹，與先前二叉樹進(jìn)行比較。遍歷算法與交換算法使用遞歸設(shè)計更加簡潔。3、測試數(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è)計：1、為了實現(xiàn)上述功能：構(gòu)造一個空的二叉樹；應(yīng)用先序遍歷輸入，建立二叉樹；中序遍歷二叉樹；調(diào)用左右子樹交換函數(shù)；中序遍歷交換過后的二叉樹。2、本程序包括 4 個函數(shù)： 主函數(shù) main（） 先序遍歷二叉樹建立函數(shù) creat_bt（） 中序遍歷二叉樹函數(shù) inorder（） 左右子樹交換函數(shù) exchange（）1各函數(shù)間關(guān)系如下：creat_bt（）main（）inorder（）exchange（）詳細(xì)設(shè)計： 1、結(jié)點類

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

4、 #include<malloc.h>typedef struct binode/定義二叉樹int data;/數(shù)據(jù)域struct binode *lchild,*rchild;/左孩子、右孩子binode,*bitree;bitree creat_bt()/按先序遍歷建二叉樹bitree t;scanf("%d",&x);if(x=0)t=NULL;/0 表示空結(jié)點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)/左、右子樹交換bitree p;if(t!=NULL)/不是空樹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("先序遍歷建立二叉樹，輸入元素(0 表示空）：n"); root=creat_bt();printf("交換前的中序序列是："); inorder(root);exchange(root);printf("n 交換后的中序序列是："); inorder(root);printf("n");測試結(jié)果:調(diào)試分析：1、函數(shù)多以遞歸設(shè)計，雖然大大減輕了代碼上的復(fù)雜度，是思路更加明了， 但也更加容易出錯，尤其要注意遞歸函數(shù)出口的設(shè)計，否則程序難以執(zhí)行。如：If（t!=NULL）即為遞歸函數(shù)出口，當(dāng)結(jié)點為空時，遞歸函數(shù)結(jié)束；If（bt）為函數(shù)出口，當(dāng) bt 為真時，執(zhí)