C语言数据结构之二叉排序树


C语言数据结构之二叉排序树

tips:前些天学习了线索二叉树,今天来总结一下二叉排序树的相关操作。

二叉排序树(BST):

若左子树非空,则左子树上所有结点的值均小于根结点的值;
若右子树非空,则右子树上所有结点的值均大于根结点的值;
二叉排序树的左右子树也是一棵二叉排序树;

总之,二叉排序树的中序序列是一个递增的序列。

二叉排序树的存储结构与普通二叉树相同:

typedef struct node
{
int key;//关键字
struct node *left;
struct node *right;
}Node,*pNode;

1、二叉排序树的构造及插入

思路:

若二叉排序树为空,则直接插入结点作为根结点;
若二叉排序树非空,当值小于根结点时,插入左子树;
若二叉排序树非空,当值等于根结点时,不予插入;
若二叉排序树非空,当值大于根结点时,插入右子树;

注意,这里我们要在子函数修改在主函数声明的bt的值,所以这里我们在子函数中传入bt的地址!

具体实现:

//二叉排序树的插入
int BSTInsert(pNode *bt, int key)
{
if ((*bt) == NULL)
{
//二叉排序树为空,直接插入
pNode ptmp = (pNode)malloc(sizeof(Node));
*bt = ptmp;
(*bt)->key = key;
(*bt)->left = (*bt)->right=NULL;
return 1;//插入成功
}
else if (key == (*bt)->key)
return 0;//key已经存在,不予插入
else if (key < (*bt)->key)
{
return BSTInsert(&((*bt)->left), key);//递归插入左子树
}
else
{
return BSTInsert(&((*bt)->right), key);//递归插入右子树
}

}

//构建二叉排序树
void CreateBST(pNode *bt, int *key)
{
int i;
(*bt) = NULL;//清空树
for (i = 0; i < N; i++)
BSTInsert(bt,key[i]);
}

2、二叉排序树的查找

思路:

从根结点开始查找,若相等,则查找成功;
若查找的值小于根结点,则查找左子树;
若查找的值大于根结点,则查找右子树;

具体实现:

//二叉排序树的查找
pNode BSTSearch(pNode bt, int key)
{
while (bt != NULL && key != bt->key)
{
if (key < bt->key)
bt = bt->left;//小于,查找左子树
else
bt = bt->right;//大于,查找右子树
}
return bt;
}

3、二叉排序树的删除

思路:

若删除的结点时叶子结点,则直接删除;
若删除的结点i只有一棵子树,则让i的子树成为i父结点的子树(替代i,独子继承父业);
若被删除结点i有两棵子树,则让i的中序序列直接后继替代i,并删除后继结点;

以上就是二叉排序树的构建及查找,删除思路。接下来我们在main()函数中测试一下:

int main()
{
int arr[N] = { 1,4,2,7,5,6,9,8,3,0 };
pNode bt;

CreateBST(&bt, arr);//结束后,bt指向arr[0]

//中序打印
printf("中序遍历:");
midorder(bt);
printf("\n");

printf("bt->key=%d\n", bt->key);

pNode pSearchNode = BSTSearch(bt,5);
if (pSearchNode != NULL)
{
printf("pSearchNode的key:%d\n", pSearchNode->key);
}
else
{
printf("查找的值不存在!\n");
}

return 0;
}

测试结果:
C语言数据结构之二叉排序树
可以看到二叉排序树的中序遍历时递增的!

tips:生是偶然,活是必然,生活不是易然。人在一生的向往面前,有时只是一叶草的语言。

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

C语言数据结构之二叉排序树

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » C语言数据结构之二叉排序树
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