二叉樹實驗報告

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

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

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