数据结构(c语言版)编写代码 线索二叉树的应用：实现线索树建立、插入、删除、恢复线索的实现。

下面是线索二叉树的建立、插入、删除和恢复线索的 C 语言实现代码。

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

// 线索二叉树的结构体
typedef struct ThreadNode {
    int data;
    struct ThreadNode *left, *right;
    int ltag, rtag; // 左右线索标志
} ThreadNode, *ThreadTree;

// 中序遍历线索化二叉树
void InThread(ThreadTree T, ThreadTree *pre) {
    if (T) {
        InThread(T->left, pre);
        if (!T->left) {
            T->left = *pre;
            T->ltag = 1;
        }
        if (*pre && !(*pre)->right) {
            (*pre)->right = T;
            (*pre)->rtag = 1;
        }
        *pre = T;
        InThread(T->right, pre);
    }
}

// 建立线索二叉树
void CreateInThread(ThreadTree T) {
    ThreadTree pre = NULL;
    if (T) {
        InThread(T, &pre);
        pre->right = NULL;
        pre->rtag = 1;
    }
}

// 中序遍历线索二叉树
void InOrder(ThreadTree T) {
    for (ThreadTree p = T->left; p != T; p = p->right) {
        while (p->ltag == 0)
            p = p->left;
        printf("%d ", p->data);
    }
}

// 插入节点
void InsertNode(ThreadTree T, int x) {
    ThreadTree p = T->left;
    while (p->rtag == 0)
        p = p->right;
    ThreadTree new_node = (ThreadTree)malloc(sizeof(ThreadNode));
    new_node->data = x;
    new_node->ltag = new_node->rtag = 0;
    new_node->left = p;
    new_node->right = p->right;
    p->right = new_node;
    p->rtag = 0;
    if (new_node->right) {
        new_node->right->left = new_node;
    }
}

// 删除节点
ThreadTree DeleteNode(ThreadTree T, int x) {
    ThreadTree p = T->left;
    while (p != T && p->data != x) {
        if (x < p->data)
            p = p->left;
        else
            p = p->right;
    }
    if (p == T) {
        printf("The node to delete does not exist.\n");
        return T;
    }
    if (p->ltag == 0 || p->rtag == 0) {
        printf("The node to delete is not a leaf node.\n");
        return T;
    }
    ThreadTree pre = p->left;
    while (pre->rtag == 0)
        pre = pre->right;
    ThreadTree suc = p->right;
    while (suc->ltag == 0)
        suc = suc->left;
    ThreadTree parent = pre;
    while (parent != T && parent->right != p)
        parent = parent->right;
    if (parent == T) {
        T->left = suc;
    } else {
        if (parent->rtag == 1) {
            suc->left = parent;
            parent->right = suc;
        }
        if (parent->rtag == 0) {
            pre->right = parent->right;
            parent->right->left = pre;
            suc->left = pre;
            pre->rtag = 1;
        }
    }
    free(p);
    return T;
}

// 恢复线索二叉树
void RestoreInThread(ThreadTree T) {
    ThreadTree p = T->left;
    while (p->ltag == 0)
        p = p->left;
    ThreadTree pre = p->left;
    while (p != T) {
        if (p->ltag == 1 && pre != T && pre->rtag == 1) {
            pre->right = p;
        }
        pre = p;
        p = p->right;
    }
    p = T->left;
    while (p->rtag == 0)
        p = p->right;
    ThreadTree suc = p->right;
    while (p != T) {
        if (p->rtag == 1 && suc != T && suc->ltag == 1) {
            suc->left = p;
        }
        suc = p;
        p = p->left;
    }
}

// 测试代码
int main() {
    // 创建线索二叉树
    ThreadTree T = (ThreadTree)malloc(sizeof(ThreadNode));
    T->data = 0;
    T->left = T->right = T;
    T->ltag = T->rtag = 1;
    InsertNode(T, 5);
    InsertNode(T, 3);
    InsertNode(T, 7);
    InsertNode(T, 1);
    InsertNode(T, 4);
    InsertNode(T, 6);
    InsertNode(T, 8);
    CreateInThread(T);

    // 中序遍历线索二叉树
    printf("Inorder traversal of threaded binary tree: ");
    InOrder(T);
    printf("\n");

    // 删除节点
    printf("Deleting node 4: ");
    T = DeleteNode(T, 4);
    printf("Inorder traversal of threaded binary tree after deleting node 4: ");
    InOrder(T);
    printf("\n");

    // 恢复线索二叉树
    RestoreInThread(T);
    printf("Inorder traversal of restored binary tree: ");
    InOrder(T);
    printf("\n");

    return 0;
}

以上是线索二叉树的建立、插入、删除和恢复线索的 C 语言实现代码。