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

线索二叉树

news 来源：原创 2025/8/12 16:05:39

一概念

线索二叉树（Threaded Binary Tree）是一种对二叉树的优化结构，主要解决传统二叉树遍历时需要借助栈或递归（额外空间开销）的问题。通过利用节点中的空指针（nullptr）存储遍历过程中的前驱或后继节点信息（称为 “线索”），可以实现无需额外空间的二叉树遍历。

传统二叉树中，每个节点有两个指针（左孩子lchild、右孩子rchild）。对于一棵有n个节点的二叉树，共有2n个指针域，但其中只有n-1个指针被有效使用（连接子节点），剩余n+1个指针为空（nullptr）。
线索二叉树的核心思想是：将这些空指针利用起来，存储节点在某种遍历顺序（如中序、前序、后序）中的前驱或后继节点的地址，这些被重新利用的指针称为 “线索”。

为了区分一个指针是指向子节点还是线索，每个节点需要增加两个标志位：

ltag：左标志位
- ltag = 0：lchild指向左子节点
- ltag = 1：lchild是前驱线索（指向当前节点在遍历顺序中的前驱）
rtag：右标志位
- rtag = 0：rchild指向右子节点
- rtag = 1：rchild是后继线索（指向当前节点在遍历顺序中的后继）

二代码

1.线索二叉树结点

//线索二叉树结点
struct TreeNode {int data;TreeNode* left;TreeNode* right;bool ltag; //左线索，若为true,则left表示前驱结点，否则为左孩子结点bool rtag; //右线索，若为true,则right表示前驱结点，否则为右孩子结点TreeNode(int d) : data(d), left(nullptr), right(nullptr), ltag(false), rtag(false) {}
};

新增左右线索标志。若左线索为true，则left表示前驱结点，否则为左孩子结点。若右线索为true，则right表示后继结点，否则为右孩子结点。

2.构建线索二叉树

//构建线索二叉树(通过前序遍历序列构建)
TreeNode* CreateTree(vector<int>& preorder, int& index, int nullnode) {//若索引超出数组范围或数组索引处为空值nullnode,则令index++并返回空if (index >= preorder.size() || preorder[index] == nullnode) {index++;return nullptr;}TreeNode* node = new TreeNode(preorder[index++]); //为新结点分配内存node->left = CreateTree(preorder, index, nullnode); //递归构建左子树node->right = CreateTree(preorder, index, nullnode); //递归构建右子树return node; //返回当前结点
}

通过前序遍历序列来构建线索二叉树，若传入的索引超出数组范围或数组索引处为空值nullnode，则令Index++并返回空。为新结点分配内存，然后递归构建左右子树。

3.中序遍历线索化

//中序遍历线索化
TreeNode* pre = nullptr; //定义前驱结点void inorderThreading(TreeNode* node) {if (node == nullptr) return; //当传入结点为空时直接返回inorderThreading(node->left); //递归左子树，找到最左边孩子结点//传入结点的左子结点为空时，令其左指针指向前驱结点preif (node->left == nullptr) { node->left = pre;node->ltag = true;}//当前驱结点不为空且其右子结点为空时，令前驱结点的右指针指向当前结点if (pre && pre->right == nullptr) { pre->right = node;pre->rtag = true;}pre = node; //令前驱结点指向当前结点inorderThreading(node->right); //递归右子树
}

中序遍历线索化是最常用的线索化方式。首先在函数外定义一个全局结点变量pre表示前驱结点。

在函数体中，当传入的结点为空时直接返回。先递归左子树找到最左边孩子结点，当传入结点的左子结点为空时，令其左指针指向前驱结点pre，当前驱结点不为空且右子结点为空时，令前驱结点的右指针指向当前结点。最后令前驱结点指向当前结点并递归右子树。

4.中序遍历线索二叉树

