《二叉排序樹(shù)的操作》課程設(shè)計(jì)報(bào)告

1、內(nèi)蒙古科技大學(xué)本科生課程設(shè)計(jì)論文數(shù)據(jù)結(jié)構(gòu)與算法題 學(xué) 專(zhuān) 班 級(jí)：13-1 班日 期：2015 年 1 月 6 日內(nèi)蒙古科技大學(xué)二叉排序樹(shù)的操作 四、進(jìn)度安排六、建議參考資料 C 等 1內(nèi)蒙古科技大學(xué)目錄 .5.6 2內(nèi)蒙古科技大學(xué) 二叉排序樹(shù)的操作以二叉鏈表表示二叉排序樹(shù)，在此基礎(chǔ)上實(shí)現(xiàn)二叉排序樹(shù)的操作。要求設(shè)計(jì)類(lèi)（或類(lèi)模板）來(lái)描述二叉排序樹(shù)，包含必要的構(gòu)造函數(shù)和析構(gòu)函數(shù)，以及其他能夠完成如下功能的成員函數(shù)： 創(chuàng)建二叉排序樹(shù) 輸出二叉排序樹(shù) 在二叉排序樹(shù)中查找給定值 在二叉排序樹(shù)中插入新結(jié)點(diǎn) 在二叉排序樹(shù)中刪除給定值3內(nèi)蒙古科技大學(xué) 序叉樹(shù)結(jié)點(diǎn)、查找給定的二叉樹(shù)結(jié)點(diǎn)、輸出二排序叉樹(shù)、退出。設(shè)

2、置二叉排序樹(shù)根結(jié)點(diǎn)添加二排序叉樹(shù)結(jié)點(diǎn)刪除二排序叉樹(shù)結(jié)點(diǎn)查找給定的二叉樹(shù)結(jié)點(diǎn)退出功能說(shuō)明： 設(shè)置二叉排序樹(shù)根結(jié)點(diǎn)：為新創(chuàng)建的二叉排序樹(shù)創(chuàng)建根節(jié)點(diǎn)。 添加二排序叉樹(shù)結(jié)點(diǎn)：需要輸入創(chuàng)建節(jié)點(diǎn)的數(shù)目，然后創(chuàng)建一定數(shù)目的二叉排序樹(shù)結(jié)點(diǎn)。 字母，然后查找，找到后刪除，否則，告知未找到， 查找給定的二叉樹(shù)結(jié)點(diǎn)：給定一個(gè)數(shù)據(jù)字母)，然后查找，并給出提示。 輸出二排序叉樹(shù)：按照先序遍歷并輸出二叉排序樹(shù)的結(jié)點(diǎn)數(shù)據(jù)。 退出：退出程序。4內(nèi)蒙古科技大學(xué) 定義格式如下：3.1 二叉樹(shù) BT抽象數(shù)據(jù)類(lèi)型的設(shè)計(jì)ADT 數(shù)據(jù)對(duì)象 ：先定義一個(gè)二叉樹(shù)結(jié)點(diǎn)的結(jié)構(gòu)體：typedef struct bstchar data;struc

