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

在二叉树的遍历过程中我们会发现大量的空指针域被浪费而线索二叉树的核心思想就是利用这些空指针将其指向节点的前驱或后继节点从而实现二叉树的非递归遍历无需借助栈提升遍历效率。本文将详细讲解中序遍历线索化的原理并通过 C 语言实现完整的中序线索二叉树的构建与遍历。一、线索二叉树的核心概念1. 问题背景普通二叉树中一个具有n个节点的二叉链表共有2n个指针域其中只有n-1个指针域被用来指向孩子节点剩余n1个指针域均为NULL造成了内存空间的浪费。2. 线索化定义利用二叉树的空指针域将空的左指针域指向该节点在中序遍历中的前驱节点将空的右指针域指向该节点在中序遍历中的后继节点这种改造后的二叉树称为线索二叉树这个改造过程称为线索化。3. 标志位设计为了区分指针域是指向孩子节点还是线索需要为每个节点增加两个标志位ltag和rtagltag0左指针域lchild指向该节点的左孩子ltag1左指针域lchild指向该节点的中序前驱节点rtag0右指针域rchild指向该节点的右孩子rtag1右指针域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;三、整体实现思路本次实现将完成普通二叉树构建→中序遍历线索化→线索二叉树的中序非递归遍历全流程核心步骤如下根据前序遍历序列含#表示空节点构建普通二叉树同时初始化标志位定义全局前驱指针prev记录中序遍历中当前节点的前一个节点通过递归实现中序线索化创建头结点优化线索二叉树的遍历让头结点与二叉树首尾节点形成闭环利用线索的特性实现无需栈的中序非递归遍历。四、代码分步实现与解析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. 中序遍历线索化核心函数线索化的过程基于中序遍历的递归顺序左→根→右在遍历过程中填充空指针的前驱 / 后继线索核心逻辑递归线索化左子树若当前节点左指针为空ltag1将左指针指向前驱节点prev若前驱节点prev的右指针为空prev-rtag1将前驱的右指针指向当前节点即后继更新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. 构建带头部的线索二叉树为了让线索二叉树的遍历更简洁我们创建一个头结点让头结点与二叉树的首尾节点形成闭环规则如下头结点的ltag0lchild指向二叉树的根节点头结点的rtag1rchild指向中序遍历的最后一个节点中序遍历的第一个节点的左指针指向头结点中序遍历的最后一个节点的右指针指向头结点。该函数完成头结点创建、前驱指针初始化、调用线索化函数、补全首尾节点的线索闭环。// 创建头结点调用线索化过程建立完整的线索二叉树 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. 线索二叉树的中序非递归遍历利用线索的特性遍历过程无需借助栈核心思路从头结点的左孩子即根节点开始遍历沿着左孩子一直走到底ltag0时继续找到中序遍历的第一个节点访问当前节点若当前节点有后继线索rtag1则顺着线索访问所有后继节点若当前节点有右孩子rtag0则进入右子树重复上述过程直到遍历回到头结点结束遍历。// 中序遍历线索化后的二叉树非递归无需栈 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作为参数传递避免全局变量头结点的作用头结点让线索二叉树形成闭环避免了遍历过程中判断首尾节点的复杂逻辑大幅简化遍历代码。七、总结中序遍历线索化是线索二叉树中最常用的实现方式其核心是基于中序遍历的递归顺序在遍历过程中填充空指针的前驱和后继线索。通过本文的实现我们可以看到线索二叉树通过标志位区分孩子指针和线索指针解决了普通二叉树空指针域浪费的问题带头部的线索二叉树让遍历形成闭环实现了无栈的高效非递归遍历整个线索化过程与中序遍历深度绑定遍历顺序决定了线索的指向关系。线索二叉树不仅适用于中序遍历也可实现前序、后序的线索化其核心思想一致仅需调整线索化的递归顺序即可。掌握中序线索二叉树的实现是理解二叉树遍历优化的重要基础。