數(shù)據(jù)結(jié)構(gòu)-二叉樹的建

數(shù)據(jù)結(jié)構(gòu)-二叉樹的建立與遍歷《數(shù)據(jù)結(jié)構(gòu)》實驗報告◎?qū)嶒烆}目:二叉樹的建立與遍歷◎?qū)嶒災康模?、掌握使用VisualC++6.0上機調(diào)試程序的基本方法；iwJ2、 掌握二叉樹的存儲結(jié)構(gòu)和非遞歸遍歷操作的實現(xiàn)方法。iwJ3、 提高自己分析問題和解決問題的能力，在實踐中理解教材上的理論?！?qū)嶒瀮?nèi)容：利用鏈式存儲結(jié)構(gòu)建立二叉樹，然后先序輸出該二叉樹的結(jié)點序列，在在本實驗中不使用遞歸的方法，而是用一個棧存儲結(jié)點的指針，以此完成實驗要求。一、需求分析1、 輸入的形式和輸入值的范圍：根據(jù)提示，輸入二叉樹的括號表示形式，按回車結(jié)束。2、 輸出的形式：輸出結(jié)果為先序遍歷二叉樹所得到的結(jié)點序列。3、 程序所能達到的功能：輸入二叉樹后，該程序可以建立二叉樹的鏈式存儲結(jié)構(gòu)，之后按照一定的順序訪問結(jié)點并輸出相應的值，從而完成二叉樹的先序遍歷。4、 測試數(shù)據(jù)：

輸入二叉樹的括號表示形式:A(B(D(,G)),C(E,F))iwJ先序遍歷結(jié)果為:ABDGCEFiwJ是否繼續(xù)？(是,輸入1;否,輸入0):1輸入二叉樹的括號表示形式:二叉樹未建立是否繼續(xù)？(是,輸入1;否,輸入0):0Pressanykeytocontinue二概要設(shè)計1、二叉樹的鏈式存儲結(jié)構(gòu)是用一個鏈表來存儲一棵二叉樹，二叉樹中每一個結(jié)點用鏈表中的一個鏈結(jié)點來存儲。每個結(jié)點的形式如下圖所示。IchilddataIchilddatarchild其中data表示值域，用于存儲對應的數(shù)據(jù)元素，lchild和rchild分別表示左指針域和右指針域，用于分別存儲左孩子結(jié)點和右孩子結(jié)點的存儲位置。2、二叉樹的建立本程序中利用數(shù)組存儲所輸入的二叉樹，然后從頭到尾掃描數(shù)組中的每一個字符根據(jù)字符的不同分別執(zhí)行不同的操作，并用一個存儲結(jié)點指針的棧輔助完成。在掃描前先申請一個結(jié)點作為根結(jié)點，也是當前指針所指結(jié)點，在二叉樹的建立的過程中，每次申請一個新結(jié)點，需對其進行初始化，即令I(lǐng)child域和rchild域為空。按照本程序的思路，二叉樹A（B（D（，G）），C（E，F(xiàn)））的鏈式存儲結(jié)構(gòu)如下圖所示。二叉樹建立的具體過程見詳細設(shè)計部分。liiiJ3、二叉樹的先序遍歷liiiJlii-J在二叉樹的先序遍歷過程中也需利用一個存儲結(jié)點指針的棧輔助完成，初始時棧為空，二叉樹遍歷結(jié)束后棧也為空，所以在開始時將頭結(jié)點入棧，之后根據(jù)當前指針所指結(jié)點的特性的不同執(zhí)行不同的操作，以棧空作為二叉樹遍歷的結(jié)束條件。二叉樹先序遍歷的具體過程見詳細設(shè)計部分。

