資源描述：
《數(shù)據(jù)結(jié)構(gòu)-二叉樹的建立與遍歷.doc》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。
1、《數(shù)據(jù)結(jié)構(gòu)》實驗報告◎?qū)嶒烆}目:二叉樹的建立與遍歷◎?qū)嶒災康模?、掌握使用VisualC++6.0上機調(diào)試程序的基本方法；2、掌握二叉樹的存儲結(jié)構(gòu)和非遞歸遍歷操作的實現(xiàn)方法。3、提高自己分析問題和解決問題的能力，在實踐中理解教材上的理論?！?qū)嶒瀮?nèi)容：利用鏈式存儲結(jié)構(gòu)建立二叉樹，然后先序輸出該二叉樹的結(jié)點序列，在在本實驗中不使用遞歸的方法，而是用一個棧存儲結(jié)點的指針，以此完成實驗要求。一、需求分析1、輸入的形式和輸入值的范圍：根據(jù)提示，輸入二叉樹的括號表示形式，按回車結(jié)束。2、輸出的形式：輸出結(jié)果為先序遍歷二叉樹所得到的結(jié)點序列。3、
2、程序所能達到的功能：輸入二叉樹后，該程序可以建立二叉樹的鏈式存儲結(jié)構(gòu)，之后按照一定的順序訪問結(jié)點并輸出相應(yīng)的值，從而完成二叉樹的先序遍歷。4、測試數(shù)據(jù)：輸入二叉樹的括號表示形式:A(B(D(,G)),C(E,F))先序遍歷結(jié)果為:ABDGCEF是否繼續(xù)?（是,輸入1;否,輸入0）:1輸入二叉樹的括號表示形式:二叉樹未建立是否繼續(xù)?（是,輸入1;否,輸入0）:0Pressanykeytocontinue二概要設(shè)計1、二叉樹的鏈式存儲結(jié)構(gòu)是用一個鏈表來存儲一棵二叉樹，二叉樹中每一個結(jié)點用鏈表中的一個鏈結(jié)點來存儲。每個結(jié)點的形式如下圖所示
3、。其中data表示值域，用于存儲對應(yīng)的數(shù)據(jù)元素，lchild和rchild分別表示左指針域和右指針域，用于分別存儲左孩子結(jié)點和右孩子結(jié)點的存儲位置。2、二叉樹的建立本程序中利用數(shù)組存儲所輸入的二叉樹，然后從頭到尾掃描數(shù)組中的每一個字符根據(jù)字符的不同分別執(zhí)行不同的操作，并用一個存儲結(jié)點指針的棧輔助完成。在掃描前先申請一個結(jié)點作為根結(jié)點，也是當前指針所指結(jié)點，在二叉樹的建立的過程中，每次申請一個新結(jié)點，需對其進行初始化，即令lchild域和rchild域為空。按照本程序的思路，二叉樹A（B（D（，G）），C（E，F(xiàn)））的鏈式存儲結(jié)構(gòu)如下
4、圖所示。二叉樹建立的具體過程見詳細設(shè)計部分。3、二叉樹的先序遍歷在二叉樹的先序遍歷過程中也需利用一個存儲結(jié)點指針的棧輔助完成，初始時棧為空，二叉樹遍歷結(jié)束后棧也為空，所以在開始時將頭結(jié)點入棧，之后根據(jù)當前指針所指結(jié)點的特性的不同執(zhí)行不同的操作，以?？兆鳛槎鏄浔闅v的結(jié)束條件。二叉樹先序遍歷的具體過程見詳細設(shè)計部分。4、本程序的基本操作和模塊：建立二叉樹的函數(shù)：voidCreate(BiTNode*B,SeqStack&K,chars[])遍歷二叉樹的函數(shù)：voidPreorder(BiTNode*B,SeqStack&K)主函數(shù)：m
5、ain()函數(shù)的調(diào)用關(guān)系如下圖所示:三詳細設(shè)計（一）元素類型、結(jié)點類型1、二叉樹結(jié)點的類型描述typedefstructnode/*二叉樹結(jié)點的類型描述*/{chardata;/*data用于存儲二叉樹中的字母*/structnode*lchild;/*lchild為指向該結(jié)點左孩子的指針*/structnode*rchild;/*rchild為指向該結(jié)點下一層的指針*/}BiTNode;2、順序棧的類型描述typedefstruct/*順序棧的類型描述*/{BiTNode*pin[40];/*指針數(shù)組，用于存儲廣義表結(jié)點指針*/i
6、nttop;/*棧頂指針*/}SeqStack;（一）每個模塊的分析1、主程序模塊main(){①定義數(shù)組，存儲輸入的字符串②定義并申請根結(jié)點③初始化順序棧④while(1){調(diào)用建立二叉樹的函數(shù)，建立二叉樹的鏈式存儲結(jié)構(gòu)調(diào)用遍歷二叉樹的函數(shù)，輸出所建立的二叉樹的結(jié)點選擇是否繼續(xù)，若是，則重新執(zhí)行循環(huán)中的操作；若否，則退出循環(huán)}}2、建立二叉樹的函數(shù)voidCreate(BiTNode*B,SeqStack&K,chars[]){①定義表示當前結(jié)點的指針p，和表示新申請結(jié)點的指針q令p指向根結(jié)點，根結(jié)點的lchild域和rchild
7、域為空。②輸入二叉樹③從頭到尾掃描輸入的字符，進入以下循環(huán)，當遇到空字符時結(jié)束循環(huán)for(j=0;s[j]!='
