排序二叉树二叉排序树实现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)
速云怎么样?速云,国人商家,提供广州移动、深圳移动、广州茂名联通、香港hkt等VDS和独立服务器。现在暑期限时特惠,力度大。广州移动/深圳移动/广东联通/香港HKT等9折优惠,最低月付9元;暑期特惠,带宽、流量翻倍,深港mplc免费试用!点击进入:速云官方网站地址速云优惠码:全场9折优惠码:summer速云优惠活动:活动期间,所有地区所有配置可享受9折优惠,深圳/广州地区流量计费VDS可选择流量翻...
快云科技怎么样?快云科技是一家成立于2020年的新起国内主机商,资质齐全 持有IDC ICP ISP等正规商家。我们秉承着服务于客户服务于大众的理念运营,机器线路优价格低。目前已注册用户达到5000+!主营产品有:香港弹性云服务器,美国vps和日本vps,香港物理机,国内高防物理机以及美国日本高防物理机!产品特色:全配置均20M带宽,架构采用KVM虚拟化技术,全盘SSD硬盘,RAID10阵列, 国...
青云互联怎么样?青云互联是一家成立于2020年6月的主机服务商,致力于为用户提供高性价比稳定快速的主机托管服务,目前提供有美国免费主机、香港主机、香港服务器、美国云服务器,让您的网站高速、稳定运行。美国cn2弹性云主机限时8折起,可选1-20个IP,仅15元/月起,附8折优惠码使用!点击进入:青云互联官方网站地址青云互联优惠码:八折优惠码:ltY8sHMh (续费同价)青云互联活动方案:美国洛杉矶...
排序二叉树为你推荐
庞大"机构庞大指挥不灵"是什么成语支付宝账单查询支付宝账单怎么查小项目现在有什么好的小项目可以做啊光纤是什么光纤是什么图片修改工具要修改图片有什么软件可用招行信用卡还款招行信用卡还款顺序是怎样的摇一摇周边微信摇一摇周边怎么申请开通黑屏操作电脑一操作就黑屏 不操作就没有事。该怎么恢复购物网站设计购物网站如何设计漂亮且实用的购物车官方网店官方网店和官方旗舰店有什么区别?
政务和公益机构域名注册管理中心 vps代购 windows主机 站群服务器 themeforest 国外私服 谷歌香港 ev证书 网站被封 52测评网 炎黄盛世 七夕促销 免费全能主机 网络空间租赁 最好的qq空间 cxz 国内域名 wordpress中文主题 广东服务器托管 789电视剧网 更多