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

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

2、輸入二叉樹后，該程序可以建立二叉樹的鏈式存儲結(jié)構(gòu)，之后按照一定的順序訪問結(jié)點并輸出相應(yīng)的值，從而完成二叉樹的先序遍歷。 、測試數(shù)據(jù)：4 輸入二叉樹的括號表示形式:A(B(D(,G),C(E,F) 先序遍歷結(jié)果為:ABDGCEF 是否繼續(xù)?（是,輸入1;否,輸入0）:1 輸入二叉樹的括號表示形式: 二叉樹未建立 是否繼續(xù)?（是,輸入1;否,輸入0）:0 Press any key to continue 二 概要設(shè)計 1、二叉樹的鏈式存儲結(jié)構(gòu)是用一個鏈表來存儲一棵二叉樹，二叉樹中每一個結(jié)點用鏈表中的一個鏈結(jié)點來存儲。 每個結(jié)點的形式如下圖所示。 其中data表示值域，用于存儲對應(yīng)的數(shù)據(jù)元素，lc

3、hild和rchild分別表示左指針域和右指針域，用于分別存儲左孩子結(jié)點和右孩子結(jié)點的存儲位置。 、二叉樹的建立2 本程序中利用數(shù)組存儲所輸入的二叉樹，然后從頭到尾掃描數(shù)組中的每一個字符根據(jù)字符的不同分別執(zhí)行不同的操作，并用一個存儲結(jié)點指 針的棧輔助完成。在掃描前先申請一個結(jié)點作為根結(jié)點，也是當(dāng)前指針所指結(jié)點，在二叉樹的建立的過程中，每次申請一個新結(jié)點，需對其進行初始化，即令lchild域和rchild域為空。按照本程序的思路，二叉樹A（B（D（，G），C（E，F(xiàn)）的鏈式存儲結(jié)構(gòu)如下圖所示。二叉樹建立的具體過程見詳細設(shè)計部分。 3、二叉樹的先序遍歷 在二叉樹的先序遍歷過程中也需利用一個存儲結(jié)點

4、指針的棧輔助完成，初始時棧為空，二叉樹遍歷結(jié)束后棧也為空，所以在開始時將頭結(jié)點入棧，之后根據(jù)當(dāng)前指針所指結(jié)點的特性的不同執(zhí)行不同的操作，以?？兆鳛槎鏄浔闅v的結(jié)束條件。二叉樹先序遍歷的具體過程見詳細設(shè)計部分。 4、本程序的基本操作和模塊： 建立二叉樹的函數(shù)：void Create(BiTNode *B,SeqStack &K,char s) 遍歷二叉樹的函數(shù)：void Preorder(BiTNode *B,SeqStack &K) 主函數(shù)：main( ) : 函數(shù)的調(diào)用關(guān)系如下圖所示 三 詳細設(shè)計 （一）元素類型、結(jié)點類型 1、二叉樹結(jié)點的類型描述 typedef struct node /

5、*二叉樹結(jié)點的類型描述*/ char data; /*data用于存儲二叉樹中的字母*/ struct node *lchild; /*lchild為指向該*/ 結(jié)點左孩子的指針 struct node *rchild; /*rchild為指向該結(jié)點下一層的指針*/ BiTNode; 2、順序棧的類型描述 typedef struct /*順序棧的類型描述*/ BiTNode *pin40; /*指針數(shù)組，用于存儲廣義表結(jié)點指針*/ int top; /*棧頂指針*/ SeqStack; （二）每個模塊的分析 1、主程序模塊 main() 定義數(shù)組，存儲輸入的字符串 定義并申請根結(jié)點 初始化順

6、序棧 while(1) 調(diào)用建立二叉樹的函數(shù)，建立二叉樹的鏈 式存儲結(jié)構(gòu) 輸出所建立的二 調(diào)用遍歷二叉樹的函數(shù)， 叉樹的結(jié)點則重新執(zhí)行循環(huán)中選擇是否繼續(xù)，若是， 的操作；若否，則退出循環(huán) 、建立二叉樹的函數(shù)2Create(BiTNode *B,SeqStack void &K,char s) 和表示新申 定義表示當(dāng)前結(jié)點的指針p，q 請結(jié)點的指針域和指向根結(jié)點，根結(jié)點的lchildp 令 域為空。rchild 輸入二叉樹 從頭到尾掃描輸入的字符，進入以下循 環(huán)，當(dāng)遇到空字符時結(jié)束循環(huán)for(j=0;sj!=0;j+) ，執(zhí)行以下操作(若字符為 p,，當(dāng)前結(jié)點若(的下一個字符為a. lchild

7、域為空的 則執(zhí)行以下,(b.若的下一個字符不為 的操作： 的q申請新結(jié)點q, 并令新結(jié)點 域為空域和rchildlchild域指向新申lchildp的 令當(dāng)前結(jié)點 q 請的結(jié)點作為新的當(dāng)前結(jié)將新申請的結(jié)點q p 點 ，執(zhí)行以下操作若字符, 令當(dāng)前結(jié)點p為棧頂元素，但不退棧 申請新結(jié)點q，并令新結(jié)點q的lchild域和rchild域為空 令當(dāng)前結(jié)點p的rchild域指向新申請的結(jié)點q 作為新的當(dāng)前結(jié)點q將新申請的結(jié)點 p 若字符為)，執(zhí)行以下操作 為棧頂元素出棧，令當(dāng)前結(jié)點p 若字符為字母，執(zhí)行以下操作 令當(dāng)前結(jié)點p的data域為該字母 若該字母的下一個字符為(則令當(dāng)前結(jié)點指針p進棧 3、遍歷二

8、叉樹的函數(shù) void Display(GLNode *G,SeqStack &K) 定義表示當(dāng)前結(jié)點的指針p，并令p指根結(jié)點。 指向根結(jié)點的指針p入棧,使棧不空。 當(dāng)棧不空時執(zhí)行以下操作 while(K.top!=-1) 出棧，棧頂元素所指的結(jié)點作為當(dāng)前結(jié)點 p，輸出當(dāng)前結(jié)點p中的字母 若當(dāng)前結(jié)點p的右孩子不為空，則令當(dāng)前結(jié)點p的右孩子進棧 若當(dāng)前結(jié)點p的左孩子不為空，則令當(dāng)前結(jié)點p的左孩子進棧 四 使用說明、測試分析及結(jié)果 1、程序使用說明： （1）本程序運行環(huán)境為Visual C+ 6.0； （2）根據(jù)界面提示進行操作,注意輸入的字符為西文字符 2、測試結(jié)果與分析： 頁面提示“輸入二叉樹的

9、括號表示形式:” 輸入“A(B(D(,G),C(E,F)”，按回車確定，頁面顯示如下： “ 先序遍歷結(jié)果為:ABDGCEF ”: ）0輸入,否1;輸入,（是?是否繼續(xù) 輸入序號“1”，按回車確定，表示繼續(xù)操作。 頁面提示“輸入二叉樹的括號表示形式:” 不輸入二叉樹，直接按回車確定，則頁面顯示 如下： “ 二叉樹未建立 是否繼續(xù)?（是,輸入1;否,輸入0）: ” 輸入序號“0”，按回車確定，表示結(jié)束操作，頁面顯示如下： “ Press any key to continue ” 由上測試結(jié)果分析得，該程序功能滿足題目要求。 3、調(diào)試過程中遇到的問題及解決方法 當(dāng)代碼編寫完成后，編譯過程出現(xiàn)了很多

10、小錯誤，比如語句末尾漏掉分號，使用了某些變量卻未定義，但這些問題很快發(fā)現(xiàn)并及時糾正。 總的來說，因為本次實驗和廣義表的建立和輸出有相似之處，所以避免了很多問題，比較順利。 4、運行界面 五、實驗總結(jié) 本次實驗提前作了預(yù)習(xí)，在編寫程序上花費的時間不算太多，我在11月1日下午完成代碼的編寫并修改正確。因為本次實驗和廣義表的建立和輸出有相似之處，所以大的問題基本沒有出現(xiàn)，一些小的問題也及時發(fā)現(xiàn)并糾正。 本次實驗，我很感謝老師和同學(xué)對我的指點。通過本次實驗，對二叉樹的存儲結(jié)構(gòu)有了更深的認識，對一些細節(jié)更加理解，收獲了很多。 教師評語： 實驗成績： 指導(dǎo)教師簽 名： 批閱日期： 代碼： # includ

11、e # include / typedef struct node /二叉樹結(jié)點的類型描述 char data; /data用于存儲二叉樹中的字母 struct node *lchild; /lchild為指向該結(jié)點左孩子的指針 /rchild struct node *rchild; 為指向該結(jié)點下一層的指針 BiTNode; / typedef struct /順序棧的類型描述 /指針數(shù)組，用于存儲廣義表結(jié)點指針 BiTNode *pin40; int top; / 棧頂指針 SeqStack; / void Create(BiTNode *B,SeqStack &K,char s) /建

12、立二叉樹的函數(shù) ,q指針指向新申請的結(jié)點 /p指針指向當(dāng)前結(jié)點 BiTNode *p,*q; /j int j; 用于標記輸入的字符在數(shù)組中的位置 牰湩晴尨輸入二叉樹的括號表示形式 :); / 提示輸入二叉樹 gets(s); / 當(dāng)前結(jié)點為根結(jié)點 p=B; p-lchild=NULL;p-rchild=NULL; /根結(jié)點的lchild域和rchild域為空 /進入循環(huán)，建立二叉樹 for(j=0;sj!=0;j+) if(sj=() /若字符為(，執(zhí)行以下操作 /若( if(sj+1=,) 的下一個字符為 ,，當(dāng)前結(jié)點p的lchild 域為空 p-lchild=NULL; /若 (的下一個

13、字符不為, else q 申請新結(jié)點/ q=(BiTNode *)malloc(sizeof(BiTNode); q-lchild=NULL;q-rchild=NULL; /令新結(jié)點q的lchild域和rchild域為空 / 令當(dāng)前結(jié)點 p 的 lchild 域指向新申 p-lchild=q; 請的結(jié)點q p=q; /將新申請的結(jié)點q作為新的當(dāng)前結(jié)p 點 else ,，執(zhí)行以下操作 / 若字符為 if(sj=,) 為棧頂元素，但不退 p=K.pinK.top; 令當(dāng)前結(jié)點 p / 棧q / q=(BiTNode *)malloc(sizeof(BiTNode); 申請新結(jié)點 域為空rchild

14、域和令新結(jié)點 / qq-lchild=NULL;q-rchild=NULL; 的lchild 域指向新申/ 令當(dāng)前結(jié)點p的 lchildp-rchild=q; 請的結(jié)點q p=q; /將新申請的結(jié)點q作為新的當(dāng)前結(jié)p 點 else ，執(zhí)行以下操作)/if(sj=) 若字符為 p=K.pinK.top; p 出棧，令當(dāng)前結(jié)點 /為棧頂元素 K.top-; / ，執(zhí)行以下操作 else 字母 若字符為 p-data=sj; 的 令當(dāng)前結(jié)點 / p域為該字母 data 若該字母的下一個字符為 if(sj+1=() /p 則令當(dāng)前結(jié)點指針 進棧 ( K.top+; K.pinK.top=p; prin

15、tf(); / 遍歷二叉樹函數(shù)/ void Preorder(BiTNode *B,SeqStack &K) 牰湩晴尨先序遍歷結(jié)果為:); /提示以下結(jié)果為先序遍歷結(jié)果 /p BiTNode *p; 指針指向當(dāng)前結(jié)點 / p=B; 當(dāng)前結(jié)點為根結(jié)點 / 令當(dāng)前結(jié)點指針p進棧 K.top+; K.pinK.top=p; while(K.top!=-1) /當(dāng)棧不為空時執(zhí)行以下操作 p=K.pinK.top; /出棧，棧頂元素所指的結(jié)點作為當(dāng)前結(jié)點p K.top-; /輸出當(dāng)前結(jié)點 printf(%c,p-data); p中的字母 / 若當(dāng)前結(jié)點p 的右孩子不為空，則令當(dāng)前結(jié)點 if(p-rchild!=NULL) p的右孩子進 棧 K.top+; K.pinK.top=p-rchild; 的左孩子進 if(p-lchild!=NULL) p 的左孩子不為空，則令當(dāng)前結(jié)點若當(dāng)前結(jié)點/ p 棧 K.top+; K.pinK.top=p-lchild; printf(); /int main() / char s40; 定義數(shù)組，存儲輸入的字符串int i; BiTNode *B; 定義根結(jié)點，并申請存儲空間/ B=(BiTNode *)malloc(sizeof(BiTNode); SeqStack K; /定義棧并初始化