//中序遍历线索二叉树
void inorderTraversal(TreeNode* root) {TreeNode* p = root;//找到中序遍历第一个节点（最左叶子）while (!p->ltag) { // 左线索为false表示有左子树，继续往左找p = p->left;}//循环遍历所有节点while (p != nullptr) {cout << p->data; //访问当前结点//找后继结点if (p->rtag) { //若rtag为true,则直接通过右线索找到后继结点p = p->right;}else { //若rtag为false,则找右子树的最左子结点p = p->right;while (!p->ltag) {p = p->left;}}}
}

首先找到中序遍历的第一个结点（最左叶子结点），左线索为false表示有左子树，继续往左找。

找到后循环遍历所有结点，每次循环先访问当前结点，然后找后继结点。若rtag为true，则直接通过右线索找到后继结点，若rtag为false，则找右子树的最左子结点。

5.释放内存

//释放线索二叉树内存
void FreeTree(TreeNode* root) {if (root == nullptr) return; // 空树直接返回// 保存当前节点的左右真实子节点（仅当标志为false时有效）TreeNode* leftChild = (root->ltag == false) ? root->left : nullptr;TreeNode* rightChild = (root->rtag == false) ? root->right : nullptr;// 递归释放左右子树（仅处理真实子节点）FreeTree(leftChild);FreeTree(rightChild);//释放当前结点delete root;root = nullptr; //指向空，避免野指针
}

若传入结点为空，直接返回。保存当前结点的左右真实结点，仅当标志为false时有效。接着递归释放左右子树，仅处理真实子结点。然后释放当前结点并让当前结点指向空以避免野指针。

三线索二叉树优化之处

线索二叉树相比传统二叉树的核心优化在于空间利用率和遍历效率，主要解决了传统二叉树在遍历和前驱 / 后继查找时的痛点。以下是具体优化点的对比分析：

1. 优化了空指针的浪费，节省存储空间

传统二叉树中，每个节点有两个指针（左 / 右孩子），但实际只有n-1个指针被有效使用（连接子节点），剩余n+1个指针为空（nullptr）。这些空指针未被利用，造成了空间浪费（以n个节点的二叉树为例，空指针占比约 50%）。

线索二叉树通过引入标志位（ltag/rtag），将空指针重新定义为 “线索”，存储节点在某种遍历顺序（如中序）中的前驱或后继节点地址。原本被浪费的n+1个空指针被充分利用，实现了空间的高效复用。

2. 优化了遍历的空间复杂度，无需额外栈 / 递归

传统二叉树的遍历（如中序、前序、后序）依赖递归或显式栈结构：

递归遍历：隐含使用调用栈，空间复杂度为O(h)（h为树的高度，最坏情况O(n)）；
迭代遍历：需手动维护栈，空间复杂度同样为O(h)。

线索二叉树通过线索直接记录前驱 / 后继关系，遍历过程中无需额外栈或递归，空间复杂度降至O(1)（仅需一个指针变量）。例如，中序线索二叉树的遍历只需从最左节点开始，沿后继线索依次访问即可。

3. 优化了前驱 / 后继的查找效率

在传统二叉树中，查找某个节点的前驱或后继（如中序前驱 / 后继）需要重新遍历整棵树或回溯父节点，时间复杂度为O(n)（最坏情况）。

线索二叉树中，若节点的线索标志位为 1（ltag=1或rtag=1），则其前驱 / 后继可直接通过线索指针获取（时间复杂度O(1)）；若标志位为 0（仍指向子节点），则仅需遍历子树即可找到前驱 / 后继（时间复杂度O(h)，优于传统二叉树的O(n)）。

总结：优化的本质是 “空间换时间” 的平衡

线索二叉树通过牺牲少量标志位（每个节点增加 2 个int标志），将原本浪费的空指针转化为遍历线索，最终实现：

空间优化：复用空指针，减少额外存储（如栈空间）；
时间优化：遍历和前驱 / 后继查找的效率显著提升（尤其在需要频繁遍历的场景中）。

这一设计使得线索二叉树在编译器语法分析、文件系统目录遍历等需要高效顺序访问的场景中被广泛应用。

线索二叉树

一概念线索二叉树（Threaded Binary Tree）是一种对二叉树的优化结构，主要解决传统二叉树遍历时需要借助栈或递归（额外空间开销）的问题。通过利用节点中的空指针（nullptr）存储遍历过程中的前驱…...

