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

【数据结构】线索二叉树之中序遍历线索化详解与实现

news 2026/7/23 14:13:06

在二叉树的遍历过程中，我们会发现大量的空指针域被浪费，而线索二叉树的核心思想就是利用这些空指针，将其指向节点的前驱或后继节点，从而实现二叉树的非递归遍历无需借助栈，提升遍历效率。本文将详细讲解中序遍历线索化的原理，并通过 C 语言实现完整的中序线索二叉树的构建与遍历。

一、线索二叉树的核心概念

1. 问题背景

普通二叉树中，一个具有n个节点的二叉链表，共有2n个指针域，其中只有n-1个指针域被用来指向孩子节点，剩余n+1个指针域均为NULL，造成了内存空间的浪费。

2. 线索化定义

利用二叉树的空指针域，将空的左指针域指向该节点在中序遍历中的前驱节点，将空的右指针域指向该节点在中序遍历中的后继节点，这种改造后的二叉树称为线索二叉树，这个改造过程称为线索化。

3. 标志位设计

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

  • ltag=0：左指针域lchild指向该节点的左孩子
  • ltag=1：左指针域lchild指向该节点的中序前驱节点
  • rtag=0：右指针域rchild指向该节点的右孩子
  • rtag=1：右指针域rchild指向该节点的中序后继节点

二、线索二叉树的节点结构设计

根据上述概念，我们设计线索二叉树的节点结构，包含数据域、左右指针域、左右标志位，C 语言定义如下：

typedef char ElemType; // 定义线索二叉树的节点结构 typedef struct ThreadNode { ElemType data; // 节点存储的数据 struct ThreadNode *lchild; // 左指针：指向左孩子或前驱 struct ThreadNode *rchild; // 右指针：指向右孩子或后继 int ltag; // 左标志：0 表示左孩子，1 表示前驱线索 int rtag; // 右标志：0 表示右孩子，1 表示后继线索 } ThreadNode; typedef ThreadNode* ThreadTree;

三、整体实现思路

本次实现将完成普通二叉树构建→中序遍历线索化→线索二叉树的中序非递归遍历全流程，核心步骤如下：

  1. 根据前序遍历序列（含#表示空节点）构建普通二叉树，同时初始化标志位；
  2. 定义全局前驱指针prev，记录中序遍历中当前节点的前一个节点，通过递归实现中序线索化；
  3. 创建头结点优化线索二叉树的遍历，让头结点与二叉树首尾节点形成闭环；
  4. 利用线索的特性，实现无需栈的中序非递归遍历。

四、代码分步实现与解析

1. 全局变量与测试序列定义

定义前序遍历的测试序列（用于构建二叉树）、扫描索引和全局前驱指针，前驱指针prev用于线索化过程中记录上一个访问的节点。

char str[] = "ABDH##I##EJ###CF##G##"; // 前序遍历序列，# 表示空节点 int idx = 0; // 扫描序列的当前索引 ThreadTree prev; // 全局变量：记录中序遍历的前一个节点

2. 普通二叉树的构建

根据前序遍历序列递归构建二叉树，同时为每个节点初始化ltag和rtag：若存在左 / 右孩子，标志位为 0；若为空，标志位为 1（后续线索化时填充线索）。

// 创建普通二叉树（根据前序字符串str） void createTree(ThreadTree *T) { ElemType ch = str[idx++]; if (ch == '#') { *T = NULL; // 空节点，直接置NULL } else { *T = (ThreadTree)malloc(sizeof(ThreadNode)); (*T)->data = ch; createTree(&(*T)->lchild); // 递归构建左子树 (*T)->ltag = (*T)->lchild ? 0 : 1; // 有左孩子→0，无→1 createTree(&(*T)->rchild); // 递归构建右子树 (*T)->rtag = (*T)->rchild ? 0 : 1; // 有右孩子→0，无→1 } }

3. 中序遍历线索化核心函数

线索化的过程基于中序遍历的递归顺序（左→根→右），在遍历过程中填充空指针的前驱 / 后继线索，核心逻辑：

  1. 递归线索化左子树；
  2. 若当前节点左指针为空（ltag=1），将左指针指向前驱节点prev；
  3. 若前驱节点prev的右指针为空（prev->rtag=1），将前驱的右指针指向当前节点（即后继）；
  4. 更新prev为当前节点，递归线索化右子树。
