当前位置: 首页 > 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而教程只给了…...

Xcode 15.0 新 #Preview 预览让 SwiftUI 界面调试更加悠然自得

概览 从 Xcode 15 开始&#xff0c;苹果推出了新的 #Preview 宏预览机制&#xff0c;它无论从语法还是灵活性上都远远超过之前的预览方式。#Preview 不但可以实时预览 SwiftUI 视图&#xff0c;而且对 UIKit 的界面预览也是信手拈来。 想学习新 #Preview 预览的一些超实用调试…...

【VS2019】x64 Native Tools Command Prompt for Vs 2019使用conda命令进入环境

【VS2019】x64 Native Tools Command Prompt for Vs 2019使用conda命令进入环境 安装完VS2019后&#xff0c;打开终端x64 Native Tools Command Prompt for Vs 2019&#xff0c;直接运行conda会出现‘conda’ 不是内部或外部命令&#xff0c;也不是可运行的程序 原因分析&am…...

网络篇09 | 运输层 udp

网络篇09 | 运输层 udp 01 简介UDP 是面向报文的 02 报文协议 01 简介 UDP 只在 IP 的数据报服务之上增加了一些功能&#xff1a;复用和分用、差错检测 UDP 的主要特点&#xff1a;无连接。发送数据之前不需要建立连接。 使用尽最大努力交付。即不保证可靠交付。 面向报文。…...

vim相关指令

vim的各种模式及其转换关系图 vim 默认处于命令模式&#xff01;&#xff01;&#xff01; 模式之间转换的指令 除【命令模式】之外&#xff0c;其它模式要切换到【命令模式】&#xff0c;只需要无脑 ESC 即可&#xff01;&#xff01;&#xff01; [ 命令模式 ] 切换至 [ 插…...

STM32常见调试工具介绍

STM32的常见调试工具主要包括ST-LINK、USB转TTL、USB转485以及USB转CAN。这些工具在嵌入式系统开发、调试以及通信中发挥着重要的作用。 1.ST-LINK&#xff1a; ST-LINK是STMicroelectronics公司专为其STM32系列微控制器开发的调试和编程工具。既能仿真也能将编译好的程序下载…...

简历上写熟悉Linux下常用命令?直接寄

大家写简历技术栈时&#xff0c;都觉得越多越好&#xff0c;其中一条&#xff0c;熟悉Linux下常用命令&#xff1f;其实开发中Linux不是必备考点&#xff0c;除了运维&#xff0c;真正用的多的仅仅cd ls mkdir等&#xff0c;但当面试官问到上面命令时&#xff0c;是不是就傻眼了…...

【设计模式】4、prototype 原型模式

四、prototype 原型模式 https://refactoringguru.cn/design-patterns/prototype 如果希望 复制对象, 可使用 “prototype 模式” 如果 “待复制的对象” 是 interface 而不是 class, 或者如果 class 有 private 变量时. 无法知道 "待复制的对象"的细节, 则需要其…...

ES6 关于Class类的继承 extends(2024-04-10)

1、简介 类Class 可以通过extends关键字实现继承&#xff0c;让子类继承父类的属性和方法。extends 的写法比 ES5 的原型链继承&#xff0c;要清晰和方便很多。 class Foo {constructor(x, y) {this.x x;this.y y;console.log(父类构造函数)}toString() {return ( this.x …...

边缘计算【智能+安全检测】系列教程--使用OpenCV+GStreamer实现真正的硬解码,完全消除马赛克

通过现有博客的GST_URL = "rtspsrc location=rtsp://admin:abcd1234@192.168.1.64:554/h264/ch01/main/av_stream latency=150 ! rtph264depay ! avdec_h264 ! videorate ! videoconvert ! appsink sync=false" GStreamer的解码方式解码,大多情况应该存在上图马赛克…...

Anaconda在Ubuntu下的安装与简单使用

一、参考资料 ubuntu16.04下安装&配置anacondatensorflow新手教程 二、安装Anaconda 下载 Miniconda镜像1 or Miniconda镜像2 # 下载 wget Miniconda3-py39_4.10.3-Linux-x86_64.sh# 安装 bash Miniconda3-py39_4.10.3-Linux-x86_64.sh一路yes 安装过程中的选项 Do you …...

政府门户网站建设的重点/上海搜索引擎优化seo

我一直在尝试创建一个简单的脚本,它将从.txt文件中获取一个查询列表,附加主url变量,然后擦除内容并将其输出到文本文件.这是我到目前为止#!/bin/bashurl"example.com/?q"for i in $(cat query.txt); docontent$(curl -o $url $i)echo $url $iecho $content >>…...

微企点网站建设的教学视频/太原网络推广价格

作者&#xff1a;依本多情http://blog.csdn.net/qq_36520235/article/details/82417949一、真实面试题之&#xff1a;Hashmap的结构&#xff0c;1.7和1.8有哪些区别不同点&#xff1a;&#xff08;1&#xff09;JDK1.7用的是头插法&#xff0c;而JDK1.8及之后使用的都是尾插法&…...

网站的栏目规划/重庆森林电影

01 A空格site&#xff1a; 搜索范围所限定的网址&#xff0c;就能在一个网站中进行垂直搜索A。举例&#xff1a; 数据分析 site&#xff1a;zhihu.com 02 A空格filetype:文件格式 就能搜索对应类型的A文件例如&#xff1a;大数据 filetype&#xff1a;PDF &#xff0c;搜索出…...

如何在网站中做公示信息/下载百度网盘app最新版

接上篇。。。 4. 可空属性&默认值&忽略属性 默认情况下, 属性值可空, 如果强制要求某个属性非空, 可以使用如下方法&#xff1a; 遵循协议方法 (NSArray *)requiredProperties { return ["name"]; } 特点&#xff1a;如果再次赋值为nil, 则会抛出异常错误 也…...

b2c网站开发多少钱/二十条优化措施全文

部分内容参考&#xff1a;http://www.aspbc.com/tech/showtech.asp?id1256 在开发的过程中&#xff0c;经常使用window.onload和body onload两种&#xff0c;很少使用document.onreadystatechange&#xff0c;但这次写了一个js&#xff0c;使用window.onload和body.onload都实…...

网站wap版怎么做/高端网站设计公司

Thrift 是什么&#xff1f; Thrift源于大名鼎鼎的facebook之手&#xff0c;在2007年facebook提交Apache基金会将Thrift作为一个开源项目&#xff0c;对于当时的facebook来说创造thrift是为了解决facebook系统中各系统间大数据量的传 输通信以及系统之间语言环境不同需要跨平…...