线索二叉树

1）输入与建树：用前序串 + `#` 表示空¶

输入是一串字符（无空格），用前序顺序描述一棵二叉树：

读到普通字符（如 a）：创建结点，然后递归构造它的左子树、右子树
读到 #：代表空指针，返回 nullptr

例如：abc##d##e#f##

a 是根
b 是 a 的左
c 是 b 的左，后面 ## 表示 c 没有左右孩子
d 是 b 的右，后面 ## 表示 d 没有左右孩子
e 是 a 的右
# 表示 e 的左为空
f 是 e 的右，后面 ## 表示 f 没有左右孩子

实现上用一个全局/引用下标 i，每次消耗一个字符：c = pre[i++]。

2）结点字段：`l/r + ltag/rtag`¶

线索二叉树结点需要 4 个核心信息：

Node* l, *r：左/右指针
bool ltag, rtag：
false：对应指针是孩子指针
true：对应指针是线索指针
- ltag==true：l 指向中序前驱
- rtag==true：r 指向中序后继

线索化前：ltag/rtag 全是 false（默认都是孩子含义，空孩子就是 nullptr）。线索化过程中：把“空孩子指针”改造为线索，并把 tag 改为 true。

3）为什么要加头结点 head¶

加头结点的好处是把遍历“封口”，让边界统一：

head->l 指向根（作为“入口”）
最后一个结点的后继指向 head
head->r 指向最后一个结点（方便从尾部回到 head，也方便一些算法）

这样遍历时可以写成 while(p != head)，不用对“第一个/最后一个结点”做额外特判。

空树时：

head->l = head
head->r = head

4）中序线索化的关键：维护“前驱 preNode”¶

中序线索化本质是在做一次中序遍历，但每访问到一个结点 cur 时，要把：

如果 cur 没有左孩子（cur->l == nullptr） => cur->ltag = true; cur->l = preNode; （把左空指针改成指向中序前驱的线索）
如果 preNode 没有右孩子（preNode->r == nullptr），且 preNode 不是 head => preNode->rtag = true; preNode->r = cur; （把前驱结点的右空指针改成指向当前结点的后继线索）

然后更新：

preNode = cur

注意两个细节：

preNode 初始设为 head，这样“第一个访问到的中序结点”的前驱就自然是 head。
给 preNode 设右线索时要排除 head，否则会错误修改 head（我们要在最后专门收尾 head 的指向）。

线索化结束后要“收尾”：

最后一个结点 preNode 的后继设为 head： preNode->rtag = true; preNode->r = head;
head->r 指向最后一个：head->r = preNode;

5）用线索进行中序遍历（非递归）的细节¶

遍历的核心思路：

从根出发，先找到中序序列的第一个结点：一路向左走到不能再走孩子为止

C++

p = head->l;
while (p != head && !p->ltag) p = p->l;

这里 !p->ltag 表示左指针是孩子，才能继续往左。

访问当前结点 p
找下一个中序结点（后继）：
如果 p->rtag == true：右指针是线索，直接 p = p->r
否则：右指针是右子树根，进入右子树后，再一路向左找到最左结点

C++

p = p->r;
while (p != head && !p->ltag) p = p->l;

直到 p == head 停止（表示走到了最后一个结点的后继 head）

6）你两组样例的结果校验¶

样例 1：`abc##d##e#f##`¶

中序序列：c b d a e f => 输出 cbdaef

样例 2：`abc######`¶

树为 a 的左是 b，b 的左是 c（一直向左）中序：c b a => 输出 cba

这与你截图预期一致。

7）实现上为何用 STL：`vector<unique_ptr<Node>> pool`¶

你说“尽可能用 STL”，所以我用：

vector<unique_ptr<Node>> pool 统一保存结点所有权，程序结束自动释放内存
结点之间用 Node* 串起来（因为线索/孩子会形成复杂互指，不能用 unique_ptr 直接当孩子指针）

这是一种很常见的“STL 管生命周期，裸指针做结构连接”写法，既安全又方便。

线索二叉树

1）输入与建树：用前序串 + # 表示空¶

2）结点字段：l/r + ltag/rtag¶