// 中序线索化函数：建立前驱/后继关系 void threading(ThreadTree T) { if (T != NULL) { threading(T->lchild); // 递归线索化左子树 // 如果当前节点左指针是空，建立前驱线索 if (T->ltag == 1) T->lchild = prev; // 如果前一个节点的右指针是空，建立其后继线索指向当前节点 if (prev && prev->rtag == 1) prev->rchild = T; prev = T; // 更新prev为当前节点，供后续节点作为前驱 threading(T->rchild); // 递归线索化右子树 } }

4. 构建带头部的线索二叉树

为了让线索二叉树的遍历更简洁，我们创建一个头结点，让头结点与二叉树的首尾节点形成闭环，规则如下：

  1. 头结点的ltag=0，lchild指向二叉树的根节点；
  2. 头结点的rtag=1，rchild指向中序遍历的最后一个节点；
  3. 中序遍历的第一个节点的左指针指向头结点；
  4. 中序遍历的最后一个节点的右指针指向头结点。

该函数完成头结点创建、前驱指针初始化、调用线索化函数、补全首尾节点的线索闭环。

// 创建头结点，调用线索化过程，建立完整的线索二叉树 void inOrderThreading(ThreadTree *T, ThreadTree *head) { *head = (ThreadTree)malloc(sizeof(ThreadNode)); // 分配头结点空间 (*head)->ltag = 0; (*head)->rtag = 1; (*head)->rchild = *head; // 初始时右指针回指自己 if (*T == NULL) { (*head)->lchild = *head; // 空树：左指针也回指自己 } else { (*head)->lchild = *T; // 头结点左指针指向根节点 prev = *head; // 初始化前驱指针为头结点 threading(*T); // 对整棵树进行中序线索化 // 补全最后一个节点的后继线索：指向头结点 prev->rchild = *head; prev->rtag = 1; (*head)->rchild = prev; // 头结点右指针指向最后一个节点 } }

5. 线索二叉树的中序非递归遍历

利用线索的特性，遍历过程无需借助栈，核心思路：

  1. 从头结点的左孩子（即根节点）开始遍历；
  2. 沿着左孩子一直走到底（ltag=0时继续），找到中序遍历的第一个节点；
  3. 访问当前节点，若当前节点有后继线索（rtag=1），则顺着线索访问所有后继节点；
  4. 若当前节点有右孩子（rtag=0），则进入右子树，重复上述过程；
  5. 直到遍历回到头结点，结束遍历。
// 中序遍历线索化后的二叉树（非递归，无需栈） void inOrder(ThreadTree T) { ThreadTree curr = T->lchild; // 从头结点的左子树（根节点）开始 while (curr != T) { // 未回到头结点则继续 // 沿着左孩子走到底，找到中序第一个节点 while (curr->ltag == 0) curr = curr->lchild; // 访问当前节点 printf("%c ", curr->data); // 顺着后继线索，依次访问所有后继节点 while (curr->rtag == 1 && curr->rchild != T) { curr = curr->rchild; printf("%c ", curr->data); } // 进入右子树，继续遍历 curr = curr->rchild; } }

6. 主函数测试

主函数按构建普通二叉树→线索化处理→中序遍历的顺序调用函数，完成整个流程的测试。