编程日记 2025/8/12 16:05:39

Git查看某个commit的改动

在Git中查看特定commit的改动有多种方法，下面是几种常用的命令行方式： 1. 使用 git show 命令这是最常用的方法，直接显示某个commit的详细信息和改动： git show <commit-hash> 例如： git show abc1234 也可…...

编程日记 2025/8/12 14:33:47

es 里的Filesystem Cache 理解

文章目录背景问题1，Filesystem Cache 里放的是啥问题2，哪些查询它们会受益于文件系统缓存问题3 查询分析背景对于es 优化来说常常看到会有一条结论给，给 JVM Heap 最多不超过物理内存的 50%，且不要超过 31GB（避免…...

编程日记 2025/8/9 9:47:34

2025年3月电子学会等级考试五级题——4、收费站在哪里

文章目录题目代码公式小结题目 4、收费站在哪里在一条高速公路上，如果已知 n 座收费站的位置 x1,x2,… ,xn（不妨假设 0x1 ≤ x2 ≤ … ≤ xn），就很容易算出一共有 n(n-1)/2 个距离的值。而比较困难的问题是，在收集…...

编程日记 2025/8/12 16:01:54

深入探索 JavaScript 中的模块对象

引言在现代 JavaScript 开发中，模块化编程是一项至关重要的技术。它允许开发者将代码拆分成多个独立的模块，每个模块专注于单一功能，从而提高代码的可维护性、可测试性和复用性。而模块对象则是模块化编程中的核心概念之一，它为…...

编程日记 2025/8/10 20:36:11

R1-Searcher：用强化学习解锁大语言模型检索新能力！

R1-Searcher：用强化学习解锁大语言模型检索新能力！ 大语言模型（LLMs）发展迅猛，却常因依赖内部知识而在复杂问题上“栽跟头”。今天解读的论文提出R1-Searcher框架，通过强化学习提升LLMs检索能力。它表现超…...

编程日记 2025/8/12 16:02:47

LangChain框架-PromptTemplate 详解

摘要本文聚焦于 LangChain 框架中PromptTemplate提示词模板模块的深度解析，主要参考langchain_core.prompts源码模块与官方文档。系统梳理 LangChain 对提示词模板的封装逻辑与设计思路，旨在帮助读者构建全面、深入的知识体系，为高效运用LangChain 框架的提示词模板开发应用…...

编程日记 2025/8/9 11:24:50

【Java ee 初阶】文件IO和操作（下）

书接上文文本操作的方法 String[] list() 返回 File 对象代表的目录下的所有文件名 File[] listFiles() 返回 File 对象代表的目录下的所有文件，以 File 对象表示此处是针对File对象打印得到的效果（调用了File的toString） boolean …...

编程日记 2025/8/8 22:15:23

Android7 Input（六）InputChannel

概述: 本文讲述Android Input输入框架中 InputChannel的功能。从前面的讲述，我们知道input系统服务最终将输入事件写入了InputChannel，而input属于system_server进程，App属于另外一个进程，当Input系统服务想要把事件传递给App进行…...

编程日记 2025/8/7 20:34:01

【Java ee初阶】初始网络

一、IP地址概念 IP地址主要用于标识网络主机、其他网络设备（如路由器）的网络地址。简单说，IP地址用于定位主机的网络地址。就像我们发送快递一样，需要知道对方的收货地址，快递员才能将包裹送到目的地。格式 IP…...

编程日记 2025/8/12 16:01:51

LabVIEW 2019 与 NI VISA 20.0 安装及报错处理

在使用 Windows 11 操作系统的电脑上，同时安装了 LabVIEW 2019 32 位和 64 位版本的软件。此前安装的 NI VISA 2024 Q1 版，该版本与 LabVIEW 2019 32 位和 64 位不兼容，之后重新安装了 NI VISA 20.0。从说明书来看，NI VISA 20.0 …...

编程日记 2025/8/7 20:33:58

http协议理解

