【数据结构】（C语言）：二叉搜索树

二叉搜索树：

  • 树不是线性的，是层级结构。
  • 基本单位是节点，每个节点最多2个子节点。
  • 有序。每个节点，其左子节点都比它小，其右子节点都比它大。
  • 每个子树都是一个二叉搜索树。每个节点及其所有子节点形成子树。
  • 可以是空树。

添加元素：从根节点开始，比对数值。若比它小，往左子树比对；若比它大，往右子树比对；直到找到为空，则为新元素的位置。

删除元素：

  1. 若删除的节点为叶子节点（即无子节点），则直接删除。
  2. 若删除的节点只有左子节点，则左子节点替代删除节点。
  3. 若删除的节点只有右子节点，则右子节点替代删除节点。
  4. 若删除的节点既有左子节点又有右子节点，则找到直接前驱（即删除节点的左子树中的最大值，即删除节点的左子节点的最右节点），直接前驱的值替代删除节点的值，删除直接前驱节点。

遍历元素：（可使用递归）

  • 前序遍历（顺序：根节点、左子节点、右子节点）。
  • 中序遍历（顺序：左子节点、根节点、右子节点）。
  • 后序遍历（顺序：左子节点、右子节点、根节点）。

查找元素：从根节点开始，比对数值。若比它小，往左子树查找；若比它大，往右子树查找；直到找到该元素，则返回1（true），若没有，则返回0（false）。

C语言实现：（使用链表实现）

 创建结构体数据类型（记录二叉搜索树的根节点和数据个数）：

typedef struct Link
{
	LinkNode *root;			// 根节点
	int length;			    // 统计有多少数据
} LinkBST;                  // 别名

创建二叉搜索树，并初始化：

LinkBST bst;
bst.root = NULL;    // 根节点，初始化为NULL
bst.length = 0;     // 数据个数，初始化为0

创建节点（结构体数据类型），并创建具体节点实例的函数：

// 节点（结构体数据类型）
typedef struct Node
{
	int value;			    // 数据类型为整型
	struct Node *left;		// 左子节点
	struct Node *right;		// 右子节点
}LinkNode;                  // 别名
// 函数：创建节点
LinkNode *createNode(int data)
{
	LinkNode *node = (LinkNode *)malloc(sizeof(LinkNode));    // 分配节点内存空间

	if(node == NULL)
	{
		perror("Memory allocation failed");
		exit(-1);
	}
	node->value = data;    // 数据
	node->left = NULL;     // 左子节点，初始化为NULL
	node->right = NULL;    // 右子节点，初始化为NULL
	return node;
}

添加元素：

void add(LinkBST *bst, int data)	// add element
{
	// 函数：往二叉搜索树中添加元素	
	LinkNode *addNode(LinkNode *node, int data)
	{
		if(node == NULL)
		{
			LinkNode *newnode = createNode(data);
			node = newnode;
			bst->length++;    // 每添加一个元素，length+1
			return node;
		}
		if(data < node->value) node->left = addNode(node->left, data);
		else if(data > node->value) node->right = addNode(node->right, data);
		return node;
	}

	// 从根节点开始比对，root指针始终指向二叉搜索树的根节点
	bst->root = addNode(bst->root, data);	
}

删除元素：

void delete(LinkBST *bst, int data)	// delete element
{
	// 函数：删除节点	
	LinkNode *del(LinkNode *node)
	{   
        // 若只有右子节点，则右子节点替代删除节点
		if(node->left == NULL)
		{
			bst->length--;        // 每删除一个元素，length-1
			return node->right;
		}
        // 若只有左子节点，则左子节点替代删除节点
		else if(node->right == NULL)
		{
			bst->length--;        // 每删除一个元素，length-1
			return node->left;
		}
        // 左右子节点都有，则直接前驱(左子节点的最右节点)替代删除节点，并删除直接前驱
		else if(node->left && node->right)
		{
			LinkNode *tmp = node, *cur = node->left;
			while(cur->right)
			{
				tmp = cur;
				cur = cur->right;
			}
			node->value = cur->value;
			if(tmp != node) tmp->right = cur->left;
			else tmp->left = cur->left;
			bst->length--;        // 每删除一个元素，length-1
			return node;
		}
	}

	// 函数：找到将要删除的节点
	LinkNode *delNode(LinkNode *node, int data)
	{
		if(node == NULL) return node;
		if(data == node->value) node = del(node);
		else if(data < node->value) node->left = delNode(node->left, data);
		else if(data > node->value) node->right = delNode(node->right, data);
		return node;
	}	
	
	// 从根节点开始比对。root指针始终指向二叉搜索树的根节点
	bst->root = delNode(bst->root, data);	
}

