数据结构二叉排序树课程设计报告
- 格式：doc
- 大小：137.00 KB
- 文档页数：17
课 程 设 计 报 告
——数据结构
题目：二叉排序树
姓 名：
学 号：
专 业：
班 级：
指导老师：
年 月 日 目 录
一、课程设计简介 ............................................................................ 3
二、原理分析及流程 ........................................................................ 3
2.1、原理分析............................................................................3
2.2、流程图................................................................................4
1、main()函数....................................................................4
2、创建...............................................................................4
3、插入...............................................................................5
4、查找...............................................................................6
5、中序遍历输出 .............................................................. 7
三、算法描述 .................................................................................... 8
3.1、存储结构 ........................................................................... 8
3.2、插入算法 ........................................................................... 8
3.3、查找算法 ........................................................................... 9
3.4、删除算法 ......................................................................... 10
四、小结与体会 .............................................................................. 12
五、程序执行过程 .......................................................................... 13
5.1、创建二叉排序树并中序输出.........................................13 5.2、插入并中序输出..............................................................13
5.3、查找..................................................................................14
六、程序清单 .................................................................................. 14
一、课程设计简介
1.1、题目：二叉排序树相关操作
1、创建二叉排序树；2、插入给定值；
3、查找给定值； 4、删除给定值的结点。
1.2、报告要求：
1、封面; 2、题目与流程图或模块图;
3、程序清单和运行结果; 4、小结(收获和体会);
5、装订成册。
1.3、目的：
课程设计为学生提供了一个既动手又动脑，独立实践的机会，将课本上的理论知识和实际有机的结合起来，锻炼学生的分析解决实际问题的能力。提高学生适应实际，实践编程的能力。
二、原理分析及流程
2.1、原理分析：
根据题目要求，要实现这些功能，就必须创建一个菜单。这个菜单设置在main（）函数里面，然后使用while()...switch()语句进行循环调用相关函数，以达到实现相关功能的目的。
2.2、流程图：
1、main（）函数：
2、创建：
3、插入： 选择操作 main()开始
选择1
创建 选择2
插入 选择3
查找 选择4
删除 选择5
退出
Create(&t)
输入结点值，以-1结束
调用插入函数
N
Y
N
Y
4、查找： Insert(&t,x)
输入给定的结点值
*t==null
x<(*t)->key
insert(&((*t)->lchild)insert(&((*t)->rchild)*t=s
结束
Y
N
Y N
5、中序遍历输出：
返回search(p->rchild,x) 输入给定的结点值x,p=t
P!=null
xkey
返回search(p->lchild,x) 返回null search(t,x)
返回p->key x=p->key
display(t)
三、算法描述
3.1、存储结构
定义一个链表式的二叉排序树，用链表的方式构造结点，存储二叉排序树中的结点、结点类型和指针类型如下：
#include #define null 0
typedef int keytype;
typedef struct node
{
keytype key;
struct node *lchild,*rchild;
}bstnode,*bstree;
3.2、插入算法
在二叉排序树中插入一个新节点，首先要查找该节点在二叉排序树中是否已经存在。若二叉排序树中不存在关键字等于x的节点，则插入。
将一个关键字值为x的节点s插入到二叉排序树中，可以用下面的方法：
（1）若二叉排序树为空，则关键字为x的节点s成为二叉排序树的根
（2）若二叉排序树非空，则将x与二叉排序树根进行比较，如果x的值等于根节点关键值，则停止插入；如果x的根节点值小于根节点关键值，则将x插入左子树；如果x的值大于根节点关键字的值，则将x插入右子树。在左右两个子树的插入方法与整个二叉排序树相同。
算法如下：
void insert(bstree *t,keytype x)
{
bstree s;
if(*t==null)
{
s=(bstree)malloc(sizeof(bstnode));
s->key=x;
s->lchild=null; s->rchild=null;
*t=s;
}
else if(x<(*t)->key)
insert(&((*t)->lchild),x);
else if(x>(*t)->key)
insert(&((*t)->rchild),x);
}
3.3、查找算法
（1）若二叉排序树不为空，将根结点的关键字与待查关键字进行比较，若相等，则查找成功；若根节点关键字大于待查值，则进入左子树重复次步骤，否则，进入右子树进行此步骤；若在查找过程中遇到二叉排序树的叶子节点时，还没有找到待查节点，则查找不成功。
（2）否则，查找失败，返回null。
算法如下：
bstree search(bstree t,keytype x)
{
bstree p;
p=t;
if(p!=null)
{
if (x==p->key) return p->key;
else if(xkey) return search(p->lchild,x);
else return search(p->rchild,x);
}
else
{ printf("%d can not be found\n",x);return null;
}
}
