数据结构二叉排序树课程设计报告

东华理工大学理学院

课 程 设 计 报 告

——数据结构

题目：二叉排序树

姓 名： 学 号： 专 业： 班 级： 指导老师：

年数据结构课程设计

月 日

1

东华理工大学理学院

目 录

一、课程设计简介 ............................................................................ 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

数据结构课程设计

2

东华理工大学理学院

一、课程设计简介

1.1、题目：二叉排序树相关操作

1、创建二叉排序树；2、插入给定值； 3、查找给定值； 4、删除给定值的结点。

1.2、报告要求：

1、封面; 2、题目与流程图或模块图; 3、程序清单和运行结果; 4、小结(收获和体会); 5、装订成册。

1.3、目的：

课程设计为学生提供了一个既动手又动脑，独立实践的机会，将课本上的理论知识和实际有机的结合起来，锻炼学生的分析解决实际问题的能力。提高学生适应实际，实践编程的能力。

二、原理分析及流程 2.1、原理分析：

根据题目要求，要实现这些功能，就必须创建一个菜单。这个菜单设置在main（）函数里面，然后使用while()...switch()语句进行循环调用相关函数，以达到实现

数据结构课程设计

3

东华理工大学理学院

相关功能的目的。

2.2、流程图：

1、main（）函数：

main()开始 选择操作 选择 1 选择2 选择3 选择4 选择5 创建 插入 查找 删除 退出 2、创建：

Create(&t)

输入结点值，以 -1结束

调用插入函数 数据结构课程设计 4

东华理工大学理学院

