第九組數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)二叉排序樹實(shí)現(xiàn)-展示頁
2025-08-06 08:53本頁面
【正文】 ，回到父節(jié)點(diǎn)，如果該指針節(jié)點(diǎn)的右孩子存在，則將該指針指向的右孩子節(jié)點(diǎn)重復(fù)執(zhí)行以上步驟，直到桟為空為止?；舅惴ㄋ枷耄?，將根節(jié)點(diǎn)入棧：如果該節(jié)點(diǎn)左孩子存在，則訪問該左孩子節(jié)點(diǎn)，并將其指針入棧。則可以用棧保存。其一可以用棧記憶在訪問途中將依次遇到的節(jié)點(diǎn)保存下來。在遍歷左、右子樹時(shí)，仍然先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹，如果二叉樹為空則返回。先序遍歷也叫做先根遍歷。二叉排序樹又稱二叉查找樹，當(dāng)二叉排序樹不為空時(shí)，首先將給定的值和根節(jié)點(diǎn)的關(guān)鍵字比較，若相等則查找成功，否則將依據(jù)給定的值和根節(jié)點(diǎn)關(guān)鍵字之間的大小關(guān)系，分別在左子樹或右子樹上繼續(xù)進(jì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)榉强占纯伞６媾判驑涫且环N動(dòng)態(tài)樹表，其特點(diǎn)是樹的結(jié)構(gòu)通常不是一次生成的，而是在查找的過程中，當(dāng)樹中不存在關(guān)鍵字等于給定值得節(jié)點(diǎn)時(shí)在進(jìn)行插入。在二叉排序樹中刪除一個(gè)節(jié)點(diǎn)的算法為voidDeleteData(bstreeamp。假設(shè)二叉排序樹上刪除節(jié)點(diǎn)為*p（指向節(jié)點(diǎn)的指針為p），其雙親節(jié)點(diǎn)為*f（節(jié)點(diǎn)指針為f）。最后，返回根節(jié)點(diǎn)T。 pare()對(duì)數(shù)組和二叉排序樹的查找效率進(jìn)行比較比較。 *SearchBST(bstreet,keytype key)查找節(jié)點(diǎn)。3. 從二叉排序樹t中通過操作void Delete(bstreeamp。：()操作建立二叉排序樹。刪除結(jié)點(diǎn)函數(shù)，采用邊查找邊刪除的方式。對(duì)二叉樹進(jìn)行中序遍歷采用遞歸函數(shù)的方式。如果查找到相等的則插入其左子樹。（設(shè)計(jì)思想）無結(jié)點(diǎn)x存在含x的結(jié)點(diǎn)，則刪除該結(jié)點(diǎn)，并作中序遍歷找到該節(jié)點(diǎn)x輸入元素x，查找二叉排序樹T對(duì)二叉排序樹T作中序遍歷,并輸出結(jié)果二叉鏈表作存儲(chǔ)結(jié)構(gòu)和順序表作存儲(chǔ)結(jié)構(gòu)輸入數(shù)列L， 以回車(‘\\n’)為輸入結(jié)束標(biāo)志生成二叉排序樹T；詳細(xì)設(shè)計(jì)思想：建立二叉排序樹采用邊查找邊插入的方式。 黃淮學(xué)院“數(shù)據(jù)結(jié)構(gòu)”課程設(shè)計(jì)報(bào)告系 （院）： 信息工程學(xué)院 設(shè)計(jì)題目： 二叉排序樹的實(shí)現(xiàn) 專業(yè)班級(jí)： 軟件工程15級(jí) 小組成員： 唐二虎、趙夢(mèng)娟、賈月 指導(dǎo)教師： 汪洋 完成時(shí)間： 17二叉排序樹的實(shí)現(xiàn)1） 實(shí)現(xiàn)二叉排序樹，包括生成、插入，刪除；2） 對(duì)二叉排序樹進(jìn)行先根、中根、和后根非遞歸遍歷；3） 每次對(duì)樹的修改操作和遍歷操作的顯示結(jié)果都需要在用樹的形狀表示出來。4） 分別用二叉排序樹和數(shù)組去存儲(chǔ)一個(gè)班(50人以上)的成員信息(至少包括學(xué)號(hào)、姓名、成績(jī)3項(xiàng)),對(duì)比查找效率，并說明為什么二叉排序樹效率高（或者低）。查找函數(shù)采用遞歸的方式進(jìn)行查找。然后利用插入函數(shù)將該元素插入原樹。在根結(jié)點(diǎn)不為空的情況下，先訪問左子樹，再訪問根結(jié)點(diǎn)，最后訪問右子樹。如果沒有查找到，進(jìn)行提示；如果查找到結(jié)點(diǎn)則將其左子樹最右邊的節(jié)點(diǎn)的數(shù)據(jù)傳給它，然后刪除其左子樹最右邊的節(jié)點(diǎn)。(bstreet,intkey,nametypename,double grade)插入一個(gè)節(jié)點(diǎn)。p)刪除任意節(jié)點(diǎn)。=SearchBST(t,key)查詢，并修改節(jié)點(diǎn)信息 。從鍵盤中輸入關(guān)鍵字及記錄，并同時(shí)調(diào)用插入函數(shù)并不斷進(jìn)行插入。：二叉排序樹上刪除一個(gè)階段相當(dāng)于刪去有序系列中的一個(gè)記錄，只要在刪除某個(gè)節(jié)點(diǎn)之后依舊保持二叉排序樹的性質(zhì)即可。若*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ū)（或直接后繼）。t,keytype key)若二叉排序樹t中存在關(guān)鍵字等于key的數(shù)據(jù)元素，則刪除該數(shù)據(jù)元素節(jié)點(diǎn)，并返回TRUE，否則返回FALSE。新插入的節(jié)點(diǎn)一定是一個(gè)新添加的葉子節(jié)點(diǎn)，并且是查找不成功時(shí)查找路徑上訪問的最后一個(gè)節(jié)點(diǎn)的左孩子或右孩子的節(jié)點(diǎn)。二叉排序樹的插入算法為bstreeInsertBST(bstreet,intkey,nametypename,double grade) 若二叉排序樹中不存在關(guān)鍵字等于key的數(shù)據(jù)元素時(shí)，插入元素并返回TRUE。為此定義一個(gè)二叉排序樹的查找算法為bstnode *SearchBST(bstreet,keytype key)
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號(hào)-1