二叉排序樹(shù)的實(shí)現(xiàn)課程設(shè)計(jì)報(bào)告

1、中北大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)說(shuō)明書(shū)學(xué)生：程亞男學(xué)號(hào)：1021011616學(xué)院：軟件學(xué)院專業(yè)：軟件工程題目：二叉排序樹(shù)的實(shí)現(xiàn)指導(dǎo)教師何志英1.設(shè)計(jì)任務(wù)概述：2011年12月20日OK!功能描述：(1)以回車(chē)(n)為輸入完畢標(biāo)志，輸入數(shù)列L,生成一棵二叉排序樹(shù)T;(2)對(duì)二叉排序樹(shù)T作中序遍歷，輸出結(jié)果；(3購(gòu)入元素x,查找二叉排序樹(shù)T,假設(shè)存在含x的結(jié)點(diǎn)，那么刪除該結(jié)點(diǎn)，并作中序遍歷(執(zhí)行操作2)；否那么輸出信息“無(wú)x。2 .本設(shè)計(jì)所采用的數(shù)據(jù)構(gòu)造二叉樹(shù)及二叉鏈表3 .功能模塊詳細(xì)設(shè)計(jì)3.1 詳細(xì)設(shè)計(jì)思想建立二叉排序樹(shù)采用邊查找邊插入的方式。查找函數(shù)采用遞歸的方式進(jìn)展查找。如果查找到相等的那么插入其

2、左子樹(shù)。然后利用插入函數(shù)將該元素插入原樹(shù)。對(duì)二叉樹(shù)進(jìn)展中序遍歷采用遞歸函數(shù)的方式。在根結(jié)點(diǎn)不為空的情況下，先訪問(wèn)左子樹(shù)，再訪問(wèn)根結(jié)點(diǎn)，最后訪問(wèn)右子樹(shù)。刪除結(jié)點(diǎn)函數(shù)，采用邊查找邊刪除的方式。如果沒(méi)有查找到，進(jìn)展提示；如果查找到結(jié)點(diǎn)那么將其左子樹(shù)最右邊的節(jié)點(diǎn)的數(shù)據(jù)傳給它，然后刪除其左子樹(shù)最右邊的節(jié)點(diǎn)。3.2 核心代碼1主菜單模塊intmain()LNoderoot=NULL;intNum,a,x;printf(nn*n)printf(*主菜單*n)printf(*1：進(jìn)展中序排列printf(*2:進(jìn)展刪除操作printf(*3:退出printf(*n);printf（請(qǐng)輸入要進(jìn)展操作的數(shù)字以0完

3、畢：n）;*n);*n);*n);運(yùn)行結(jié)果3中序遍歷模塊voidview(LNodep)/中序遍歷函數(shù)if(p)view(p-lch);printf(%d,p-date);view(p-rch);/遞歸調(diào)用return;return;運(yùn)行結(jié)果輸人省遂行:國(guó)作拘數(shù)字以用言束3刪除模塊LNodeDelNode(LNodet,intx)LNodep=t;LNodeq=NULL;LNodes;LNodef;while(p!=NULL)if(p-date=x)break;q=p;if(xdate)p=p-lch;elsep=p-rch;if(p=NULL)printf(不存在您要?jiǎng)h除的數(shù)%d匚x);re

4、turnp;if(p-lch)s=p-lch;/s指向其左子樹(shù);f=p-lch;/f指向其左子樹(shù);while(s-rch)/搜索左子樹(shù)的最右邊的葉子結(jié)點(diǎn)f=s;s=s-rch;p-date=s-date;iff!=s)假設(shè)不是p的左孩子，把r的左孩子作為r的父親的右孩子f-rch=s-lch;elsep-lch=s-lch;否那么結(jié)點(diǎn)p的左子樹(shù)指向s的左子樹(shù)free(s);returnp;elseif(q-lch=p)q-lch=p-rch;elseq-rch=p-rch;free(p);returnq;3.3程序運(yùn)行結(jié)果4課程設(shè)計(jì)心得、存在問(wèn)題及解決方法通過(guò)這次課程設(shè)計(jì)，我進(jìn)一步的懂得了二叉鏈表的建立方法，進(jìn)一步的了解了二叉排序樹(shù)的構(gòu)造方法。對(duì)函數(shù)的構(gòu)造以及調(diào)用有了更進(jìn)一步的掌握，讓我在調(diào)試程序是有了一定的經(jīng)歷。多考慮算法的