C语言实现中序线索遍历

中序线索化是一种将二叉树转换成线索二叉树的过程，线索二叉树是一种利用空指针存储前驱和后继信息的二叉树结构。中序线索化的过程就是在遍历二叉树的同时，将每个节点的左右指针指向其前驱和后继节点，以便在遍历时方便地访问它们。

以下是 C 语言中实现中序线索化的代码：

#include <stdio.h>
#include <stdlib.h>

// 定义二叉树结点
typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
    int ltag, rtag;  // 左右线索标志
} TreeNode;

// 创建二叉树
TreeNode* createTree() {
    int val;
    scanf("%d", &val);
    if (val == -1) {
        return NULL;
    }
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->val = val;
    root->left = createTree();
    root->right = createTree();
    return root;
}

// 中序线索化
void inThread(TreeNode* root, TreeNode* pre) {
    if (root == NULL) {
        return;
    }
    inThread(root->left, pre);
    if (root->left == NULL) {
        root->left = pre;
        root->ltag = 1;
    }
    if (pre != NULL && pre->right == NULL) {
        pre->right = root;
        pre->rtag = 1;
    }
    pre = root;
    inThread(root->right, pre);
}

// 中序遍历线索二叉树
void inOrderThread(TreeNode* root) {
    TreeNode* p = root;
    while (p != NULL) {
        while (p->ltag == 0) {
            p = p->left;
        }
        printf("%d ", p->val);
        while (p->rtag == 1) {
            p = p->right;
            printf("%d ", p->val);
        }
        p = p->right;
    }
}

int main() {
    TreeNode* root = createTree();
    TreeNode* pre = NULL;
    inThread(root, pre);
    inOrderThread(root);
    return 0;
}

在中序线索化的过程中，我们定义了 `ltag` 和 `rtag` 两个标志，它们分别表示左右指针是否为线索。如果某个节点的左指针为 `NULL`，则将其指向其前驱节点，并将 `ltag` 设为 1；如果某个节点的右指针为 `NULL`，则将其指向其后继节点，并将 `rtag` 设为 1。

在遍历线索二叉树时，我们从根节点开始，沿着左指针一直走到最左侧的叶子节点，输出该节点的值，并沿着右指针回溯到它的后继节点，重复以上过程，直到遍历完整棵树。