数据结构二叉排序树.docx
《数据结构二叉排序树.docx》由会员分享，可在线阅读，更多相关《数据结构二叉排序树.docx（15页珍藏版）》请在冰点文库上搜索。
数据结构二叉排序树
数据结构课程设计
系别
电子信息系
专业
计算机科学与技术
班级学号
姓名
指导教师
成绩
年月日
一、需求分析
程序设计要求对一学生成绩管理程序构造二叉排序树，并在二叉排序树中实现多种方式的查找。
基本任务：
（1）以回车（'\n'）为输入结束标志,输入数列L，生成一棵二叉排序树T；
（2）对二叉排序树T作中序遍历，输出结果；（3）输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历（执行操作2）；否则输出信息“无x”；
若要完成题目的要求，需要解决以下几个问题：
1、选择一种数据结构存储二叉树的信息
2、建立一个新的二叉排序树
3、在二叉排序树中实现插入、删除、查找相关节点的操作
二、概要设计
1、数据结构的选择：
题目要求选择合适的存储结构构造二叉排序树，我选择链式结构存储。
用链表的方式构造节点，存储二叉排序树中的节点。
节点类型和指针类型如下：
typedefstructnode
{intkey;
intother;
structnode*lchild,*rchild;
}Bstnode;
2、概要设计：
为了完成所需的功能，需要的函数及其功能如下：
main（）：
主函数模块
Bsearch（）：
查找相应的节点
InsertBST（）：
插入一个新节点
CreateBST（）：
创建一棵二叉排序树
Inorder（）：
对二叉排序树进行中序遍历
menu（）：
主函数显示菜单模块
DeleteBST（）：
删除节点
主函数流程图：
图主函数流程图
子函数流程图：
A.插入子函数InsertBST（）的流程图：
图子函数InsertBST（）的流程图
B.子函数Bsearch（p）的流程图
图子函数Bsearch（p）的流程图
三、详细设计
二叉排序树的基本操作
1、二叉排序树的查找算法
（1）若二叉排序树为空，则查找失败。
（2）否则，将根结点的关键字与待查关键字进行比较，若相等，则查找成功；若根节点关键字大于待查值，则进入左子树重复次步骤，否则，进入右子树进行此步骤；若在查找过程中遇到二叉排序树的叶子节点时，还没有找到待查节点，则查找不成功。
算法如下：
Bstnode*Bsearch（Bstnode*t,intx）//查找
{Bstnode*p;
intflag=0;p=t;
while（p!
=NULL）
{if（p->key==x）
{printf（"已找到该节点！
"）;flag=1;return（p）;break;}
if（xkey）
p=p->lchild;
elsep=p->rchild;
}
if（flag==0）
{printf（"找不到值为%d的节点！
",x）;returnNULL;}
}
2、二叉排序树的节点插入算法
在二叉排序树中插入一个新节点，首先要查找该节点在二叉排序树中是否已经存在。
若二叉排序树中不存在关键字等于x的节点，则插入。
将一个关键字值为x的节点s插入到二叉排序树中，可以用下面的方法：
（1）若二叉排序树为空，则关键字为x的节点s成为二叉排序树的根‘
（2）若二叉排序树非空，则将x与二叉排序树根进行比较，如果x的值等于根节点关键值，则停止插入；如果x的根节点值小于根节点关键值，则将x插入左子树；如果x的值大于根节点关键字的值，则将x插入右子树。
在左右两个子树的插入方法与整个二叉排序树相同。
算法如下：
Bstnode*InsertBST（Bstnode*t,intx）//插入
{Bstnode*s,*p,*f;p=t;
while（p!
=NULL）{
f=p;//查找过程中，f指向*p的父节点
if（x==p->key）returnt;//二叉排序树中已有关键字为x的元素，无序插入
if（xkey）p=p->lchild;
elsep=p->rchild;
}
s=（Bstnode*）malloc（sizeof（Bstnode））;
s->key=x;s->lchild=NULL;s->rchild=NULL;
if（t==NULL）returns;//原树为空，新节点成为二叉排序树的根
if（xkey）f->lchild=s;//新节点作为*f的左孩子
elsef->rchild=s;//新节点作为*f的右孩子
returnt;
}
3、二叉排序树的节点删除算法
在二叉排序树中删除节点，首先要进行查找操作，以确定被删除的节点是否在二叉排序树中
若不在，则不做任何操作；否则，假设要删除的节点为*p，节点*p的父节点为*f，并假设*p是*f的左孩子。
根据被删除节点*p有无孩子，删除部分可做以下3中情况讨论：
（1）若*p为叶子节点，则可令其父节点*f的左孩子指针域为空，直接将其删除。
（2）若*p节点只有右子树或左子树，则可以将p的左子树或右子树直接改为其双亲节点f的左子树。
（3）若*p既有左子树又有右子树；将节点*s为*p的中序前驱。
首先找到*p的中序前驱节点*s，然后用节点*s的值代替节点*p的值，再将节点*s删除，节点*s的原左子树改为*s的双亲节点*q的右子树；
算法如下：
Bstnode*DeleteBST（Bstnode*t,intk）//删除
{
Bstnode*p,*f,*s,*q;p=t;f=NULL;
while（p）{//查找关键字为k的待删节点*p
if（p->key==k）break;//找到，则退出循环
f=p;//节点*f为节点*p的父节点
if（p->key>k）p=p->lchild;
elsep=p->rchild;
}
if（p==NULL）returnt;//若找不到，则返回原二叉排序树的根指针
if（（p->lchild==NULL）||（p->rchild==NULL））{//若*p无左孩子或右孩子
if（f==NULL）//若*p是原二叉排序树的根
if（p->lchild==NULL）t=p->rchild;
elset=p->lchild;
elseif（p->lchild==NULL）//若*p无左孩子
if（f->lchild==p）f->lchild=p->rchild;//p是*f的左孩子
elsef->rchild=p->rchild;
elseif（f->lchild==p）//若*p无右孩子
f->lchild=p->lchild;//p是*f的左孩子
elsef->lchild=p->lchild;//p是*f的右孩子
free（p）;
}
else{
q=p;s=p->lchild;//若p有左右子树
while（s->rchild）{
q=s;s=s->rchild;//在*p的左子树中查找最右下节点
}
if（q==p）q->lchild=s->lchild;
p->key=s->key;//将*s的值赋给*p
free（s）;
}
returnt;
}
四、调试分析
1、所写的程序和课本上二叉排序树程序基本相同。
但是在调试过程中遇到了一些问题。
由于采用的是非递归思想进行遍历，所以存在的基本的语法错误，问题主要在于函数和变量的定义，关键字和函数名的书写。
2、时间、空间性能分析：
二叉排序树的查找方法与二分查找类似，是一个逐一缩小查找范围的过程。
具有n个节点的排序二叉树是一棵深度为n的单枝树，平均查找长度与顺序查找相同，为（n+1）/2；即平均查找长度的数量级为O（n）。
五、用户手册
1、用户更具提示输入二叉排序树的节点信息并且以0结束输入
2、根据菜单提示选择相应的操作
3、输出的结果是中序遍历后的结果
六、测试结果
1、输入成绩信息：
2、显示菜单后，根据提示选择操作
选择插入一个新成绩
3、继续选择操作，查找一个已有的节点
5、删除一个成绩
七、附录
源程序文件名清单：
#include"stdio.h"
#include"malloc.h"
#defineNULL0
typedefstructnode
{intkey;
intother;
structnode*lchild,*rchild;
}Bstnode;
Bstnode*Bsearch（Bstnode*t,intx）//查找
{Bstnode*p;
intflag=0;p=t;
while（p!
=NULL）
{if（p->key==x）
{printf（"已找到该成绩！
"）;flag=1;return（p）;break;}
if（xkey）
p=p->lchild;
elsep=p->rchild;
}
if（flag==0）
{printf（"找不到值为%d的成绩！
",x）;returnNULL;}
}
Bstnode*InsertBST（Bstnode*t,intx）//插入
{
Bstnode*s,*p,*f;p=t;
while（p!
=NULL）{
f=p;//查找过程中，f指向*p的父成绩
if（x==p->key）returnt;//二叉排序树中已有关键字为x的元素，无序插入
if（xkey）p=p->lchild;
elsep=p->rchild;
}
s=（Bstnode*）malloc（sizeof（Bstnode））;
s->key=x;s->lchild=NULL;s->rchild=NULL;
if（t==NULL）returns;//原树为空，新成绩成为二叉排序树的根
if（xkey）f->lchild=s;//新成绩作为*f的左孩子
elsef->rchild=s;//新成绩作为*f的右孩子
returnt;
}
Bstnode*CreateBST（）//创建一个新的二叉树
{
Bstnode*t;intkey;t=NULL;//设置二叉排序树的初态为空
scanf（"%d",&key）;//读入第一个成绩的关键字
while（key!
=0）{
t=InsertBST（t,key）;scanf（"%d",&key）;
}
returnt;
}
voidInorder（Bstnode*T）//中序遍历
{
if（T）{//若二叉树不空
Inorder（T->lchild）;//中序遍历左子树
printf（"%4d",T->key）;//访问根成绩
Inorder（T->rchild）;//中序遍历右子树
}
}
Bstnode*DeleteBST（Bstnode*t,intk）//删除
{
Bstnode*p,*f,*s,*q;p=t;f=NULL;
while（p）{//查找关键字为k的待删成绩*p
if（p->key==k）break;//找到，则退出循环
f=p;//成绩*f为成绩*p的父成绩
if（p->key>k）p=p->lchild;
elsep=p->rchild;
}
if（p==NULL）returnt;//若找不到，则返回原二叉排序树的根指针
if（（p->lchild==NULL）||（p->rchild==NULL））{//若*p无左孩子或右孩子
if（f==NULL）//若*p是原二叉排序树的根
if（p->lchild==NULL）t=p->rchild;
elset=p->lchild;
elseif（p->lchild==NULL）//若*p无左孩子
if（f->lchild==p）f->lchild=p->rchild;//p是*f的左孩子
elsef->rchild=p->rchild;
elseif（f->lchild==p）//若*p无右孩子
f->lchild=p->lchild;//p是*f的左孩子
elsef->lchild=p->lchild;//p是*f的右孩子
free（p）;
}
else{
q=p;s=p->lchild;//若p有左右子树
while（s->rchild）{
q=s;s=s->rchild;//在*p的左子树中查找最右下成绩
}
if（q==p）q->lchild=s->lchild;
p->key=s->key;//将*s的值赋给*p
free（s）;
}
returnt;
}
voidmenu（）
{printf（"┏━━━━━━━━━━━━━━━┓\n"）;
printf（"┃1----------插入成绩-----------┃\n"）;
printf（"┠───────────────┨\n"）;
printf（"┃2----------查找成绩-----------┃\n"）;
printf（"┠───────────────┨\n"）;
printf（"┃3----------删除成绩-----------┃\n"）;
printf（"┠───────────────┨\n"）;
printf（"┃4-----------退出--------------┃\n"）;
printf（"┗━━━━━━━━━━━━━━━┛\n"）;
}
voidmain（）{
Bstnode*tree,*p;intseai,deli,x;
intk,flag=1;
printf（"请输入成绩信息，并以‘0’结束:
\n"）;tree=CreateBST（）;
printf（"中序遍历所得序列为:
\n"）;Inorder（tree）;
printf（"\n"）;
menu（）;
while（flag）
{
printf（"请选择操作:
"）;
scanf（"%d",&k）;
switch（k）
{
case1:
{printf（"插入一个新的成绩:
"）;scanf（"%d",&x）;InsertBST（tree,x）;
printf（"插入后，中序遍历所得序列:
\n"）;Inorder（tree）;printf（"\n"）;
break;}
case2:
{
printf（"输入查找的数据:
"）;scanf（"%d",&seai）;
p=Bsearch（tree,seai）;printf（"\n"）;
break;}
case3:
{
printf（"输入删除的数据:
"）;scanf（"%d",&deli）;
tree=DeleteBST（tree,deli）;
printf（"删除后，中序遍历所得序列:
\n"）;
Inorder（tree）;printf（"\n"）;
break;}
case4:
{flag=0;break;}
}
}
}
升级会员 