數(shù)據(jù)結(jié)構(gòu) 二叉樹(shù)的建立與遍歷

《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告◎?qū)嶒?yàn)題目:二叉樹(shù)的建立與遍歷◎?qū)嶒?yàn)?zāi)康模?、掌握使用VisualC++6.0上機(jī)調(diào)試程序的基本方法；2、掌握二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)和非遞歸遍歷操作的實(shí)現(xiàn)方法。3、提高自己分析問(wèn)題和解決問(wèn)題的能力，在實(shí)踐中理解教材上的理論?！?qū)嶒?yàn)內(nèi)容：利用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)建立二叉樹(shù)，然后先序輸出該二叉樹(shù)的結(jié)點(diǎn)序列，在在本實(shí)驗(yàn)中不使用遞歸的方法，而是用一個(gè)棧存儲(chǔ)結(jié)點(diǎn)的指針，以此完成實(shí)驗(yàn)要求。一、需求分析1、輸入的形式和輸入值的范圍：根據(jù)提示，輸入二叉樹(shù)的括號(hào)表示形式，按回車(chē)結(jié)束。2、輸出的形式：輸出結(jié)果為先序遍歷二叉樹(shù)所得到的結(jié)點(diǎn)序列。3、程序所能達(dá)到的功能：輸入二叉樹(shù)后，該程序可以建立二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，之后按照一定的順序訪問(wèn)結(jié)點(diǎn)并輸出相應(yīng)的值，從而完成二叉樹(shù)的先序遍歷。4、測(cè)試數(shù)據(jù)：輸入二叉樹(shù)的括號(hào)表示形式:A(B(D(,G)),C(E,F))先序遍歷結(jié)果為:ABDGCEF是否繼續(xù)？(是，輸入1;否，輸入0):1輸入二叉樹(shù)的括號(hào)表示形式:二叉樹(shù)未建立是否繼續(xù)？(是，輸入1;否，輸入0):0Pressanykeytocontinue二概要設(shè)計(jì)1、二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是用一個(gè)鏈表來(lái)存儲(chǔ)一棵二叉樹(shù)，二叉樹(shù)中每一個(gè)結(jié)點(diǎn)用鏈表中的一個(gè)鏈結(jié)點(diǎn)來(lái)存儲(chǔ)。每個(gè)結(jié)點(diǎn)的形式如下圖所示。1childdatarchild其中data表示值域，用于存儲(chǔ)對(duì)應(yīng)的數(shù)據(jù)元素，lchild和rchild分別表示左指針域和右指針域，用于分別存儲(chǔ)左孩子結(jié)點(diǎn)和右孩子結(jié)點(diǎn)的存儲(chǔ)位置。2、二叉樹(shù)的建立本程序中利用數(shù)組存儲(chǔ)所輸入的二叉樹(shù)，然后從頭到尾掃描數(shù)組中的每一個(gè)字符根據(jù)字符的不同分別執(zhí)行不同的操作，并用一個(gè)存儲(chǔ)結(jié)點(diǎn)指針的棧輔助完成。在掃描前先申請(qǐng)一個(gè)結(jié)點(diǎn)作為根結(jié)點(diǎn)，也是當(dāng)前指針?biāo)附Y(jié)點(diǎn)，在二叉樹(shù)的建立的過(guò)程中，每次申請(qǐng)一個(gè)新結(jié)點(diǎn)，需對(duì)其進(jìn)行初始化，即令lchild域和rchild域?yàn)榭?。按照本程序的思路，二叉?shù)A(B(D(，G))，C(E，F(xiàn)))的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)如下圖所示。二叉樹(shù)建立的具體過(guò)程見(jiàn)詳細(xì)設(shè)計(jì)部分。3、二叉樹(shù)的先序遍歷在二叉樹(shù)的先序遍歷過(guò)程中也需利用一個(gè)存儲(chǔ)結(jié)點(diǎn)指針的棧輔助完成，初始時(shí)棧為空，二叉樹(shù)遍歷結(jié)束后棧也為空，所以在開(kāi)始時(shí)將頭結(jié)點(diǎn)入棧，之后根據(jù)當(dāng)前指針?biāo)附Y(jié)點(diǎn)的特性的不同執(zhí)行不同的操作，以?？兆鳛槎鏄?shù)遍歷的結(jié)束條件。二叉樹(shù)先序遍歷的具體過(guò)程見(jiàn)詳細(xì)設(shè)計(jì)部分。

4、本程序的基本操作和模塊:建立二叉樹(shù)的函數(shù)：voidCreate(BiTNode*B,SeqStack&K,chars[])遍歷二叉樹(shù)的函數(shù)：voidPreorder(BiTNode*B,SeqStack&K)主函數(shù)：main()函數(shù)的調(diào)用關(guān)系如下圖所示：三詳細(xì)設(shè)計(jì)(一)元素類(lèi)型、結(jié)點(diǎn)類(lèi)型

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

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

