




版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、二叉排序樹(shù)的基本操作的實(shí)現(xiàn)I. 設(shè)計(jì)要求1. 問(wèn)題描述 從磁盤讀入一組數(shù)據(jù),建立二叉排序樹(shù)并對(duì)其進(jìn)行查找、遍歷、插入、刪除等基本操作。2. 需求分析建立二叉排序樹(shù)并對(duì)其進(jìn)行查找,包括成功和不成功兩種情況。II. 概要設(shè)計(jì)為了實(shí)現(xiàn)需求分析中的功能,可以從以下3方面著手設(shè)計(jì)。1. 主界面設(shè)計(jì)為了方便對(duì)二叉排序樹(shù)的基本操作,設(shè)計(jì)一個(gè)包含多個(gè)菜單選項(xiàng)的主控制子程序以實(shí)現(xiàn)二叉排序樹(shù)的各項(xiàng)功能。本系統(tǒng)的主控制菜單運(yùn)行界面如圖1所示。圖1二叉排序樹(shù)的基本操作的主菜單2. 存儲(chǔ)結(jié)構(gòu)的設(shè)計(jì)本程序主要采二叉樹(shù)結(jié)構(gòu)類型來(lái)表示二叉排序樹(shù)。其中二叉樹(shù)節(jié)點(diǎn)由1個(gè)表示關(guān)鍵字的分量組成,還有指向該左孩子和右孩子的指針。3.
2、系統(tǒng)功能設(shè)計(jì)本程序設(shè)置了5個(gè)子功能菜單,其設(shè)計(jì)如下。1) 建立二叉排序樹(shù)。根據(jù)系統(tǒng)提示,輸入節(jié)點(diǎn)的關(guān)鍵字,并以0作為結(jié)束的標(biāo)識(shí)符。該功能由Bstree Create()函數(shù)實(shí)現(xiàn)。2) 插入二叉排序新的節(jié)點(diǎn)信息。每次只能夠插入一個(gè)節(jié)點(diǎn)信息,如果該節(jié)點(diǎn)已經(jīng)存在,則不插入。該功能由Bstree Insert(y)函數(shù)實(shí)現(xiàn)。3) 查詢二叉排序樹(shù)的信息。每次進(jìn)行查詢,成功則顯示“查詢到該節(jié)點(diǎn)”,不成功則“顯示查詢不到該節(jié)點(diǎn)“該功能由Bstree Search()函數(shù)實(shí)現(xiàn)。4) 刪除二叉排序樹(shù)的節(jié)點(diǎn)信息。可以對(duì)二叉排序樹(shù)中不需要的節(jié)點(diǎn)進(jìn)行刪除,刪除的方式是輸入關(guān)鍵字,查詢到該節(jié)點(diǎn)后刪除。該功能由Bstre
3、e Delete()函數(shù)實(shí)現(xiàn)。 5) 遍歷二叉排序樹(shù)。遍歷二叉排序樹(shù)可以顯示該二叉排序樹(shù)的全部節(jié)點(diǎn)信息。該功能由void Traverse()實(shí)現(xiàn)。III. 模塊設(shè)計(jì)1. 模塊設(shè)計(jì)本程序包含兩個(gè)模塊:主程序模塊和二叉排序樹(shù)操作模塊。其調(diào)用關(guān)系如圖2主程序模塊二叉排序樹(shù)操作模塊 圖2模塊調(diào)用示意圖2. 系統(tǒng)子程序及其功能設(shè)計(jì)本系統(tǒng)共設(shè)計(jì)了5個(gè)子程序,個(gè)程序的的函數(shù)名及其功能說(shuō)明如下:1) Bstree Create(); /創(chuàng)建二叉排序樹(shù)2) Bstree Insert(Bstree tree,int key); /插入3) Bstree Search(Bstree tree,int key);
4、 /查找4) void Traverse(Bstree tree); /遍歷5) Bstree Delete(Bstree tree,int key); /刪除信息3. 函數(shù)主要的調(diào)用關(guān)系本系統(tǒng)9個(gè)子程序見(jiàn)的主要調(diào)用關(guān)系圖3.Main()Main()Insert()Search( )Traverse ()Delete ()IV. 詳細(xì)設(shè)計(jì)1. 數(shù)據(jù)類型定義本系統(tǒng)采用二叉樹(shù)結(jié)構(gòu)存儲(chǔ)節(jié)點(diǎn)信息,節(jié)點(diǎn)定義如下: typedef struct Bstnodeint key;struct Bstnode *lchild,*rchild;Bstnode,* Bstree;2. 主要子程序的詳細(xì)設(shè)計(jì)1) 二叉
5、排序樹(shù)的創(chuàng)建函數(shù),主要用來(lái)建立二叉排序樹(shù)。 Bstree Create() int key;Bstree tree=NULL; /初始化空樹(shù)scanf("%d",&key); while(key!=0)tree=Insert(tree,key); /逐個(gè)插入節(jié)點(diǎn)scanf("%d",&key);return tree;2) 二叉排序插入函數(shù)如下: Bstree Insert(Bstree tree,int key)Bstree p=tree;Bstree s,f;while (p!=NULL)f=p; if(key=p->key)
6、return tree; if(key<p->key) p=p->lchild; else p=p->rchild;s=(Bstree)malloc(sizeof(Bstnode);s->key=key;s->lchild=NULL;s->rchild=NULL;if(tree=NULL) return s; /新節(jié)點(diǎn)為二叉排序樹(shù)的根if(key<f->key) f->lchild=s; else f->rchild=s; return tree; 3) 二叉排序樹(shù)查詢函數(shù)如下: Bstree Search(Bstree tre
7、e,int key)Bstree p=tree; int flag=0; while(p!=NULL) if(p->key=key) printf("查詢到該節(jié)點(diǎn)!");flag=1;return(p);break;if (key<p->key) p=p->lchild; else p=p->rchild; if(flag=0)printf("查詢不到關(guān)鍵字為%d的節(jié)點(diǎn)!",key);return NULL; V. 測(cè)試分析1. 二叉排序樹(shù)的建立首先進(jìn)入主菜單,如圖1。在主菜單下,用戶根據(jù)菜單的選項(xiàng)輸入1,然后按照提示建立二
8、叉排序樹(shù),并以0未結(jié)束符。運(yùn)行的結(jié)果如圖4. 圖4二叉排序樹(shù)的建立2. 遍歷二叉樹(shù)的節(jié)點(diǎn)信息在主菜單下,用戶選擇4,可以打印出全部的節(jié)點(diǎn)信息。運(yùn)行的結(jié)果如圖5. 圖5遍歷二叉排序樹(shù)3. 插入節(jié)點(diǎn)信息信息在主菜單下,用戶選擇2,可以插入一個(gè)新的節(jié)點(diǎn)信息。運(yùn)行的結(jié)果如圖6.圖6插入新的節(jié)點(diǎn)4. 查詢二叉樹(shù)的節(jié)點(diǎn)信息在主菜單下,用戶選擇3,首先通過(guò)輸入關(guān)鍵字查詢相關(guān)信息。運(yùn)行的結(jié)果如圖7. 圖7查詢節(jié)點(diǎn)信息5. 刪除二叉樹(shù)的節(jié)點(diǎn)在主菜單下,用戶選擇5,可以通過(guò)輸入要?jiǎng)h除的關(guān)鍵字來(lái)刪除該節(jié)點(diǎn)的全部信息。運(yùn)行的結(jié)果如圖8. 圖8刪除二叉排序樹(shù)的節(jié)點(diǎn)VI. 原程序清單#include<stdio.h
9、>#include<stdlib.h>#include<malloc.h>/*二叉排序樹(shù)的數(shù)據(jù)結(jié)構(gòu)*/typedef struct Bstnodeint key;struct Bstnode *lchild,*rchild;Bstnode,* Bstree;Bstree Create(); /創(chuàng)建二叉排序樹(shù)Bstree Insert(Bstree tree,int key); /插入Bstree Search(Bstree tree,int key); /查找void Traverse(Bstree tree); /遍歷Bstree Delete(Bstree t
10、ree,int key); /刪除/*創(chuàng)建二叉排序樹(shù)*/Bstree Create() int key;Bstree tree=NULL; /初始化空樹(shù)scanf("%d",&key); while(key!=0)tree=Insert(tree,key); /逐個(gè)插入節(jié)點(diǎn)scanf("%d",&key);return tree;/*插入*/ Bstree Insert(Bstree tree,int key)Bstree p=tree;Bstree s,f;while (p!=NULL)f=p; if(key=p->key) re
11、turn tree; if(key<p->key) p=p->lchild; else p=p->rchild;s=(Bstree)malloc(sizeof(Bstnode);s->key=key;s->lchild=NULL;s->rchild=NULL;if(tree=NULL) return s; /新節(jié)點(diǎn)為二叉排序樹(shù)的根if(key<f->key) f->lchild=s; else f->rchild=s; return tree;/*查找*/Bstree Search(Bstree tree,int key)Bst
12、ree p=tree; int flag=0; while(p!=NULL) if(p->key=key) printf("查詢到該節(jié)點(diǎn)!");flag=1;return(p);break;if (key<p->key) p=p->lchild; else p=p->rchild; if(flag=0)printf("查詢不到關(guān)鍵字為%d的節(jié)點(diǎn)!",key);return NULL; /*遍歷*/void Traverse(Bstree tree)if(tree) Traverse(tree->lchild); pri
13、ntf("%4d",tree->key); Traverse(tree->rchild); /*刪除*/Bstree Delete(Bstree tree,int key)Bstree p=tree; Bstree f,s,q; f=NULL;while(p) /查找關(guān)鍵字為key的節(jié)點(diǎn)if(p->key=key) break; f=p; if(p->key>key) p=p->lchild;else p=p->rchild;if (p=NULL) return tree; if (p->lchild=NULL)|(p->
14、;rchild=NULL) if(f=NULL) if(p->lchild=NULL) tree=p->rchild;else tree=p->lchild;else if (p->lchild=NULL) if(f->lchild=p) f->lchild=p->rchild; else f->rchild=p->rchild; else if(f->lchild=p) f->lchild=p->lchild; else f->lchild=p->lchild; free(p);else q=p;s=p-&g
15、t;lchild; while(s->rchild)q=s;s=s->rchild; if(q=p) q->lchild=s->lchild;p->key=s->key; free(s);return tree;/*/void main() system("color 1E");Bstree tree,p;int key1,key2,key3;int select,flag;printf("#n");printf("|* 歡迎您使用本系統(tǒng) *|n");printf("|*|n")
16、;printf("|* 1.創(chuàng)建二叉排序樹(shù) *|n");printf("|* 2.插入 *|n");printf("|* 3.查找 *|n");printf("|* 4.遍歷 *|n");printf("|* 5.刪除 *|n");printf("|* 6.退出 *|n");printf("*n");while(select!=6) printf("選擇的功能:"); scanf("%d",&select);
17、 switch(select) case 1: printf("請(qǐng)輸入節(jié)點(diǎn)信息(0為結(jié)束符):n"); tree=Create(); printf("n"); break; case 2: printf("插入一個(gè)新的節(jié)點(diǎn):"); scanf("%d",&key1);Insert(tree,key1); printf("插入后得序列為:n"); Traverse(tree); printf("n"); break; case 3: printf("輸入查找的
18、數(shù)據(jù):"); scanf("%d",&key2); p=Search(tree,key2); printf("n"); break; case 4: printf("遍歷所得序列為:n"); Traverse(tree); printf("n"); break; case 5: printf("輸入刪除的數(shù)據(jù):"); scanf("%d",&key3); tree=Delete(tree,key3); printf("刪除后遍歷所得序列:n"); Traverse(tree); printf("n"); break; case 6: printf("謝謝您的使用,再見(jiàn)!n");flag=0;break; def
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 農(nóng)民家庭農(nóng)場(chǎng)創(chuàng)建合同
- 電子商務(wù)合作協(xié)議簽署流程及要點(diǎn)
- 國(guó)際進(jìn)出口貿(mào)易代理協(xié)議
- 工程管理中的溝通藝術(shù)試題及答案
- 行政管理公文寫作模擬考試及試題及答案
- 行政管理的關(guān)鍵績(jī)效指標(biāo)探索與試題及答案
- 2025:加工承攬合同與買賣合同的辨別及應(yīng)用
- 2025前期咨詢服務(wù)合同協(xié)議書(shū)模板
- 確立企業(yè)核心競(jìng)爭(zhēng)力的途徑試題及答案
- 2025電梯維護(hù)保養(yǎng)合同范本
- 第三單元《增強(qiáng)法治意識(shí)》測(cè)試卷-高二思想政治課《職業(yè)道德與法治》附答案
- 教育革新:2024版《認(rèn)識(shí)交通標(biāo)志》課件
- (高清版)DB4202∕T 39-2024 城市橋梁與隧道運(yùn)行監(jiān)測(cè)技術(shù)規(guī)范
- 2024年社區(qū)警務(wù)工作規(guī)范考試題庫(kù)
- 2020-2024年各地中考語(yǔ)文試卷【標(biāo)點(diǎn)符號(hào)使用題】匯集練附答案解析
- 數(shù)據(jù)分析師歷年考試真題試題庫(kù)(含答案)
- 住宅小區(qū)園林景觀綠化工程施工組織設(shè)計(jì)方案
- 物質(zhì)的量說(shuō)課
- 人教版八年級(jí)下冊(cè)歷史教案全冊(cè)
- 企業(yè)網(wǎng)絡(luò)設(shè)備資產(chǎn)清查合同
- 2024年北京普通高中學(xué)業(yè)水平等級(jí)性考試化學(xué)試題及答案
評(píng)論
0/150
提交評(píng)論