文章目录 http协议理解基本概念HTTP版本演变版本编年史版本对比未来趋势 HTTP请求/响应结构请求报文响应报文HTTP方法分类对比方法选择原则必须遵守的约束常见状态码HTTP头部字段HTTPSHTTPS 核心功能说明HTTPS 如何工作？ HTTP特点补充知识点启用HTTP/2Nginx 中配置…...

编程日记 2025/8/12 16:03:35

typecho中的Widget设计文档

组成系统的最基本元素什么是Widget Widget是组成Typecho的最基本元素，除了已经抽象出来的类库外，其它几乎所有的功能都会通过Widget来完成。在实践中我们发现，在博客这种小型但很灵活的系统中实施一些大型框架的思想是不合适的&#xff0c…...

编程日记 2025/8/11 17:27:31

使用ESPHome烧录固件到ESP32-C3并接入HomeAssistant

文章目录一、安装ESPHome二、配置ESP32-C3控制灯1.主配置文件esp32c3-luat.yaml2.基础通用配置base.yaml3.密码文件secret.yaml4.围栏灯four_light.yaml5.彩灯rgb_light.yaml6.左右柱灯left_right_light.yaml 三、安装固件四、HomeAssistant配置ESPHome1.直接访问2.配置ESPHom…...

编程日记 2025/8/8 21:32:12

基于STM32、HAL库的CH340N USB转UART收发器驱动程序设计

一、简介： CH340N是南京沁恒电子生产的一款USB转串口芯片，具有以下特点：支持USB 2.0全速（12Mbps）内置时钟，无需外部晶振支持5V和3.3V电源电压提供常用的MODEM联络信号内置上电复位电路支持Windows/Linux/Mac OSX等多平台驱动体积小，SOP-8封装二、硬件接口： CH…...

编程日记 2025/8/12 16:04:44

Spring Boot Controller 如何处理HTTP请求体

Spring Boot (通过Spring MVC) 提供了强大的机制来处理不同 Content-Type 的HTTP请求体。这主要依赖于 HttpMessageConverter 接口的各种实现，它们能够自动将请求体内容转换成Java方法参数。一、核心机制：HttpMessageConverter Spring MVC会根据…...

编程日记 2025/8/11 22:20:50

【deepseek教学应用】001：deepseek如何撰写教案并自动实现word排版

本文讲述利用deepseek如何撰写教案并自动实现word高效完美排版。文章目录一、访问deepseek官网二、输入教案关键词三、格式转换四、word进一步排版一、访问deepseek官网官网：https://www.deepseek.com/ 进入主页后，点击【开始对话】，如…...

编程日记 2025/8/12 16:01:53

【Spring Boot 多模块项目】@MapperScan失效、MapperScannerConfigurer 报错终极解决方案

在使用 Spring Boot 构建多模块项目，集成 MyBatis-Plus 时，很多开发者会遇到类似如下启动报错： Error creating bean with name mapperScannerConfigurer ... Caused by: java.lang.IllegalArgumentException: Property basePackage is requ…...

编程日记 2025/8/12 16:00:36

vue 中如何使用region？

vue 中如何使用region？ 在 Vue 文件中，你可以使用 //#region 和 //#endregion 注释来创建可折叠的代码区块（类似于 C# 的 region）。这可以显著提高大型 Vue 组件的可读性。 1. 基本用法在 <script> 部分使用 <script&…...

编程日记 2025/8/11 6:44:06

Spring Boot 启动原理的核心机制

一、核心启动流程概览 Spring Boot 的启动流程可概括为 7 个关键阶段： 1. 加载启动类 (Main Class) 2. 初始化 SpringApplication 实例 3. 加载配置 & 准备环境 (Environment) 4. 创建 ApplicationContext（容器） 5. 刷新容器&#…...

编程日记 2025/8/11 3:54:16

【每天学习一点点】使用Python的pathlib模块分割文件路径

使用Python的pathlib模块分割文件路径 pathlib模块（Python 3.4）提供了面向对象的文件系统路径操作方式，比传统的os.path更加直观和易用。以下是使用pathlib分割文件路径的几种方法： 基本路径分割 from pathlib import Path# 创…...

