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树中的节点关键值相同,就终止插入操作】

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

(0)

相关推荐

  • C语言二叉排序(搜索)树实例

    本文实例为大家分享了C语言二叉排序(搜索)树实例代码,供大家参考,具体内容如下 /**1.实现了递归 非递归插入(创建)二叉排序(搜索)树: 分别对应Insert_BinSNode(TBinSNode* T,int k),NonRecursion_Insert_BinSNode(TBinSNode* T,int k); 2.实现了递归 非递归查找 二叉排序(搜索)树 : 分别对应Find_BinSNode(TBinSNode *T,int s),NonRecursion_Find_BinSNod

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

    本文实例为大家分享了C语言实现BST二叉排序树的基本操作代码,供大家参考,具体内容如下 BST-二叉排序树的几个基本操作. 头文件声明与函数定义 #include <stdio.h> #include <stdlib.h> typedef int ElemType; /** * 定义节点 */ typedef struct BSTNode{ ElemType data;//数据域 struct BSTNode *lchild,//左孩子 *rchild;//右孩子 }BSTNode

  • C语言对栈的实现基本操作

    c语言中栈是一种数据结构,后进先出,即最后进入栈的数据最先弹出.c语言中没有栈这种数据类型,需要自己编程构建.下面我们就一起来了解一下c语言中栈的基本操作. C语言对栈的实现基本操作,操作如下: #include <stdio.h> #include <malloc.h> #include <stdlib.h> #include <stdbool.h> typedef struct Node { int data; struct Node * pNext;

  • C语言实现线性表的基本操作详解

    目录 前言 一.实训名称 二.实训目的 三.实训要求 四.实现效果 五.顺序存储代码实现 六.链式存储代码实现 前言 这里使用的工具是DEV C++ 可以借鉴一下 一.实训名称 线性表的基本操作 二.实训目的 1.掌握线性表的基本概念 2.掌握线性表的存储结构(顺序存储与链式存储) 3.掌握线性表的基本操作 三.实训要求 1.线性表可以顺序表也可以用单链表实现,鼓励大家用两种方式实现. 2.创建线性表时,数据从键盘输入整形数据 3.线性表类型定义和或各种操作的实现,可以用教材给出的方法,也可以自

  • C语言实现顺序表的基本操作的示例详解

    目录 一.认识顺序表 1.线性表 2.顺序表的概念及结构 二.顺序表的基本操作(接口实现) 1.初始化顺序表 2.打印顺序表 3.尾插 4.尾删 5.扩容 6.头插 7.头删 8.任意位置插入 9.任意位置删除 10.查找某个数的位置 三.顺序表演示及代码(含源码) 1.演示效果 2.完整源代码 一.认识顺序表 1.线性表 线性表是n个具有相同特性的数据元素的有限序列,线性表是一种在实际中广泛使用的数据结构,常见的线性表有顺序表.链表.栈.队列.字符串……线性表在逻辑上是线性结构,也就是说是一条

  • Go语言实现栈与队列基本操作学家

    目录 一.前言 二.实现栈与队列基本操作 2.1 栈基本操作 2.2 队列基本操作 三.用栈实现队列 3.1 理论 3.2 算法题 3.3 思路 3.4 代码部分 四.用队列实现栈 4.1 理论 4.2 算法题 4.3 思路 4.4 使用两个队列实现 4.5 优化 4.6 使用一个队列实现 一.前言 go语言中,并没有栈与队列相关的数据结构,但是我们可以借助切片来实现栈与队列的操作:接下来我们一起实现栈与队列基本操作,并且还会实现用栈实现队列,用队列实现栈的操作. 二.实现栈与队列基本操作 2.

  • C语言实现单链表的基本操作分享

    目录 导语 单链表 单链表的特点 定义 初始化操作 头插法 尾插法 删除第i个元素 在第i个位置插入 导语 无论是顺序存储结构还是链式存储结构,在内存中进行存放元素的时候,不仅需要存放该元素的相关信息,还需要存放该元素和其他元素之间的关系,而我们之前所学的顺序表“与生俱来”的物理结构自然地能够表达出元素和元素之间的关系,不需要额外的信息去表达元素和元素之间的关系,而对于链式存储这种非顺序存储的结构,需要额外附加指针去表示这种关系. 单链表 每个结点除了存放数据元素外,还要存储指向下一个节点的指针

  • C语言中带头双向循环链表基本操作的实现详解

    目录 一.概念与结构 二.基本操作的实现 1.创建结点 2.初始化链表 3.打印链表 4.尾插 5.尾删 6.头插 7.头删 8.查找某个数并返回其指针 9.在某个位置之前插入 10.删除某个位置 11.判断链表是否为空 12.计算链表中有效值的个数 13.销毁链表 三.测试代码 一.概念与结构 无头单向非循环链表结构简单,一般不会单独用来存数据.实际中更多的是作为其他数据结构的子结构,如哈希桶.图的邻接表等等.而带头双向循环链表的结构较为复杂,一般用在单独存储数据.实际中使用的链表数据结构,都

  • Go 语言结构体链表的基本操作

    目录 1. 什么是链表 2. 单项链表的基本操作 3. 使用 struct 定义单链表 4. 尾部添加节点方法一 5. 头部插入节点方法一 6. 指定节点后添加新节点 7. 删除节点 1. 什么是链表 链表是一种物理存储单元上非连续.非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的. 链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成.每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域. 使用链表结构可以避免在使用数组

  • c语言实现顺序表的基本操作

    数据结构顺序表操作 复制代码 代码如下: #include <stdio.h>#include <stdlib.h>#include <malloc.h>#define LIST_INIT_SIZE 100#define LISINCREMENT 10#define ElemType int#define Status inttypedef struct Sq{ ElemType *elem; int length; int listsize;}SqList;Statu

  • C语言数据结构之链队列的基本操作

    目录 1.队列的定义 2.队列的表示和实现 (1) 初始化操作 (2)销毁队列 (3) 入队操作 (4) 出队操作 附录完整代码: 总结 1.队列的定义 队列 (Queue)是另一种限定性的线性表,它只允许在表的一端插入元素,而在另一端删除元素,所以队列具有先进先出(Fist In Fist Out,缩写为FIFO)的特性.在队列中,允许插入的一端叫做队尾(rear),允许删除的一端则称为队头(front). 假设队列为q=(a1,a2,-,an),那么a1就是队头元素,an则是队尾元素.队列中

随机推荐