int main() { ThreadTree T, head; createTree(&T); // 创建原始二叉树 inOrderThreading(&T, &head); // 执行中序线索化处理 printf("中序遍历结果："); inOrder(head); // 遍历线索二叉树 return 0; }

7.完整可运行代码

#include <stdio.h> #include <stdlib.h> // ====================== 1. 线索二叉树节点结构定义 ====================== // 节点数据类型，这里用字符型 typedef char ElemType; // 线索二叉树节点结构体 typedef struct ThreadNode { ElemType data; // 数据域：存储节点值 struct ThreadNode *lchild; // 左指针：指向左孩子 或 前驱节点 struct ThreadNode *rchild; // 右指针：指向右孩子 或 后继节点 int ltag; // 左标志：0=指向左孩子，1=指向前驱 int rtag; // 右标志：0=指向右孩子，1=指向后继 } ThreadNode; // 重命名指针类型，方便使用 typedef ThreadNode *ThreadTree; // ====================== 2. 全局变量定义 ====================== // 二叉树前序遍历序列（#代表空节点，用于自动构建二叉树） char str[] = "ABDH##I##EJ###CF##G##"; int idx = 0; // 遍历序列的索引指针 ThreadTree prev; // 全局前驱指针：记录上一个访问的节点（线索化核心） // ====================== 3. 创建普通二叉树（前序遍历） ====================== // 功能：根据前序序列生成一棵普通二叉树，并初始化标志位 // 参数：T 二级指针，用于修改根节点指针 void createTree(ThreadTree *T) { // 读取当前字符 char ch = str[idx++]; // 如果是 #，代表空节点 if (ch == '#') { *T = NULL; } else { // 分配节点空间 *T = (ThreadTree)malloc(sizeof(ThreadNode)); // 赋值数据域 (*T)->data = ch; // 递归创建左子树 createTree(&(*T)->lchild); // 初始化左标志：有左孩子=0，无左孩子=1 (*T)->ltag = (*T)->lchild ? 0 : 1; // 递归创建右子树 createTree(&(*T)->rchild); // 初始化右标志：有右孩子=0，无右孩子=1 (*T)->rtag = (*T)->rchild ? 0 : 1; } } // ====================== 4. 中序遍历线索化核心函数 ====================== // 功能：递归对二叉树进行中序线索化，建立前驱、后继关系 void threading(ThreadTree T) { // 递归终止条件：节点为空 if (T == NULL) { return; } // ========== 第一步：递归线索化 左子树 ========== threading(T->lchild); // ========== 第二步：处理当前节点，建立线索 ========== // 1. 如果当前节点没有左孩子，左指针指向前驱节点 prev if (T->ltag == 1) { T->lchild = prev; } // 2. 如果上一个节点没有右孩子，上一个节点的右指针指向当前节点（后继） if (prev != NULL && prev->rtag == 1) { prev->rchild = T; } // 3. 更新前驱节点为当前节点，为下一个节点做准备 prev = T; // ========== 第三步：递归线索化 右子树 ========== threading(T->rchild); } // ====================== 5. 创建带 头结点 的中序线索二叉树 ====================== // 功能：创建头结点，完成整棵树的线索化，并形成闭环（首尾相连） // 参数：T 原树根节点，head 输出的线索二叉树头结点 void inOrderThreading(ThreadTree *T, ThreadTree *head) { // 1. 创建头结点 *head = (ThreadTree)malloc(sizeof(ThreadNode)); (*head)->ltag = 0; // 头结点左标志=0 (*head)->rtag = 1; // 头结点右标志=1 (*head)->rchild = *head; // 初始右指针指向自己 // 2. 如果是空树，直接让头结点自环 if (*T == NULL) { (*head)->lchild = *head; } else { // 3. 头结点左指针指向原树的根节点 (*head)->lchild = *T; // 4. 初始化前驱节点为头结点 prev = *head; // 5. 对整棵树进行中序线索化 threading(*T); // 6. 最后一个节点的右指针指向头结点，形成闭环 prev->rchild = *head; prev->rtag = 1; // 7. 头结点右指针指向最后一个节点 (*head)->rchild = prev; } } // ====================== 6. 线索二叉树 中序遍历（非递归，无栈） ====================== // 功能：利用线索遍历，效率极高，空间复杂度 O(1) void inOrderTraverse(ThreadTree head) { ThreadTree curr; // curr 指向根节点（头结点的左孩子） curr = head->lchild; // 循环条件：没有回到头结点 while (curr != head) { // 1. 找到中序遍历的第一个节点（一直往左走，直到没有左孩子） while (curr->ltag == 0) { curr = curr->lchild; } // 2. 访问当前节点 printf("%c ", curr->data); // 3. 顺着后继线索一直访问 while (curr->rtag == 1 && curr->rchild != head) { curr = curr->rchild; printf("%c ", curr->data); } // 4. 进入右子树继续遍历 curr = curr->rchild; } } // ====================== 7. 主函数测试 ====================== int main() { ThreadTree T; // 原始二叉树根节点 ThreadTree head; // 线索二叉树头结点 // 1. 创建普通二叉树 createTree(&T); // 2. 对二叉树进行中序线索化 inOrderThreading(&T, &head); // 3. 输出遍历结果 printf("线索二叉树 中序遍历结果："); inOrderTraverse(head); printf("\n"); return 0; }

五、运行结果

对于测试序列ABDH##I##EJ###CF##G##构建的二叉树，中序遍历的结果为：

六、线索二叉树的优势与注意事项

1. 核心优势

  • 节省内存：利用空指针域存储前驱 / 后继线索，无需额外开辟空间；
  • 遍历高效：非递归遍历无需借助栈或队列，时间复杂度为O(n)，空间复杂度为O(1)（仅需少量遍历指针）；
  • 遍历方便：可直接通过线索快速找到任意节点的前驱和后继，无需重新遍历整棵树。

2. 注意事项

  • 线索化后不可随意修改二叉树：若增删二叉树的节点，会破坏已建立的前驱 / 后继线索，需要重新进行线索化；
  • 全局前驱指针的使用：本次实现使用全局变量prev简化递归过程，也可通过二级指针将prev作为参数传递，避免全局变量；
  • 头结点的作用：头结点让线索二叉树形成闭环，避免了遍历过程中判断首尾节点的复杂逻辑，大幅简化遍历代码。

七、总结

中序遍历线索化是线索二叉树中最常用的实现方式，其核心是基于中序遍历的递归顺序，在遍历过程中填充空指针的前驱和后继线索。通过本文的实现，我们可以看到：

  1. 线索二叉树通过标志位区分孩子指针和线索指针，解决了普通二叉树空指针域浪费的问题；
  2. 带头部的线索二叉树让遍历形成闭环，实现了无栈的高效非递归遍历；
  3. 整个线索化过程与中序遍历深度绑定，遍历顺序决定了线索的指向关系。

线索二叉树不仅适用于中序遍历，也可实现前序、后序的线索化，其核心思想一致，仅需调整线索化的递归顺序即可。掌握中序线索二叉树的实现，是理解二叉树遍历优化的重要基础。

http://www.jsqmd.com/news/583847/

相关文章：

  • 2026最权威的六大AI论文网站解析与推荐
  • Arduino多板型编译期引脚元数据库：variants_collector
  • 技术创业中的技术创新：从内核开发到商业价值
  • OpenClaw安全审计：Qwen3-32B私有镜像下的操作日志与回滚机制
  • 2026届学术党必备的六大AI辅助论文神器推荐
  • OpenClaw安全防护方案：Gemma-3-12b-it任务执行权限管控
  • 2026年云南全屋定制如何选？深度解析昆明木菲装饰的一站式整装之道 - 2026年企业推荐榜
  • OpenClaw模型微调：优化千问3.5-35B-A3B-FP8在特定任务的表现
  • G-Helper：华硕硬件全能调控工具 玩家与创作者指南
  • OpenClaw性能调优实战：Qwen3-32B在RTX4090D上的量化推理加速
  • 2026届最火的AI辅助论文助手解析与推荐
  • 低成本数据标注：OpenClaw+Phi-3-vision-128k-instruct半自动化标记工具
  • PatchTST模型（Patch Time series Transformer）时间序列预测...
  • 解放科研生产力：Elsevier投稿状态追踪的智能革命
  • uClock：嵌入式音乐设备的高精度BPM时钟库
  • 嵌入式BSP驱动开发：硬件抽象层的工程实践与设计规范
  • OpenClaw安全实验室：基于平台镜像快速搭建SecGPT-14B测试环境
  • 疫苗冷链物流监测系统设计与实现
  • 2025届学术党必备的十大AI写作平台实际效果
  • 重庆户外LED显示屏批发优选：为何专业客户信赖倪杰光电 - 2026年企业推荐榜
  • C语言整数字节拆解：联合体与移位操作详解
  • OpenClaw+Phi-3-mini-128k-instruct：中文长文本处理专项优化
  • C语言宏定义实战技巧与嵌入式开发应用
  • 无人机三维路径规划改进双向人工势场引导 RRT * 算法研究（Matlab代码实现）
  • OpenClaw资源监控：Qwen3.5-9B-AWQ-4bit长期运行时的内存管理技巧
  • ESP32/ESP8266轻量级二进制RPC库设计与实践
  • L293D电机驱动库：嵌入式直流电机控制实战指南
  • Arduino非阻塞软件定时器MillisTimer原理与实践
  • 基于蜣螂优化算法（DBO）优化Kmeans图像分割的Matlab代码 首先，利用DBO算法良好...
  • 2026年AI搜索优化服务商综合实力深度解析与选购指南 - 2026年企业推荐榜