數(shù)據(jù)結(jié)構(gòu)二叉樹的建立與遍歷(已修改)
2025-07-07 07:23 本頁面
【正文】 《數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告◎?qū)嶒?yàn)題目:二叉樹的建立與遍歷◎?qū)嶒?yàn)?zāi)康模赫莆帐褂肰isual C++； 掌握二叉樹的存儲(chǔ)結(jié)構(gòu)和非遞歸遍歷操作的實(shí)現(xiàn)方法。 提高自己分析問題和解決問題的能力，在實(shí)踐中理解教材上的理論?！?qū)嶒?yàn)內(nèi)容：利用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)建立二叉樹，然后先序輸出該二叉樹的結(jié)點(diǎn)序列，在在本實(shí)驗(yàn)中不使用遞歸的方法，而是用一個(gè)棧存儲(chǔ)結(jié)點(diǎn)的指針，以此完成實(shí)驗(yàn)要求。一、需求分析輸入的形式和輸入值的范圍：根據(jù)提示，輸入二叉樹的括號(hào)表示形式，按回車結(jié)束。輸出的形式：輸出結(jié)果為先序遍歷二叉樹所得到的結(jié)點(diǎn)序列。程序所能達(dá)到的功能：輸入二叉樹后，該程序可以建立二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，之后按照一定的順序訪問結(jié)點(diǎn)并輸出相應(yīng)的值，從而完成二叉樹的先序遍歷。測試數(shù)據(jù)：輸入二叉樹的括號(hào)表示形式:A(B(D(,G)),C(E,F))先序遍歷結(jié)果為:ABDGCEF是否繼續(xù)?（是,輸入1。否,輸入0）:1輸入二叉樹的括號(hào)表示形式:二叉樹未建立是否繼續(xù)?（是,輸入1。否,輸入0）:0Press any key to continue二 概要設(shè)計(jì)二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是用一個(gè)鏈表來存儲(chǔ)一棵二叉樹，二叉樹中每一個(gè)結(jié)點(diǎn)用鏈表中的一個(gè)鏈結(jié)點(diǎn)來存儲(chǔ)。每個(gè)結(jié)點(diǎn)的形式如下圖所示。其中data表示值域，用于存儲(chǔ)對應(yīng)的數(shù)據(jù)元素，lchild和rchild分別表示左指針域和右指針域，用于分別存儲(chǔ)左孩子結(jié)點(diǎn)和右孩子結(jié)點(diǎn)的存儲(chǔ)位置。 二叉樹的建立本程序中利用數(shù)組存儲(chǔ)所輸入的二叉樹，然后從頭到尾掃描數(shù)組中的每一個(gè)字符根據(jù)字符的不同分別執(zhí)行不同的操作，并用一個(gè)存儲(chǔ)結(jié)點(diǎn)指針的棧輔助完成。在掃描前先申請一個(gè)結(jié)點(diǎn)作為根結(jié)點(diǎn)，也是當(dāng)前指針?biāo)附Y(jié)點(diǎn)，在二叉樹的建立的過程中，每次申請一個(gè)新結(jié)點(diǎn)，需對其進(jìn)行初始化，即令lchild域和rchild域?yàn)榭铡０凑毡境绦虻乃悸?，二叉樹A（B（D（，G）），C（E，F(xiàn)））的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)如下圖所示。二叉樹建立的具體過程見詳細(xì)設(shè)計(jì)部分。 二叉樹的先序遍歷在二叉樹的先序遍歷過程中也需利用一個(gè)存儲(chǔ)結(jié)點(diǎn)指針的棧輔助完成，初始時(shí)棧為空，二叉樹遍歷結(jié)束后棧也為空，所以在開始時(shí)將頭結(jié)點(diǎn)入棧，之后根據(jù)當(dāng)前指針?biāo)附Y(jié)點(diǎn)的特性的不同執(zhí)行不同的操作，以?？兆鳛槎鏄浔闅v的結(jié)束條件。二叉樹先序遍歷的具體過程見詳細(xì)設(shè)計(jì)部分。本程序的基本操作和模塊：建立二叉樹的函數(shù)：void Create(BiTNode *B,SeqStack amp。K,char s[]) 遍歷二叉樹的函數(shù)：void Preorder(BiTNode *B,SeqStack amp。K)主函數(shù)：main( )函數(shù)的調(diào)用關(guān)系如下圖所示:三 詳細(xì)設(shè)計(jì)（1） 元素類型、結(jié)點(diǎn)類型 二叉樹結(jié)點(diǎn)的類型描述typedef struct node /*二叉樹結(jié)點(diǎn)的類型描述*/ { char data。 /*data用
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1