数据结构课程设计之二叉排序树基本操作的实现盘

设计题目<二>：6.4.1二叉排序树基本操作的实现盘P134 ............................................................... 错误！未定义书签

一、设计要求 ................................................................................................................................................................

1．问题描述 ..........................................................................................................................................................2． 需求分析 ........................................................................................................................................................二、概要设计 ................................................................................................................................................................

1．主界面设计 ......................................................................................................................................................2． 存储结构设计 ................................................................................................................................................3． 系统功能设计 ................................................................................................................................................三、 模块设计 ..............................................................................................................................................................

1．模块设计 ..........................................................................................................................................................2． 系统子程序及功能设计 ................................................................................................................................3． 函数主要调用关系图 ....................................................................................................................................四、详细设计 ................................................................................................................................................................

1．数据类型定义 ..................................................................................................................................................2． 系统主要子程序详细设计 ............................................................................................................................

五、测试分析 ........................................................................................................................................................................六、 用户手册 ......................................................................................................................................................................七、 调试报告 ......................................................................................................................................................................

设计题目<二>：6.4.1二叉排序树基本操作的实现盘P134 一、设计要求 1．问题描述

从键盘读入一组数据，并建立排序树并对其进行查找，遍历，格式化输出操作。

2．需求分析

二叉树是一种数据结构，用于保存和处理树状的数据，比如家谱。他的应用极为广泛，因为根据数据结构的理论，任何复杂的数能够转为二叉树，并进行处理，二叉树在排序，查找，大规模数据索引方面有很多很多应用。而且二叉树排序是简单算法排序中速度是最快的。

在二叉树的一些应用中，常常要求在树中查找具有某些特征的节点，或是对数中全部节点逐一进行某种处理。这就提出了遍历二叉树。根据遍历的方向的选择，就有了后序遍历二叉树查找，删除等。因此掌握二叉树的算法非常重要，而且高效的算法能够节省很多成本。

二、概要设计 1．主界面设计

图2-1 主界面

2．存储结构设计

typedef struct Bstnode {

//链表结点类型 //定义要操作的步骤 //链队列的类型定义

int key;

struct Bstnode *rchild,*lchild;

}Bstnode,*Bstree;

3．系统功能设计

本系统分为以下6个功能模块。 （1）创建二叉排序树。 （2）插入。插入元素到序列中

（3）查找。分为查找成功和查找不成功。 （4）遍历。遍历二叉树序列 （5）删除。删除存在的元素 （6）退出。退出整个系统

三、模块设计 1．模块设计

主程序模块 菜单选项模块 二叉树操作模块

图2-2 模块调用示意图

2．系统子程序及功能设计

本系统共设置5个子程序，各子程序的函数名及功能说明如下。 （1）Bstree Create()

//初始化空数 //插入元素

//查找关键字为key的

（2）Bstree Insert(Bstree tree,int key) （3）Bstree Search(Bstree tree,int key) 节点

（4）void Traverse(Bstree tree)

//遍历

//删除关键字为key的

（5）Bstree Delete(Bstree tree,int key) 节点

以下是二叉树的基本操作。 Bstree Create();

//创建二叉排序树 //插入 //查找 //遍历

Bstree Insert(Bstree tree,int key); Bstree Search(Bstree,int key); void Traverse(Bstree,int key); void Traverse(Bstree tree); Bstree Delete(Bstree tree,int key);

//删除

3．函数主要调用关系图

7Main（） 四、详细设计 1．数据类型定义

（1）二叉树的定义

1 2 3 4 5 6 图2-5 系统函数调用关系图

typedef struct Bstnode { int key;

//链表结点类型

struct Bstnode *rchild,*lchild;

}Bstnode,*Bstree; （2）全局变量的定义 int key1,key2,key3; int select,flag;

义

2．系统主要子程序详细设计

（1）创建二叉树 Bstree Create() { int key;

Bstree tree=NULL;

scanf(\ while(key!=0) { tree=Insert(tree,key); scanf(\

} return tree;

}

（2）插入元素

Bstree Insert(Bstree tree,int key) { Bstree p=tree;

Bstree s,f;

while(p!=NULL)

//关键字定义

//选择项定义和标识符定

//初始化空数

//逐个插入节点

{ f=p;

if(key==p->key)

return tree;

if(keykey)

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;

if(keykey)

f->lchild=s;

else

f->rchild=s;

return tree;

}

（3）查找

Bstree Search(Bstree tree,int key) { Bstree p=tree; int flag=0; while(p!=NULL) {

if(p->key==key)

{

//申请空间

//新节点为二叉排序树的根//查找关键字为key的节点

本文来源：https://www.bwwdw.com/article/qdl2.html