一、 什么是线索二叉树？

线索二叉树是对普通二叉树的一种改进。其目标是利用空指针存储遍历信息（即前驱节点或后继节点），从而节约存储空间并提高树的遍历效率。
在线索二叉树中，每个节点包含以下内容：

• 数据域：存储数据。
• 左指针（lChild）：通常指向左子节点。如果左子节点为空，则存储前驱节点的线索。
• 右指针（rChild）：通常指向右子节点。如果右子节点为空，则存储后继节点的线索。
• 左标志（LTag）：标记左指针是指向子节点还是线索。
• 右标志（RTag）：标记右指针是指向子节点还是线索。

其结点形式为：

lchild

LTag

data

RTag

rchild

其中：

• LTag = 0：lchild域指示节点的左孩子
• LTag = 1：lchild域指示节点的前驱
• RTag = 0：rchild域指示节点的右孩子
• RTag = 1：rchild域指示节点的后继

---

二、 线索的定义

• 前驱节点：在某种遍历序列中，当前节点的前一个节点。
• 后继节点：在某种遍历序列中，当前节点的下一个节点。

举个简单的例子：如果一棵树的中序遍历序列是 4 → 2 → 5 → 1 → 3，那么：

• 节点 4 的前驱是 null，后继是 2。
• 节点 2 的前驱是 4，后继是 5。
• 节点 5 的前驱是 2，后继是 1。

---

三、 线索二叉树的分类

根据线索化的方式（遍历顺序），线索二叉树可以分为以下几类：

• 前序线索二叉树：
  • 节点的线索表示前序遍历中的前驱和后继节点。

• 中序线索二叉树：
  • 节点的线索表示中序遍历中的前驱和后继节点（使用最广泛）。

• 后序线索二叉树：
  • 节点的线索表示后序遍历中的前驱和后继节点。

其中最常见的是 中序线索二叉树。

---

四、 线索二叉树的节点结构

对于每个节点，线索二叉树需要额外的两个标志位来区分普通指针和线索指针。节点的结构如下：

struct ThreadNode {
    int data;           // 数据域
    ThreadNode* lChild; // 左指针
    ThreadNode* rChild; // 右指针
    int LTag;           // 左标志：0表示指向左子节点，1表示存储前驱线索
    int RTag;           // 右标志：0表示指向右子节点，1表示存储后继线索
};

在构造线索二叉树时，LTag 和 RTag 的值非常重要，它们决定了如何解释节点中的指针：

• 如果 LTag = 0，lChild 指向左子节点
• 如果 LTag = 1，lChild 指向前驱线索
• 如果 RTag = 0，rChild 指向右子节点
• 如果 RTag = 1，rChild 指向后继线索

---

五、 构造线索二叉树的步骤

以 中序线索化 为例，详细步骤如下：

1. 基本思路

1. 使用递归或非递归方法，对普通二叉树进行中序遍历。
2. 在遍历的过程中，根据遍历顺序，将空指针替换为前驱或后继的线索，并更新 LTag 和 RTag。

2. 具体步骤

假设我们有一个指针 pre，用来保存当前节点的前驱。实现过程如下：

// 中序线索化函数
void InThreading(ThreadNode* p, ThreadNode*& pre) {
    if (p) {
        // 1. 线索化左子树
        InThreading(p->lChild, pre);

        // 2. 处理当前节点
        if (!p->lChild) {       // 如果左指针为空
            p->lChild = pre;    // 左指针指向前驱
            p->LTag = 1;        // 标记为线索
        }
        if (pre && !pre->rChild) { // 如果前驱的右指针为空
            pre->rChild = p;       // 前驱的右指针指向当前节点
            pre->RTag = 1;         // 标记为线索
        }
        pre = p;                 // 更新前驱为当前节点

        // 3. 线索化右子树
        InThreading(p->rChild, pre);
    }
}

调用时传入根节点和一个初始为空的前驱指针 pre。

3. 完整线索化流程

1. 初始化一个虚拟的 pre 节点，用于跟踪前驱。
2. 对树进行中序遍历，逐步建立前驱和后继的线索。
3. 处理根节点和子节点的空指针，将它们改为线索。

---

六、 线索二叉树的遍历

1. 中序遍历

遍历中序线索二叉树时，不需要递归或栈，可以直接通过线索找到后继节点：

1. 找到中序遍历的第一个节点（即最左下节点）。
2. 依次访问当前节点的后继节点（根据线索指针）。
3. 如果当前节点的 RTag = 0（右指针不是线索），则移动到右子树继续。

实现代码如下：

void InOrderTraversal(ThreadNode* root) {
    ThreadNode* p = root;
    while (p) {
        // 找到中序遍历的起始节点
        while (p->LTag == 0) {
            p = p->lChild;
        }
        // 访问当前节点
        cout << p->data << " ";

        // 按后继线索访问后继节点
        while (p->RTag == 1 && p->rChild) {
            p = p->rChild;
            cout << p->data << " ";
        }
        // 移动到右子树
        p = p->rChild;
    }
}

2. 前序和后序遍历

类似的，我们可以通过前序或后序线索化的规则，实现前序线索二叉树和后序线索二叉树的遍历，在此不将演示。

---

七、 示例

以如下普通二叉树为例：

        1
       / \
      2   3
     / \
    4   5

中序遍历序列：

4 → 2 → 5 → 1 → 3

中序线索化后结构：

• 节点 4 的左线索为空，右线索指向 2。
• 节点 2 的左子节点是 4，右线索指向 5。
• 节点 5 的左线索指向 2，右线索指向 1。
• 节点 1 的左子节点是 2，右线索指向 3。
• 节点 3 的左右线索为空。