《數據結構》實驗報告◎實驗題目:二叉樹的建立與遍歷◎實驗目的：1、掌握使用VisualC++6.0上機調試程序的基本方法；2、掌握二叉樹的存儲結構和非遞歸遍歷操作的實現方法。3、提高自己分析問題和解決問題的能力，在實踐中理解教材上的理論。◎實驗內容：利用鏈式存儲結構建立二叉樹，然后先序輸出該二叉樹的結點序列，在在本實驗中不使用遞歸的方法，而是用一個棧存儲結點的指針，以此完成實驗要求。一、需求分析1、輸入的形式和輸入值的范圍：根據提示，輸入二叉樹的括號表示形式，按回車結束。2、輸出的形式：輸出結果為先序遍歷二叉樹所得到的結點序列。3、程序所能達到的功能：輸入二叉樹后，該程序可以建立二叉樹的鏈式存儲結構，之后按照一定的順序訪問結點并輸出相應的值，從而完成二叉樹的先序遍歷。4、測試數據：輸入二叉樹的括號表示形式:A(B(D(,G)),C(E,F))先序遍歷結果為:ABDGCEF是否繼續？(是，輸入1;否，輸入0):1輸入二叉樹的括號表示形式:二叉樹未建立是否繼續？(是，輸入1;否，輸入0):0Pressanykeytocontinue二概要設計1、二叉樹的鏈式存儲結構是用一個鏈表來存儲一棵二叉樹，二叉樹中每一個結點用鏈表中的一個鏈結點來存儲。每個結點的形式如下圖所示。1childdatarchild其中data表示值域，用于存儲對應的數據元素，lchild和rchild分別表示左指針域和右指針域，用于分別存儲左孩子結點和右孩子結點的存儲位置。2、二叉樹的建立本程序中利用數組存儲所輸入的二叉樹，然后從頭到尾掃描數組中的每一個字符根據字符的不同分別執行不同的操作，并用一個存儲結點指針的棧輔助完成。在掃描前先申請一個結點作為根結點，也是當前指針所指結點，在二叉樹的建立的過程中，每次申請一個新結點，需對其進行初始化，即令lchild域和rchild域為空。按照本程序的思路，二叉樹A(B(D(，G))，C(E，F))的鏈式存儲結構如下圖所示。二叉樹建立的具體過程見詳細設計部分。3、二叉樹的先序遍歷在二叉樹的先序遍歷過程中也需利用一個存儲結點指針的棧輔助完成，初始時棧為空，二叉樹遍歷結束后棧也為空，所以在開始時將頭結點入棧，之后根據當前指針所指結點的特性的不同執行不同的操作，以棧空作為二叉樹遍歷的結束條件。二叉樹先序遍歷的具體過程見詳細設計部分。

4、本程序的基本操作和模塊:建立二叉樹的函數：voidCreate(BiTNode*B,SeqStack&K,chars[])遍歷二叉樹的函數：voidPreorder(BiTNode*B,SeqStack&K)主函數：main()函數的調用關系如下圖所示：三詳細設計(一)元素類型、結點類型