编程日记 2025/8/9 13:17:13

Qt/C++面试【速通笔记八】—Qt的事件处理机制

在Qt中，事件处理机制是应用程序与用户或系统交互的核心。通过事件处理，Qt能够响应用户的输入、窗口的变化、定时器的触发等各种情况。 1. 事件循环（Event Loop） 在Qt应用程序中，事件循环是事件处理机制的基础。事件循…...

编程日记 2025/8/7 22:07:43

uniapp自定义步骤条(可二开进行调试)

前言有一个业务需求是需要一个步骤条，但是发现开源的都不太合适，所以就自己写了一个。开始 test.vue <template><view class"authenticateRecordDetails_container"><view class"authenticateSte…...

编程日记 2025/8/12 2:11:43

uniapp｜实现多终端聊天对话组件、表情选择、消息发送

基于UniApp框架，实现跨平台多终端适配的聊天对话组件开发、表情选择交互设计及消息发送，支持文本与表情混合渲染。目录聊天界面静态组件实现消息列表布局消息气泡双向布局辅助元素定位与样式静态数据模拟与扩展性设计表情选择器静态模块浮层实现符号网格排列多端样式适配方…...

编程日记 2025/8/7 22:07:39

1.3.1 Linux音频框架alsa详细介绍

ALSA作为对旧OSS系统的替代方案，始于1998年。当时OSS还闭源商业化，因此社区开始开发开源的ALSA。经过多年的发展，ALSA成为Linux内核中音频架构的标准。结构和架构 ALSA由以下几个主要部分组成： 内核模块： 这是ALSA的…...

编程日记 2025/8/12 10:58:52

R 语言机器学习：为遥感数据处理开启新视角

技术点目录基础理论、机器学习与数据准备建模与空间预测实践案例与项目了解更多 ——————————————————————————————————————————— 前言综述在当今科技快速发展的时代，遥感技术为生态学研究提供了海量的数据资源&#xf…...

编程日记 2025/8/11 18:17:31

深度 |提“智”向新，奔向未来——当前机器人产业观察

机器人踏着“猫步”在T台走秀、进入工厂协助造车，教育、医疗、城市管理等领域都有了机器人的帮助……今天，机器人已得到广泛应用，走进你我的生活。伴随着技术日新月异，机器人产业加快提“智”向新。特别是今年以来&#xf…...

编程日记 2025/8/12 6:40:11

Web开发-JavaEE应用SpringBoot栈ActuatorSwaggerHeapDump提取自动化

知识点： 1、安全开发-JavaEE-常见依赖-Actuator&Swagger 2、安全开发-JavaEE-安全问题-配置安全&接口测试一、演示案例-WEB开发-JavaEE-监控依赖-SpringBoot&Actuator&配置安全 SpringBoot Actuator模块提供了生产级别的功能，比如健康…...

编程日记 2025/8/11 3:57:39

AI Agent开发之门：微软官方课程全面解析

AI Agent开发之门：微软官方课程全面解析引言项目概览10 节核心课程内容详解1. AI 代理简介及应用场景2. 探索 AI Agentic 框架3. 理解 AI Agentic 设计模式4. 工具使用设计模式5. Agentic RAG（检索增强生成）6. 构建可信赖的 AI Agents7. 规划…...

编程日记 2025/8/11 3:04:16

Unity-Shader详解-其五

