[README] 更新项目概述、算法史故事、新手破冰指南、避坑锦囊等核心内容
学生：黄宝麓 (202521093007) 选题编号：A19 所属分队：红队 指导教师：朱宗晓
本项目源自《计算机程序设计艺术》（TAOCP）算法库的知识的系统化工程落地。
二叉树作为计算机科学最基础的数据结构之一，其系统化的遍历方法（前序、中序、后序）奠定了树处理的基础。1960年Perlis和Thornton发明了线索二叉树，利用空指针存储前驱/后继线索，使遍历无需递归或栈空间，对内存极度受限的嵌入式系统意义重大。
为化工厂设计一个设备故障诊断系统，将专家经验建模为二叉决策树（节点为症状判断，叶子为故障结论）。实现标准二叉树的三种递归/非递归遍历，并进一步将其线索化，实现 O(1) 空间的遍历，适配 PLC 等内存受限控制器。
理解专家知识的系统化沉淀对工业安全的重要性，培养将领域知识转化为可执行算法的工程能力。
我们为什么要在今天拥有 GB 级内存的时代，去学习 1960 年代发明的线索二叉树？
因为在真实的工业现场（如化工厂防爆区、核电站控制室），用于控制阀门和诊断故障的底层 PLC 设备，其内存可能依然只有几十 KB，且绝对不允许出现由于”栈溢出”导致的不可预测宕机。
递归很美，那是数学家的浪漫；但彻底消除由于动态内存和深度调用带来的不确定性，保证系统在最极端的恶劣条件下依然能稳定输出诊断结果，这是我们作为工业软件工程师必须坚守的安全底线。线索二叉树不是过时的技巧，而是对硬件资源的极致敬畏。
如果把工业故障排查比作医院看病：
简而言之：算法库提供的是”树的指针魔术”，而A19项目要求你解决”极端受限环境下的绝对安全问题”。
你的现状：只会机械地写 if (root == NULL) return; inorder(root->left); …
你要做的：赋予二叉树业务生命。
定义决策树节点：包含一个字符串 char message[64]。如果是非叶子节点，它是一个”问题”（如：”电机温度是否过高？”）；如果是叶子节点，它是一个”结论”（如：”故障：冷却风扇损坏”）。
手写几行代码，用硬编码（Hardcode）的方式把这棵树拼接起来。
用你最熟悉的递归，写一个前序或中序遍历，把所有的”排查规则”打印成一本诊断手册。
你的现状：觉得递归代码只有三行，优雅且完美。
你要做的：看见隐藏的代价。
当你调用 inorder(root->left) 时，操作系统会在内存中开辟一块”栈帧（Stack Frame）”来保存当前状态。如果你的决策树有 100 层深，你的 PLC 内存当场就会被撑爆，系统崩溃死机。
尝试写一个非递归的中序遍历。你会发现你需要自己 malloc 一个数组来模拟栈（Stack）。无论怎样，你都逃不掉 O(h)（树高）的额外内存开销。这就是工业控制领域的隐患。
你要做的：理解 Perlis 和 Thornton 在 1960 年的伟大洞察——“一棵有 n 个节点的二叉树，一定有 n+1 个空指针（NULL）”。为什么不把这些浪费的空指针利用起来？
改造节点结构体：加入两个布尔标志位 int ltag, rtag;（0代表指向真正的孩子，1代表这是一个”线索”）。
织网（Threading）：写一个普通的递归中序遍历（只在初始化时运行一次）。在遍历时，用一个全局指针 pre 记录上一个访问的节点。
你要做的：享受线索化带来的巨大红利。
现在，你需要写一个全新的 threaded_inorder_traverse 函数。
直接顺着树往下找最左边的节点。然后，如果 rtag == 1，说明右指针是线索，直接顺着线索 node = node->right 就能瞬间”穿越”到下一个节点。如果 rtag == 0，说明有真正的右子树，就走到右子树的最左边。
你实现了一个空间复杂度绝对为 O(1) 的全树遍历引擎。
在实现”线索二叉树”时，初学者极易踩中以下三个雷区（指针的无间道）：
在普通的树中，往下走遇到 NULL 就知道该停了。但在线索二叉树中，根本没有 NULL（或者极少）！
如果你在遍历时忘记检查 ltag 和 rtag，把”线索快捷方式”当成了”真正的孩子”继续往下遍历，你的程序会立刻陷入无尽的死循环。永远先查 tag，再动指针。
在进行线索化（织网）时，第一个被访问的节点（整棵树最左下角的节点），它的 pre 是 NULL。必须在代码中小心处理 if (pre != NULL)，否则会在绑定右线索时触发段错误（Segmentation Fault）。
不要只打印遍历结果。你需要编写一个监控函数：
. ├── README.md # 本文件（项目总览） ├── Makefile # GCC编译脚本 ├── .gitignore # Git忽略规则 ├── src/ # 源代码目录 │ ├── main.c # 主程序入口 │ ├── algorithm_a.c # 算法A实现 │ ├── algorithm_b.c # 算法B实现 │ ├── utils.c # 工具函数 │ └── include/ # 头文件目录 │ ├── algorithm_a.h │ ├── algorithm_b.h │ └── utils.h ├── docs/ # 文档目录 │ ├── 01-需求分析.md │ ├── 02-算法史故事.md │ ├── 03-功能框图.png │ ├── 04-详细设计.md │ └── 05-测试报告.md ├── report/ # 课程设计报告 │ └── 设计报告模板.md └── test/ # 测试代码 ├── unit_test.c # 单元测试 └── test_data/ # 测试数据集
make # 编译主程序 make test # 编译测试 make clean # 清理
./main ./unit_test
[A-模块] 具体修改内容 示例： [A-二叉树] 实现从症状-结论规则自动构建决策树 [A-遍历] 实现递归前序/中序/后序与非递归中序遍历 [A-线索化] 实现中序线索二叉树的构建与O(1)遍历 [A-内存对比] 实现标准遍历与线索遍历内存占用统计
源自《计算机程序设计艺术》的新故事 —— 这本书的作者栏，写着你的名字。
A19 工业设备故障决策树智能诊断系统 — 黄宝麓(202521093007) 课程设计仓库。组合算法：二叉树遍历 + 线索二叉树。TAOCP出处：卷1 §2.3.1 + §2.3.2。
版权所有：中国计算机学会技术支持：开源发展技术委员会 京ICP备13000930号-9 京公网安备 11010802032778号
A19 工业设备故障决策树智能诊断系统
学生：黄宝麓 (202521093007) 选题编号：A19 所属分队：红队 指导教师：朱宗晓
项目概述
本项目源自《计算机程序设计艺术》（TAOCP）算法库的知识的系统化工程落地。
算法史故事
二叉树作为计算机科学最基础的数据结构之一，其系统化的遍历方法（前序、中序、后序）奠定了树处理的基础。1960年Perlis和Thornton发明了线索二叉树，利用空指针存储前驱/后继线索，使遍历无需递归或栈空间，对内存极度受限的嵌入式系统意义重大。
课程任务
为化工厂设计一个设备故障诊断系统，将专家经验建模为二叉决策树（节点为症状判断，叶子为故障结论）。实现标准二叉树的三种递归/非递归遍历，并进一步将其线索化，实现 O(1) 空间的遍历，适配 PLC 等内存受限控制器。
核心要求
工程哲学：可控可观（Controllability-Observability）
工程伦理
理解专家知识的系统化沉淀对工业安全的重要性，培养将领域知识转化为可执行算法的工程能力。
我们为什么要在今天拥有 GB 级内存的时代，去学习 1960 年代发明的线索二叉树？
因为在真实的工业现场（如化工厂防爆区、核电站控制室），用于控制阀门和诊断故障的底层 PLC 设备，其内存可能依然只有几十 KB，且绝对不允许出现由于”栈溢出”导致的不可预测宕机。
递归很美，那是数学家的浪漫；但彻底消除由于动态内存和深度调用带来的不确定性，保证系统在最极端的恶劣条件下依然能稳定输出诊断结果，这是我们作为工业软件工程师必须坚守的安全底线。线索二叉树不是过时的技巧，而是对硬件资源的极致敬畏。
新手破冰指南：C语言视角的四步上手路径
如果把工业故障排查比作医院看病：
简而言之：算法库提供的是”树的指针魔术”，而A19项目要求你解决”极端受限环境下的绝对安全问题”。
第一步：复现老专家的思维（打破递归黑盒）
你的现状：只会机械地写 if (root == NULL) return; inorder(root->left); …
你要做的：赋予二叉树业务生命。
定义决策树节点：包含一个字符串 char message[64]。如果是非叶子节点，它是一个”问题”（如：”电机温度是否过高？”）；如果是叶子节点，它是一个”结论”（如：”故障：冷却风扇损坏”）。
手写几行代码，用硬编码（Hardcode）的方式把这棵树拼接起来。
用你最熟悉的递归，写一个前序或中序遍历，把所有的”排查规则”打印成一本诊断手册。
第二步：直面内存的深渊（理解栈的代价）
你的现状：觉得递归代码只有三行，优雅且完美。
你要做的：看见隐藏的代价。
当你调用 inorder(root->left) 时，操作系统会在内存中开辟一块”栈帧（Stack Frame）”来保存当前状态。如果你的决策树有 100 层深，你的 PLC 内存当场就会被撑爆，系统崩溃死机。
尝试写一个非递归的中序遍历。你会发现你需要自己 malloc 一个数组来模拟栈（Stack）。无论怎样，你都逃不掉 O(h)（树高）的额外内存开销。这就是工业控制领域的隐患。
第三步：变废为宝的空间魔法（实现线索化）
你要做的：理解 Perlis 和 Thornton 在 1960 年的伟大洞察——“一棵有 n 个节点的二叉树，一定有 n+1 个空指针（NULL）”。为什么不把这些浪费的空指针利用起来？
改造节点结构体：加入两个布尔标志位 int ltag, rtag;（0代表指向真正的孩子，1代表这是一个”线索”）。
织网（Threading）：写一个普通的递归中序遍历（只在初始化时运行一次）。在遍历时，用一个全局指针 pre 记录上一个访问的节点。
第四步：零内存消耗的永动机（闭环遍历）
你要做的：享受线索化带来的巨大红利。
现在，你需要写一个全新的 threaded_inorder_traverse 函数。
直接顺着树往下找最左边的节点。然后，如果 rtag == 1，说明右指针是线索，直接顺着线索 node = node->right 就能瞬间”穿越”到下一个节点。如果 rtag == 0，说明有真正的右子树，就走到右子树的最左边。
你实现了一个空间复杂度绝对为 O(1) 的全树遍历引擎。
给新手的避坑锦囊
在实现”线索二叉树”时，初学者极易踩中以下三个雷区（指针的无间道）：
1. “真假美猴王”的无限死循环
在普通的树中，往下走遇到 NULL 就知道该停了。但在线索二叉树中，根本没有 NULL（或者极少）！
如果你在遍历时忘记检查 ltag 和 rtag，把”线索快捷方式”当成了”真正的孩子”继续往下遍历，你的程序会立刻陷入无尽的死循环。永远先查 tag，再动指针。
2. 悬空的”前驱”指针（初始化陷阱）
在进行线索化（织网）时，第一个被访问的节点（整棵树最左下角的节点），它的 pre 是 NULL。必须在代码中小心处理 if (pre != NULL)，否则会在绑定右线索时触发段错误（Segmentation Fault）。
3. 如何证明你的优化有价值？（建立可观性）
不要只打印遍历结果。你需要编写一个监控函数：
目录结构
快速开始
编译
运行
里程碑
Git提交规范