用c写一个不带头结点线索二叉树中序遍历算法

以下是C语言实现线索二叉树中序遍历的代码：

typedef struct ThreadNode {
    ElemType data;
    struct ThreadNode *lchild, *rchild;
    int ltag, rtag; // 线索标记
}ThreadNode, *ThreadTree;

void InThread(ThreadTree p, ThreadTree &pre) { // 中序遍历线索化
    if (p) {
        InThread(p->lchild, pre); // 递归左子树线索化
        if (!p->lchild) {
            p->lchild = pre; // 左指针为空，建立前驱线索
            p->ltag = 1;
        }
        if (pre && !pre->rchild) {
            pre->rchild = p; // 右指针为空，建立后继线索
            pre->rtag = 1;
        }
        pre = p;
        InThread(p->rchild, pre); // 递归右子树线索化
    }
}

ThreadTree CreateInThread() { // 创建中序线索二叉树
    ThreadTree T = NULL, pre = NULL;
    ElemType ch;
    scanf("%c", &ch);
    if (ch == '#')
        return NULL;
    T = (ThreadNode*)malloc(sizeof(ThreadNode));
    T->data = ch;
    T->ltag = T->rtag = 0;
    T->lchild = T->rchild = NULL;
    InThread(T->lchild, pre); // 递归左子树
    if (pre)
        pre->rchild = NULL; // 处理遍历的最后一个结点
    pre = NULL;
    InThread(T->rchild, pre); // 递归右子树
    if (pre)
        pre->rchild = NULL; // 处理遍历的最后一个结点
    return T;
}

ThreadTree FirstNode(ThreadTree p) { // 返回中序遍历的第一个结点
    while (p->ltag == 0)
        p = p->lchild;
    return p;
}

ThreadTree NextNode(ThreadTree p) { // 返回中序遍历的后继结点
    if (p->rtag == 0)
        return FirstNode(p->rchild);
    else
        return p->rchild;
}

void InOrder(ThreadTree T) { // 中序遍历
    for (ThreadTree p = FirstNode(T); p != NULL; p = NextNode(p))
        printf("%c ", p->data);
}

注意：这是一个不带头结点的线索二叉树，使用时需要把最左侧的结点的 `ltag` 设置为 `1`，把最右侧的结点的 `rtag` 设置为 `1`。另外，如果要自己输入二叉树，需要在每个元素后面加空格。