c语言实现线索二叉树的前中后序遍历

线索二叉树是一种对普通二叉树进行优化的数据结构，其中每个节点除了左右子树指针之外，还有指向其前驱和后继节点的线索指针。线索化后，可以使用线索指针直接遍历整个树，而无需使用递归或栈等数据结构。

下面是使用 C 语言实现线索二叉树的前中后序遍历的代码：

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

// 定义线索二叉树节点结构体
typedef struct ThreadedBinaryTreeNode {
    int data;                                   // 节点数据
    struct ThreadedBinaryTreeNode *leftChild;   // 左子树指针
    struct ThreadedBinaryTreeNode *rightChild;  // 右子树指针
    bool leftTag;                               // 左线索标记
    bool rightTag;                              // 右线索标记
} ThreadedBinaryTreeNode;

// 全局变量，记录上一次遍历的节点
ThreadedBinaryTreeNode *preNode = NULL;

// 创建新节点
ThreadedBinaryTreeNode* createNode(int data) {
    ThreadedBinaryTreeNode *newNode = (ThreadedBinaryTreeNode*)malloc(sizeof(ThreadedBinaryTreeNode));
    newNode->data = data;
    newNode->leftChild = NULL;
    newNode->rightChild = NULL;
    newNode->leftTag = false;
    newNode->rightTag = false;
    return newNode;
}

// 中序线索化二叉树
void threadedInorder(ThreadedBinaryTreeNode *root) {
    if (root != NULL) {
        // 先线索化左子树
        threadedInorder(root->leftChild);
        // 处理当前节点
        if (root->leftChild == NULL) {
            root->leftChild = preNode;
            root->leftTag = true;
        }
        if (preNode != NULL && preNode->rightChild == NULL) {
            preNode->rightChild = root;
            preNode->rightTag = true;
        }
        preNode = root;
        // 线索化右子树
        threadedInorder(root->rightChild);
    }
}

// 中序遍历线索二叉树
void inorderTraversal(ThreadedBinaryTreeNode *root) {
    ThreadedBinaryTreeNode *p = root;
    while (p != NULL) {
        while (p->leftTag == false) {
            p = p->leftChild;
        }
        printf("%d ", p->data);
        while (p->rightTag == true) {
            p = p->rightChild;
            printf("%d ", p->data);
        }
        p = p->rightChild;
    }
}

// 前序遍历线索二叉树
void preorderTraversal(ThreadedBinaryTreeNode *root) {
    ThreadedBinaryTreeNode *p = root;
    while (p != NULL) {
        printf("%d ", p->data);
        if (p->leftTag == false) {
            p = p->leftChild;
        } else if (p->rightTag == false) {
            p = p->rightChild;
        } else {
            while (p != NULL && p->rightTag == true) {
                p = p->rightChild;
            }
            if (p != NULL) {
                p = p->rightChild;
            }
        }
    }
}

// 后序遍历线索二叉树
void postorderTraversal(ThreadedBinaryTreeNode *root) {
    ThreadedBinaryTreeNode *p = root;
    while (p->leftTag == false || p->rightTag == false) {
        if (p->leftTag == false) {
            p = p->leftChild;
        } else if (p->rightTag == false) {
            p = p->rightChild;
        }
    }
    printf("%d ", p->data);
    while (p != root) {
        ThreadedBinaryTreeNode *q = root;
        while (q->leftChild != p && q->rightChild != p) {
            if (q->rightTag == false) {
                q = q->rightChild;
            } else {
                q = q->rightChild;
                while (q != NULL && q->leftTag == true) {
                    q = q->leftChild;
                }
            }
        }
        p = q;
        printf("%d ", p->data);
    }
}

int main() {
    // 创建示例线索二叉树
    ThreadedBinaryTreeNode *root = createNode(1);
    root->leftChild = createNode(2);
    root->rightChild = createNode(3);
    root->leftChild->leftChild = createNode(4);
    root->leftChild->rightChild = createNode(5);
    root->rightChild->leftChild = createNode(6);
    root->rightChild->rightChild = createNode(7);

    // 中序线索化二叉树
    threadedInorder(root);

    // 遍历线索二叉树
    printf("Inorder traversal: ");
    inorderTraversal(root);
    printf("\n");

    printf("Preorder traversal: ");
    preorderTraversal(root);
    printf("\n");

    printf("Postorder traversal: ");
    postorderTraversal(root);
    printf("\n");

    return 0;
}

上述代码中，`createNode` 函数用于创建新节点；`threadedInorder` 函数用于中序线索化二叉树，其中使用全局变量 `preNode` 记录上一次遍历的节点；`inorderTraversal` 函数用于中序遍历线索二叉树；`preorderTraversal` 函数用于前序遍历线索二叉树；`postorderTraversal` 函数用于后序遍历线索二叉树。最后在 `main` 函数中创建示例线索二叉树，并测试各种遍历方法。