一、算法原理
二叉排序树(Binary Sort Tree或 Binary Search Tree)又称二叉查找树,可以用来实现数据的快速查找,也方便数据的插入、删除等工作,因此适用于数据的动态查找。
二叉排序树是一棵二叉树,其左子树上的元素都小于树根,右子树上的元素都大于树根,所有的子树也满足这个性质。
要想实现二叉排序树的查找,需要事先已经建立了二叉排序树。其原理很简单,如果已知一个数组,则首先把数组的第一个元素存储到树根。读入第二个元素的时候需要和树根进行比较,比树根小则存到左子树,否则存到右子树。读入第三个元素时,依旧先和树根进行比较,如果大于树根元素,则存入右子树,否则就与当前左子树树根进行比较,小的话则存入左子树的左子树。以后读入其它元素也是如此操作,就可以创建一棵二叉排序树。
下面以具体案例给出二叉排序树创建的详细过程。
Demo:
假设一组散乱数据:{ 18, 3, 7, 20, 14, 19, 27, 2 }
Step 1:创建二叉树,将18存入树根,结果如下图所示。
Step 2:取元素3,与树根18进行比较,此时小于18,所以存入左子树树根,结果如下图所示。
Step 3:取元素7,与树根18进行比较,小于18,再与左子树树根3比较,此时大于3,所以存入3的右子树位置,结果如下图所示。
Step 4:取元素20,与树根18进行比较,大于18,所以存入右子树树根位置,结果如下图所示。
Step 5:取元素14,与树根18进行比较,小于18,再与左子树树根3比较,大于3,接着与3的右子树树根7进行比较,大于7,所以插入7的右子树树根位置,结果如下图所示。
Step 6:取元素19,与树根18进行比较,大于树根,再与右子树树根20比较,小于20,所以插入到20的左子树位置,结果如下图所示。
Step 7:取元素27,与树根18进行比较,大于树根,再与右子树树根20比较,大于20,所以插入到20的右子树位置,结果如下图所示。
Step 8:取元素2,与树根18进行比较,小于18,再与左子树树根3比较,小于3,所以插入到3的左子树位置,结果如下图所示。
至此,完成了把该数组存入到一棵二叉排序树。
二、创建二叉排序树算法的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.测试代码(仅供参考)文章来源:https://www.toymoban.com/news/detail-470964.html
#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.运行结果
文章来源地址https://www.toymoban.com/news/detail-470964.html
到了这里,关于二叉排序树(BST)创建详解之C语言版的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!