当前位置： 首页 > article >正文

嵌入式初学-C语言-数据结构--七

article 2024/11/15 2:20:39

二叉搜索树（BST）

二叉树（BST）的组成

根指针：指向根节点的指针变量

        节点：

                数据域 (存储的实际数据)

                指针域 (左，右指针)

结构设计：

typedef int data_t;
typedef struct _node
{
data_t data; // 数据域
struct _node *left; // 左子树指针
struct _node *right;// 右子树指针
}NODE;

二叉树（BST）的算法

创建二叉树

int btree_create(NODE** root,data_t data);

 二叉树数据添加

int btree_add(NODE** root,data_t data);

 二叉树数据遍历

前序遍历（先序遍历，即 根左右 )）

void Preorder(const NODE* root);

 前序遍历通俗的说就是从二叉树的根结点出发，先输出根结点数据，然后输出左结点，最后输 出右结点的数据。

 从根结点出发，则第一次到达结点A，故输出A;继续向左访问，第一次访问结点B，故输出B； 按照同样规则，输出D，输出H；当到达叶子结点H，返回到D，此时已经是第二次到达D，故不 在输出D，进而向D右子树访问，D右子树不为空，则访问至I，第一次到达I，则输出I；I为叶子 结点，则返回到D，D左右子树已经访问完毕，则返回到B，进而到B右子树，第一次到达E，故 输出E；向E左子树，故输出J；按照同样的访问规则，继续输出C、F、G。

前序遍历输出结果：ABDHIEJCFG

中序遍历（即 左根右 ）

void Midorder(const NODE* root); 

 中序遍历通俗的说就是从二叉树的根结点出发，先输出左结点数据，然后输出根结点，最后输 出右结点的数据。

从根结点出发，则第一次到达结点A，不输出A，继续向左访问，第一次访问结点B，不输出 B；继续到达D，H；

到达H，H左子树为空，则返回到H，此时第二次访问H，故输出H；H右子树为空，则返回至 D，此时第二次到达

D，故输出D；由D返回至B，第二次到达B，故输出B；按照同样规则继续访问，输出J、E、A、 F、C、G；

中序遍历输出结果：HDIBJEAFCG

后序遍历（即 左右根 ）

void Postorder(const NODE* root);

 后序遍历通俗的说就是从二叉树的根结点出发，先输出左结点数据，然后输出右结点，最后输 出根结点的数据。

从根结点出发，则第一次到达结点A，不输出A，继续向左访问，第一次访问结点B，不输出 B；继续到达D，H；

到达H，H左子树为空，则返回到H，此时第二次访问H，不输出H；H右子树为空，则返回至 H，此时第三次到达

H，故输出H；由H返回至D，第二次到达D，不输出D；继续访问至I，I左右子树均为空，故第 三次访问I时，输出

I；返回至D，此时第三次到达D，故输出D；按照同样规则继续访问，输出J、E、B、F、G、 C，A；

后序遍历输出为： HIDJEBFGCA

层序遍历

void Levelorder(const NODE* root);

二叉树数据查询

① 从根结点出发

② 如果比根节点小，那么就去其左子树找

③ 如果比根节点大就去其右子树找

④ 找到叶子都没找到， 就代表查找失败

 二叉树数据更新

int btree_update(const NODE* root,data_t old,data_t newdata);

 二叉树回收

void btree_destroy(NODE** root);

二叉树数据删除 

int btree_delete(NODE** root,data_t data);

原则：将待删除的节点尽量转换为删除叶子节点，因为删除叶子节点对BST树影响是最小的；

思路：

        ① 从根节点开始遍历BST找到待删除的节点；

        ② 对待删除的节点状态进行判断，如果节点有左子树，找到左子树中最大的节点，然后利用 左子树中最大的节 点数据替换待删除的节点数据，删除左子树中最大的节点；左子树中最大的节点大概率 是叶子节点。

        ③ 如果节点只有右子树，找到右子树中最小的节点，然后 利用右子树中最小的节点数据替 换待删除的节点数 据，删除右子树中最小的节点；右子树中最小的节点大概率是叶子节点。

        ④ 如果待删除节点是叶子节点，直接删除。

