二叉排序树(BST)创建详解之C语言版

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

一、算法原理

二叉排序树(Binary Sort Tree或 Binary Search Tree)又称二叉查找树,可以用来实现数据的快速查找,也方便数据的插入、删除等工作,因此适用于数据的动态查找。
二叉排序树是一棵二叉树,其左子树上的元素都小于树根,右子树上的元素都大于树根,所有的子树也满足这个性质。
要想实现二叉排序树的查找,需要事先已经建立了二叉排序树。其原理很简单,如果已知一个数组,则首先把数组的第一个元素存储到树根。读入第二个元素的时候需要和树根进行比较,比树根小则存到左子树,否则存到右子树。读入第三个元素时,依旧先和树根进行比较,如果大于树根元素,则存入右子树,否则就与当前左子树树根进行比较,小的话则存入左子树的左子树。以后读入其它元素也是如此操作,就可以创建一棵二叉排序树。
下面以具体案例给出二叉排序树创建的详细过程。
Demo:
假设一组散乱数据:{ 18, 3, 7, 20, 14, 19, 27, 2 }
Step 1:创建二叉树,将18存入树根,结果如下图所示。
二叉排序树(BST)创建详解之C语言版
Step 2:取元素3,与树根18进行比较,此时小于18,所以存入左子树树根,结果如下图所示。

二叉排序树(BST)创建详解之C语言版
Step 3:取元素7,与树根18进行比较,小于18,再与左子树树根3比较,此时大于3,所以存入3的右子树位置,结果如下图所示。
二叉排序树(BST)创建详解之C语言版
Step 4:取元素20,与树根18进行比较,大于18,所以存入右子树树根位置,结果如下图所示。
二叉排序树(BST)创建详解之C语言版
Step 5:取元素14,与树根18进行比较,小于18,再与左子树树根3比较,大于3,接着与3的右子树树根7进行比较,大于7,所以插入7的右子树树根位置,结果如下图所示。
二叉排序树(BST)创建详解之C语言版
Step 6:取元素19,与树根18进行比较,大于树根,再与右子树树根20比较,小于20,所以插入到20的左子树位置,结果如下图所示。
二叉排序树(BST)创建详解之C语言版
Step 7:取元素27,与树根18进行比较,大于树根,再与右子树树根20比较,大于20,所以插入到20的右子树位置,结果如下图所示。
二叉排序树(BST)创建详解之C语言版
Step 8:取元素2,与树根18进行比较,小于18,再与左子树树根3比较,小于3,所以插入到3的左子树位置,结果如下图所示。
二叉排序树(BST)创建详解之C语言版
至此,完成了把该数组存入到一棵二叉排序树。

二、创建二叉排序树算法的C程序

1. 创建二叉排序树函数

void CreateBST( BST *T, int arr[], int n ) 
{
	BST *s, *p, *q; 
	int i; 
	T->data = arr[0]; 
	T->LChild = NULL; 
	T->RChild = NULL; 
	for( i = 1; i < n; i++ ) 
	{
		s = (BST *)malloc( sizeof(BST) ); 
		s->data   = arr[i];
		s->LChild = NULL;
		s->RChild = NULL;
		p = T;
		while( p != NULL )
		{
			if( s->data == p->data )
			{
				printf( "%d existed.\n", s->data );
				q = NULL;
				break; 
			}
			q = p;
			if( s->data < p->data )
			{
				p = p->LChild;
			}
			else if( s->data > p->data )
			{
				p = p->RChild;			
			}
		} 
		if( q != NULL && s->data < q->data )
		{
			q->LChild = s;
		}
		else if( q != NULL && s->data > q->data )
		{
			q->RChild = s;
		}	
	}
}

2.测试代码(仅供参考)

#include"stdio.h" 
#include"malloc.h"

#define MAX_NODE 100

typedef struct node
{
	int data;
	struct node *LChild;
	struct node *RChild;
}BST;
void CreateBST( BST *T, int arr[], int n );
void  InorderSearch( BST *T );

int main()
{
	int arr[] = { 18, 3, 7, 20, 14, 19, 27, 2 };
	BST *T = ( BST * )malloc( sizeof( BST ) );
	CreateBST( T, arr, 8 );
	InorderSearch( T );
	return 0;
}
void CreateBST( BST *T, int arr[], int n ) 
{
	BST *s, *p, *q; 
	int i; 
	T->data = arr[0]; 
	T->LChild = NULL; 
	T->RChild = NULL; 
	for( i = 1; i < n; i++ ) 
	{
		s = (BST *)malloc( sizeof(BST) ); 
		s->data   = arr[i];
		s->LChild = NULL;
		s->RChild = NULL;
		p = T;
		while( p != NULL )
		{
			if( s->data == p->data )
			{
				printf( "%d existed.\n", s->data );
				q = NULL;
				break; 
			}
			q = p;
			if( s->data < p->data )
			{
				p = p->LChild;
			}
			else if( s->data > p->data )
			{
				p = p->RChild;			
			}
		} 
		if( q != NULL && s->data < q->data )
		{
			q->LChild = s;
		}
		else if( q != NULL && s->data > q->data )
		{
			q->RChild = s;
		}	
	}
}

