實驗三 二叉樹的遍歷一、實驗目的１、熟悉二叉樹的結點類型和二叉樹的基本操作。２、掌握二叉樹的前序、中序和后序遍歷的算法。3、加深對二叉樹的理解，逐步培養解決實際問題的編程能力。二、實驗環境運行Ｃ或 VC++的微機。三、實驗內容1、依次輸入元素值，以鏈表方式建立二叉樹，并輸出結點的值。2、分別以前序、中序和后序遍歷二叉樹的方式輸出結點內容。四、設計思路對于這道題，我的設計思路是先做好各個分部函數，然后在主函數中進行順序排列，以此完成實驗要求2．二叉樹采用動態數組3.二叉樹運用 9個函數，主要有主函數、構建空二叉樹函數、建立二叉樹函數、訪問節點函數、銷毀二叉樹函數、先序函數、中序函數、后序函數、范例函數，關鍵在于訪問節點五、程序代碼#include<stdio.h>#include<stdlib.h>#include<malloc.h>#defineOK1#defineERROR0typedefstructTNode//{

結構體定義intdata;// 數據域structTNode*lchild,*rchild;//

指針域包括左右孩子指針}TNode,*Tree;voidCreateT(Tree*T)//

創建二叉樹按

,依次輸入二叉樹中結點的值{inta;scanf("%d",&a);if(a==00)// 結點的值為空*T=NULL;else// 結點的值不為空{*T=(Tree)malloc(sizeof(TNode));if(!T){printf("

分配空間失敗！

！

TAT");exit(ERROR);}(*T)->data=a;CreateT(&((*T)->lchild));//CreateT(&((*T)->rchild));//

遞歸調用函數，構造左子樹遞歸調用函數，構造右子樹}}voidInitT(Tree*T)//{

構建空二叉樹T=NULL;}voidDestroyT(Tree*T)//{

銷毀二叉樹if(*T)//{

二叉樹非空DestroyT(&((*T)->lchild));//DestroyT(&((*T)->rchild));//free(T);T=NULL;

遞歸調用函數，銷毀左子樹遞歸調用函數，銷毀右子樹}}voidvisit(inte)//{

訪問結點printf("%d",e);}voidPreOrderT(Tree*T,void(*visit)(int))//

先序遍歷

T{if(*T)//{

二叉樹非空visit((*T)->data);//

先訪問根結點PreOrderT(&((*T)->lchild),visit);//PreOrderT(&((*T)->rchild),visit);//

遞歸調用函數，先序遍歷左子樹遞歸調用函數，先序遍歷右子樹}}voidInOrderT(Tree*T,void(*visit)(int)){if(*T){InOrderT(&((*T)->lchild),visit);//

遞歸調用函數，中序遍歷左子樹visit((*T)->data);//

訪問根結點InOrderT(&((*T)->rchild),visit);//

遞歸調用函數，中序遍歷右子樹}}voidPostOrderT(Tree*T,void(*visit)(int)){if(*T){PostOrderT(&((*T)->lchild),visit);//PostOrderT(&((*T)->rchild),visit);//visit((*T)->data);// 訪問根結點

遞歸調用函數遞歸調用函數

,后序遍歷左子樹,序遍歷右子樹}}voidexample(){inti;printf("

如果你想建立如圖所示的二叉樹

\n");printf("\n");printf("printf("printf("printf("printf("

4

/

3

1/ \\\\5

3

\\

7

\n");\n");\n");\n");\n");printf("\n");printf("

請輸入：

13400005000030070000\n");printf("\n

按先序次序輸入二叉樹中結點的值

(

輸入

00表示節點為空

)\n");for(i=0;i<71;i++)printf("*");printf("\n");}intmain(){TreeT;printf("************** 歡迎使用！ ************** 潘俊達\n");example();printf("\n 請輸入所要建立的二叉樹 :\n");CreateT(&T);InitT(&T);inti;printf(" 先序遍歷二叉樹： \n");PreOrderT(&T,visit);printf("\n");printf("\n 中序遍歷二叉樹： \n");InOrderT(&T,visit);printf("\n");printf("\n 后序遍歷二叉樹： \n");