二叉树（BST）完整实现 

队列实现

SQueue.h
#ifndef __SQUEUE_H
#define __SQUEUE_H
#include "btree.h"
typedef NODE* type_t;
typedef struct
{
type_t *pData;
int size;
int head;
int tail;
}SQueue;
int SQ_init(SQueue *q, int num);
int SQ_isfull(SQueue *q);
int SQ_isempty(SQueue *q);
int SQ_push(SQueue *q,type_t data);
int SQ_pop(SQueue *q,type_t *data);
int SQ_free(SQueue *q);
#endif
SQueue.c
#include <stdlib.h>
#include "SQueue.h"
int SQ_init(SQueue* q,int num)
{
q -> pData = (type_t*)calloc(sizeof(type_t),num);
if(q -> pData == NULL)
return -1;
q -> size = num ;
q -> head = q -> tail = 0;
return 0;
}
int SQ_isfull(SQueue *q)
{
return (q -> tail + 1) % q -> size == q -> head;
}
int SQ_isempty(SQueue *q)
{
return q -> tail == q -> head;
}
int SQ_push(SQueue *st,type_t data)
{
if(SQ_isfull(st))
return -1;
st -> pData[st -> tail] = data;
st -> tail = (st -> tail+1) % st -> size;
return 0;
}
int SQ_pop(SQueue *st,type_t *data)
{
if(SQ_isempty(st))
return -1;
*data = st -> pData[st -> head];
st -> head = (st -> head+1) % st -> size;
return 0;
}
int SQ_free(SQueue *st)
{
if(st -> pData)
{
free(st->pData);
st -> pData = NULL;
}
st -> head = st -> tail = 0;
}

树的实现

