C语言实现中序和先序线索遍历

中序和先序线索化是二叉树的一种遍历方式，其目的是为了方便查找某个结点的前驱和后继结点。下面是 C 语言实现中序和先序线索遍历的代码：

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

// 定义二叉树结点
typedef struct Node {
    char data;
    struct Node *left, *right;
    int ltag, rtag;    // 线索标记
} Node;

// 先序遍历二叉树，并线索化
void preorder(Node *p, Node **pre) {
    if (p != NULL) {
        // 线索化左子树
        if (p->left == NULL) {
            p->left = *pre;
            p->ltag = 1;
        }
        // 线索化右子树
        if (*pre != NULL && (*pre)->right == NULL) {
            (*pre)->right = p;
            (*pre)->rtag = 1;
        }
        // 保存前驱结点
        *pre = p;
        // 处理左子树
        if (p->ltag == 0) {
            preorder(p->left, pre);
        }
        // 处理右子树
        if (p->rtag == 0) {
            preorder(p->right, pre);
        }
    }
}

// 中序遍历二叉树，并线索化
void inorder(Node *p, Node **pre) {
    if (p != NULL) {
        // 线索化左子树
        inorder(p->left, pre);
        if (p->left == NULL) {
            p->left = *pre;
            p->ltag = 1;
        }
        if (*pre != NULL && (*pre)->right == NULL) {
            (*pre)->right = p;
            (*pre)->rtag = 1;
        }
        *pre = p;
        // 线索化右子树
        inorder(p->right, pre);
    }
}

// 创建二叉树
Node* createTree() {
    char ch;
    scanf("%c", &ch);
    if (ch == '#') {
        return NULL;
    }
    Node *p = (Node*)malloc(sizeof(Node));
    p->data = ch;
    p->left = p->right = NULL;
    p->ltag = p->rtag = 0;
    p->left = createTree();
    p->right = createTree();
    return p;
}

// 先序线索遍历
void preorderThread(Node *root) {
    Node *pre = NULL;
    preorder(root, &pre);
}

// 中序线索遍历
void inorderThread(Node *root) {
    Node *pre = NULL;
    inorder(root, &pre);
}

int main() {
    Node *root = createTree();
    printf("先序线索化：\n");
    preorderThread(root);
    printf("中序线索化：\n");
    inorderThread(root);
    return 0;
}

其中，`Node` 结构体定义了二叉树结点的数据结构，包含了 `data` 数据，`left` 和 `right` 分别表示左子树和右子树的指针，`ltag` 和 `rtag` 分别表示左子树和右子树的线索标记。

`preorder()` 和 `inorder()` 函数分别实现了先序和中序遍历，并在遍历的过程中进行了线索化。`preorderThread()` 和 `inorderThread()` 函数分别实现了先序和中序线索遍历。`createTree()` 函数用于创建二叉树。

在 `main()` 函数中，我们首先创建了一棵二叉树，然后分别进行了先序和中序线索遍历，输出了线索化后的结果。