數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告二叉排序樹的實(shí)現(xiàn)(已修改)
2025-08-02 12:14 本頁面
【正文】 專業(yè)資料整理分享 課 程 設(shè) 計(jì) 課程名稱 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 題目名稱 二叉排序樹的實(shí)現(xiàn) 學(xué) 院 應(yīng)用數(shù)學(xué)學(xué)院 專業(yè)班級(jí) 學(xué) 號(hào) 學(xué)生姓名 指導(dǎo)教師 2013 年 12 月 26 日 完美WORD格式編輯 1） 實(shí)現(xiàn)二叉排序樹，包括生成、插入，刪除；2） 對(duì)二叉排序樹進(jìn)行先根、中根、和后根非遞歸遍歷；3） 每次對(duì)樹的修改操作和遍歷操作的顯示結(jié)果都需要在屏幕上 用樹的形狀表示出來。4） 分別用二叉排序樹和數(shù)組去存儲(chǔ)一個(gè)班(50人以上)的成員信 息(至少包括學(xué)號(hào)、姓名、成績3項(xiàng)),對(duì)比查找效率，并說明 為什么二叉排序樹效率高（或者低）。2. 函數(shù)模塊： CreatTree()操作建立二叉排序樹。 InsertBST(bstree t,int key,nametype name,double grade)插入一個(gè)節(jié)點(diǎn)。3. 從二叉排序樹t中通過操作void Delete(bstree amp。p)刪除任意節(jié)點(diǎn)。4. 在二叉排序樹t中通過操作bstnode *SearchBST(bstree t,keytype key)查找節(jié)點(diǎn)。5. 在二叉排序樹t中通過操作p=SearchBST(t,key)查詢，并修改節(jié)點(diǎn)信息 6. 非遞歸遍歷二叉排序樹。7. 定義函數(shù)void pare()對(duì)數(shù)組和二叉排序樹的查找效率進(jìn)行比較比較。從鍵盤中輸入關(guān)鍵字及記錄，并同時(shí)調(diào)用插入函數(shù)并不斷進(jìn)行插入。最后，返回根節(jié)點(diǎn)T。：二叉排序樹上刪除一個(gè)階段相當(dāng)于刪去有序系列中的一個(gè)記錄，只要在刪除某個(gè)節(jié)點(diǎn)之后依舊保持二叉排序樹的性質(zhì)即可。假設(shè)二叉排序樹上刪除節(jié)點(diǎn)為*p（指向節(jié)點(diǎn)的指針為p），其雙親節(jié)點(diǎn)為*f（節(jié)點(diǎn)指針為f）。若*p節(jié)點(diǎn)為葉子節(jié)點(diǎn)，則即左右均為空樹，由于刪去葉子節(jié)點(diǎn)不破壞整棵樹的結(jié)構(gòu)，則只需修改其雙親節(jié)點(diǎn)的指針即可；若*p節(jié)點(diǎn)只有左子樹或只有右子樹，此時(shí)只要令左子樹或右子樹直接成為其雙親節(jié)點(diǎn)*f的左子樹即可；若*p節(jié)點(diǎn)的左子樹和右子樹均不為空，其一可以令*p的左子樹為*f的左子樹，而*p的右子樹為*s的右子樹，其二可以令*p的直接前驅(qū)（或直接后繼）替代*p，然后再從二叉排序樹中刪去它的直接前驅(qū)（或直接后繼）。在二叉排序樹中刪除一個(gè)節(jié)點(diǎn)的算法為void DeleteData(bstree amp。t,keytype key)若二叉排序樹t中存在關(guān)鍵字等于key的數(shù)據(jù)元素，則刪除該數(shù)據(jù)元素節(jié)點(diǎn)，并返回TRUE，否則返回FALSE。二叉排序樹是一種動(dòng)態(tài)樹表，其特點(diǎn)是樹的結(jié)構(gòu)通常不是一次生成的，而是在查找的過程中，當(dāng)樹中不存在關(guān)鍵字等于給定值得節(jié)點(diǎn)時(shí)在進(jìn)行插入。新插入的節(jié)點(diǎn)一定是一個(gè)新添加的葉子節(jié)點(diǎn)，并且是查找不成功時(shí)查找路徑上訪問的最后一個(gè)節(jié)點(diǎn)的左孩子或右孩子的節(jié)點(diǎn)。一個(gè)無序系列可以通過構(gòu)造一棵二叉排序樹而變成一個(gè)有序系列，構(gòu)造樹的過程即為對(duì)無序系列進(jìn)行排序的過程， 并且每次插入的節(jié)點(diǎn)都是二叉排序樹上新的葉子節(jié)點(diǎn)，則在進(jìn)行插入操作時(shí)，不必移動(dòng)其他節(jié)點(diǎn)，僅需改變某個(gè)節(jié)點(diǎn)的指針由空變?yōu)榉强占纯伞６媾判驑涞牟迦胨惴閎stree InsertBST(bstree t,int key,nametype name,double grade) 若二叉排序樹中不存在關(guān)鍵字等于key的數(shù)據(jù)元素時(shí)，插入元素并返回TRUE。二叉排序樹又稱二叉查找樹，當(dāng)二叉排序樹不為空時(shí)，首先將給定的值和根節(jié)點(diǎn)的關(guān)鍵字比較，若相等則查找成功，否則將依據(jù)給定的值和根節(jié)點(diǎn)關(guān)鍵字之間的大小關(guān)系，分別在左子樹或右子樹上繼續(xù)進(jìn)行查找。為此定義一個(gè)二叉排序樹的查找算法為bstnode *SearchBST(bstree t,keytype key) 在根指針t所指向的二叉排序樹中查找關(guān)鍵字等于key的數(shù)據(jù)元素，如成功，返回指向該元素節(jié)點(diǎn)的指針，否則返回空指針。void pare()對(duì)數(shù)組和二叉排序樹的查找效率進(jìn)行比較比較。先序遍歷也叫做先根遍歷。首先訪問根結(jié)點(diǎn)然后遍歷左子樹，最后遍歷右子樹。在遍歷左、右子樹時(shí)，仍然先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹，如果二叉樹為空則返回。其實(shí)過程為：先遍歷左子樹rootleftleftleft...null，由于是先序遍歷，因此一遇到節(jié)點(diǎn)，便需要立即訪問；由于一直走到最左邊后，需要逐步返回到父節(jié)點(diǎn)訪問右節(jié)點(diǎn)，因此必須有一個(gè)措施能夠?qū)?jié)點(diǎn)序列回溯。其一可以用棧記憶在訪問途中將依次遇到的節(jié)點(diǎn)保存下來。根據(jù)棧的先進(jìn)后出、后進(jìn)先出的特點(diǎn)特點(diǎn)。則可以用棧保存。每次都將遇到的節(jié)點(diǎn)壓入棧，當(dāng)左子樹遍歷完畢后從棧中彈出最后一個(gè)訪問的節(jié)點(diǎn)，然后訪問其右子樹?；舅惴ㄋ枷耄海瑢⒏?jié)點(diǎn)入棧：如果該節(jié)點(diǎn)左孩子存在，則訪問該左孩子節(jié)點(diǎn)，并將其指針入棧。重復(fù)以上操作，直到節(jié)點(diǎn)的左孩子不存在。將棧頂?shù)脑?，即其指針出棧，回到父?jié)點(diǎn)，如果該指針節(jié)點(diǎn)的右孩子存在，則將該指針指向的右孩子節(jié)點(diǎn)重復(fù)執(zhí)行以上步驟，直到桟為空為止。操作函數(shù)為void x_print(Tree T)中序遍歷：中序遍歷和先序遍歷訪問的順序不同。中序遍歷訪問順序?yàn)橹行虮闅v左子數(shù)，在訪問根節(jié)點(diǎn)，最后中序遍歷右子樹。先序遍歷是先訪問,再入棧；而中序遍歷則是先入棧，彈棧后再訪問。將二叉樹的根節(jié)點(diǎn)入棧，如果該節(jié)點(diǎn)有左孩子，將左孩子直接入棧，重復(fù)該操作，直到該節(jié)點(diǎn)無左孩子；在將棧頂元素出棧，并訪問該節(jié)點(diǎn)指向的節(jié)點(diǎn)，如果該指針指向的右孩子存在，則將當(dāng)前指針指向右孩子節(jié)點(diǎn)。重復(fù)執(zhí)行步驟直到棧為空為止。操作函數(shù)為void z_print(Tree T )。后序遍歷：先后序遍歷左子樹，在后序遍歷右子樹，最后訪問根節(jié)點(diǎn)。先將根節(jié)點(diǎn)入棧，如果該節(jié)點(diǎn)左孩子節(jié)
研究報(bào)告相關(guān)推薦
鄂ICP備17016276號(hào)-1