btree.h
#ifndef __BTREE_H
#define __BTREE_H
typedef int data_t;
typedef struct _node
{
data_t data; // 节点上的数据
struct _node *left; // 该节点左侧子节点的地址
struct _node *right;// 该节点右侧子节点的地址
}NODE;
// 创建搜索二叉树
int btree_create(NODE** root,data_t data);
// 二叉树数据添加
int btree_add(NODE** root,data_t data);
// 二叉树数据删除
int btree_delete(NODE** root,data_t data);
// 二叉树前序遍历
void Preorder(const NODE* root);
// 二叉树中序遍历
void Midorder(const NODE* root);
// 二叉树后序遍历
void Postorder(const NODE* root);
// 二叉树层序遍历
void Levelorder(const NODE* root);
// 二叉树数据查询
NODE* btree_find(const NODE* root,data_t data);
// 更新二叉树数据old 为 newdata
int btree_update(const NODE* root,data_t old,data_t newdata);
// 二叉树回收
void btree_destroy(NODE** root);
#endif
btree.c
#include "btree.h"
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "SQueue.h"
/*
@function: int btree_create(NODE** root,data_t data)
@brief: 创建搜索二叉树
@argument: root: 根指针地址
@argument: data: 存储的数据
@ret : 0 成功
-1 失败
*/
int btree_create(NODE** root,data_t data)
{
if(*root)
return -1;
NODE* p = (NODE*)malloc(sizeof(NODE));
if(!p)
return -1;
p -> data = data;
p -> left = NULL;
p -> right = NULL;
*root = p;
return 0;
}
/*
@function: int btree_add(NODE** root,data_t data)
@brief: 二叉树数据添加
@argument: root: 根指针地址
@argument: data: 添加的数据
@ret : 0 成功
-1 失败
*/
int btree_add(NODE** root,data_t data)
{
NODE* pNew = (NODE*)malloc(sizeof(NODE));
if(!pNew)
return -1;
pNew -> data = data;
pNew -> left = NULL;
pNew -> right = NULL;
NODE* p = *root, *q = NULL;
if(!p)
{
*root = pNew;
return 0;
}
while(p)
{
q = p;
if(memcmp(&data,&(p -> data),sizeof(data_t)) < 0)
p = p -> left;
else
p = p -> right;
}
if(memcmp(&data,&(q -> data),sizeof(data_t)) < 0)
q -> left = pNew;
else
q -> right = pNew;
return 0;
}
/*
@function: int btree_delete(NODE** root,data_t data)
@brief: 二叉树数据删除
@argument: root: 根指针地址
@argument: data: 待删除的节点数据
@ret : 0 成功
-1 失败
*/
int btree_delete(NODE** root,data_t data)
{
/*
原则：将待删除的节点尽量转换为删除叶子节点，因为删除叶子节点对BST树影响是最小的；
思路：
1. 从根节点开始遍历BST找到待删除的节点；
2. 对待删除的节点状态进行判断，如果节点有左子树，找到左子树中最大的节点，然后利用左子树中最大的
节点数据替换待删除 的节点数据，删除左子树中最大的节点；左子树中最大的节点大概率是叶子节点
3. 如果节点只有右子树，找到右子树中最小的节点，然后 利用右子树中最小的节点数据替换待删除的节点
数据，删除右子树中 最小的节点；右子树中最小的节点大概率是叶子节点
4. 如果待删除节点是叶子节点，直接删除。
*/
NODE* del = *root; //指向待删除的节点
NODE* parent = NULL; //指向实际删除节点的双亲节点
NODE* replace = NULL; //指向实际删除的节点
while(del)
{
if(memcmp(&(del -> data),&data,sizeof(data_t)) < 0) //待删除的数据大于当前节点数据，向右子
树继续查找
{
parent = del;
del = del -> right;
}
else if(memcmp(&(del->data),&data,sizeof(data_t)) > 0) //待删除的数据小于当前节点数据，向
左子树继续查找
{
parent = del;
del = del -> left;
}
else // 找到了待删除的节点
{
if(del -> left) //待删除的节点有左子树
{
parent = del ;
replace = del -> left;
while(replace -> right) //找左子树中最大的节点
{
parent = replace;
replace = replace -> right;
}
del -> data = replace -> data;
if(parent -> right == replace) //实际删除的节点在双亲节点的右子树上
parent -> right = replace -> left;
else
parent -> left = replace -> left;
free(replace);
}
else if(del -> right) //待删除的节点只有右子树
{
parent = del;
replace = del -> right;
while(replace -> left)
{
parent = replace;
replace = replace -> left;
}
del -> data = replace -> data;
if(parent -> right == replace)
parent -> right = replace -> right;
else
parent -> left = replace -> right;
free(replace);
}
else //待删除的节点是叶子
{
if(!parent)
{
free(del);
*root = NULL;
return 0;
}
if(parent -> left == del)
parent -> left = NULL;
else
parent -> right = NULL;
free(del);
}
return 0;
}
}
return -1;
}
/*
@function: void Preorder(const NODE* root)
@brief: 二叉树前序遍历
@argument: root: 根指针
@ret : 无
*/
void Preorder(const NODE* root)
{
if(!root)
return ;
printf("%4d",root -> data);
Preorder(root->left);
Preorder(root->right);
}
/*
@function: void Midorder(const NODE* root)
@brief: 二叉树中序遍历
@argument: root: 根指针
@ret : 无
*/
void Midorder(const NODE* root)
{
if(!root)
return ;
Midorder(root->left);
printf("%4d",root -> data);
Midorder(root->right);
}
/*
@function: void Postorder(const NODE* root)
@brief: 二叉树后序遍历
@argument: root: 根指针
@ret : 无
*/
void Postorder(const NODE* root)
{
if(!root)
return ;
Postorder(root->left);
Postorder(root->right);
printf("%4d",root -> data);
}
/*
@function: void Postorder(const NODE* root)
@brief: 二叉树层序遍历
@argument: root: 根指针
@ret : 无
*/
void Levelorder(const NODE* root)
{
SQueue q;
SQ_init(&q,100);
SQ_push(&q,(type_t)root);
while(!SQ_isempty(&q))
{
type_t dt;
if(0 == SQ_pop(&q,&dt))
{
printf("%4d",dt -> data);
if(dt -> left)
SQ_push(&q,dt->left);
if(dt -> right)
SQ_push(&q,dt->right);
}
}
printf("\n");
SQ_free(&q);
}
/*
@function: NODE* btree_find(const NODE* root,data_t data)
@brief: 二叉树数据查询
@argument: root: 根指针
@argument: data: 待查询的数据
@ret : 成功：返回查询到的节点地址
失败: NULL
*/
NODE* btree_find(const NODE* root,data_t data)
{
const NODE *p = root;
while(p)
{
if(memcmp(&data,&(p -> data),sizeof(data_t)) < 0)
p = p -> left;
else if(memcmp(&data,&(p -> data),sizeof(data_t)) > 0)
p = p -> right;
else
return (NODE*)p;
}
return NULL;
}
/*
@function: int btree_update(const NODE* root,data_t old,data_t newdata)
@brief: 更新二叉树数据old 为 newdata
@argument: root: 根指针
@argument: old: 待更新的数据
@argument: newdata: 更新后的数据
@ret : 成功：0
失败: -1
*/
int btree_update(const NODE* root,data_t old,data_t newdata)
{
NODE* pfind = btree_find(root,old);
if(!pfind)
return -1;
pfind -> data = newdata;
return 0;
}
/*
@function: void btree_destroy(NODE** root)
@brief: 二叉树回收
@argument: root: 根指针地址
@ret : 无
*/
static void btree_free(NODE* root)
{
if(!root)
return ;
btree_free(root->left);
btree_free(root->right);
free(root);
}
void btree_destroy(NODE** root)
{
btree_free(*root);
*root = NULL;
}
btree_main.c
#include "btree.h"
#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define N 10
int main(void)
{
NODE *root = NULL;
register int i = 0;
data_t a[] = {20,15,25,10,19,28,6,13,26,30,11,27};
int n = sizeof a / sizeof a[0];
srand(time(NULL));
for(; i < n ; i++)
{
// int data = rand() % 99 + 1;
// printf("%4d",data);
// btree_add(&root,data);
btree_add(&root,a[i]);
}
printf("\n");
puts("====先序遍历====");
Preorder(root);
printf("\n");
puts("====中序遍历====");
Midorder(root);
printf("\n");
puts("====后序遍历====");
Postorder(root);
printf("\n");
puts("====层序遍历====");
Levelorder(root);
printf("\n");
data_t deldata = 0;
while(1)
{
printf("请输入要删除的数据(-1退出):");
scanf("%d",&deldata);
if(deldata == -1)
break;
if(btree_delete(&root,deldata) == -1)
{
puts("删除失败请重试...");
continue;
}
puts("====先序遍历====");
Preorder(root);
printf("\n");
}
btree_destroy(&root);
return 0;
}


