數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)之二叉排序樹的實(shí)現(xiàn)

本文格式為Word版，下載可任意編輯——數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)之二叉排序樹的實(shí)現(xiàn)

中南大學(xué)信息科學(xué)與工程學(xué)院

課題名稱：學(xué)班學(xué)姓

院：級(jí)：號(hào)：名：

二叉排序樹的實(shí)現(xiàn)信息科學(xué)與工程學(xué)院通信工程

指導(dǎo)老師：

漆華妹

完成日期——2023年7月10日

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

一、引言

數(shù)據(jù)結(jié)構(gòu)是一門理論性強(qiáng)、思維抽象、難度較大的課程，是基礎(chǔ)課和專業(yè)課之間的橋梁。該課程的先行課程是計(jì)算機(jī)基礎(chǔ)、程序設(shè)計(jì)語言、離散數(shù)學(xué)等，后續(xù)課程有操作系統(tǒng)、編譯原理、數(shù)據(jù)庫原理、軟件工程等。通過本門課程的學(xué)習(xí)，我們應(yīng)當(dāng)能透徹地理解各種數(shù)據(jù)對(duì)象的特點(diǎn)，學(xué)會(huì)數(shù)據(jù)的組織方法和實(shí)現(xiàn)方法，并進(jìn)一步培養(yǎng)良好的程序設(shè)計(jì)能力和解決實(shí)際問題的能力。

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)的一門核心專業(yè)基礎(chǔ)課程，在該專業(yè)的課程體系中起著承上啟下的作用，學(xué)好數(shù)據(jù)結(jié)構(gòu)對(duì)于提高理論認(rèn)知水平和實(shí)踐能力有著極為重要的作用。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的最終目的是為了獲得求解問題的能力。對(duì)于現(xiàn)實(shí)世界中的問題，應(yīng)當(dāng)能從中抽象出一個(gè)適當(dāng)?shù)臄?shù)學(xué)模型，該數(shù)學(xué)模型在計(jì)算機(jī)內(nèi)部用相應(yīng)的數(shù)據(jù)結(jié)構(gòu)來表示，然后設(shè)計(jì)一個(gè)解此數(shù)學(xué)模型的算法，再進(jìn)行編程調(diào)試，最終獲得問題的解答。

實(shí)習(xí)課程是為了加強(qiáng)編程能力的培養(yǎng)，勉勵(lì)學(xué)生使用新興的編程語言。相信通過數(shù)據(jù)結(jié)構(gòu)課程實(shí)踐，無論是理論知識(shí)，還是實(shí)踐動(dòng)手能力，我們都會(huì)有不同程度上的提高。

二、課程設(shè)計(jì)目的

本課程是數(shù)據(jù)結(jié)構(gòu)課程的實(shí)踐環(huán)節(jié)。主要目的在于加強(qiáng)學(xué)生在課程中學(xué)習(xí)的相關(guān)算法和這些方法的具體應(yīng)用，使學(xué)生進(jìn)一步把握在C++或其他語言中應(yīng)用這些算法的能力。通過課程設(shè)計(jì)題目的練習(xí)，加強(qiáng)學(xué)生對(duì)所學(xué)知識(shí)的把握及對(duì)問題分析和任務(wù)定義的理解。

第2頁共15頁

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

三、問題描述及基本要求

二叉排序樹的實(shí)現(xiàn)：用順序和二叉鏈表作存儲(chǔ)結(jié)構(gòu)

1）以回車（?\\n?）為輸入終止標(biāo)志，輸入數(shù)列L,生成一棵二叉排序樹T;2)對(duì)二叉排序樹T作中序遍歷，輸出結(jié)果；

3）輸入元素x，查找二叉排序樹T，若存在含x的結(jié)點(diǎn)，則刪除該結(jié)點(diǎn)，并作中序遍歷（執(zhí)行操作2）；否則輸出信息“無x〞。

一、問題分析和任務(wù)定義

在設(shè)計(jì)之前，首先應(yīng)當(dāng)充分地分析和理解問題，明確問題要求做什么？限制條件是什么？對(duì)所需完成的任務(wù)作出明確的回復(fù)。二、系統(tǒng)設(shè)計(jì)

系統(tǒng)設(shè)計(jì)分為規(guī)律設(shè)計(jì)和詳細(xì)設(shè)計(jì)兩步。規(guī)律設(shè)計(jì)指的是，對(duì)問題描述中的操作對(duì)象定義相應(yīng)的數(shù)據(jù)類型，并依照以數(shù)據(jù)結(jié)構(gòu)為中心的原則劃分模塊，定義軟件模塊結(jié)構(gòu)圖；詳細(xì)設(shè)計(jì)則為定義相應(yīng)的存儲(chǔ)結(jié)構(gòu)，并寫出各函數(shù)模塊的偽碼算法。三、編碼實(shí)現(xiàn)和調(diào)試

四、軟件模塊結(jié)構(gòu)圖

第3頁共15頁

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

主程序模塊初始化模塊CreateBST()中序遍歷二叉排序樹inorder()查找元素xBSTSearch()中序遍歷二叉排序樹inorder()

五、程序設(shè)計(jì)流程圖（設(shè)計(jì)思想）

二叉鏈表作存儲(chǔ)結(jié)構(gòu)和順序表作存儲(chǔ)結(jié)構(gòu)輸入數(shù)列L，以回車(‘\\\\n’)為輸入終止標(biāo)志生成二叉排序樹T；對(duì)二叉排序樹T作中序遍歷,并輸出結(jié)果

輸入元素x，查找二叉排序樹T找到該節(jié)點(diǎn)x無結(jié)點(diǎn)x存在含x的結(jié)點(diǎn)，則刪除該第4頁共15頁結(jié)點(diǎn)，并作中序遍歷數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

詳細(xì)設(shè)計(jì)思想：

建立二叉排序樹采用邊查找邊插入的方式。查找函數(shù)采用遞歸的方式進(jìn)行查找。假使查找到相等的則插入其左子樹。然后利用插入函數(shù)將該元素插入原樹。

對(duì)二叉樹進(jìn)行中序遍歷采用遞歸函數(shù)的方式。在根結(jié)點(diǎn)不為空的狀況下，先訪問左子樹，再訪問根結(jié)點(diǎn)，最終訪問右子樹。

刪除結(jié)點(diǎn)函數(shù)，采用邊查找邊刪除的方式。假使沒有查找到，進(jìn)行提醒；假使查找到結(jié)點(diǎn)則將其左子樹最右邊的節(jié)點(diǎn)的數(shù)據(jù)傳給它，然后刪除其左子樹最右邊的節(jié)點(diǎn)。

六、源代碼

1、用二叉鏈表存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)

#includetypedefintKeyType;

typedefcharElemType[10];typedefstructtnode{

KeyTypekey;ElemTypedata;

structtnode*lchild,*rchild;}BSTNode;

voidBSTdisp(BSTNode*b);

BSTNode*BSTSearch(BSTNode*bt,KeyTypek){

BSTNode*p=bt;

while(p!=NULL/*沿左子樹查找*/else

p=p->rchild;/*沿右子樹查找*/}

return(p