当前位置: 首页 > news >正文

二叉树的链式存储

     二叉树是一种非常重要的数据结构,它能够高效地进行数据的插入、删除和查找操作。二叉树的每个节点最多有两个子节点,分别是左子节点和右子节点。二叉树可以采用多种不同的存储方式来实现,其中链式存储是最为直观和常用的一种方法。本文将深入探讨二叉树的链式存储技术,包括其定义、特点、实现以及相关操作。

一、二叉树的定义

     二叉树是一种特殊的树形结构,它的每个节点最多有两个子节点,分别称为左子节点和右子节点。二叉树有一个特殊的节点,称为根节点,它没有父节点。二叉树中的其他节点分为内部节点和叶子节点。内部节点是指至少有一个子节点的节点,而叶子节点是没有子节点的节点。

二、链式存储的特点

    链式存储是一种动态的数据存储方式,它使用指针来链接数据元素,形成链表。在二叉树的链式存储中,每个节点包含三个部分:数据域、左指针域和右指针域。数据域用于存储节点的值,左指针域和右指针域分别指向该节点的左子节点和右子节点。如果某个子节点不存在,相应的指针域为空(通常用`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 {// 找到了要删除的节点,进行删除操作// ...}
}

相关文章:

二叉树的链式存储

二叉树是一种非常重要的数据结构&#xff0c;它能够高效地进行数据的插入、删除和查找操作。二叉树的每个节点最多有两个子节点&#xff0c;分别是左子节点和右子节点。二叉树可以采用多种不同的存储方式来实现&#xff0c;其中链式存储是最为直观和常用的一种方法。本文将深入…...

[计算机效率] 鼠标手势工具:WGestures(解放键盘的超级效率工具)

3.22 鼠标手势工具&#xff1a;WGestures 通过设置各种鼠标手势和操作进行绑定。当用户通过鼠标绘制出特定的鼠标手势后就会触发已经设置好的操作。有点像浏览器中的鼠标手势&#xff0c;通过鼠标手势操纵浏览器做一些特定的动作。这是一款强大的鼠标手势工具&#xff0c;可以…...

Linux useradd命令教程:如何创建新的用户账户(附实例详解和注意事项)

Linux useradd命令介绍 useradd是Linux中用于添加用户账户的命令。它可以用于创建新的用户&#xff0c;并可以配合不同的选项来指定用户的主目录、UID、GID、组等信息。 Linux useradd命令适用的Linux版本 useradd命令在大多数Linux发行版中都可以使用&#xff0c;包括但不限…...

基于ollama搭建本地chatGPT

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

C++11 数据结构3 线性表的循环链式存储,实现,测试

上一节课&#xff0c;我们学了线性表 单向存储结构&#xff08;也就是单链表&#xff09;&#xff0c;这个是企业常用的技术&#xff0c;且是后面各种的基本&#xff0c;一定要牢牢掌握&#xff0c;如果没有掌握&#xff0c;下面的课程会云里雾里。 一 &#xff0c;循环链表 1…...

初识DOM

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

计算机视觉实验五——图像分割

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

移动Web学习06-移动端适配Less预处理器项目案例

项目目标&#xff1a;实现在不同宽度设备中等比缩放的网页效果 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&#xff08;Reasoning and Acting&#xff09;是一种新兴的技术框架&#xff0c;旨在通过逻辑推理和行动序列的构建&#xff0c;使大型语言模型&#xff08;LLM&#xff09;能够达成特定的目标。这一框架的核心思想是赋予机器模型类似人类的推理和行动能…...

24/04/15总结

多线程&#xff1a; 线程 线程是操作系统能够进行运算调度的最小单位。它被包含在进程之中&#xff0c;是进程中的实际运作单位 并发:在同一时刻&#xff0c;有多个指令在单个cpu上交替执行 并行:在同一时刻&#xff0c;有多个指令在多个cpu上同时执行 多线程的实现方式 1.继承…...

vue3、vue2中nextTick源码解析

nexttick是啥 nextTick是Vue提供的一个全局API&#xff0c;由于Vue的异步更新策略导致我们对数据的修改不会更新&#xff0c;如果此时想要获取更新后的Dom&#xff0c;就需要使用这个方法. vue的异步更新策略意思是如果数据变化,vue不会立刻更新dom,而是开启一个队列,把组件更…...

【氮化镓】GaN HEMTs结温和热阻测试方法

文章《Temperature rise detection in GaN high-electron-mobility transistors via gate-drain Schottky junction forward-conduction voltages》&#xff0c;由Xiujuan Huang, Chunsheng Guo, Qian Wen, Shiwei Feng, 和 Yamin Zhang撰写&#xff0c;发表在《Microelectroni…...

c++11 标准模板(STL)本地化库 - 平面类别(std::codecvt) - 在字符编码间转换,包括 UTF-8、UTF-16、UTF-32 (四)

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

【状态压缩 容斥原理 组合数学】100267. 单面值组合的第 K 小金额

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

.net框架和c#程序设计第三次测试

目录 一、测试要求 二、实现效果 三、实现代码 一、测试要求 二、实现效果 数据库中的内容&#xff1a; 使用数据库中的账号登录&#xff1a; 若不是数据库中的内容&#xff1a; 三、实现代码 login.aspx文件&#xff1a; <% Page Language"C#" AutoEventW…...

架构师系列-搜索引擎ElasticSearch(五)- 索引设计

索引创建后&#xff0c;要非常谨慎&#xff0c;创建不好后面会出现各种问题。 索引设计的重要性 索引创建后&#xff0c;索引分片只能通过_split和_shrink 接口对其进行成倍的增加和缩减。 ES的数据是通过_routing分配到各个分片上的&#xff0c;所以本质上不推荐区改变索引的…...

kafka ----修改log4j、jmx、jvm参数等

1、修改log4j 日志路径 在kafka-run-class.sh文件中修改如下配置&#xff0c;将 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 数据库交互&#xff08;ORM&#xff09;。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安装教程&#xff0c;git clone xxxgit https://blog.csdn.net/Castlehe/article/details/117356343 只有paddle 1.x 的教程&#xff1a;https://github.com/PaddlePaddle/PaddleOCR/blob/static/doc/doc_en/quickstart_en.md 报错是因为安装的是paddle 2.x而教程只给了…...

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?

编辑&#xff1a;陈萍萍的公主一点人工一点智能 未来机器人的大脑&#xff1a;如何用神经网络模拟器实现更智能的决策&#xff1f;RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战&#xff0c;在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...

装饰模式(Decorator Pattern)重构java邮件发奖系统实战

前言 现在我们有个如下的需求&#xff0c;设计一个邮件发奖的小系统&#xff0c; 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式&#xff08;Decorator Pattern&#xff09;允许向一个现有的对象添加新的功能&#xff0c;同时又不改变其…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

无法与IP建立连接,未能下载VSCode服务器

如题&#xff0c;在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈&#xff0c;发现是VSCode版本自动更新惹的祸&#xff01;&#xff01;&#xff01; 在VSCode的帮助->关于这里发现前几天VSCode自动更新了&#xff0c;我的版本号变成了1.100.3 才导致了远程连接出…...

JVM垃圾回收机制全解析

Java虚拟机&#xff08;JVM&#xff09;中的垃圾收集器&#xff08;Garbage Collector&#xff0c;简称GC&#xff09;是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象&#xff0c;从而释放内存空间&#xff0c;避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明

AI 领域的快速发展正在催生一个新时代&#xff0c;智能代理&#xff08;agents&#xff09;不再是孤立的个体&#xff0c;而是能够像一个数字团队一样协作。然而&#xff0c;当前 AI 生态系统的碎片化阻碍了这一愿景的实现&#xff0c;导致了“AI 巴别塔问题”——不同代理之间…...

uniapp中使用aixos 报错

问题&#xff1a; 在uniapp中使用aixos&#xff0c;运行后报如下错误&#xff1a; AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...

零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)

本期内容并不是很难&#xff0c;相信大家会学的很愉快&#xff0c;当然对于有后端基础的朋友来说&#xff0c;本期内容更加容易了解&#xff0c;当然没有基础的也别担心&#xff0c;本期内容会详细解释有关内容 本期用到的软件&#xff1a;yakit&#xff08;因为经过之前好多期…...

LeetCode - 199. 二叉树的右视图

题目 199. 二叉树的右视图 - 力扣&#xff08;LeetCode&#xff09; 思路 右视图是指从树的右侧看&#xff0c;对于每一层&#xff0c;只能看到该层最右边的节点。实现思路是&#xff1a; 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...

嵌入式学习笔记DAY33(网络编程——TCP)

一、网络架构 C/S &#xff08;client/server 客户端/服务器&#xff09;&#xff1a;由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序&#xff0c;负责提供用户界面和交互逻辑 &#xff0c;接收用户输入&#xff0c;向服务器发送请求&#xff0c;并展示服务…...