二叉排序樹(shù)的基本操作的實(shí)現(xià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