一.什么是二叉排序树
二叉排序树是一种特殊的二叉树,它满足一定的规律。其具体规律如下:
简单来说,就是任何一个二叉树的节点的左孩子比它的值小,右孩子的值比它大。
如图,这就是一颗二叉排序树。对任意一个节点,都满足左孩子的值比根节点的值小,右孩子的值比根节点大。满足这个排序的二叉树就是一颗二叉排序树。如果想要了解更多的信息,大家可以去自行搜索,在这里我只简单介绍。
二.二叉排序树的创建
如果大家看到这篇文章,相信大家应该已经学习过了二叉树的知识,应该有所了解。
关于二叉树相关的结构体都是大同小异的,我采用如下的结构体,代码如下:
typedef int ElemType;
typedef struct BSTNode{
ElemType data;
struct BSTNode *rchild,*lchild;
}BSTNode,*BSTree;
这个大家应该很熟悉,我就不废话了。
再添加元素之前,我们需要对建立的二叉树进行初始化。
void Init_BSTree(BSTree *t){
(*t)=NULL;
}
不写函数也可以,可以直接赋值:
BSTree t;
t=NULL;
其效果都是一样的。
接下来我们对二叉树插入元素,采用递归的方法。其算法就是,如果传递的值比当前节点的值小,就递归传递给当前节点的左孩子,如果传递的值比当前节点的值大,就递归传递给当前节点的右孩子,结束条件就是节点的左孩子或右孩子为空。
代码如下:
Status CreatBSTree(BSTree *t,ElemType data){
if(!(*t)){
(*t)=(BSTree)malloc(sizeof(BSTNode));
(*t)->data=data;
(*t)->rchild=NULL;
(*t)->lchild=NULL;
}
else if(data>(*t)->data){
CreatBSTree(&((*t)->rchild),data);
}
else{
CreatBSTree(&((*t)->lchild),data);
}
return ok;
}
最后,需要简单说一下排序二叉树的中序遍历。因为二叉排序树的特性,其中序遍历的结果就是递增序列,二叉排序树中不存在值相同的节点,所以输出的结果是递增的(递减也可以)。因为中序遍历是先左孩子再根节点最后才是右孩子,这个访问顺序正好决定了输出是严格递增的。
中序遍历代码:
void InOrderTraverse(BSTree t){
if(t==NULL){
return;
}
InOrderTraverse(t->lchild);
printf("%d ",t->data);
InOrderTraverse(t->rchild);
}
三.完整代码如下
#include<stdio.h>
#include<stdlib.h>
#define ok 1
#define error -1
typedef int Status;
typedef int ElemType;
typedef struct BSTNode{
ElemType data;
struct BSTNode *rchild,*lchild;
}BSTNode,*BSTree;
void Init_BSTree(BSTree *t){
(*t)=NULL;
}
Status CreatBSTree(BSTree *t,ElemType data){
if(!(*t)){
(*t)=(BSTree)malloc(sizeof(BSTNode));
(*t)->data=data;
(*t)->rchild=NULL;
(*t)->lchild=NULL;
}
else if(data>(*t)->data){
CreatBSTree(&((*t)->rchild),data);
}
else{
CreatBSTree(&((*t)->lchild),data);
}
return ok;
}
void InOrderTraverse(BSTree t){
if(t==NULL){
return;
}
InOrderTraverse(t->lchild);
printf("%d ",t->data);
InOrderTraverse(t->rchild);
}
int main()
{
BSTree t;
int i;
Init_BSTree(&t);
for(i=0;i<10;i++){
int a;
scanf("%d",&a);
CreatBSTree(&t,a);
}
InOrderTraverse(t);
return 0;
}
希望看到的朋友能点个赞,祝大家学业有成,天天开心!!!文章来源:https://www.toymoban.com/news/detail-477725.html
有问题可以评论哦文章来源地址https://www.toymoban.com/news/detail-477725.html
到了这里,关于基于C语言二叉排序树的创建的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!