关于Unity的Shader部分的基础知识其实已经讲解得差不多了，今天我们来一些实例分享： 溶解效果如下： 代码如下： Shader "Chapter8/chapter8_1" {Properties{// 定义属性[NoScaleOffset]_Albedo("Albedo", 2…...

编程日记 2025/8/7 22:07:27

从零打造个人博客静态页面与TodoList应用：前端开发实战指南

前言在当今数字时代，拥有个人博客和高效的任务管理工具已成为开发者展示自我和提升生产力的标配。本文将带你从零开始，通过纯前端技术实现一个兼具个人博客静态页面和TodoList任务管理功能的综合应用。无论你是前端新手还是希望巩固基础的中级开发者&a…...

编程日记 2025/8/7 20:10:22

开发者如何优雅应对HTTPS抓包难题

开发者如何优雅应对HTTPS抓包难题：工具实战深度解析调试HTTPS接口这件事，真是程序员永远的痛。特别是在移动端、或者遇到客户端集成了第三方安全SDK的项目时，网络调试的门槛几乎成倍提升。你可能也遇到过：Charles不识别证书、…...

编程日记 2025/8/7 22:07:23

Ubuntu 安装远程桌面连接RDP方式

1. 安装 XFCE4 桌面环境如果你的 Ubuntu 系统默认使用 GNOME 或其它桌面环境，可以安装轻量级的 XFCE4： sudo apt update sudo apt install xfce4 xfce4-goodies 说明：xfce4-goodies 包含额外的插件和工具（如面板插件、终端等&a…...

编程日记 2025/8/7 22:07:21

Ubuntu 22.04 出现 ‘Temporary failure resolving‘ 解决方案

a、使用apt 安装 resolvconf sudo apt-get install resolvconf b、使用 cd /etc/resolvconf/resolv.conf.d/ 进入文件夹，使用 ls 查看目录，会显示 base head tail c、使用 sudo vim base 编辑base文件， 进入时为空，添加 name…...

编程日记 2025/8/12 9:36:10

ubuntu 22.04 换源

参考：清华大学开源软件镜像站 ubuntu | 镜像站使用帮助 | 清华大学开源软件镜像站 | Tsinghua Open Source Mirror...

编程日记 2025/8/7 22:07:17

Java并发编程几个问题的解答

目录 1、以前你编写的Java程序同时能做几件事情？有几个执行流程？main方法执行完，整个程序一定会退出吗？2、早期的电脑一般是单核CPU，但那时我们就可以在编写程序的同时听歌，你觉得其CPU可以同时执行两个程序…...

编程日记 2025/8/7 22:07:14

JavaScript中数组和对象不同遍历方法的顺序规则

在JavaScript中，不同遍历方法的顺序规则和适用场景存在显著差异。以下是主要方法的遍历顺序总结： 一、数组遍历方法 for循环 • 严格按数组索引顺序遍历（0 → length-1） • 支持break和continue中断循环 • 性能最优，…...

编程日记 2025/8/7 22:07:13

C++ STL入门：set 集合容器

C STL入门：set 集合容器一、核心特性与适用场景 set 是 C STL 提供的关联式容器，基于红黑树实现，具有两大核心特性： 特性表现形式底层原理元素唯一性重复值自动去重插入时进行二叉树键比对自动排序元素默认升序排列红黑树中序遍…...

编程日记 2025/8/7 22:07:11

[论文笔记] 超详细解读DeepSeek v3全论文技术报告

DeepSeek-V3是一个强大的专家混合（Mixture-of-Experts，MoE）语言模型，总共671B参数，每个token激活37B参数（可以理解为有多个专家，但每个token只会选择一部分专家进行推理，所以一个token的预测，只会用到37B参数），DeepSeek-V3 使用了多头潜在注意力（...

编程日记 2025/8/7 22:07:09

JS 问号（？）运算符避免中间报错

一、场景在前端开发过程中，有一些情况比如某些属性可能由于渲染数据的时机不同，一开始是null 或者undifine, 这样访问下面的属性的时候就会报错，我们可以给每个层级后面加个? 就可以避免这个错误。 let data {user: {profile: {name: &q…...

编程日记 2025/8/11 8:42:46

4：点云处理—去噪、剪切、调平

1.点云去噪 dev_clear_window ()dev_open_window(0, 0, 560, 560, black, WindowHandle)GenParamNames : [lut,intensity,light_position,disp_pose,alpha]GenParamValues : [color1,coord_z,0.0 0.0 -0.3 1.0,true,1]DispPose : [0,-0.0005,717.04,280,0,20,0]Instructions[0]…...

编程日记 2025/8/7 17:16:01

一 概念

二 代码