数据结构课程设计-二叉排序树的实现.doc

课程设计说明书
课程名称: 数据结构
设计题目: 二叉排序树的实现
院系:
学生姓名:
学号:
专业班级:
指导教师:
2010年5月29日
课程设计任务书
设计题目
二叉排序树的实现
姓名
罗浩
院系
计算机科学与信息工程系
专业、年级、班
08软件工程1班
设计要求:
以回车('\n')为输入结束标志,输入数列L,生成一棵二叉排序树T;
对二叉排序树T作中序遍历,输出结果;
输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2);否则输出信息“无x”;
学生应完成的工作:
1、按设计要求完成各项任务。
2、测试数据及测试结果在上交的资料中写明,必须上机调试通过。l
3、按《数据结构课程设计大纲》中的要求完成课程设计报告格式。
4、设计结束后,上交如下材料:
1)《课程设计报告》打印稿一份
2)课程设计的源代码电子文档一份
参考文献阅读:
[1] .
[2]
[3](C++版)

工作计划:
共计一周时间,进度安排如下:
选题,在上机实验之前看透设计要求,翻阅资料完成程序设计大致提纲。
选好题,上级编写程序(需求分析、概要设计) 。
填写算法,实现设计要求的各项功能(详细设计) 。
4. 调试和分析,最终完成较合理的程序设计。
5. 按《数据结构课程设计大纲》中的要求完成课程设计报告格式。
任务下达日期: 2010 年 5 月 27 日
任务完成日期: 2010 年 6 月 3 日
指导教师(签名): 学生(签名):罗浩
(设计题目)
摘要:
设计一个程序,根据任一数列生成一棵二叉排序树;实现基本的遍历方法;查询结点并删除结点且保证仍为二叉排序树。具体要求:用顺序和二叉链表作存储结构,输入数列L,以回车('\n')为输入结束标志生成一棵二叉排序树T;对二叉排序树T作中序遍历,输出结果;输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,否则输出信息“无x”。根据二叉排序树的概念,查找当前插入的元素的位置;删除结点如果不是叶子结点,要注意考虑如何使树仍为二叉排序树。
关键词:
二叉排序树,二叉链表,遍历,查询,删除
目录
1. 设计背景 4
问题的提出 4
任务与分析 4
4
4
3. 方案实施 5
5
5
1).实现二叉树的初始化 5
2). 创建一棵二叉树: 6
: 7
查找并删除元素模块设计方案 8
1) 查找元素x: 8
2) 删除元素x: 8
主函数设计方案 10
4. 结果与结论 11
11
12
5. 收获与致谢 12
: 12
: 13
6. 参考文献 13
7. 附件 13
: 13
1. 设计背景
问题的提出
根据自己的知识功底和能力水平,选择二叉排序树的实现问题。而随着计算机发展并逐渐成为各行业不可缺少的东西,数据结构与算法包含计算机科学与技术的许多重要方面,对训练学生编出质量高、风格好的程序,又语言的发展,C++已成为用处最为广泛的语言。该设计运用数据结构知识,利用C++编写,来锻炼和提高我自己的编程及独立解决问题的能力,故选较为基础,但知识点广泛的题目。
任务与分析
任务是一个二叉排序树的实现问题,根据任一数列生成一棵二叉排序树;实现基本的遍历方法;查询结点并删除结点且保证仍为二叉排序树。根据二叉排序树的概念,查找当前插入的元素的位置;删除结点如果不是叶子结点,要注意考虑如何使树仍为二叉排序树。


此课题研究二叉排序树的实现,建立二叉排序树;中序遍历并显示遍历结果;输入元素x,查找x;若存在删除之,否则输出“无x”;然后再进行中序遍历输出遍历结果。为方便起见,画出流程图如图1:
初始化模块
CreateBST()
中序遍历二叉排序树inorder()
中序遍历二叉排序树inorder()
查找元素x
BSTSearch()
主程序模块
图1
该程图描述了主要程序及函数。
3. 方案实施

#include <>
typedef int KeyType;
typedef char ElemType[10];
typedef struct tnod