3、t bst *left;struct bst *right;struct bst *father;BSTree,*BST;root 是指向二叉樹(shù)結(jié)點(diǎn)的指針；數(shù)據(jù)關(guān)系：R=(V 或者 C)P(V 或者 D, 表示由運(yùn)算符 P 結(jié)合起來(lái)的表達(dá)式 E基本操作：BST InitRoot()結(jié)點(diǎn)的基址給指針。void Inserter(root, key)初始條件：二叉排序樹(shù)不為空，存在根節(jié)點(diǎn)；右孩子指針置空，父指針指向父節(jié)點(diǎn)地址，然后返回主菜單。BSTree *SearchKey(root,key)5內(nèi)蒙古科技大學(xué)初始條件：二叉排序樹(shù)不為空，存在根節(jié)點(diǎn)；則返回次數(shù)據(jù)項(xiàng)的地址給指針變量，沒(méi)有則就返回該數(shù)

4、據(jù)按照二叉排序樹(shù)規(guī)則，應(yīng)該插入位置的父節(jié)點(diǎn)地址。void DeleteKey(root,key);初始條件：二叉排序樹(shù)不為空，存在根節(jié)點(diǎn)；操作結(jié)果：輸入一個(gè)字符型數(shù)據(jù)，調(diào)用 BSTree 函數(shù)，除結(jié)點(diǎn)，修改相應(yīng)二叉樹(shù)結(jié)點(diǎn)指針，返回主菜單；沒(méi)有則就返回提示語(yǔ)句“沒(méi)有void ChainTree_LDR(root)初始條件：二叉排序樹(shù)不為空，存在根節(jié)點(diǎn)；操作結(jié)果：按照中序遍歷并輸出有序的數(shù)據(jù)序列。 ADT BT3.2 BT 抽象數(shù)據(jù)類(lèi)型的設(shè)計(jì)class BTprivate:BST root;public:BT() :root(NULL) BST InitRoot();void Inserter(B

5、STree *t,char key);BSTree *SearchKey(BSTree *t,char key);void DeleteKey(BSTree *t,char key);void ChainTree_LDR(BSTree *bt);6內(nèi)蒙古科技大學(xué)7內(nèi)蒙古科技大學(xué)4.3 函數(shù)的調(diào)用關(guān)系main 主程序中序遍歷二叉排序樹(shù)創(chuàng)建根節(jié)點(diǎn)顯示菜單插入結(jié)點(diǎn)查找結(jié)點(diǎn)刪除結(jié)點(diǎn)8內(nèi)蒙古科技大學(xué)4.4 主程序流程圖算法：主程序主要用運(yùn)了 switch 結(jié)構(gòu)，使得主程序更加方便的調(diào)用成員函數(shù)，各個(gè)成員函數(shù)間的關(guān)系也清晰明了。否4.5 主要算法的流程圖據(jù)存入結(jié)點(diǎn)的數(shù)據(jù)域中同時(shí)給左右孩子指針和父指針置指針

6、。結(jié)束輸入返回主界面9內(nèi)蒙古科技大學(xué)初始條件：二叉排序樹(shù)不為空，存在根節(jié)點(diǎn)；操作結(jié)果：輸入一個(gè)字符型數(shù)是排序樹(shù)的構(gòu)造方法返回要插入旳數(shù)否開(kāi)始返回主菜單。返回主界面開(kāi)始初始條件：二叉排序樹(shù)不為空，存在根節(jié)點(diǎn)；操作結(jié)果：輸入一個(gè)字符型數(shù)據(jù)，先尋找二叉排序樹(shù)中是否有此數(shù)據(jù)的，有則返回次數(shù)據(jù)項(xiàng)的地址給指針變量，沒(méi)有則就返回該數(shù)據(jù)按照二叉排序樹(shù)規(guī)則，應(yīng)該插入位置的父節(jié)點(diǎn)地址。否是結(jié)束返回主界面內(nèi)蒙古科技大學(xué)初始條件：二叉排序樹(shù)不為空，存在根節(jié)點(diǎn)；操作結(jié)果：輸入一個(gè)字符 型 數(shù) 據(jù) ， 調(diào) 用 BSTree*SearchKey(root,key)函數(shù)，先尋找二叉排序樹(shù)中是否有此數(shù)據(jù)的，有則返回次數(shù)據(jù)項(xiàng)的地

7、址給指針變量，然后就此節(jié)點(diǎn)的特征分為四類(lèi)：刪除葉子節(jié)點(diǎn)；刪除只有右孩子的節(jié)點(diǎn)；刪除只有左孩子的節(jié)點(diǎn)；刪除左右孩子都有的節(jié)點(diǎn)，根據(jù)結(jié)點(diǎn)類(lèi)型進(jìn)入不同刪除模塊，刪除結(jié)點(diǎn)，修改相應(yīng)二叉樹(shù)結(jié)點(diǎn)指針，返回主菜單；沒(méi)有則就返回提示語(yǔ)句“沒(méi)有找到該數(shù)據(jù)否是結(jié)束返回主界面內(nèi)蒙古科技大學(xué)ChainTree_LDR(root)初始條件：二叉排序樹(shù)不為空，存在根節(jié)點(diǎn)；并輸出有序的數(shù)據(jù)序列。結(jié)束輸入返回主界面內(nèi)蒙古科技大學(xué)：2.設(shè)置二叉排序樹(shù)根節(jié)點(diǎn)：結(jié)束到主界面。內(nèi)蒙古科技大學(xué)3.添加二叉排序樹(shù)結(jié)點(diǎn)：先進(jìn)行判空操作，若二叉排序樹(shù)為空，給出提示：內(nèi)蒙古科技大學(xué)先進(jìn)行判空操作，若二叉排序樹(shù)為空，給出提示：內(nèi)蒙古科技大學(xué)先進(jìn)行判空操作，若二叉排序樹(shù)為空，給出提示：否則按照提示輸入要?jiǎng)h除的結(jié)點(diǎn)數(shù)據(jù)：內(nèi)蒙古科技大學(xué)6.查找給定二叉排序樹(shù)結(jié)點(diǎn)：在主界面，輸入 4，進(jìn)入查找界面。先進(jìn)行判空操作，若二叉排序樹(shù)為空，給出提示：內(nèi)蒙古科技大學(xué)然后按照提示輸入要查找的結(jié)點(diǎn)數(shù)據(jù)：內(nèi)蒙古科技大學(xué)在主界面，輸入 0，退出程序。內(nèi)蒙古科技大學(xué) 這次課程設(shè)計(jì)花費(fèi)了將近 20 天時(shí)間，這次課程設(shè)計(jì)在有了前幾次課設(shè)的經(jīng) 后后修改，換思路繼續(xù)修改，好多回，又逢各種考