C语言实现先序线索遍历

先序线索遍历是一种二叉树的遍历方法，它可以将一棵二叉树转换为一条线性序列，具有一定的应用价值。下面是用C语言实现先序线索遍历的代码：

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

typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
    int ltag;
    int rtag;
} Node;

Node* create_node(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    node->ltag = 0;
    node->rtag = 0;
    return node;
}

// 将二叉树转化为线索二叉树
void threaded(Node* node, Node** prev) {
    if (node == NULL) {
        return;
    }
    if (node->left == NULL) {
        node->ltag = 1;
        node->left = *prev;
    }
    if (*prev != NULL && (*prev)->right == NULL) {
        (*prev)->rtag = 1;
        (*prev)->right = node;
    }
    *prev = node;
    if (node->ltag == 0) {
        threaded(node->left, prev);
    }
    if (node->rtag == 0) {
        threaded(node->right, prev);
    }
}

// 打印线索二叉树
void print_threaded(Node* node) {
    printf("先序线索遍历结果为：");
    while (node != NULL) {
        printf("%d ", node->data);
        if (node->ltag == 1) {
            node = node->left;
        } else if (node->rtag == 1) {
            node = node->right;
        } else {
            while (node->right != NULL && node->rtag == 0) {
                node = node->right;
            }
            node = node->right;
        }
    }
    printf("\n");
}

int main() {
    Node* root = create_node(1);
    root->left = create_node(2);
    root->right = create_node(3);
    root->left->left = create_node(4);
    root->left->right = create_node(5);
    root->right->left = create_node(6);
    root->right->right = create_node(7);

    Node* prev = NULL;
    threaded(root, &prev);
    print_threaded(root);

    return 0;
}

该代码中，我们定义了一个`Node`结构体表示二叉树的节点，其中`ltag`和`rtag`分别表示左右指针是否为线索指针，0表示为普通指针，1表示为线索指针。`create_node`函数用于创建一个新的节点，`threaded`函数用于将二叉树转化为线索二叉树，`print_threaded`函数用于打印线索二叉树的先序遍历结果。在`main`函数中，我们构建了一个简单的二叉树，并将其转化为线索二叉树，最后打印出了先序线索遍历的结果。