数据结构二叉排序树Word文件下载.docx
《数据结构二叉排序树Word文件下载.docx》由会员分享，可在线阅读，更多相关《数据结构二叉排序树Word文件下载.docx（15页珍藏版）》请在冰点文库上搜索。
节点类型和指针类型如下：
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（x<
p->
key）
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;
while（p!
=NULL）{
f=p;
//查找过程中，f指向*p的父节点
if（x==p->
key）returnt;
//二叉排序树中已有关键字为x的元素，无序插入
if（x<
key）p=p->
elsep=p->
s=（Bstnode*）malloc（sizeof（Bstnode））;
s->
key=x;
lchild=NULL;
rchild=NULL;
if（t==NULL）returns;
//原树为空，新节点成为二叉排序树的根
f->
key）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;
f=NULL;
while（p）{//查找关键字为k的待删节点*p
if（p->
key==k）break;
//找到，则退出循环
f=p;
//节点*f为节点*p的父节点
key>
k）p=p->
elsep=p->
if（p==NULL）returnt;
//若找不到，则返回原二叉排序树的根指针
if（（p->
lchild==NULL）||（p->
rchild==NULL））{//若*p无左孩子或右孩子
if（f==NULL）//若*p是原二叉排序树的根
lchild==NULL）t=p->
elset=p->
elseif（p->
lchild==NULL）//若*p无左孩子
if（f->
lchild==p）f->
lchild=p->
//p是*f的左孩子
elsef->
rchild=p->
elseif（f->
lchild==p）//若*p无右孩子
f->
//p是*f的右孩子
free（p）;
else{
q=p;
s=p->
//若p有左右子树
while（s->
rchild）{
q=s;
s=s->
//在*p的左子树中查找最右下节点
}
if（q==p）q->
lchild=s->
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"
malloc.h"
#defineNULL0
已找到该成绩！
找不到值为%d的成绩！
Bstnode*s,*p,*f;
while（p!
//查找过程中，f指向*p的父成绩
if（x==p->
if（x<
//原树为空，新成绩成为二叉排序树的根
//新成绩作为*f的左孩子
//新成绩作为*f的右孩子
Bstnode*CreateBST（）//创建一个新的二叉树
Bstnode*t;
intkey;
t=NULL;
//设置二叉排序树的初态为空
scanf（"
%d"
&
key）;
//读入第一个成绩的关键字
while（key!
=0）{
t=InsertBST（t,key）;
scanf（"
voidInorder（Bstnode*T）//中序遍历
if（T）{//若二叉树不空
Inorder（T->
lchild）;
//中序遍历左子树
printf（"
%4d"
T->
//访问根成绩
rchild）;
//中序遍历右子树
while（p）{//查找关键字为k的待删成绩*p
//成绩*f为成绩*p的父成绩
//在*p的左子树中查找最右下成绩
voidmenu（）
┏━━━━━━━━━━━━━━━┓\n"
┃1----------插入成绩-----------┃\n"
┠───────────────┨\n"
┃2----------查找成绩-----------┃\n"
┃3----------删除成绩-----------┃\n"
┃4-----------退出--------------┃\n"
┗━━━━━━━━━━━━━━━┛\n"
voidmain（）{
Bstnode*tree,*p;
intseai,deli,x;
intk,flag=1;
printf（"
请输入成绩信息，并以‘0’结束:
\n"
tree=CreateBST（）;
中序遍历所得序列为:
Inorder（tree）;
menu（）;
while（flag）
{
请选择操作:
scanf（"
k）;
switch（k）
{
case1:
{printf（"
插入一个新的成绩:
x）;
InsertBST（tree,x）;
插入后，中序遍历所得序列:
printf（"
break;
case2:
{
输入查找的数据:
seai）;
p=Bsearch（tree,seai）;
break;
case3:
输入删除的数据:
deli）;
tree=DeleteBST（tree,deli）;
删除后，中序遍历所得序列:
Inorder（tree）;
case4:
{flag=0;
升级会员 