树形查找（二叉查找树）
介绍
我们在平时的查找算法中，最多的往往是顺序查找和折半查找，而对树形查找往往一知半解，本文主要介绍二叉排序树的创建，插入和查找。
树的定义
树是一种数据结构，它是由n(n≥0)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点： 每个节点有零个或多个子节点；没有父节点的节点称为根节点；每一个非根节点有且只有一个父节点；除了根节点外，每个子节点可以分为多个不相交的子树。 而如果一棵树他的每个节点最多含有两个子树的树称为二叉树。 二叉树的程序定义一般如下：
typedef char Elemtype ;typedef struct BiNode{
Elemtype data;
struct BiNode *lchild,*rchild;}*BiTree;二叉排序树的插入
添加一个值为k的节点到树T上。
int BST_inser(BiTree T,Elemtype k){
if(T==NULL)
{
T=(BiTree)malloc(sizeof(BiNode));
T->data=k;
T->lchild=NULL;
T->rchild=NULL;
return 1;//插入成功
}
else if(T->data==k)
{
return 0;
}
else if(T->data>k)
{
return BST_inser( T=T->lchild,k);
}
else
{
return BST_inser(T=T->rchild,k);
}}二叉排序树的创建
二叉排序树的创建其实就是创建一个空树，然后将一组数据依次存放到这个树种。
void Creat_BST(BiTree &T,Elemtype a[],int n){
T=NULL;//初始时T为空树
int i=0;
while(i<n)
{
BST_inser(T,a[i]);
i++;
}}树形查找
二叉排序树的查找其实非常简单，就是将值k从排序树的根节点，依次往下差，当k大于当前比对的T节点值的时候，查找此节点T的右孩子，当k小于当前比对的T节点值的时候，查找此节点T的左孩子，当等于此节点的值的时候，返回此节点。
BiNode *Bst_search(BiTree T,Elemtype k){
while(T!=NULL&&T->data!=k)
{
if(k<T->data)
T=T->lchild;
else
T=T->rchild;
}
return T;}本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2022-08-04，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录