C语言实现BST二叉排序树的基本操作

本文实例为大家分享了c语言实现bst二叉排序树的基本操作代码，供大家参考，具体内容如下

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

头文件声明与函数定义

#include <stdio.h>
#include <stdlib.h>

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)->data<e)
  return bst_insertnode(&(*bstnode)->rchild,e);//小于插入值，将其作为右子树节点
}

/**
* 创建bst树
*/
void bst_create(bstnode** bsttree,elemtype* dataset,int n){
 int i=0;
 *bsttree=null;//bst树初始化为空
 while (i<n)
 {
  printf("%d\t",dataset[i]);
  bst_insertnode(bsttree,dataset[i++]);
 }
 printf("\n");
}

/**
 * 查找bst树节点
 */
bstnode* bst_searchnode(bstnode** bstnode,elemtype e){
 if (*bstnode==null)//判空
  return *bstnode;
 //查找结点
 if ((*bstnode)->data==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树中的节点关键值相同，就终止插入操作】

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。