3、插入： Insert(&t,x) 输入给定的结点值 N *t==null Y *t=s x<(*t)->key N Y 结束 insert(&((*insert(&((*t)->lchild)t)->rchild)

数据结构课程设计

5

东华理工大学理学院

4、查找： search(t,x) 输入给定的结点值x,p=t Y P!=null N 返回null x=p->key xkey 返回 p->key Y N 返回返回search(p->search(p->lchild,x) rchild,x) 数据结构课程设计

6

东华理工大学理学院

5、中序遍历输出：

display(t) t!=null display(t->lchild) 访问并输出根节点 display(t->rchild) 数据结构课程设计

7

东华理工大学理学院

三、算法描述

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插入右子树。在左右两个子树的插入方法与

数据结构课程设计

8

东华理工大学理学院

整个二叉排序树相同。 算法如下：

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) {

数据结构课程设计

9

东华理工大学理学院

if (x==p->key) return p->key;

else if(xkey) return search(p->lchild,x); else return search(p->rchild,x); } else

{ printf(\ } }

3.4、删除算法

在二叉排序树中删除节点，首先要确定被删除的节点是否在二叉排序树中。

若不在，则不做任何操作；否则，假设要删除的节点为p，节点p的父节点为r，并假设p是r的左孩子。根据被删除节点p有无孩子，删除部分可做以下3中情况讨论：

（1）若p为叶子节点，则可令其父节点r的左孩子指针域为空，直接将其删除。

（2）若p节点只有右子树或左子树，则可以将p的左子树或右子树直接改为其双亲节点r的左子树。

（3）若p既有左子树又有右子树；将节点s为p的中序前驱。首先找到p的中序前驱节点s，然后用节点s的值代替节点p的值，再将节点s删除，节点s的原左子树改为s的双亲节点q的右子树。 算法如下：

bstree delete(bstree t,keytype x) {

bstree p,q,r,s; p=t;

数据结构课程设计

10

东华理工大学理学院

r=null; while(p) {

if(x==p->key) break; r=p;

if(xkey) p=p->lchild; else p=p->rchild; }

if(p==null) {printf(\ if((p->lchild==null)||(p->rchild==null)) {

if(r==null)

if(p->lchild==null) t=p->rchild; else t=p->lchild;

else if(p->lchild==null) if(r->lchild==p) r->lchild=p->rchild; else r->rchild=p->rchild; else if(r->lchild==p) r->lchild=p->lchild; else r->lchild=p->lchild; free(p); } else { q=p;

s->lchild;

while(s->rchild)

{q=s;s->rchild;}

if(q==p) q->lchild=s->lchild; else p->key=s->key; free(s); } return t; }

四、小结与体会

数据结构课程设计

11

东华理工大学理学院

经过一个多星期来夜以继日的努力，终于把课程设计——二叉排序树的相关算法全部完成！在编写程序过程中，让我对二叉排序树的创建、插入、查找、删除算法有了较系统的认识，也发现了一些以前纸上谈兵时的思想误区。比如实现插入功能时，从根节点开始比较；当实现删除功能时，如果待删除结点p左、右子树齐全，首先找到p的中序前驱节点s（p的中序前驱），然后用节点s的值代替节点p的值，再将节点s删除，节点s的原左子树改为s的双亲节点q的右子树。实现中序遍历功能时，采用递归思想......

这是第一次关于编写程序的课程设计。虽然上机安排只有两天时间，可却并不像平时上机实验一样，离开了机房就不用再对着电脑屏幕编写代码，更多的工作实在离开机房后完成的。一遍一遍地按F9调试程序，error从几十个减少到几个，再到只剩几个warring，当按下Ctrl+F9，那精心设计的“菜单”出现在屏幕上时，那一刻的心情无以言表！涌上心头的除了自豪感、成就感之外，还有对编程工作之辛苦的慨叹！因为自己专业将来的方向与这有关，不免让我考虑起毕业后的发展方向。如果朝这方面发展的话，我是否可以胜任这样的工作？如果不是，又该选择什么？

五、程序执行过程

5.1、创建二叉排序树并中序输出

数据结构课程设计

12

东华理工大学理学院

5.2插入并中序输出

5.3、查找

数据结构课程设计

13

东华理工大学理学院

5.4、删除并中序输出

六、程序清单

#include #define null 0

typedef int keytype; typedef struct node {

keytype key;

struct node *lchild,*rchild; }bstnode,*bstree;

void insert(bstree *t,keytype x); bstree search(bstree t,keytype x);

数据结构课程设计

14

东华理工大学理学院

void display(bstree t); void create(bstree *t) {

keytype x; *t=null;

scanf(\ while(x!=-1) {

insert(t,x);

scanf(\ } }

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); }

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(\ return null; } }

bstree delete(bstree t,keytype x)

数据结构课程设计

15

东华理工大学理学院

{

bstree p,q,r,s; p=t; r=null; while(p) {

if(x==p->key) break; r=p;

if(xkey) p=p->lchild; else p=p->rchild; }

if(p==null) {printf(\ if((p->lchild==null)||(p->rchild==null)) {

if(r==null)

if(p->lchild==null) t=p->rchild; else

t=p->lchild;

else if(p->lchild==null) if(r->lchild==p) r->lchild=p->rchild; else r->rchild=p->rchild; else if(r->lchild==p) r->lchild=p->lchild; else r->lchild=p->lchild; free(p); } else { q=p;

s->lchild;

while(s->rchild)

{q=s;s->rchild;} if(q==p)

q->lchild=s->lchild; else

p->key=s->key; free(s); } return t; }

数据结构课程设计

16

东华理工大学理学院

void display(bstree t) {

if(t!=null) {

display(t->lchild); printf(\ display(t->rchild); } }

void main(void) {

bstree t,b; int i=1,j; keytype x; while(i) {

printf(\

printf(\ MENU OF BSTREE *\\n\ printf(\ 1.create 2.insert *\\n\ printf(\ 3.search 4.delete *\\n\ printf(\ 5.exit *\\n\ printf(\

printf(\ switch(j) {

case 1: printf(\ printf(\

case 2: printf(\ insert(&t,x);display(t);break;

case 3: printf(\ printf(\

case 4: printf(\ delete(t,x);display(t);break;

case 5: i=0;break; } }

clrscr(); }

数据结构课程设计

17

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