void  InorderSearch( BST *T )
{
	if( T != NULL )
	{
		InorderSearch( T->LChild );
		printf( "%5d", T->data );
		InorderSearch( T->RChild );
	} 
}

3.运行结果
二叉排序树(BST)创建详解之C语言版文章来源地址https://www.toymoban.com/news/detail-470964.html

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

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

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

相关文章

  • C语言数据结构二叉排序树的建立、插入、删除、查找操作(原理+完整代码)

    1、若左子树不为空,左子树上所有节点值小于 它根节点的值 2、若右子树不为空,右子树上所有节点值大于 它根节点的值 3、每个节点的左右子树也是二叉排序树 目的:提高查找、插入、删除的速度(不是为了排序) 时间复杂度:由于查找性能取决于树的形态,所以

    2024年02月09日
    浏览(49)
  • C语言--直接插入排序【排序算法|图文详解】

    直接插入排序又叫简单插入排序,是一种 简单直观 的排序算法,它通过构建有序序列,对于未排序的数据,在已排序序列中从后向前扫描,找到相应位置并插入。 算法描述: 假设要排序的列表为arr,列表的第一个元素arr[0]默认已经是有序序列。 从第二个元素开始,即arr[

    2024年01月19日
    浏览(43)
  • 拓扑排序详解(包含算法原理图解、算法实现过程详解、算法例题变式全面讲解等)

    在图论中,如果一个有向图无法从某个顶点出发经过若干条边回到该点,则这个图是一个有向无环图(DAG图)。 如图所示。 对于一个有向图,若x点指向y点,则称x点为y点的入度。 对于一个有向图,若x点指向y点,则称y点为x点的出度。 队列是一种特殊的线性表,特殊之处在

    2024年02月07日
    浏览(52)
  • 快速排序算法详解(原理,时间复杂度,实现代码)

    快速排序算法详解(原理、实现和时间复杂度) 快速排序是对冒泡排序的一种改进,由 C.A.R.Hoare(Charles Antony Richard Hoare,东尼·霍尔)在 1962 年提出。 快速排序的基本思想是 :通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据比另一部分的所有数据

    2024年02月13日
    浏览(50)
  • 折半插入排序算法详解之C语言版

    折半插入排序是插入排序方法中一种,相比较与直接插入排序算法,减少了排序过程中比较次数,也是一种常用的排序算法。 折半插入排序算法基本原理是将折半查找方法与直接插入排序方法相结合,也就是在每一次插入新元素时,利用折半查找方法找到其待插入的位置。

    2024年02月12日
    浏览(36)
  • C语言入门:冒泡法排序、交换法排序和选择法排序算法的详解(代码分析)

     冒泡法排序 :顾名思义,小的数据就好像水中的气泡一样总是逐渐往上升, 大的数据就像石块一样往下沉,因此称为冒泡法排序法。 假如有n个数字,则需要进行n-1轮  第一轮结果:最大的数,被放在了最后一位  第二轮:元素 ‘8’ 已经拍好了顺序,所以只用将前4个元素

    2024年02月03日
    浏览(49)
  • 【C++】二叉搜索树BST

    二叉搜索树又称二叉排序树,具有以下 性质 : 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值 若它的右子树不为空,则右子树上所有节点的值都大于根节点的值 它的左右子树也分别为二叉搜索树 搜索二叉树不允许数据冗余,也就是说其中 没有重复的数据

    2023年04月25日
    浏览(41)
  • 【数据结构】深入浅出理解快速排序背后的原理 以及 版本优化【万字详解】(C语言实现)

    快速排序是 Hoare 于1962年提出的一种 二叉树结构 的 交换排序 方法。 任取待排序元素序列中的 某元素作为基准值 ,按照该排序码将待排序集合 分割成两子序列 , 左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值 ,然后最左右子序列重复该过程,直到所

    2024年02月05日
    浏览(100)
  • Java之二叉搜索树(BST)

    目录 一.二叉搜索树(BST) 1.什么是二叉搜索树 2.判断一颗二叉搜索树 二.二叉搜索树CRUD操作 1.二叉搜索树的数据结构 2.添加操作 3.查找操作 1.查找最大值 2.查找最小值 3.查找任意值 4.删除操作 1.删除最大值 2.删除最小值 3.删除任意值 5.其他操作 1.打印操作(toString的实现) 6.代码

    2023年04月25日
    浏览(41)
  • C语言实现八大排序算法(详解插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序(递归和非递归)、归并排序(递归和非递归)和计数排序)

    本篇文章使用C语言实现了数据结构中常见的八大排序算法,它们分别是 插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序和计数排序 。在排序算法的实现过程中,每种算法都有其独特的特点和适用场景。插入排序通过逐步构建有序序列来排序,希尔

    2024年01月24日
    浏览(51)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包