if(s[j+1]==',')〃若'('的下一個(gè)字符為','，當(dāng)前結(jié)點(diǎn)p的lchild域?yàn)榭誴->lchild=NULL;else〃若'('的下一個(gè)字符不為',’(q=(BiTNode*)malloc(sizeof(BiTNode));〃申請(qǐng)新結(jié)點(diǎn)qq->lchild=NULL;q->rchild=NULL;〃令新結(jié)點(diǎn)q的lchild域和rchild域?yàn)榭誴->lchild=q;〃令當(dāng)前結(jié)點(diǎn)p的lchild域指向新申請(qǐng)的結(jié)點(diǎn)q

p=q;〃將新申請(qǐng)的結(jié)點(diǎn)q作為新的當(dāng)前結(jié))elseif(s[j]==',')(p=K.pin[K.top];q=(BiTNode*)malloc(sizeof(BiTNode));q->lchild=NULL;q->rchild=NULL;〃若字符為','，執(zhí)行以下操作〃令當(dāng)前結(jié)點(diǎn)p為棧頂元素，但不退棧//申請(qǐng)新結(jié)點(diǎn)q〃令新結(jié)點(diǎn)q的lchild域和rchild域?yàn)榭铡町?dāng)前結(jié)點(diǎn)p的lchild域指向新申請(qǐng)的結(jié)點(diǎn)〃將新申請(qǐng)的結(jié)點(diǎn)q作為新的當(dāng)前結(jié)//若字符為')'，執(zhí)行以下操作〃出棧，令當(dāng)前結(jié)點(diǎn)p為棧頂元素〃若字符為'字母'，執(zhí)行以下操作〃令當(dāng)前結(jié)點(diǎn)p的data〃令當(dāng)前結(jié)點(diǎn)p的lchild域指向新申請(qǐng)的結(jié)點(diǎn)〃將新申請(qǐng)的結(jié)點(diǎn)q作為新的當(dāng)前結(jié)//若字符為')'，執(zhí)行以下操作〃出棧，令當(dāng)前結(jié)點(diǎn)p為棧頂元素〃若字符為'字母'，執(zhí)行以下操作〃令當(dāng)前結(jié)點(diǎn)p的data域?yàn)樵撟帜浮ㄈ粼撟帜傅南乱粋€(gè)字符為'('則令當(dāng)前結(jié)點(diǎn)指針p進(jìn)棧)printf("\n");)//voidPreorder(BiTNode*B,SeqStack&K)(printf(-先序遍歷結(jié)果為:")；BiTNode*p;p=B;K.top++;K.pin[K.top]=p;while(K.top!=-1)〃遍歷二叉樹(shù)函數(shù)〃提示以下結(jié)果為先序遍歷結(jié)果//p指針指向當(dāng)前結(jié)點(diǎn)〃當(dāng)前結(jié)點(diǎn)為根結(jié)點(diǎn)〃令當(dāng)前結(jié)點(diǎn)指針p進(jìn)棧〃當(dāng)棧不為空時(shí)執(zhí)行以下操作(〃出棧，棧頂元素所指的結(jié)點(diǎn)作為當(dāng)前結(jié)點(diǎn)p〃輸出當(dāng)前結(jié)點(diǎn)p中的字母〃若當(dāng)前結(jié)點(diǎn)p的右孩子不為空，則令當(dāng)前結(jié)點(diǎn)p的右孩子進(jìn)?！ㄈ舢?dāng)前結(jié)點(diǎn)p的左孩子不為空，則令當(dāng)前結(jié)點(diǎn)p的左孩子進(jìn)?！ǔ鰲?，棧頂元素所指的結(jié)點(diǎn)作為當(dāng)前結(jié)點(diǎn)p〃輸出當(dāng)前結(jié)點(diǎn)p中的字母〃若當(dāng)前結(jié)點(diǎn)p的右孩子不為空，則令當(dāng)前結(jié)點(diǎn)p的右孩子進(jìn)?！ㄈ舢?dāng)前結(jié)點(diǎn)p的左孩子不為空，則令當(dāng)前結(jié)點(diǎn)p的左孩子進(jìn)棧)printf("\n");)//intmain()(chars[40];〃定義數(shù)組，存儲(chǔ)輸入的字符串inti;BiTNode*B;〃定義根結(jié)點(diǎn)，并申請(qǐng)存儲(chǔ)空間B=(BiTNode*)malloc(sizeof(BiTNode));SeqStackK;〃定義棧并初始化棧K.t