數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)---二叉排序樹(shù)和平衡二叉樹(shù)的判別(已修改)
2025-06-22 01:24 本頁(yè)面
【正文】 武漢理工大學(xué)《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)說(shuō)明書(shū) 二叉排序樹(shù)和平衡二叉樹(shù)的判別 1 引言 數(shù)據(jù)結(jié)構(gòu)是軟件工程的一門(mén)核心專業(yè)基礎(chǔ)課程，在我們專業(yè)的課程體系中起著承上啟下的作用，學(xué)好數(shù)據(jù)結(jié)構(gòu)對(duì)于提高理論認(rèn)知水平和實(shí)踐能力有著極為重要的作用。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的最終目的是為了獲得求解問(wèn)題的能力。對(duì)于現(xiàn)實(shí)世界中的問(wèn)題，應(yīng)該能從中抽象出一個(gè)適當(dāng)?shù)臄?shù)據(jù)模型，該數(shù)學(xué)模型在計(jì)算機(jī)內(nèi)部用相應(yīng)的數(shù)據(jù)結(jié)構(gòu)來(lái)表示，然后設(shè)計(jì)一個(gè)解此數(shù)學(xué)模型的算法，在進(jìn)行編程調(diào)試，最后獲得問(wèn)題的解答 。 本次課程設(shè)計(jì)的題目是對(duì)二叉排序樹(shù)和平衡二叉樹(shù)的擴(kuò)展延伸應(yīng)用。首先我們得建立一個(gè)二叉樹(shù)，二叉樹(shù)有順序存儲(chǔ) 結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)兩種存儲(chǔ)結(jié)構(gòu)，此次我選用的是二叉鏈表的存儲(chǔ)結(jié)構(gòu)。對(duì)于判斷平衡二叉樹(shù)，需要求出其每個(gè)葉子結(jié)點(diǎn)所在的層數(shù)，這里我采用的邊遍歷邊求的方式，遍歷采用的是先序遍歷。二叉樹(shù)的建立以及二叉排序樹(shù)和平衡二叉樹(shù)的判別中都用到了遞歸思想。 2 需求分析 在日常生活中，人們幾乎每天都要進(jìn)行“查找”工作。所謂“查找”即為在一個(gè)含有眾多的數(shù)據(jù)元素（或記錄）的查找表中找出某個(gè)“特定的”數(shù)據(jù)元素（或記錄），即關(guān)鍵字。 本程序意為對(duì)一個(gè)已經(jīng)建立的動(dòng)態(tài)查找表 —— 二叉樹(shù) —— 判斷其是否是二叉排序樹(shù)和平衡二叉樹(shù)。 3 數(shù) 據(jù)結(jié)構(gòu)設(shè)計(jì) ： ADT BinaryTree{ 數(shù)據(jù)對(duì)象 D： D 是具有相同特性的數(shù)據(jù)元素的集合。 數(shù)據(jù)關(guān)系 R: 若 D=NULL，則 R=NULL，稱 BinaryTree 為空的二叉樹(shù)； 若 D!=NULL,則 R={H}， H是如下的二元關(guān)系 : 在 D 中存在唯一的稱為根的數(shù)據(jù)元素 root，它在關(guān)系 H 下無(wú)前驅(qū)； 若 D{root}!=NULL,則存在 D{root}={Dl,Dr},且 Dl 與 Dr相交為空； 若 Dl！ =NULL，則 Dl 中存在唯一的元素 xl,root,xl屬于 H，且存在Dl 上的關(guān)系 Hl 屬于 H；若 Dr！ =NULL，則 Dr 中存在唯一的元素 xr,root,xr武漢理工大學(xué)《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)說(shuō)明書(shū) 屬于 H，且存在 Dr 上的關(guān)系 Hr 屬于 H； H={root,xl,root,xr,Hl,Hr}； （ Dl,{Hl})是一棵符合本定義的二叉樹(shù)，稱為根的左子樹(shù)， （ Dr,{Hr})是一棵符合本定義的二叉樹(shù)，稱為根的右子樹(shù)。 P： InitBiTree(amp。T)。 操作結(jié)果：構(gòu)造空二叉樹(shù) T。 CreateBiTree(amp。T,definition)； 初始條件： definition 給出二叉樹(shù) T 的定義。 操作結(jié)果：按 definition 構(gòu)造二叉樹(shù) T。 }ADT Tree //包含頭文件 includeiostream using namespace std。 //數(shù)據(jù)結(jié)構(gòu) typedef struct Bitre
畢業(yè)設(shè)計(jì)相關(guān)推薦
鄂ICP備17016276號(hào)-1