遍历元素：（使用递归）

// 前序遍历（根，左，右）
void pretravel(LinkNode *node)
{
	if(node == NULL) return ;
	printf("%d  ", node->value);
	pretravel(node->left);
	pretravel(node->right);
}
// 中序遍历（左，根，右）
void midtravel(LinkNode *node)
{
	if(node == NULL) return ;
	midtravel(node->left);
	printf("%d  ", node->value);
	midtravel(node->right);
}
// 后序遍历（左，右，根）
void posttravel(LinkNode *node)
{
	if(node == NULL) return ;
	posttravel(node->left);
	posttravel(node->right);
	printf("%d  ", node->value);
}

查找元素：

找到元素，返回1(true)；没找到，返回0(false)。

int find(LinkNode *node, int data)
{
	if(node ==  NULL) return 0;
	if(data == node->value) return 1;
	if(data < node->value) find(node->left, data);
	else if(data > node->value) find(node->right, data);	
}

完整代码：（bst.c）

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

/* structure */
typedef struct Node			// linkedlist node
{
	int value;			// value type is integer
	struct Node *left;		// left child node
	struct Node *right;		// right child node
}LinkNode;

typedef struct Link			// binary search tree
{
	LinkNode *root;			// root node of the tree
	int length;			// the number of the tree
} LinkBST;

/* function prototype */
void add(LinkBST *, int);		// add element to the tree
void delete(LinkBST *, int);		// delete element from the tree
void pretravel(LinkNode *);		// show element one by one,(root,left,right)
void midtravel(LinkNode *);		// show element one by one,(left,root,right)
void posttravel(LinkNode *);		// show element one by one,(left,right,root)
int find(LinkNode *, int);		// if find data,return 1(true),or return 0(false)

/* main function */
int main(void)
{
	// create binary search tree and initialization
	LinkBST bst;
	bst.root = NULL;
	bst.length = 0;
	printf("isempty(1:true, 0:false): %d, length is %d\n",  bst.root==NULL, bst.length);
	
	add(&bst, 15);
	add(&bst, 8);
	add(&bst, 23);
	add(&bst, 10);
	add(&bst, 12);
	add(&bst, 19);
	add(&bst, 6);
	printf("isempty(1:true, 0:false): %d, length is %d\n",  bst.root==NULL, bst.length);

	printf("midtravel: ");
	midtravel(bst.root);
	printf("\n");
	printf("pretravel: ");
	pretravel(bst.root);
	printf("\n");
	printf("posttravel: ");
	posttravel(bst.root);
	printf("\n");
	
	printf("find 10 (1:true, 0:false): %d\n", find(bst.root, 10));
	printf("find 9 (1:true, 0:false): %d\n", find(bst.root, 9));
	
	delete(&bst, 23);
	delete(&bst, 15);
	delete(&bst, 6);

	printf("isempty(1:true, 0:false): %d, length is %d\n",  bst.root==NULL, bst.length);
	printf("midtravel: ");
	midtravel(bst.root);
	printf("\n");
	printf("pretravel: ");
	pretravel(bst.root);
	printf("\n");
	printf("posttravel: ");
	posttravel(bst.root);
	printf("\n");
	return 0;
}

/* subfunction */
LinkNode *createNode(int data)		// create a node
{
	LinkNode *node = (LinkNode *)malloc(sizeof(LinkNode));

	if(node == NULL)
	{
		perror("Memory allocation failed");
		exit(-1);
	}
	node->value = data;
	node->left = NULL;
	node->right = NULL;
	return node;
}

