BST二叉查找树
- 二叉查找树的创建以及初始化
- 二叉查找树节点插入
- 二叉查找树的节点数、深度、叶子节点数（递归）
- 二叉查找树的先、中、后序遍历
/*****************************************************
* file name:sequencelist.c
* author :zzlyx1239@126.com
* date :2025.3.18
* brief :BST二叉查找树
* note :none
*
* Copyright (c) 2025 zzlyx1239@126.com All Right Reserved
*
*******************************************************/
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
//设计BST的接口，为了方便对二叉树进行节点的增删，所以采用双向不循环链表实现，每个节点都有两个指针，分别指向左子树lchild和右子树rchild
//BST树中有效键值的数据类型，用户可以根据需要修改
typedef int DataType_t;
//BST树的节点
typedef struct BSTreeNode
{
DataType_t data;//节点的键值
struct BSTreeNode *lchild;//节点的左孩子指针域
struct BSTreeNode *rchild;//节点的右孩子指针域
}BSTNode_t;
//创建一个带根节点的BST树，对根节点初始化（数据域+指针域）
BSTNode_t * BSTree_Creat(DataType_t data)
{
//为根节点申请堆内存空间
BSTNode_t *Root=(BSTNode_t*)calloc(1,sizeof(BSTNode_t));
if(Null==Root)
{
perror("calloc for Root memory is Failed!!! ");
exit(-1);
}
//对根节点初始化
Root->data=data;
Root->lchild=NULL;
Root->rchild=NULL;
return Root;
}
//创建新的结点，并对新结点进行初始化（数据域 + 指针域）
BSTNode_t * BSTree_NewNode(BSTNode_t *Root,DataType_t data)
{
//为新节点申请堆内存空间
BSTNode_t *New=(BSTNode_t*)calloc(1,sizeof(BSTNode_t));
if(Null==New)
{
perror("calloc for New memory is Failed!!! ");
exit(-1);
}
//对新节点初始化
New->data=data;
New->lchild=NULL;
New->rchild=NULL;
return New;
}
//向BST二叉树中插入新节点 规则：根节点的左子树的键值都是比根节点小的，根节点的右子树的键值都是比根节点大的
bool BSTree_InsertNode(BSTNode_t *Root,DataType_t destval)
{
//为了避免根节点地址丢失，所以需要对地址进行备份
BSTnode_t *Proot = Root;
//1.为新节点申请内存空间
New=BSTree_NewNode(Root,destval);
if (NULL == New)
{
printf("Create NewNode Error\n");
return false;
}
//2.判断根节点是否存在,根节点不存在，新插入的节点作为根节点
if(Root==NULL)
{
Root=New;
}
else//
{
while(Proot)//根节点存在，如果新节点的值比根的值大，就在右子树找，反则就在左子树找
{
if(Proot->data==destval)//如果和根节点的值相等，插入失败
{
printf("Can Not Insert\n");
return false;
}
else
{
if(Proot->data>destval)
{
if(Proot->lchild==NULL)
{
Proot->lchild=New;
break;
}
Proot=Proot->lchild;
}
else
{
if(Proot->rchild==NULL)
{
Proot->rchild=New;
break;
}
Proot=Proot->rchild;
}
}
}
}
return true;
}
//BST二叉树节点的数量
int BSTree_NodeNum(BSTNode_t *Root)
{
int n1,n2;//n1为左子树节点数量，n2为右子树节点数量
//1.判断树是否为空，如果为空返回0
if(Root==NULL)
{
return 0;
}
n1=BSTree_NodeNum(Root->lchild);
n2=BSTree_NodeNum(Root->rchild);
return n1+n2+1;
}
//叶子节点数量
int BSTree_LeafNodeNum(BSTNode_t *Root)
{
int n1,n2;记录左右叶子节点数量
//终止条件
if(Root=NULL)
{
return 0;
}
elseif(Root->lchild=NULL&&Root->rchild)
{
return 1;
}
else
{
n1=BSTree_LeafNodeNum(Root->lchild);
n2=BSTree_LeafNodeNum(Root->rchild);
}
return n1+n2;
}
//树的深度
int BSTree_GetDepth(Root)
{
int n1,n2;//定义左右子树的高度
//1.定义左右子树的结束条件
if(Root=NULL)
{
//空树，返回0
return 0;
}
elseif(Root->lchild==NULL&&Root->rchild->NULL)
{
//只有根节点返回1
return 1;
}
else
{
n1=BSTree_GetDepth(Root->lchild);
n2=BSTree_GetDepth(Root->rchild);
}
return (n1>n2?n1:n2)+1;
}
//先序遍历 根左右
bool BSTree_PreOrder(BSTNode_t Root)
{
//使用递归函数，写好终止条件
if(NULL=Root)
{
return false;
}
//输出根节点
printf("keyval=%d\n",Root->data);
//输出左子树
BSTree_PreOrder(Root->lchild);
//输出右子树
BSTree_PreOrder(Root->rchild);
}
//中序遍历 左根右
bool BSTree_InOrder(BSTNode_t Root)
{
//使用递归函数，写好终止条件
if(NULL=Root)
{
return false;
}
//输出左子树
BSTree_PreOrder(Root->lchild);
//输出根节点
printf("keyval=%d\n",Root->data);
//输出右子树
BSTree_PreOrder(Root->rchild);
}
//后序遍历 左右根
bool BSTree_PostOrder(BSTNode_t Root)
{
//使用递归函数，写好终止条件
if(NULL=Root)
{
return false;
}
//输出左子树
BSTree_PreOrder(Root->lchild);
//输出右子树
BSTree_PreOrder(Root->rchild);
//输出根节点
printf("keyval=%d\n",Root->data);
}
int main()
{
return 0;
}
