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