北理工數(shù)據(jù)結(jié)構(gòu)實驗遍歷二叉樹

北京鏗兀大孝本科實驗報告實驗名稱：遍歷二叉樹 課程名稱：數(shù)據(jù)結(jié)構(gòu)實驗時間：任課教師：實驗地點：良鄉(xiāng)機房實驗教師：實驗類型：□原理驗證■綜合設(shè)計□自主創(chuàng)新學(xué)生姓名：學(xué)號班級：組 號：學(xué) 院：同組搭檔：專 業(yè)：成 績：信息與電子學(xué)院、實驗?zāi)康?、 熟悉VC環(huán)境，學(xué)習(xí)使用C語言實現(xiàn)樹的基本操作。2、 通過編程、上機調(diào)試，進一步理解數(shù)、二叉數(shù)、拓展二叉數(shù)的基本概念。3、 了解并熟悉二叉數(shù)的存儲結(jié)構(gòu)及其各種操作，掌握各種二叉數(shù)的遍歷方法。4、 鍛煉動手編程，獨立思考的能力。二、 實驗題目遍歷二叉樹（1）問題描述遍歷二叉樹：要求：請輸入一棵二叉樹的擴展的前序序列，經(jīng)過處理后生成一棵二叉樹，然后對于該二叉樹輸出前序、中序和后序遍歷序列。例如：124*5***3**三、 實驗基礎(chǔ)知識線性表、二叉樹的基本概念的熟練掌握并實際運用。并了解創(chuàng)建樹、遍歷二叉樹的思想解決問題的能力四、 實驗設(shè)計方法1、概要設(shè)計為實現(xiàn)上述程序功能，首先需要二叉樹的抽象數(shù)據(jù)結(jié)構(gòu)。⑴二叉樹的抽象數(shù)據(jù)類型定義為：ADTBinaryTree{數(shù)據(jù)對象D：D是具有相同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系R：若D二①，則R二①，稱BinaryTree為空二叉樹；若D工①，則R={H},H是如下二元關(guān)系；在D中存在惟一的稱為根的數(shù)據(jù)元素root,它在關(guān)系H下無前驅(qū)；若D-{root}工①，則存在D-{root}二{Dl,Dr}，且DlPlDr二①；若D1工①，則D1中存在惟一的元素xl,〈root,xl〉WH,且存在D1上的關(guān)系HlUH；若Dr工①，則Dr中存在惟一的元素xr，＜root,xr〉WH,且存在上的關(guān)系HrUH；H二{〈root,x1〉，〈root,xr〉，H1,Hr}；(D1,{H1})是一棵符合本定義的二叉樹，稱為根的左子樹；(Dr,{Hr})是一棵符合本定義的二叉樹，稱為根的右子樹?；静僮鳎篊reateTree(&T)操作結(jié)果：按先序次序建立二叉鏈表表示的二叉樹TPreOrderTraverse(T,Visit())初始條件：二叉樹T已經(jīng)存在‘visit是對結(jié)點操作的應(yīng)用函數(shù)操作結(jié)果：先序遍歷二叉樹T,對每個結(jié)點調(diào)用visit函數(shù)僅一次；一旦visit()失敗，則操作失敗。InOrderTraverse(T,Visit())初始條件：二叉樹T已經(jīng)存在‘visit是對結(jié)點操作的應(yīng)用函數(shù)操作結(jié)果：中序遍歷二叉樹T,對每個結(jié)點調(diào)用visit函數(shù)僅一次；一旦visit()失敗，則操作失敗。PostOrderTraverse(T,Visit)())初始條件：二叉樹T已經(jīng)存在’visit是對結(jié)點操作的應(yīng)用函數(shù)操作結(jié)果：后序遍歷二叉樹T,對每個結(jié)點調(diào)用visit函數(shù)僅一次；一旦visit()失敗，則操作失敗。}ADTBinaryTree(2)、宏定義#defineok1#defineerror0(3)主程序流程主程序先調(diào)用CreateTree(BiTree&T)函數(shù)，根據(jù)輸入的先序序列構(gòu)造出一棵二叉樹，再依次調(diào)用PreOrderTraverse(BiTreeT,int(*visit)(chare))，InOrderTraverse(BiTreeT,int(*visit)(chare))，PostOrderTraverse(BiTreeT,int(*visit)(chare))函數(shù)，對該二叉樹進行先序、中序、后序遍歷并輸出結(jié)果。模塊調(diào)用關(guān)系由主函數(shù)調(diào)用創(chuàng)建模塊，再調(diào)用計算模塊，由計算模塊將結(jié)果輸出。流程圖五、實驗結(jié)果及數(shù)據(jù)分析331422碎ithreturnvalue1:叉樹的先序序列：11叉樹的電序序列：4:義樹的丿【331422碎ithreturnvalue1Processexitedafter2.1seconds請按任意犍繼續(xù)???■2、]23**4**5***■'C:\Users\Sunsky\Deskto鵝結(jié)構(gòu)圖據(jù)結(jié)構(gòu)程員遍歷ZS^fc.exe4151叉樹的先序序列：1415:叉樹的中序序列:3:叉樹的后序序列:3Processexitedafter9.206secondswithreturnvalue1請按任意鍵繼續(xù)???六、總結(jié)此次編程實驗，讓我了解到全面思考的重要性，再開始的程序設(shè)計中，我只想著直接建立樹，沒想到用隊列輔助，在開始的時候一直測試失敗，這讓我想到知識是相互聯(lián)系的，必須全面學(xué)習(xí)。七、附錄程序清單

