排序二叉树二叉排序树实现1) 编程实现二叉排序树,包括生成、插入,删除
排序二叉树 时间:2021-09-12 阅读:(
)
二叉排序树(急啊)
当用线性表作为表的组织形式时,可以有三种查找法。
其中以二分查找效率最高。
但由于二分查找要求表中结点按关键字有序,且不能用链表作存储结构,因此,当表的插入或删除操作频繁时,为维护表的有序性,势必要移动表中很多结点。
这种由移动结点引起的额外时间开销,就会抵消二分查找的优点。
也就是说,二分查找只适用于静态查找表。
若要对动态查找表进行高效率的查找,可采用下面介绍的几种特殊的二叉树或树作为表的组织形式。
不妨将它们统称为树表。
下面将分别讨论在这些树表上进行查找和修改操作的方法。
二叉排序树
1、二叉排序树的定义
二叉排序树(Binary Sort Tree)又称二叉查找(搜索)树(Binary Search Tree)。
其定义为:二叉排序树或者是空树,或者是满足如下性质的二叉树:
①若它的左子树非空,则左子树上所有结点的值均小于根结点的值;
②若它的右子树非空,则右子树上所有结点的值均大于根结点的值;
③左、右子树本身又各是一棵二叉排序树。
上述性质简称二叉排序树性质(BST性质),故二叉排序树实际上是满足BST性质的二叉树。
2、二叉排序树的特点
由BST性质可得:
(1) 二叉排序树中任一结点x,其左(右)子树中任一结点y(若存在)的关键字必小(大)于x的关键字。
(2) 二叉排序树中,各结点关键字是惟一的。
注意:
实际应用中,不能保证被查找的数据集中各元素的关键字互不相同,所以可将二叉排序树定义中BST性质(1)里的"小于"改为"大于等于",或将BST性质(2)里的"大于"改为"小于等于",甚至可同时修改这两个性质。
(3) 按中序遍历该树所得到的中序序列是一个递增有序序列。
【例】下图所示的两棵树均是二叉排序树,它们的中序序列均为有序序列:2,3,4,5,7,8。
3、二叉排序树的存储结构
typedef int KeyType; //假定关键字类型为整数
typedef struct node { //结点类型
KeyType key; //关键字项
InfoType otherinfo; //其它数据域,InfoType视应用情况而定,下面不处理它
struct node *lchild,*rchild; //左右孩子指针
} BSTNode;
typedef BSTNode *BSTree; //BSTree是二叉排序树的类型C语言 排序二叉树
#include?<stdio.h>
#include?<stdlib.h>
struct?node{
int?data;
struct?node?*lc,*rc;
}*head,*s;
//-----必须传递二维指针才能改变实参指针变量的值!!
void?find(struct?node?**p,struct?node?*x){
if((*p)==NULL)?
*p=x;
else?if(x->data<=?(*p)->data)
find(?&((*p)->lc),x);
else?
find(?&((*p)->rc),x);
}
void?print(struct?node?*p){
if(p!=NULL){
print(p->lc);
printf("%d?",p->data);
print(p->rc);
}
}
int?main?(){
FILE?*fin=fopen("排序二叉树.txt","r");
int?a;
while(!feof(fin)){
fscanf(fin,"%d",&a);
s=(struct?node?*)malloc(sizeof(struct?node));//--
s->data=a;
s->lc=s->rc=NULL?;//--
find(?&head,s);//--
}
print(head);
fclose(fin);
system("pause");
return?0;
}二叉排序树实现1) 编程实现二叉排序树,包括生成、插入,删除
#include <stdio.h>
struct node { int data;
struct node *lchild;
struct node *rchild;
};
typedef struct node NODE;
(1)递归函数
NODE *search(t, x)
NODE *t;
char x;
{ if (t==NULL)
return(NULL);
else
{ if (t->data==x)
return(t);
if (x<t->data)
return(search(t->lchild));
else
return(search(t->rchild));
}
}
(2)非递归函数 用非递归实现查找,程序同样很简单,但效率比递归程序高的多。
NODE *search(NODE *t, char x)
{ NODE *p;
p=t;
while (p!=NULL)
{ if (p->data==x) return(p); /* 查找成功 */
if (x<p->data)
p=p->lchild;
else
p=p->rchlid;
}
printf(“找不到值为%x的结点!”,x);
return (NULL); /* 查找失败 */
void insert(t, s)
NODE **t, *s
{ if (*t==NULL)
*t=s;
else
{ if (s->data<(*t)->data)
insert(&((*t)->lchild),s);
else if (s->data>(*t)->data)
insert(&((*t)->rchild),s);
else
printf("
数据%d已在二叉排序树中!", s->data);
}
}
void creat(t)
NODE **t
{ int x;
NODE *s;
printf("
输入待排序的数据序列(以-1结束):");
scanf("%d",&x);
while (x!=-1) /* 以-1结束输入 */
{ s=(NODE *)malloc(sizeof(NODE));
s->data=x;
s->lchild=NULL;
s->rchild=NULL;
insert(t,s); /* 插入到二叉排序树中 */
scanf("%d",&x);
}
}
main( )
{ NODE *root=NULL;
printf("
创建一棵二叉排序树!");
creat(&root);
printf("二叉排序树中序序列为:");
midorder(root);
} }
void delete(NODE **t,int x)
{ NODE *f,*p,*r;
p=(*t); /* p指向数据域值为x的结点 */
f=NULL; /* f指向p所指的结点的父结点 */
while (p!=NULL&&p->data!=x) /* 查找数据域值为x的结点 */
if (x<p->data)
{ f=p;
p=p->lchild;
}
else
{ f=p;
p=p->rchild;
}
if (p==NULL)
printf("找不到键值为 %d的结点
",x);
else if (p->lchild==NULL) /* 被删除结点无左子树 */
{ if (f==NULL)
(*t)=p->rchild; /* 被删除结点为根结点 */
else if (f->lchild==p)
f->lchild=p->rchild; /* 被删除结点为其父结点的左子树*/
else
f->rchild=p->rchild; /* 被删除结点为其父结点的右子树*/
}
else /* 被删除结点有左子树 */
{ r=p->lchild;
while (r->rchild!=NULL) /* 找到最右e68a84e8a2ad62616964757a686964616f31333337623535边的结点 */
r=r->rchild;
r->rchild=p->rchild; /* 把被删除结点的右子树作为r的右子树 */
if (f==NULL)
(*t)=p->lchild; /* 被删除结点为根结点 */
else if (f->lchild==p)
f->lchild=p->lchild; /* 被删除结点为其父结点的左子树*/
else
f->rchild=p->lchild; /* 被删除结点为其父结点的右子树*/
}
free(p)
搬瓦工vps(bandwagonhost)现在面向中国大陆有3条顶级线路:美国 cn2 gia,香港 cn2 gia,日本软银(softbank)。详细带宽是:美国cn2 gia、日本软银,都是2.5Gbps~10Gbps带宽,香港 cn2 gia为1Gbps带宽,搬瓦工是目前为止,全球所有提供这三种带宽的VPS(云服务器)商家里面带宽最大的,成本最高的,没有第二家了! 官方网站:https...
搬瓦工今天正式对外开卖荷兰阿姆斯特丹机房走联通AS9929高端线路的VPS,官方标注为“NL - China Unicom Amsterdam(ENUL_9)”,三网都走联通高端网络,即使是在欧洲,国内访问也就是飞快。搬瓦工的依旧是10Gbps带宽,可以在美国cn2 gia、日本软银与荷兰AS9929之间免费切换。官方网站:https://bwh81.net优惠码:BWH3HYATVBJW,节约6...
BGP.TO目前针对日本和新加坡服务器进行促销,其中日本东京服务器6.5折,而新加坡服务器7.5折起。这是一家专门的独立服务器租售网站,提供包括中国香港、日本、新加坡和洛杉矶的服务器租用业务,基本上都是自有硬件、IP资源等,国内优化直连线路,机器自动化部署上架,并提供产品的基本管理功能(自助开关机重启重装等)。新加坡服务器 $93.75/月CPU:E3-1230v3内存:16GB硬盘:480GB ...
排序二叉树为你推荐
按键精灵教程按键精灵教程anychartjfreechar制作柱状图的时候。由于柱子之间的差距太大。有些柱子才个位有上千导致了Y轴数据太密集。求教育城域网怎样进入寿光教育城域网网站资源优化配置社会资源优化配置的标志是什么?怎样实现?小项目如何搞小工程网络限速软件有什么比较好的网络限速的软件硬盘分区格式化怎样给硬盘分区并格式化黑屏操作麻烦问一下 黑屏的各个指令主板说明书主板各个接口,插口的详细说明淘宝推广网站有没有淘宝第三方推广平台好用的?
北京主机租用 cn域名价格 备案域名出售 香港bgp机房 樊云 账号泄露 促正网秒杀 admit的用法 北京双线 免费高速空间 域名dns 百度云空间 服务器防火墙 买空间网 阿里云邮箱个人版 webmin 防盗链 卡巴斯基免费版下载 挂马检测工具 香港云主机 更多