用C语言写出线索二叉树的建立与遍历的代码

以下是用C语言实现线索二叉树的建立和遍历的样例代码：

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

// 定义二叉树结点结构体
typedef struct TreeNode
{
    int data;                // 数据
    struct TreeNode *left;   // 左子树指针
    struct TreeNode *right;  // 右子树指针
    int ltag;                // 左线索标记（0表示左指针指向左子树，1表示指向前驱结点）
    int rtag;                // 右线索标记（0表示右指针指向右子树，1表示指向后继结点）
} TreeNode, *pTreeNode;

// 全局变量，用于记录当前访问的前驱结点
pTreeNode pre = NULL;

// 以前序序列构建二叉树
void createTree(pTreeNode *root)
{
    int data;
    scanf("%d", &data);

    if (data == -1)  // 输入-1表示该结点为空
    {
        *root = NULL;
    }
    else
    {
        *root = (pTreeNode)malloc(sizeof(TreeNode));
        (*root)->data = data;
        (*root)->ltag = 0;
        (*root)->rtag = 0;

        createTree(&((*root)->left));   // 递归构建左子树
        createTree(&((*root)->right));  // 递归构建右子树
    }
}

// 中序遍历线索化
void inThreading(pTreeNode root)
{
    if (root)
    {
        inThreading(root->left);  // 递归线索化左子树

        if (!root->left)  // 如果左子树为空，则设置左线索标记为1，并将左指针指向前驱结点
        {
            root->ltag = 1;
            root->left = pre;
        }

        if (pre && !pre->right)   // 如果前驱结点右子树为空，则设置前驱结点的右线索标记为1，并将右指针指向当前结点
        {
            pre->rtag = 1;
            pre->right = root;
        }

        pre = root;      // 记录当前结点作为下一个结点的前驱结点
        inThreading(root->right);  // 递归线索化右子树
    }
}

// 中序遍历线索二叉树
void inOrderTraversal(pTreeNode root)
{
    pTreeNode p = root;
    while (p)
    {
        while (p->ltag == 0)  // 如果左线索标记为0，则一直访问左子树结点
        {
            p = p->left;
        }
        printf("%d ", p->data);  // 访问当前结点
        while (p->rtag == 1 && p->right)  // 如果右线索标记为1，则一直访问后继结点
        {
            p = p->right;
            printf("%d ", p->data);  // 访问后继结点
        }
        p = p->right;    // 移动到右子树
    }
}

int main()
{
    pTreeNode root = NULL;
    printf("请输入二叉树前序序列，-1表示空结点：\n");
    createTree(&root);

    inThreading(root);  // 中序遍历线索化
    printf("线索化完毕！\n");

    printf("线索二叉树中序遍历结果为：\n");
    inOrderTraversal(root);  // 中序遍历线索二叉树

    return 0;
}