c语言实现线索二叉树的建立和遍历

线索二叉树是一种特殊的二叉树，它在原有的二叉树上增加了一些指向前驱和后继节点的指针，以实现更加高效的遍历。下面是C语言实现线索二叉树的建立和遍历的示例代码。

首先，定义线索二叉树的节点结构体：

typedef struct ThreadedNode {
    int data;
    struct ThreadedNode *left;
    struct ThreadedNode *right;
    int left_tag;
    int right_tag;
} ThreadedNode;

其中，left_tag和right_tag分别表示该节点的左右指针是否为线索指针，0表示指向子节点，1表示指向前驱或后继。

接下来，定义建立线索二叉树的函数：

ThreadedNode *createThreadedTree(int *arr, int n) {
    ThreadedNode *root = NULL;
    ThreadedNode **p = &root;
    int i = 0;
    for (; i < n; i++) {
        ThreadedNode *node = (ThreadedNode *) malloc(sizeof(ThreadedNode));
        node->data = arr[i];
        node->left = NULL;
        node->right = NULL;
        node->left_tag = 0;
        node->right_tag = 0;
        *p = node;
        p = &(node->right);
    }
    return root;
}

该函数接收一个整型数组和数组长度，返回一个指向根节点的指针。函数通过遍历数组创建二叉树，并将每个节点的右指针设置为下一个节点的指针，以便后续线索化。

接下来，定义线索化函数：

void inorderThreaded(ThreadedNode *root, ThreadedNode **pre) {
    if (root == NULL) {
        return;
    }
    inorderThreaded(root->left, pre);
    if (root->left == NULL) {
        root->left_tag = 1;
        root->left = *pre;
    }
    if (*pre != NULL && (*pre)->right == NULL) {
        (*pre)->right_tag = 1;
        (*pre)->right = root;
    }
    *pre = root;
    inorderThreaded(root->right, pre);
}

void threaded(ThreadedNode *root) {
    ThreadedNode *pre = NULL;
    inorderThreaded(root, &pre);
}

该函数接收一个指向根节点的指针，将二叉树线索化。通过中序遍历二叉树，并将每个节点的前驱和后继指针设置为前一个和后一个节点，以实现遍历时的跳转。

最后，定义遍历线索二叉树的函数：

void inorderTraverse(ThreadedNode *root) {
    ThreadedNode *p = root;
    while (p != NULL) {
        while (p->left_tag == 0) {
            p = p->left;
        }
        printf("%d ", p->data);
        while (p->right_tag == 1) {
            p = p->right;
            printf("%d ", p->data);
        }
        p = p->right;
    }
}

该函数接收一个指向根节点的指针，按中序遍历顺序输出二叉树节点的值。函数先从根节点开始，沿着左子树的线索指针一直往下走，直到找到最左边的节点，输出该节点的值。然后沿着右子树的线索指针往上回溯，输出每个节点的值，直到回到根节点。最后沿着右指针走到右子树，继续进行遍历。

完整代码如下：

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

typedef struct ThreadedNode {
    int data;
    struct ThreadedNode *left;
    struct ThreadedNode *right;
    int left_tag;
    int right_tag;
} ThreadedNode;

ThreadedNode *createThreadedTree(int *arr, int n) {
    ThreadedNode *root = NULL;
    ThreadedNode **p = &root;
    int i = 0;
    for (; i < n; i++) {
        ThreadedNode *node = (ThreadedNode *) malloc(sizeof(ThreadedNode));
        node->data = arr[i];
        node->left = NULL;
        node->right = NULL;
        node->left_tag = 0;
        node->right_tag = 0;
        *p = node;
        p = &(node->right);
    }
    return root;
}

void inorderThreaded(ThreadedNode *root, ThreadedNode **pre) {
    if (root == NULL) {
        return;
    }
    inorderThreaded(root->left, pre);
    if (root->left == NULL) {
        root->left_tag = 1;
        root->left = *pre;
    }
    if (*pre != NULL && (*pre)->right == NULL) {
        (*pre)->right_tag = 1;
        (*pre)->right = root;
    }
    *pre = root;
    inorderThreaded(root->right, pre);
}

void threaded(ThreadedNode *root) {
    ThreadedNode *pre = NULL;
    inorderThreaded(root, &pre);
}

void inorderTraverse(ThreadedNode *root) {
    ThreadedNode *p = root;
    while (p != NULL) {
        while (p->left_tag == 0) {
            p = p->left;
        }
        printf("%d ", p->data);
        while (p->right_tag == 1) {
            p = p->right;
            printf("%d ", p->data);
        }
        p = p->right;
    }
}

void destroyThreadedTree(ThreadedNode *root) {
    if (root != NULL) {
        destroyThreadedTree(root->left);
        destroyThreadedTree(root->right);
        free(root);
    }
}

int main() {
    int arr[] = {5, 3, 7, 2, 4, 6, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    ThreadedNode *root = createThreadedTree(arr, n);
    threaded(root);
    inorderTraverse(root);
    destroyThreadedTree(root);
    return 0;
}