二叉树的链式存储
二叉树是一种非常重要的数据结构,它能够高效地进行数据的插入、删除和查找操作。二叉树的每个节点最多有两个子节点,分别是左子节点和右子节点。二叉树可以采用多种不同的存储方式来实现,其中链式存储是最为直观和常用的一种方法。本文将深入探讨二叉树的链式存储技术,包括其定义、特点、实现以及相关操作。
一、二叉树的定义
二叉树是一种特殊的树形结构,它的每个节点最多有两个子节点,分别称为左子节点和右子节点。二叉树有一个特殊的节点,称为根节点,它没有父节点。二叉树中的其他节点分为内部节点和叶子节点。内部节点是指至少有一个子节点的节点,而叶子节点是没有子节点的节点。
二、链式存储的特点
链式存储是一种动态的数据存储方式,它使用指针来链接数据元素,形成链表。在二叉树的链式存储中,每个节点包含三个部分:数据域、左指针域和右指针域。数据域用于存储节点的值,左指针域和右指针域分别指向该节点的左子节点和右子节点。如果某个子节点不存在,相应的指针域为空(通常用`NULL`表示)。
链式存储的优点包括:
1. 动态性:链式存储允许动态地分配和释放内存空间,便于进行节点的插入和删除操作。
2. 灵活性:链式存储不受内存空间限制,可以灵活地扩展二叉树的大小。
3. 方便性:通过指针可以直接访问任何节点,便于进行各种操作。
三、 链式存储的结构定义
可以使用结构体来定义二叉树的节点:
typedef struct BiTNode {ElemType data; // 数据域,ElemType可以是任何类型struct BiTNode *lchild; // 左子节点指针struct BiTNode *rchild; // 右子节点指针
} BiTNode, *BiTree;
在这个定义中,BiTNode是一个结构体,包含了数据域data和两个指针域lchild和rchild。BiTree是一个指向`BiTNode`的指针类型,通常用来表示二叉树。
四、二叉树的链式存储操作
1.创建二叉树
创建二叉树通常是从根节点开始,逐步添加子节点。以下是一个简单的创建二叉树的函数:
BiTree createBiTree() {BiTree root = (BiTree)malloc(sizeof(BiTNode));if (!root) {return NULL;}// 初始化根节点的值和子节点指针root->data = /* 初始化值 */;root->lchild = NULL;root->rchild = NULL;// 递归地创建左子树和右子树// ...return root;
}
2.插入节点
插入节点的操作通常需要找到合适的位置来插入新节点。以下是一个简单的插入节点的函数:
void insertNode(BiTree root, ElemType value) {if (!root) {// 如果根节点不存在,直接创建一个新节点作为根节点root = (BiTree)malloc(sizeof(BiTNode));if (!root) {return;}root->data = value;root->lchild = NULL;root->rchild = NULL;return;}// 根据value的值,决定插入到左子树还是右子树if (value < root->data) {if (!root->lchild) {// 如果左子节点不存在,直接创建一个新节点作为左子节点root->lchild = (BiTree)malloc(sizeof(BiTNode));if (!root->lchild) {return;}root->lchild->data = value;root->lchild->lchild = NULL;root->lchild->rchild = NULL;} else {// 如果左子节点已存在,递归地插入到左子树insertNode(root->lchild, value);}} else {// 类似地,处理右子树的情况// ...}
}
3.搜索节点
搜索节点的操作是从根节点开始,根据节点的值来决定向左还是向右遍历。以下是一个简单的搜索节点的函数:
BiTree searchNode(BiTree root, ElemType value) {if (!root || root->data == value) {return root;}if (value < root->data) {return searchNode(root->lchild, value);} else {return searchNode(root->rchild, value);}
}
4.删除节点
删除节点的操作比较复杂,需要考虑多种情况,如被删除节点是否有子节点、是否有一个子节点或两个子节点等。以下是一个简单的删除节点的函数:
void deleteNode(BiTree root, ElemType value) {if (!root) {return;}if (value < root->data) {deleteNode(root->lchild, value);} else if (value > root->data) {deleteNode(root->rchild, value);} else {// 找到了要删除的节点,进行删除操作// ...}
}
相关文章:
二叉树的链式存储
二叉树是一种非常重要的数据结构,它能够高效地进行数据的插入、删除和查找操作。二叉树的每个节点最多有两个子节点,分别是左子节点和右子节点。二叉树可以采用多种不同的存储方式来实现,其中链式存储是最为直观和常用的一种方法。本文将深入…...

[计算机效率] 鼠标手势工具:WGestures(解放键盘的超级效率工具)
3.22 鼠标手势工具:WGestures 通过设置各种鼠标手势和操作进行绑定。当用户通过鼠标绘制出特定的鼠标手势后就会触发已经设置好的操作。有点像浏览器中的鼠标手势,通过鼠标手势操纵浏览器做一些特定的动作。这是一款强大的鼠标手势工具,可以…...
Linux useradd命令教程:如何创建新的用户账户(附实例详解和注意事项)
Linux useradd命令介绍 useradd是Linux中用于添加用户账户的命令。它可以用于创建新的用户,并可以配合不同的选项来指定用户的主目录、UID、GID、组等信息。 Linux useradd命令适用的Linux版本 useradd命令在大多数Linux发行版中都可以使用,包括但不限…...

基于ollama搭建本地chatGPT
ollama帮助我们可以快速在本地运行一个大模型,再整合一个可视化页面就能构建一个chatGPT,可视化页面我选择了chat-ollama(因为它还能支持知识库,可玩性更高),如果只是为了聊天更推荐chatbox 部署步骤 下载…...

C++11 数据结构3 线性表的循环链式存储,实现,测试
上一节课,我们学了线性表 单向存储结构(也就是单链表),这个是企业常用的技术,且是后面各种的基本,一定要牢牢掌握,如果没有掌握,下面的课程会云里雾里。 一 ,循环链表 1…...

初识DOM
目录 前言: 1.初识DOM: 1.1DOM树: 1.2节点(Node): 1.2.1元素节点: 1.2.2属性节点: 1.2.3文本节点: 1.3Document对象: 2.操作网页元素: 2.1找出元素: 2.1.1document.getElementById(id)࿱…...

计算机视觉实验五——图像分割
计算机视觉实验五——图像分割 一、实验目标二、实验内容1.了解图割操作,实现用户交互式分割,通过在一幅图像上为前景和背景提供一些标记或利用边界框选择一个包含前景的区域,实现分割①图片准备②代码③运行结果④代码说明 2.采用聚类法实现…...

移动Web学习06-移动端适配Less预处理器项目案例
项目目标:实现在不同宽度设备中等比缩放的网页效果 Less代码 import ./base; import ./normalize;// 变量: 存储37.5 rootSize: 37.5rem; *{margin: 0;padding: 0; } body {background-color: #F0F0F0; }// 主体内容 .main {// padding-bottom: (50 / 37.5rem);pa…...

LangChain-25 ReAct 让大模型自己思考和决策下一步 AutoGPT实现途径、AGI重要里程碑
背景介绍 大模型ReAct(Reasoning and Acting)是一种新兴的技术框架,旨在通过逻辑推理和行动序列的构建,使大型语言模型(LLM)能够达成特定的目标。这一框架的核心思想是赋予机器模型类似人类的推理和行动能…...
24/04/15总结
多线程: 线程 线程是操作系统能够进行运算调度的最小单位。它被包含在进程之中,是进程中的实际运作单位 并发:在同一时刻,有多个指令在单个cpu上交替执行 并行:在同一时刻,有多个指令在多个cpu上同时执行 多线程的实现方式 1.继承…...
vue3、vue2中nextTick源码解析
nexttick是啥 nextTick是Vue提供的一个全局API,由于Vue的异步更新策略导致我们对数据的修改不会更新,如果此时想要获取更新后的Dom,就需要使用这个方法. vue的异步更新策略意思是如果数据变化,vue不会立刻更新dom,而是开启一个队列,把组件更…...

【氮化镓】GaN HEMTs结温和热阻测试方法
文章《Temperature rise detection in GaN high-electron-mobility transistors via gate-drain Schottky junction forward-conduction voltages》,由Xiujuan Huang, Chunsheng Guo, Qian Wen, Shiwei Feng, 和 Yamin Zhang撰写,发表在《Microelectroni…...

c++11 标准模板(STL)本地化库 - 平面类别(std::codecvt) - 在字符编码间转换,包括 UTF-8、UTF-16、UTF-32 (四)
本地化库 本地环境设施包含字符分类和字符串校对、数值、货币及日期/时间格式化和分析,以及消息取得的国际化支持。本地环境设置控制流 I/O 、正则表达式库和 C 标准库的其他组件的行为。 平面类别 在字符编码间转换,包括 UTF-8、UTF-16、UTF-32 std::…...

【状态压缩 容斥原理 组合数学】100267. 单面值组合的第 K 小金额
本文涉及知识点 状态压缩 容斥原理 组合数学 二分查找算法合集 LeetCode100267. 单面值组合的第 K 小金额 给你一个整数数组 coins 表示不同面额的硬币,另给你一个整数 k 。 你有无限量的每种面额的硬币。但是,你 不能 组合使用不同面额的硬币。 返回…...

.net框架和c#程序设计第三次测试
目录 一、测试要求 二、实现效果 三、实现代码 一、测试要求 二、实现效果 数据库中的内容: 使用数据库中的账号登录: 若不是数据库中的内容: 三、实现代码 login.aspx文件: <% Page Language"C#" AutoEventW…...

架构师系列-搜索引擎ElasticSearch(五)- 索引设计
索引创建后,要非常谨慎,创建不好后面会出现各种问题。 索引设计的重要性 索引创建后,索引分片只能通过_split和_shrink 接口对其进行成倍的增加和缩减。 ES的数据是通过_routing分配到各个分片上的,所以本质上不推荐区改变索引的…...
kafka ----修改log4j、jmx、jvm参数等
1、修改log4j 日志路径 在kafka-run-class.sh文件中修改如下配置,将 LOG_DIR变量指定为自己想要存储的路径 # Log directory to use if [ "x$LOG_DIR" "x" ]; thenLOG_DIR"$base_dir/logs" fi2、修改jmx参数 在kafka-run-class.s…...

Python 全栈 Web 应用模板:成熟架构,急速开发 | 开源日报 No.223
tiangolo/full-stack-fastapi-template Stars: 15.6k License: MIT full-stack-fastapi-template 是一个现代化的全栈 Web 应用模板。 使用 FastAPI 构建 Python 后端 API。使用 SQLModel 进行 Python SQL 数据库交互(ORM)。Pydantic 用于数据验证和设…...

STM32之DHT11温湿度传感器
目录 一 DHT11温湿度传感器简介 1.1 传感器特点 1.2 传感器特性 1.3 传感器引脚说明 二 测量原理及方法 2.1 典型应用电路 2.2 单线制串行简介 2.2.1 串行接口 (单线双向) 2.2.2 数据示例 2.3 通信时序 三 单片机简介 3.1 STM32F103C8T6最小系统板 四 接线说明 …...
paddle ocr
paddle安装教程,git clone xxxgit https://blog.csdn.net/Castlehe/article/details/117356343 只有paddle 1.x 的教程:https://github.com/PaddlePaddle/PaddleOCR/blob/static/doc/doc_en/quickstart_en.md 报错是因为安装的是paddle 2.x而教程只给了…...

wordpress后台更新后 前端没变化的解决方法
使用siteground主机的wordpress网站,会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后,网站没有变化的情况。 不熟悉siteground主机的新手,遇到这个问题,就很抓狂,明明是哪都没操作错误&#x…...
uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖
在前面的练习中,每个页面需要使用ref,onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入,需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...
线程与协程
1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指:像函数调用/返回一样轻量地完成任务切换。 举例说明: 当你在程序中写一个函数调用: funcA() 然后 funcA 执行完后返回&…...
GitHub 趋势日报 (2025年06月08日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...

算法笔记2
1.字符串拼接最好用StringBuilder,不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...
MySQL账号权限管理指南:安全创建账户与精细授权技巧
在MySQL数据库管理中,合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号? 最小权限原则…...

2025季度云服务器排行榜
在全球云服务器市场,各厂商的排名和地位并非一成不变,而是由其独特的优势、战略布局和市场适应性共同决定的。以下是根据2025年市场趋势,对主要云服务器厂商在排行榜中占据重要位置的原因和优势进行深度分析: 一、全球“三巨头”…...
MySQL 8.0 事务全面讲解
以下是一个结合两次回答的 MySQL 8.0 事务全面讲解,涵盖了事务的核心概念、操作示例、失败回滚、隔离级别、事务性 DDL 和 XA 事务等内容,并修正了查看隔离级别的命令。 MySQL 8.0 事务全面讲解 一、事务的核心概念(ACID) 事务是…...
【Android】Android 开发 ADB 常用指令
查看当前连接的设备 adb devices 连接设备 adb connect 设备IP 断开已连接的设备 adb disconnect 设备IP 安装应用 adb install 安装包的路径 卸载应用 adb uninstall 应用包名 查看已安装的应用包名 adb shell pm list packages 查看已安装的第三方应用包名 adb shell pm list…...

打手机检测算法AI智能分析网关V4守护公共/工业/医疗等多场景安全应用
一、方案背景 在现代生产与生活场景中,如工厂高危作业区、医院手术室、公共场景等,人员违规打手机的行为潜藏着巨大风险。传统依靠人工巡查的监管方式,存在效率低、覆盖面不足、判断主观性强等问题,难以满足对人员打手机行为精…...