何彬?qū)嶒?yàn)報(bào)告.doc

《何彬?qū)嶒?yàn)報(bào)告.doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、計(jì)算機(jī)科學(xué)與工程學(xué)院《算法與數(shù)據(jù)結(jié)構(gòu)》實(shí)驗(yàn)報(bào)告(九)專(zhuān)業(yè)班級(jí)2013網(wǎng)絡(luò)工程01實(shí)驗(yàn)地點(diǎn)423機(jī)房學(xué)生學(xué)號(hào)指導(dǎo)教師趙卿松學(xué)生姓名實(shí)驗(yàn)時(shí)間實(shí)驗(yàn)項(xiàng)目查找技術(shù)綜合應(yīng)用實(shí)驗(yàn)類(lèi)別基礎(chǔ)性（）設(shè)計(jì)性（√）綜合性（）其它（）實(shí)驗(yàn)?zāi)康募耙螅?）熟練掌握查找的常用算法；（2）設(shè)計(jì)和應(yīng)用查找算法解決比較簡(jiǎn)單的實(shí)際問(wèn)題。成績(jī)?cè)u(píng)定表類(lèi)別評(píng)分標(biāo)準(zhǔn)分值得分合計(jì)上機(jī)表現(xiàn)積極出勤、遵守紀(jì)律按要求完成設(shè)計(jì)任務(wù)30分程序與報(bào)告程序代碼規(guī)范、功能正確報(bào)告詳實(shí)完整、體現(xiàn)收獲70分說(shuō)明：評(píng)閱教師：趙卿松日期：2015年6月13日實(shí)驗(yàn)內(nèi)容實(shí)驗(yàn)內(nèi)容：二叉排序樹(shù)。任意給定一組數(shù)據(jù)，設(shè)計(jì)一個(gè)算法

2、，建立一棵二叉排序樹(shù)，對(duì)它進(jìn)行查找、插入、刪除等操作。實(shí)驗(yàn)說(shuō)明：二叉排序樹(shù)存儲(chǔ)結(jié)構(gòu)如下：typedefstructBiTNode{//結(jié)點(diǎn)結(jié)構(gòu)structBiTNode*lchild,*rchild;//左右孩子指針}BiTNode,*BiTree;二叉排序樹(shù)插入算法偽代碼如下：1.若root是空樹(shù)，則將結(jié)點(diǎn)s作為根結(jié)點(diǎn)插入；否則2.若s->data＜root->data，則把結(jié)點(diǎn)s插入到root的左子樹(shù)中；否則3.把結(jié)點(diǎn)s插入到root的右子樹(shù)中。二叉排序樹(shù)中刪除一個(gè)結(jié)點(diǎn)f的左孩子結(jié)點(diǎn)p算法偽代碼如下：1.若結(jié)點(diǎn)p是葉子，則直接刪除結(jié)點(diǎn)p；2.

3、若結(jié)點(diǎn)p只有左子樹(shù)，則只需重接p的左子樹(shù)；若結(jié)點(diǎn)p只有右子樹(shù)，則只需重接p的右子樹(shù)；3.若結(jié)點(diǎn)p的左右子樹(shù)均不空，則3.1查找結(jié)點(diǎn)p的右子樹(shù)上的最左下結(jié)點(diǎn)s以及結(jié)點(diǎn)s的雙親結(jié)點(diǎn)par；3.2將結(jié)點(diǎn)s數(shù)據(jù)域替換到被刪結(jié)點(diǎn)p的數(shù)據(jù)域；3.3若結(jié)點(diǎn)p的右孩子無(wú)左子樹(shù)，則將s的右子樹(shù)接到par的右子樹(shù)上；否則，將s的右子樹(shù)接到結(jié)點(diǎn)par的左子樹(shù)上；3.4刪除結(jié)點(diǎn)s；實(shí)驗(yàn)內(nèi)容#include#include#include#defineMax100typedefintKeyType;typedefst

4、ructnode{KeyTypekey;structnode*lchild,*rchild;}BSTNode;intInsertBST(BSTNode*&p,KeyTypek)//插入關(guān)鍵字為k的結(jié)點(diǎn){if(p==NULL){p=(BSTNode*)malloc(sizeof(BSTNode));p->key=k;p->lchild=p->rchild=NULL;return1;}elseif(k==p->key)return0;elseif(kkey)returnInsertBST(p->lchild,k);elsereturnInse

5、rtBST(p->rchild,k);}BSTNode*CreateBST(KeyTypeA[],intn)//創(chuàng)建二叉排序樹(shù){BSTNode*bt=NULL;inti=0;while(i

6、

7、bt->key==k)returnbt;if(kkey)returnSearchBST(bt->lchild,k);elsereturnSearchBST(bt->rch

8、ild,k);}voidcharu(BSTNode*&bt){KeyTypen;printf("請(qǐng)輸入你要插入的元素：");scanf("%d",&n);InsertBST(bt,n);}voidchazhao(BSTNode*bt){system("cls");//清屏intk;BSTNode*a;printf("請(qǐng)輸入要查找的元素：");scanf("%d",&k);a=SearchBST(bt,k);if(a!=NULL)printf("找到了元素%d",k);elseprintf("找不到該元素");}voidshuru(BSTN

9、ode*&e,int&n){system("cls");//清屏intm,a[Max]={0},i;printf("請(qǐng)輸入二叉排序樹(shù)中元素的個(gè)數(shù)：");scanf("%d",&m);n=m;for(i=0;ilchild);printf("%d",b->key);print1(b->rchild);}

10、}voidprint(BSTNode*b){system("cls");//清屏print1(b);}intDeleteBST(BSTN