二叉排序樹的實現(xiàn)課程設(shè)計報告

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

2、左子樹。然后利用插入函數(shù)將該元素插入原樹。對二叉樹進(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)。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（請輸入要進(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é)果輸人省遂行:國作拘數(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(不存在您要刪除的數(shù)%d匚x);re

4、turnp;if(p-lch)s=p-lch;/s指向其左子樹;f=p-lch;/f指向其左子樹;while(s-rch)/搜索左子樹的最右邊的葉子結(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的左子樹指向s的左子樹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è)計心得、存在問題及解決方法通過這次課程設(shè)計，我進(jìn)一步的懂得了二叉鏈表的建立方法，進(jìn)一步的了解了二叉排序樹的構(gòu)造方法。對函數(shù)的構(gòu)造以及調(diào)用有了更進(jìn)一步的掌握，讓我在調(diào)試程序是有了一定的經(jīng)歷。多考慮算法的