C语言如何实现BST二叉排序树

这篇文章主要介绍了C语言如何实现BST二叉排序树，具有一定借鉴价值，感兴趣的朋友可以参考下，希望大家阅读完这篇文章之后大有收获，下面让小编带着大家一起了解一下。

具体内容如下

BST-二叉排序树的几个基本操作。

头文件声明与函数定义

#include #include typedef int ElemType;/*** 定义节点*/typedef struct BSTNode{ ElemType data;//数据域 struct BSTNode *lchild,//左孩子  *rchild;//右孩子}BSTNode;/*** 插入节点*/int BST_InsertNode(BSTNode** bstNode,ElemType e);/*** 创建BST树*/void BST_Create(BSTNode** bstTree,ElemType* dataSet,int n);/** * 查找BST树节点 */BSTNode* BST_SearchNode(BSTNode** bstNode,ElemType e);/** * 遍历BST树节点 */void BST_PrintNodes(BSTNode* bstNode);

函数编写

#include "BSTree.h"/*** 插入节点*/int BST_InsertNode(BSTNode** bstNode,ElemType e){ //如果BST树为空，直接创建根节点 if (*bstNode==NULL) {  *bstNode=(BSTNode*)malloc(sizeof(BSTNode));  (*bstNode)->data=e;  (*bstNode)->lchild=NULL;  (*bstNode)->rchild=NULL;  return 1; } //如果BST树不为空,则比较插入值与根节点值的大小关系 if ((*bstNode)->data==e)  return 0;//关键值相同，则插入失败 else if ((*bstNode)->data>e)  return BST_InsertNode(&(*bstNode)->lchild,e);//大于插入值，将其作为左子树节点 else if ((*bstNode)->datarchild,e);//小于插入值，将其作为右子树节点}/*** 创建BST树*/void BST_Create(BSTNode** bstTree,ElemType* dataSet,int n){ int i=0; *bstTree=NULL;//BST树初始化为空 while (idata==e)//验证是否为根节点  return *bstNode; else if ((*bstNode)->data>e) {  return BST_SearchNode(&(*bstNode)->lchild,e);//如果小于根节点的值，查找左子树 }else {  return BST_SearchNode(&(*bstNode)->rchild,e);//如果大于根节点的值，查找右子树 }}/** * 遍历BST树节点 */void BST_PrintNodes(BSTNode* bstNode){ if (bstNode==NULL)//根节点判空 {  return; } //打印根节点的值 printf("%d\t",(bstNode)->data); //从根节点开始遍历 if (bstNode->lchild!=NULL)  BST_PrintNodes((bstNode)->lchild);//遍历左子树 if (bstNode->rchild!=NULL)  BST_PrintNodes(bstNode->rchild);//遍历右子树}

测试

#include "BSTree.h"int main(int argc,char** argv){ int i; ElemType arr[]={45,24,53,45,12,24,68,25,36,96,100,25,64,78};//只有4个元素，因为关键字重复的元素不能被插入 BSTNode* bstNode=NULL; BSTNode* bstTemp=NULL; //创建BST树 BST_Create(&bstNode,arr,sizeof(arr)/sizeof(ElemType)); printf("%d\t%d\n",bstNode,bstNode->data); printf("%d\t%d\n",bstNode,bstNode->lchild->data); //查找结点 bstTemp=BST_SearchNode(&bstNode,53); printf("the aimed node is %d,\n",bstNode->data);  //遍历BST树的所有节点 BST_PrintNodes(bstNode); printf("\n");}

贴上测试结果如下，【插入和遍历的节点数量不一致是因为-如果BST树中的节点关键值相同，就终止插入操作】

感谢你能够认真阅读完这篇文章，希望小编分享的"C语言如何实现BST二叉排序树"这篇文章对大家有帮助，同时也希望大家多多支持，关注行业资讯频道，更多相关知识等着你来学习!