#include"stdio.h"#include"stdlib.h"#defineok1#defineerror0/*二叉鏈表的結(jié)點*/typedefstructBiTNode{chardata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;/*隊列*/typedefBiTreeQElemType;//定義隊列元素類型typedefstructQNode{//定義隊列結(jié)點QElemTypedata;structQNode*next;}QNode,*QueuePtr;typedefstruct//定義隊列結(jié)點QueuePtrfront;QueuePtrrear;}LinkQueue;//定義隊列數(shù)據(jù)類型charc; //輸入的字符/*創(chuàng)建隊列*/intInitQueue(LinkQueue&Q){Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(1); //存儲分配失敗Q.front->next=NULL;returnok;}/*插入元素e作為新的隊尾元素*/intEnQueue(LinkQueue&Q,QElemTypee){QNode*p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(1);p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;returnok;}/*刪除隊頭元素并以e返回*/intDeQueue(LinkQueue&Q,QElemType&e){if(Q.front==Q.rear)returnerror;QNode*p=Q.front->next;e=p->data;Q.front->next=p->next;if(Q.rear==p)Q.rear=Q.front;free(p);returnok;}/*建立二叉樹*/intCreateTree(BiTree&T){c=getchar();if(c=='*')T=NULL;else{T=(BiTree)malloc(sizeof(BiTNode));if(!T){printf("ERROE\n");exit(1);}T->data=c;CreateTree(T->lchild); //遞歸建立左子樹CreateTree(T->rchild); //遞歸建立右子樹}returnok;}intVisit(chare){printf("%c",e);returnok;}/*先序遍歷二叉樹*/intPreOrderTraverse(BiTreeT,int(*Visit)(charc)){if(T)

//先序遍歷左子樹//先序遍歷左子樹//先序遍歷右子樹PreOrderTraverse(T->lchild,Visit);

PreOrderTraverse(T->rchild,Visit);}returnok;}/*中序遍歷二叉樹*/intInOrderTraverse(BiTreeT,int(*Visit)(charc)){if(T){InOrderTraverse(T->lchild,Visit); //中序遍歷左子樹Visit(T->data);InOrderTraverse(T->rchild,Visit); //中序遍歷右子樹}returnok;}/*后序遍歷二叉樹*/intPostOrderTraverse(BiTreeT,int(*Visit)(charc)){if(T){PostOrderTraverse(T->lchild,Visit);//后序遍歷左子樹PostOrderTraverse(T->rchild,Visit); //后序遍歷右子樹Visit(T->data);}returnok;}intmain(){BiTreeT;printf(“輸入二叉樹的擴展的前序序列\(zhòng)n");CreateTree(T);pr