void add(LinkBST *bst, int data)	// add element
{
	// subfunction(recursion): add element to the binary search tree	
	LinkNode *addNode(LinkNode *node, int data)
	{
		if(node == NULL)
		{
			LinkNode *newnode = createNode(data);
			node = newnode;
			bst->length++;
			return node;
		}
		if(data < node->value) node->left = addNode(node->left, data);
		else if(data > node->value) node->right = addNode(node->right, data);
		return node;
	}

	// root node receive the result
	bst->root = addNode(bst->root, data);	
}

void delete(LinkBST *bst, int data)	// delete element
{
	// subfunction(recursion): delete element from the binary search tree	
	LinkNode *del(LinkNode *node)
	{
		if(node->left == NULL)
		{
			bst->length--;
			return node->right;
		}
		else if(node->right == NULL)
		{
			bst->length--;
			return node->left;
		}
		else if(node->left && node->right)
		{
			LinkNode *tmp = node, *cur = node->left;
			while(cur->right)
			{
				tmp = cur;
				cur = cur->right;
			}
			node->value = cur->value;
			if(tmp != node) tmp->right = cur->left;
			else tmp->left = cur->left;
			bst->length--;
			return node;
		}
	}

	// subfunction: find delete node,return node
	LinkNode *delNode(LinkNode *node, int data)
	{
		if(node == NULL) return node;
		if(data == node->value) node = del(node);
		else if(data < node->value) node->left = delNode(node->left, data);
		else if(data > node->value) node->right = delNode(node->right, data);
		return node;
	}	
	
	// root node receive the result
	bst->root = delNode(bst->root, data);	
}

void pretravel(LinkNode *node)		// show element one by one,(root,left,right)
{
	if(node == NULL) return ;
	printf("%d  ", node->value);
	pretravel(node->left);
	pretravel(node->right);
}

void midtravel(LinkNode *node)		// show element one by one,(left,root,right)
{
	if(node == NULL) return ;
	midtravel(node->left);
	printf("%d  ", node->value);
	midtravel(node->right);
}

void posttravel(LinkNode *node)		// show element one by one,(left,right,root)
{
	if(node == NULL) return ;
	posttravel(node->left);
	posttravel(node->right);
	printf("%d  ", node->value);
}

int find(LinkNode *node, int data)	// if find data,return 1(true),or return 0(false)
{
	if(node ==  NULL) return 0;
	if(data == node->value) return 1;
	if(data < node->value) find(node->left, data);
	else if(data > node->value) find(node->right, data);	
}

编译链接： gcc -o bst bst.c

执行可执行文件： ./bst

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/760038.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

leetCode.98. 验证二叉搜索树

leetCode.98. 验证二叉搜索树