1、二叉樹結點的類型描述/*二叉樹結點的類型描述*//*data用于存儲二叉樹中的字母*//*lchild為指向該結點左孩子的指針*//*rchild為指向該結點下一層的指針*/typedefstructnode{chardata;structnode*lchild;structnode*rchild;}BiTNode;/*二叉樹結點的類型描述*//*data用于存儲二叉樹中的字母*//*lchild為指向該結點左孩子的指針*//*rchild為指向該結點下一層的指針*//*順序棧的類型描述*//*指針數組，用于存儲廣義表結點指針*//*棧頂指針*/2、順序棧的類型描述typedefstruct{BiTNode*pin[40];inttop;}SeqStack;/*順序棧的類型描述*//*指針數組，用于存儲廣義表結點指針*//*棧頂指針*/(二)每個模塊的分析1、主程序模塊main(){定義數組，存儲輸入的字符串定義并申請根結點初始化順序棧while(1){調用建立二叉樹的函數，建立二叉樹的鏈式存儲結構調用遍歷二叉樹的函數，輸出所建立的二叉樹的結點選擇是否繼續，若是，則重新執行循環中的操作；若否，則退出循環}}2、建立二叉樹的函數voidCreate(BiTNode*B,SeqStack&K,chars[]){定義表示當前結點的指針p，和表示新申請結點的指針q令p指向根結點，根結點的lchild域和rchild域為空。輸入二叉樹從頭到尾掃描輸入的字符，進入以下循環，當遇到空字符時結束循環for(j=0;s[j]!='\0';j++){◎若字符為'('，執行以下操作{若'('的下一個字符為','，當前結點p的lchild域為空若'('的下一個字符不為','則執行以下的操作：{申請新結點q,并令新結點q的lchild域和rchild域為空令當前結點p的Ichild域指向新申請的結點q將新申請的結點q作為新的當前結點p}}◎若字符為','，執行以下操作{令當前結點p為棧頂元素，但不退棧申請新結點q，并令新結點q的Ichild域和rchild域為空令當前結點p的rchild域指向新申請的結點q將新申請的結點q作為新的當前結點p}◎若字符為')'，執行以下操作{出棧，令當前結點p為棧頂元素}◎若字符為字母，執行以下操作{令當前結點p的data域為該字母若該字母的下一個字符為'('則令當前結點指針p進棧}}}3、遍歷二叉樹的函數voidDisplay(GLNode*G,SeqStack&K){定義表示當前結點的指針p，并令p指根結點。指向根結點的指針p入棧，使棧不空'。當棧不空時執行以下操作while(K.top!=-1){出棧，棧頂元素所指的結點作為當前結點p，輸出當前結點p中的字母若當前結點p的右孩子不為空，則令當前結點p的右孩子進棧若當前結點p的左孩子不為空，則令當前結點p的左孩子進棧}}四使用說明、測試分析及結果1、程序使用說明：本程序運行環境為VisualC++6.0；根據界面提示進行操作，注意輸入的字符為西文字符2、測試結果與分析：頁面提示“輸入二叉樹的括號表示形式:”輸入“A(B(D(,G)),C(E,F))”，按回車確定，頁面顯示如下：“先序遍歷結果為:ABDGCEF是否繼續？（是，輸入1；否，輸入0）:”輸入序號“1”，按回車確定，表示繼續操作。頁面提示“輸入二叉樹的括號表示形式:”不輸入二叉樹，直接按回車確定，則頁面顯示如下：“二叉樹未建立是否繼續？（是,輸入1；否，輸入0）:”輸入序號“0”，按回車確定，表示結束操作，頁面顯示如下：“Pressanykeytocontinue”由上測試結果分析得，該程序功能滿足題目要求。3、調試過程中遇到的問題及解決方法當代碼編寫完成后，編譯過程出現了很多小錯誤，比如語句末尾漏掉分號，使用了某些變量卻未定義，但這些問題很快發現并及時糾正。總的來說，因為本次實驗和廣義表的建立和輸出有相似之處，所以避免了很多問題，比較順利。4、運行界面五、實驗總結本次實驗提前作了預習，在編寫程序上花費的時間不算太多，我在11月1日下午完成代碼的編寫并修改正確。因為本次實驗和廣義表的建立和輸出有相似之處，所以大的問題基本沒有出現，一些小的問題也及時發現并糾正。本次實驗，我很感謝老師和同學對我的指點。通過本次實驗，對二叉樹的存儲結構有了更深的認識，對一些細節更加理解，收獲了很多。教師評語:

指導教師簽名:批閱日期：指導教師簽名:批閱日期：代碼：include<stdio.h>include<stdlib.h>//typedefstructnode〃二叉樹結點的類型描述(chardata;//data用于存儲二叉樹中的字母structnode*lchild;//lchild為指向該結點左孩子的指針structnode*rchild;//rchild為指向該結點下一層的指針}BiTNode;//typedefstruct〃順序棧的類型描述(BiTNode*pin[40];〃指針數組，用于存儲廣義表結點指針inttop;〃棧頂指針}SeqStack;//voidCreate(BiTNode*B,SeqStack&K,chars[])〃建立二叉樹的函數(BiTNode*p,*q;//p指針指向當前結點,q指針指向新申請的結點intj;//j用于標記輸入的字符在數組中的位置printf("輸入二叉樹的括號表示形式:");〃提示輸入二叉樹gets(s);p=B;p->lchild=NULL;p->rchild=NULL;for(j=0;s[j]!='\0';j++)〃當前結點為根結點〃根結點的lchild域和p=B;p->lchild=NULL;p->rchild=NULL;for(j=0;s[j]!='\0';j++)〃當前結點為根結點〃根結點的lchild域和rchild域為空〃進入循環，建立二叉樹(

if(s[j+1]==',')〃若'('的下一個字符為','，當前結點p的lchild域為空p->lchild=NULL;else〃若'('的下一個字符不為',’(q=(BiTNode*)malloc(sizeof(BiTNode));〃申請新結點qq->lchild=NULL;q->rchild=NULL;〃令新結點q的lchild域和rchild域為空p->lchild=q;〃令當前結點p的lchild域指向新申請的結點q

p=q;〃將新申請的結點q作為新的當前結)elseif(s[j]==',')(p=K.pin[K.top];q=(BiTNode*)malloc(sizeof(BiTNode));q->lchild=NULL;q->rchild=NULL;〃若字符為','，執行以下操作〃令當前結點p為棧頂元素，但不退棧//申請新結點q〃令新結點q的lchild域和rchild域為空〃令當前結點p的lchild域指向新申請的結點〃將新申請的結點q作為新的當前結//若字符為')'，執行以下操作〃出棧，令當前結點p為棧頂元素〃若字符為'字母'，執行以下操作〃令當前結點p的data〃令當前結點p的lchild域指向新申請的結點〃將新申請的結點q作為新的當前結//若字符為')'，執行以下操作〃出棧，令當前結點p為棧頂元素〃若字符為'字母'，執行以下操作〃令當前結點p的data域為該字母〃若該字母的下一個字符為'('則令當前結點指針p進棧)printf("\n");)//voidPreorder(BiTNode*B,SeqStack&K)(printf(-先序遍歷結果為:")；BiTNode*p;p=B;K.top++;K.pin[K.top]=p;while(K.top!=-1)〃遍歷二叉樹函數〃提示以下結果為先序遍歷結果//p指針指向當前結點〃當前結點為根結點〃令當前結點指針p進棧〃當棧不為空時執行以下操作(〃出棧，棧頂元素所指的結點作為當前結點p〃輸出當前結點p中的字母〃若當前結點p的右孩子不為空，則令當前結點p的右孩子進棧〃若當前結點p的左孩子不為空，則令當前結點p的左孩子進棧〃出棧，棧頂元素所指的結點作為當前結點p〃輸出當前結點p中的字母〃若當前結點p的右孩子不為空，則令當前結點p的右孩子進棧〃若當前結點p的左孩子不為空，則令當前結點p的左孩子進棧)printf("\n");)//intmain()(chars[40];〃定義數組，存儲輸入的字符串inti;BiTNode*B;〃定義根結點，并申請存儲空間B=(BiTNode*)malloc(sizeof(BiTNode));SeqStackK;〃定義棧并初始化棧K.t