线索二叉树用c语言怎么写

线索二叉树是一种特殊的二叉树，在其中每个节点除了左右子树指针外还包含两个指针：一个前驱指针和一个后继指针。这些指针用于存储树中的前驱和后继节点。下面是一个简单的用 C 语言实现线索二叉树的例子：

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

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    int ltag;
    int rtag;
};
typedef struct TreeNode TreeNode;

// 构建线索二叉树
void createThreadTree(TreeNode *root, TreeNode **pre) {
    if (root == NULL) return;
    // 遍历左子树
    createThreadTree(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;
    // 遍历右子树
    createThreadTree(root->right, pre);
}

// 中序遍历线索二叉树
void inOrderThreadTree(TreeNode *root) {
    TreeNode *p = root;
    while (p != NULL) {
        // 找到最左边的节点
        while (p->ltag == 0) {
            p = p->left;
        }
        printf("%d ", p->val);
        // 找到后继节点
        while (p->rtag == 1 && p->right != NULL) {
            p = p->right;
            printf("%d ", p->val);
        }
        // 继续遍历
        p = p->right;
    }
}

int main() {
    // 创建二叉树
    TreeNode *root = (TreeNode*)malloc(sizeof(TreeNode));
    root->val = 1;
    root->left = (TreeNode*)malloc(sizeof(TreeNode));
    root->left->val = 2;
    root->right = (TreeNode*)malloc(sizeof(TreeNode));
    root->right->val = 3;
    root->left->left = (TreeNode*)malloc(sizeof(TreeNode));
    root->left->left->val = 4;
    root->left->right = (TreeNode*)malloc(sizeof(TreeNode));
    root->left->right->val = 5;
    root->right->left = (TreeNode*)malloc(sizeof(TreeNode));
    root->right->left->val = 6;
    root->right->right = (TreeNode*)malloc(sizeof(TreeNode));
    root->right->right->val = 7;

    // 初始化前驱和后继指针
    TreeNode *pre = NULL;
    // 构建线索二叉树
    createThreadTree(root, &pre);

    // 中序遍历线索二叉树
    inOrderThreadTree(root);
    
    return 0;
}

在上述代码中，我们定义了一个 `TreeNode` 结构体来表示二叉树的节点，其中 `ltag` 和 `rtag` 分别表示节点的左右指针是否为线索指针。我们使用了递归方式来构建线索二叉树，同时在构建的过程中更新了每个节点的前驱和后继指针。最后，我们使用中序遍历的方式来遍历线索二叉树。