基于C语言二叉排序树的创建

这篇具有很好参考价值的文章主要介绍了基于C语言二叉排序树的创建。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一.什么是二叉排序树

二叉排序树是一种特殊的二叉树,它满足一定的规律。其具体规律如下:

简单来说,就是任何一个二叉树的节点的左孩子比它的值小,右孩子的值比它大。

基于C语言二叉排序树的创建

 如图,这就是一颗二叉排序树。对任意一个节点,都满足左孩子的值比根节点的值小,右孩子的值比根节点大。满足这个排序的二叉树就是一颗二叉排序树。如果想要了解更多的信息,大家可以去自行搜索,在这里我只简单介绍。

二.二叉排序树的创建

如果大家看到这篇文章,相信大家应该已经学习过了二叉树的知识,应该有所了解。

关于二叉树相关的结构体都是大同小异的,我采用如下的结构体,代码如下:

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

到了这里,关于基于C语言二叉排序树的创建的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构(C语言实现)——二叉树的概念及二叉树顺序结构和链式结构的实现(堆排序+TOP-K问题+链式二叉树相关操作)

    前面学习了数据结构中线性结构的几种结构,顺序表,链表,栈和队列等,今天我们来学习一种非线性的数据结构——树。由于二叉树是数据结构中的一个重点和难点,所以本文着重介绍二叉树的相关概念和性质,以及二叉树的应用。 树是一种非线性的数据结构,它是由n(

    2023年04月21日
    浏览(43)
  • 二叉排序树(BST)创建详解之C语言版

    二叉排序树(Binary Sort Tree或 Binary Search Tree)又称二叉查找树,可以用来实现数据的快速查找,也方便数据的插入、删除等工作,因此适用于数据的动态查找。 二叉排序树是一棵二叉树,其左子树上的元素都小于树根,右子树上的元素都大于树根,所有的子树也满足这个性质

    2024年02月07日
    浏览(32)
  • 14-数据结构-二叉树的创建以及前中后遍历,以及结点和叶子节点的计算(C语言)

    概述:         二叉树,这里采用孩子链表存储法,即一个数据域和两个左右孩子指针域。随后递归进行遍历即可。在创建二叉树的时候,先创建各个二叉树结点(这里的结点采用动态分配,因此结点为指针变量),随后,再根据逻辑结构图,手动通过左右指针域,链接到对

    2024年02月11日
    浏览(42)
  • 考研算法第十三天:二叉排序树 【二叉排序树的插入和遍历】

    这道题很妙。题目给的二叉排序树好像没学过其实就是二叉查找树。然后这道题主要的就是思路     1.先找到那个要删除节点所在处     2.找到之后处理分三种情况     删除的节点是叶节点,直接删除即可     删除的节点只有右节点或者左节点 将左节点或者右节点删除即可

    2024年02月05日
    浏览(46)
  • 二叉排序树的查找、插入、删除

    目录 二叉排序树的定义 二叉排序树的查找 二叉排序树的插入 二叉排序树的定义 二叉排序树(Binary Sort Tree, BST),也称二叉查找树。 二叉排序树或者是一棵空树,或者是一棵具有下列特性的非空二叉树: 1) 若左子树非空,则左子树上所有结点均小于根结点的关键

    2024年02月07日
    浏览(36)
  • 【数据结构】【算法】二叉树、二叉排序树、树的相关操作

    树结构是以分支关系定义的一种层次结构,应用树结构组织起来的数据,逻辑上都具有明显的层次关系。 操作系统中的文件管理系统、网络系统中的域名管理、数据库系统中的索引管理等都使用了树结构来组织和管理数据。 树 Tree 是由n个节点组成的有限集合。在任意一颗非

    2024年02月04日
    浏览(50)
  • 【数据结构】二叉排序树——平衡二叉树的调整

    参考视频: 懒猫老师-数据结构-(59)平衡二叉树【互动视频】 (1)什么是平衡二叉树 平衡二叉树(Balanced Binary Tree)是一种特殊的二叉查找树,它的目的是保持树的高度尽量平衡,以保证查找、插入、删除等操作的时间复杂度为 O(log n)。 常见的平衡二叉树算法包括 AVL 树、红

    2024年02月04日
    浏览(38)
  • 二叉树的创建与遍历

    {用先序讲解举例,请自己联系中序和后序(在最后):} (在自己作为儿子的同时自己也是根) 注意:递归的形参不是你看到的形参,而是逻辑上的形参! 首先是创建的函数,如果我们要先序输入这样一个二叉树:那么我们在计算机内部其实是要先序输入:ab##c##的,【这里

    2023年04月24日
    浏览(36)
  • 二叉树的创建和遍历

    目录 一.二叉树的创建 1.顺序存储二叉树的创建 2.链式存储二叉树的创建 2.1先序和中序创建二叉树 2.2中序和后序创建二叉树 二.二叉树的递归遍历 1.二叉树的遍历原理 2.中序遍历 3.先序遍历 4.后序遍历 三.二叉树的非递归遍历 1.中序遍历 2.先序遍历 3.后序遍历 方法2:用出栈的

    2024年02月06日
    浏览(46)
  • 二叉树的创建及遍历方法

    目录 1、二叉树的定义及特点 2、满二叉树和完全二叉树的概念 3、二叉树的存储结构 4、创建二叉树 5、树的四种遍历方法 6、结果及其分析         二叉树是指树中节点的度不大于2的有序树,它是一种最简单且最重要的树。二叉树的递归定义为:二叉树是一棵空树,或者

    2024年02月02日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包