http://www.kler.cn/a/306498.html

相关文章：

  • Spring高手之路26——全方位掌握事务监听器
  • flutter下拉刷新上拉加载的简单实现方式三
  • C++ 的协程
  • uniapp使用scroll-view下拉刷新与上滑加载
  • INQUIRE：一个包含五百万张自然世界图像，涵盖10,000个不同物种的专为专家级文本到图像检索任务设计的新型基准数据集。
  • 2024/11/13 英语每日一段
  • 【linux基础】linux中的开发工具(4)--调试器gdb的使用
  • 问题及解决方案汇总
  • 结构体内存对齐
  • 【算法】动态规划—最长公共子序列
  • HTML+CSS - 网页布局之多列布局定位
  • 网络安全应急响应概述
  • 用STM32做一个USB-TTL工具吧
  • JavaScript Promise 异步编程的一些代码分享
  • 远程桌面内网穿透是什么？有什么作用？
  • openssl下载和创建证书
  • 如何在 Visual Studio Code 中反编译具有正确行号的 Java 类？
  • C++：opencv多边形逼近二值图轮廓--cv::approxPolyDP
  • Java集合进阶--双列集合
  • R与机器学习系列|15.可解释的机器学习算法（Interpretable Machine Learning）（下）
  • HarmonyOS开发5.0【rcp网络请求】
  • ChatGPT+2：修订初始AI安全性和超级智能假设
  • L298N电机驱动方案简介
  • JAVA：Nginx（轻量级的Web服务器、反向代理服务器）--（1）
  • JAVA学习-练习试用Java实现“串联所有单词的子串”
  • 物联网——USART协议