线性二叉树中序线索化方法

线性二叉树的中序遍历是指按照左子树、根节点、右子树的顺序遍历二叉树。线性二叉树中序线索化方法是在二叉树的中序遍历过程中，将每个节点的左右子节点指针指向其前驱和后继节点，以便快速定位前驱和后继节点，从而实现快速查找、插入和删除操作。

线性二叉树中序线索化的具体实现步骤如下：

1. 定义一个全局变量pre，用于记录当前节点的前驱节点。
2. 从根节点开始中序遍历二叉树。
3. 对于每个节点，先递归遍历其左子树。
4. 如果当前节点的左子节点为空，将其左子节点指针指向其前驱节点pre。
5. 如果当前节点的前驱节点pre的右子节点为空，将其右子节点指针指向当前节点。
6. 更新pre为当前节点，递归遍历其右子树。

具体实现代码如下：

// 定义二叉树节点结构体
struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int x) : val(x), left(NULL), right(NULL) {}
};

// 定义全局变量pre
Node* pre = NULL;

// 中序遍历二叉树并线索化
void inOrderThread(Node* root) {
    if (root == NULL) {
        return;
    }
    // 递归遍历左子树
    inOrderThread(root->left);
    // 处理当前节点
    if (root->left == NULL) {
        // 将左子节点指针指向前驱节点pre
        root->left = pre;
    }
    if (pre != NULL && pre->right == NULL) {
        // 将前驱节点pre的右子节点指针指向当前节点
        pre->right = root;
    }
    // 更新pre为当前节点
    pre = root;
    // 递归遍历右子树
    inOrderThread(root->right);
}

线性二叉树中序线索化的时间复杂度为O(n)，其中n为二叉树的节点数。因为需要遍历每个节点，对每个节点进行指针操作。空间复杂度为O(1)，因为只需要一个全局变量pre来记录前驱节点。