二叉排序树_二叉排序树的创建过程_二叉排序树的建立

电子与资讯工程学院

数据结构课程设计报告

( 2012——2013年度第一学期)

课程名称：数据结构课程设计

题 目 一：6.4.1二叉排序树基本操作的实现

院 系：计算机科学系

班 级：10软件本二班

姓 名：学 号：100913005指导教师：孙凌宇老师

成 绩：

2012 年 12 月 01 日

成 绩 评 定

一、 指导教师评语

二、 成绩

指导教师：

日 期：年 月 日

设计题目<一>： 6.4.1二叉排序树基本操作的实现

一、设计要求

1．问题描述

从键盘读入一组数据，建立二叉排序树并对其进行查找、插入、遍历、打印输出操作。测试数据元素关键词序列为｛11，33，44，55，58，79，88｝.

1． 需求分析

(1) 建二叉排序树。按照用户需要的二叉排序树，构建二叉排序树。二叉排序树

(2) 按照树形结构打印输出二叉排序树。

(3) 对二叉排序树进行遍历操作。

(4) 对二叉排序树进行查找，包括成功和不成功两种情况，并给出查找长度。

(5) 对二叉排序树进行插入操作。

二、概要设计

1．主接口设计

图1 二叉排序树操作程序主菜单

2．存储结构设计

本程序主要采二叉树结构类型来表示二叉排序树。其中二叉树节点由1个表示关键词的分量组成，还有数据域（data）、左孩子指针域（Lchild）、和右孩子指针域（Rchild）。

3．系统功能设计

本程序除了完成二叉排序树的创建功能外还设置了5个子功能菜单。由于这5个子功能都是建立在二叉排序树的构造上，所以二叉排序树的创建由主函数main（）实现。5个子功能的设计描述如下：

(1)建立二叉排序树。根据系统提示，输入节点的关键词，并以-1作为结束的标识符。该功能由Bstree Create()函数实现。

(2) 树状输出二叉排序树。树状输出二叉排序树有函数TranslevelPrint（）实现。当用户选择该功能时，系统即以树状的形式输出用户所创建的二叉排序树。

(3) 在二叉排序树中插入新结点。由函数Bstree Insert（）实现。当用户选择该功能时，系统即在二叉排序树中自动插入添加的新结点，构建新的二叉排序树。

(4)在二叉排序树中查找结点。由函数Bstree Search（）实现。二叉排序树该功能按照二叉排序树数组元素的顺利对比找出关键词key，查找成功就给出查找长度，否则输出无此结点。

(5)遍历二叉排序树。由函数void Traverse（）实现。该功能是将输入的数组元素按顺序依次输出。

三、模块设计

1．模块设计

本程序包含两个模块：主程序模块和二叉排序树操作模块。其调用关系如图2

图2 二叉排序树模块调用关系

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

本系统共设计了5个子程序，个程序的的函数名及其功能说明如下：

Bstree Create();//创建二叉排序树

Bstree Insert(Bstree tree,int key);//插入

Bstree Search(Bstree tree,int key);//查找

void Traverse(Bstree tree);//遍历

void TranslevelPrint(Bstree bt);//树状打印

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-23873-1.html