lii-JA(B(DG))；C(E；F))4、本程序的基本操作和模塊:建立二叉樹的函數(shù)：voidCreate(BiTNode*B,SeqStack&K,chars[])遍歷二叉樹的函數(shù)：voidPreorder(BiTNode*B,SeqStack&K)主函數(shù)：main()函數(shù)的調(diào)用關(guān)系如下圖所示:三詳細設(shè)計（一）元素類型、結(jié)點類型1、二叉樹結(jié)點的類型描述typedefstructnode /*二叉樹結(jié)點的類型描述*/{chardata;/*data用于存儲二叉樹中的字母*/structnode*lchild;/*lchild為指向該結(jié)點左孩子的指針*/

structnode*rchild;/*rchild為指向該結(jié)點下一層的指針*/}BiTNode;/*順序棧的類型2、順序棧的類型描述/*順序棧的類型typedefstruct描述*/{/*指針數(shù)組，用BiTNode*pin[40];/*指針數(shù)組，用于存儲廣義表結(jié)點指針*/inttop; /*棧頂指針*/}SeqStack;(二)每個模塊的分析1、主程序模塊main。{定義數(shù)組，存儲輸入的字符串定義并申請根結(jié)點初始化順序棧while(1){調(diào)用建立二叉樹的函數(shù)，建立二叉樹的鏈式存儲結(jié)構(gòu)iwJ調(diào)用遍歷二叉樹的函數(shù)，輸出所建立的二叉樹的結(jié)點iwJ選擇是否繼續(xù)，若是，則重新執(zhí)行循環(huán)中的操作；若否，則退出循環(huán)}}2、建立二叉樹的函數(shù)voidCreate(BiTNode*B,SeqStack&K,chars[]){定義表示當前結(jié)點的指針p，和表示新申請結(jié)點的指針q令p指向根結(jié)點，根結(jié)點的lchild域和rchild域為空。輸入二叉樹從頭到尾掃描輸入的字符，進入以下循環(huán)，當遇到空字符時結(jié)束循環(huán)for(j=0;s[j]!='\0';j++){◎若字符為'('，執(zhí)行以下操作

若'('的下一個字符為','，當前結(jié)點p的Ichild域為空若'('的下一個字符不為','則執(zhí)行以下的操作：{申請新結(jié)點q,并令新結(jié)點q的Ichild域和rchild域為空令當前結(jié)點p的Ichild域指向新申請的結(jié)點q請的結(jié)點q將新申請的結(jié)點q作為新的當前結(jié)?=i點p}}◎若字符為','，執(zhí)行以下操作{令當前結(jié)點p為棧頂元素，但不退棧申請新結(jié)點q，并令新結(jié)點q的lchild域和rchild域為空令當前結(jié)點p的rchild域指向新申請的結(jié)點q將新申請的結(jié)點q作為新的當前結(jié)點p}◎若字符為')'，執(zhí)行以下操作(出棧，令當前結(jié)點p為棧頂元素}◎若字符為字母，執(zhí)行以下操作{令當前結(jié)點p的data域為該字母若該字母的下一個字符為’('則令當前結(jié)點指針p進棧}}}3、遍歷二叉樹的函數(shù)voidDisplay(GLNode*G,SeqStack&K){定義表示當前結(jié)點的指針p，并令p指根結(jié)點。指向根結(jié)點的指針p入棧，使棧不空'。當棧不空時執(zhí)行以下操作while(K.top!=-1){出棧，棧頂元素所指的結(jié)點作為當前結(jié)點p,輸出當前結(jié)點p中的字母若當前結(jié)點p的右孩子不為空，則令當前結(jié)點p的右孩子進棧若當前結(jié)點p的左孩子不為空，則令當前結(jié)點p的左孩子進棧}}四使用說明、測試分析及結(jié)果1、 程序使用說明：本程序運行環(huán)境為VisualC++6.0；根據(jù)界面提示進行操作，注意輸入的字符為西文字符2、 測試結(jié)果與分析：頁面提示“輸入二叉樹的括號表示形式:”輸入“A(B(D(,G)),C(E,F))”，按回車確定，頁面顯示如下：ilijJ“先序遍歷結(jié)果為:ABDGCEFilijJ是否繼續(xù)？(是,輸入1;否,輸入0):”

輸入序號“1”，按回車確定，表示繼續(xù)操作。頁面提示“輸入二叉樹的括號表示形式:”不輸入二叉樹，直接按回車確定，則頁面顯示如下：“二叉樹未建立是否繼續(xù)？（是,輸入1；否，輸入0）:”輸入序號“0”，按回車確定，表示結(jié)束操作，頁面顯示如下：“Pressanykeytocontinue”由上測試結(jié)果分析得，該程序功能滿足題目要求。3、 調(diào)試過程中遇到的問題及解決方法l=J

w當代碼編寫完成后，編譯過程出現(xiàn)了很多小錯誤，比如語句末尾漏掉分號，使用了某些變量卻未定義，但這些問題很快發(fā)現(xiàn)并及時糾正。l=J

w總的來說，因為本次實驗和廣義表的建立和輸出有相似之處，所以避免了很多問題，比較順利。4、 運行界面礦"Di^wo^C'iDebugXworkA.exe"BA—XHS5括號表示形"序遍歷結(jié)果為：朋DQCEF尊繼續(xù)了（是-輸入1；否?輸加）=1入二只樹的括號表示形式，卜又相未建亶基繼續(xù)？（是-輸入否，輸如）=ePressanykeytocontinue五、實驗總結(jié)本次實驗提前作了預習，在編寫程序上花費的時間不算太多，我在11月1日下午完成代碼的編寫并修改正確。因為本次實驗和廣義表的建立和輸出有相似之處，所以大的問題基本沒有出現(xiàn)，一些小的問題也及時發(fā)現(xiàn)并糾正。本次實驗，我很感謝老師和同學對我的指點。通過本次實驗，對二叉樹的存儲結(jié)構(gòu)有了更深的認識，對一些細節(jié)更加理解，收獲了很多。教師評語:實驗成績:指導教師簽名:批閱日期:代碼:#include<stdio.h>// typedefstructnode{chardata;structnode*lchild;structnode*rchild;}BiTNode;//〃二叉樹結(jié)點的類型描述//data用于存儲二叉樹中的字母//lchild為指向該結(jié)點左孩子的指針//rchild為指向該結(jié)點下一層的指針typedefstruct{BiTNode*pin[40];inttop;}SeqStack;// 〃順序棧的類型描述〃指針數(shù)組，用于存儲廣義表結(jié)點指針〃棧項指針#include<stdlib.h>voidCreate(BiTNode*B,SeqStack&K,chars[])//建立二叉樹的函數(shù)BiTNode*p,*q;intj;printfC輸入二叉樹的括號表示形式:");//p指針指向當前結(jié)點,q指針指向新申請的結(jié)點//j用于標記輸入的字符在數(shù)組中的位置〃提示輸入二叉樹gets(s);P=B;〃當前結(jié)點為根結(jié)點p->lchild=NULL;p->rchild=NULL;〃根結(jié)點的lchild域和rchild域為空for(j=0;s[j]!='\0';j++)〃進入循環(huán)，建立二叉樹if(s[j]=='(')〃若字符為'('，執(zhí)行以下操作if(s[j+1]==',')//若'('的下一個字符為','，當前結(jié)點p的lchild域為空elsep->lchild=NULL;//若'('的下一個字符不為','q=(BiTNode*)malloc(sizeof(BiTNode));〃申請新結(jié)點q〃令新結(jié)點q的lchild域和rchild域為空//令當前結(jié)點〃令新結(jié)點q的lchild域和rchild域為空//令當前結(jié)點p的lchild域指向新申〃將新申請的結(jié)點q作為新的當前結(jié)//若字符為','，執(zhí)行以下操作〃令當前結(jié)點p為棧頂元素，但不退〃申請新結(jié)點q〃令新結(jié)點q的lchild域和rchild域為空if(s[j]==')')〃若字符為')'，執(zhí)行以下操作//}printf("\n");{p=K.pin[K.top];K.top--;}else{p->data=s[j];if(s[j+1]=='('){K.top++;K.pin[K.top]=p;}}〃出棧，令當前結(jié)點p為棧頂元素//若字符為字母'，執(zhí)行以下操作〃令當前結(jié)點p的data域為該字母//若該字母的下一個字符為'('則令當前結(jié)點指針p進棧voidPreorder(BiTNode*B,SeqStack&K)〃遍歷二叉樹函數(shù)q->lchild=NULL;q->rchild=NULL;p->lchild=q;請的結(jié)點qp=q;點p}}else(if(s[j]==','){p=K.pin[K.top];棧q=(BiTNode*)malloc(sizeof(BiTNode));q->lchild=NULL;q->rchild=NULL;p->rchild=q; 〃令當前結(jié)點p的lchild域指向新申請的結(jié)點qp=q; 〃將新申請的結(jié)點q作為新的當前結(jié)點p}else

printf("先序遍歷結(jié)果為:，printf("先序遍歷結(jié)果為:，BiTNode*p;P=B;K.top++;〃提示以下結(jié)果為先序遍歷結(jié)果//p指針指向當前結(jié)點〃當前結(jié)點為根結(jié)點〃令當前結(jié)點指針p進棧K.pin[K.top]=p;//當棧不為空時執(zhí)行以下操作//當棧不為空時執(zhí)行以下操作〃出棧，棧頂元素所指的結(jié)點作為當前結(jié)點p//輸出當前結(jié)點p中的字母//若當前結(jié)點p的右孩子不為空，則令當前結(jié)點p的右孩子進//若當前結(jié)點p的左孩子不為空，則令當前結(jié)點p的左孩子進p=K.pin[K.top];K.top--;printf("%c",p->data);if(p->rchild!=NULL)棧K.top++;K.pin[K.top]=p->rchild;if(p->lchild!=NULL)棧K.top++;K.pin[K.top]=p->lchild;printf("\n");// intmain。{chars[40]; 〃定義數(shù)組，存儲輸入的字符串inti;BiTNode*B; 〃定義根結(jié)點，并申請存儲空間B=(BiTNode*)malloc(sizeof(BiTNode));SeqStackK; 〃定義棧并初始化棧K