leetCode.98. 验证二叉搜索树 题目描述 代码 /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(n…
阅读更多...
鱼叉式钓鱼

鱼叉式钓鱼

鱼叉式网络钓鱼&#xff1a; 鱼叉式网络钓鱼是一种网络钓鱼形式&#xff0c;它针对特定个人或组织发送定制消息&#xff0c;旨在引发特定反应&#xff0c;例如泄露敏感信息或安装恶意软件。这些攻击高度个性化&#xff0c;使用从各种来源收集的信息&#xff0c;例如社交媒体资…
阅读更多...
sky18流水线设计

sky18流水线设计

1.最大时钟频率确定 时钟周期要大于等于组合逻辑的delay&#xff08;最大的那条delay&#xff09; Freq_max(Mhz) 1000/T_delay(ns); 数据吞吐率Throughput Freq_max *Toggle_rate;//Toggle_rate&#xff1a;如两个时钟&#xff0c;输入变一次&#xff0c;就是50%&#xff1b…
阅读更多...
【考研408计算机组成原理】微程序设计重要考点指令流水线考研真题＋考点分析

【考研408计算机组成原理】微程序设计重要考点指令流水线考研真题＋考点分析

苏泽 “弃工从研”的路上很孤独&#xff0c;于是我记下了些许笔记相伴&#xff0c;希望能够帮助到大家 目录 微指令的形成方式 微指令的地址形成方式 对应考题 题目&#xff1a;微指令的地址形成方式 - 断定方式 解题思路&#xff1a; 答题&#xff1a; 分析考点&…
阅读更多...
大模型系列课程学习-基于2080TI-22G魔改卡搭建双卡大模型训练平台（双系统）

大模型系列课程学习-基于2080TI-22G魔改卡搭建双卡大模型训练平台（双系统）

1.选择合适的硬件配置 再配置电脑之前&#xff0c;需要确认自己需要的显存大小、主板、内存条、电源、散热等核心配件。经过前期调研&#xff0c;选择的硬件配置如下&#xff1a; &#xff08;1&#xff09;主板&#xff1a;华南X99_F8D(DDR4主板)&#xff0c;因为需要支持双卡…
阅读更多...
1Panel运维利器：功能详解与实操指南

1Panel运维利器：功能详解与实操指南

官网地址:https://1panel.cn/ 1Panel简介 1Panel是杭州飞致云信息科技有限公司旗下产品&#xff0c;是一款现代化、开源的Linux服务器运维管理面板&#xff0c;于2023年3月推出。 名称&#xff1a;1Panel开源Linux面板 所属公司&#xff1a;杭州飞致云信息科技有限公司 编写语…
阅读更多...
基于HarmonyOS NEXT开发智能提醒助手

基于HarmonyOS NEXT开发智能提醒助手

目录 目录 目录 前言 关于HarmonyOS NEXT 智能提醒助手需求分析 智能提醒助手设计 1、系统架构 2、功能模块 智能提醒助手的应用场景 智能提醒助手的竞争力 具体技术实现 未来展望 结束语 前言 随着智能设备的普及和物联网技术的飞速发展&#xff0c;人们对于智能…
阅读更多...
忙忙碌碌的混沌之中差点扑了个空而错过年中这条线

忙忙碌碌的混沌之中差点扑了个空而错过年中这条线

文章目录 前言初见端倪混沌初始力不从心心力交瘁拾遗补缺总结 前言 突然意识到过完这个周末已经7月份了&#xff0c;他预示着我的2024年已经过半了&#xff0c;过年回家仿佛还是昨天的事情&#xff0c;怎么转眼间已经到了年中了。心里还是不愿承认这件事&#xff0c;翻开自己2…
阅读更多...
Nacos配置中心客户端源码分析（一）: 客户端如何初始化配置

Nacos配置中心客户端源码分析（一）: 客户端如何初始化配置

本文收录于专栏 Nacos 推荐阅读&#xff1a;Nacos 架构 & 原理 文章目录 前言一、NacosConfigBeanDefinitionRegistrar二、NacosPropertySourcePostProcessor三、AbstractNacosPropertySourceBuilder总结「AI生成」 前言 专栏前几篇文章主要讲了Nacos作为服务注册中心相关…
阅读更多...
github主页这样优化，让人眼前一亮

github主页这样优化，让人眼前一亮

我的主页&#xff08;一之十六&#xff09; 1. 创建与账户ID同名的仓库 注意&#xff1a;记得勾选Add a README file 2. markdown语法自定义README.md 3. 辅助工具 优秀profile&#xff1a;https://zzetao.github.io/awesome-github-profile/动态文字&#xff1a;https://r…
阅读更多...
SpringMVC（1）——入门程序+流程分析

SpringMVC（1）——入门程序+流程分析

MVC都是哪三层&#xff1f;在Spring里面分别对应什么&#xff1f;SpringMVC的架构是什么&#xff1f; 我们使用Spring开发JavaWeb项目&#xff0c;一般都是BS架构&#xff0c;也就是Browser&#xff08;浏览器&#xff09;-Server&#xff08;服务器&#xff09;架构 这种架构…
阅读更多...
谷歌开发者新号上架攻略：开发者实战经验分享

谷歌开发者新号上架攻略：开发者实战经验分享

前段时间&#xff0c;不少开发者朋友们在纷纷在吐槽新账号没法上架成功。以前谷歌对新号是真的很严格&#xff0c;但现在情况似乎有所好转。 今天&#xff0c;和大家聊聊如何在新号成功上架上“快人一步”&#xff0c;以及怎样增加账号权重提高上架成功率。 首先&#xff0c;我…
阅读更多...
成绩发布背后：老师的无奈与痛点

成绩发布背后：老师的无奈与痛点

在教育的广阔天地里&#xff0c;教师这一角色承载着无数的期望与责任。他们不仅是知识的传播者&#xff0c;更是学生心灵的引路人。而对于班主任老师来说&#xff0c;他们的角色更加多元&#xff0c;他们不仅是老师&#xff0c;还必须是“妈妈”。除了像其他老师一样备课、上课…
阅读更多...
Linux文件系统与设备文件

Linux文件系统与设备文件

一、Linux文件操作 Linux的文件系统API主要涉及创建、打开、读写、定位、关闭文件 创建 int creat(const char *filename, mode_t mode);mode: 代表新建文件的存取权限&#xff0c;需要和umask相与才能确定最终权限(mode&umask)。 umask代表文件在创建时需要去掉的存取…
阅读更多...
8.12 矢量图层面要素单一符号使用十(箭头线渲染边界)

8.12 矢量图层面要素单一符号使用十(箭头线渲染边界)

前言 本章介绍矢量图层线要素单一符号中箭头线渲染边界的使用说明&#xff1a;文章中的示例代码均来自开源项目qgis_cpp_api_apps 箭头线渲染边界&#xff08;Outline: Arrow&#xff09; Outline系列只画边界&#xff0c;不填充内容以protected_areas.shp为例&#xff0c;图…
阅读更多...
Spring 动态增强逻辑执行分析

Spring 动态增强逻辑执行分析

1、假如UserService中存在被增强的public 普通方法&#xff0c;那么spring ioc时就会创建对应的代理对象放置到容器中&#xff1b; 2、那么Controller中注入的userService就是代理对象&#xff1b; Service public class UserService {Transactionalpublic void f2(String us…
阅读更多...
【训练篇】MLU370-M8 完成 qwen1.5-7b-chat-lora训练及推理

【训练篇】MLU370-M8 完成 qwen1.5-7b-chat-lora训练及推理

文章目录 前言一、平台环境配置二、环境 or 模型准备1.模型下载2.环境准备2.1 modelscope2.2 transformers2.3 accelerate2.4 deepspeed2.5 peft2.6 环境代码修改 3训练代码准备4 代码修改 三&#xff0c;训练后推理验证四.推理效果展示1.微调前2.微调后 前言 本期我们采用魔塔…
阅读更多...
【雷达原理】雷达测角原理及实现方法

【雷达原理】雷达测角原理及实现方法

目录 一、雷达测角原理1.1 测角研究历史和现状1.2 测角方法总结1.3 3DFFT测角1.3.1 基本原理1.2.2 测角性能 二、MATLAB仿真案例参考文献 一、雷达测角原理 1.1 测角研究历史和现状 &#xff08;1&#xff09;早期采用窄波束对准目标&#xff0c;目标的角度对应于天线的角度读…
阅读更多...
【高性能服务器】服务器概述

【高性能服务器】服务器概述

&#x1f525;博客主页&#xff1a; 我要成为C领域大神&#x1f3a5;系列专栏&#xff1a;【C核心编程】 【计算机网络】 【Linux编程】 【操作系统】 ❤️感谢大家点赞&#x1f44d;收藏⭐评论✍️ 本博客致力于知识分享&#xff0c;与更多的人进行学习交流 ​ 服务器概述 服…
阅读更多...
[深入理解DDR] 总目录

[深入理解DDR] 总目录

依公知及经验整理&#xff0c;原创保护&#xff0c;禁止转载。 专栏 《深入理解DDR》 蓝色的是传送门&#xff0c;点击链接即可到达指定文章。 图。 DDR 分类 导论 [RAM] DRAM 导论&#xff1a;DDR4 | DDR5 | LPDDR5 | GDRR6 | HBM 应运而生 运存与内存&#xff1f;内存与存…
阅读更多...
最新文章

Copyright @ 2022~2023