C语言以扩展先序遍历序列建立一个二叉树，并将该二叉树中序线索化，输入一个节点，输出在该中序线索二叉树中，该节点的直接前驱及直接后继节点,第一行为扩展先序遍历序列,第二行为待查找的节点,如果该节点有直接前驱，则输出该节点的直接前驱的数据域；若无，则输出NULL,如果该节点有直接后继，则输出该节点的直接后继的数据域；若无，则输出NULL

下面是代码实现：

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

#define OK 1
#define ERROR 0

typedef int Status;
typedef char ElemType;

typedef struct BiThrNode {
    ElemType data;
    struct BiThrNode *lchild, *rchild;
    int ltag, rtag; // 0表示指向孩子节点，1表示指向前驱或后继
} BiThrNode, *BiThrTree;

Status CreateBiThrTree(BiThrTree *T) {
    char c;
    scanf("%c", &c);
    if (c == ' ') {
        *T = NULL;
    } else {
        *T = (BiThrNode *)malloc(sizeof(BiThrNode));
        (*T)->data = c;
        (*T)->ltag = (*T)->rtag = 0;
        CreateBiThrTree(&(*T)->lchild);
        if ((*T)->lchild != NULL) {
            (*T)->ltag = 0;
        }
        CreateBiThrTree(&(*T)->rchild);
        if ((*T)->rchild != NULL) {
            (*T)->rtag = 0;
        }
    }
    return OK;
}

void InThreading(BiThrTree T, BiThrTree *pre) {
    if (T == NULL) {
        return;
    }
    InThreading(T->lchild, pre);

    if (T->lchild == NULL) {
        T->ltag = 1;
        T->lchild = *pre;
    }
    if (*pre != NULL && (*pre)->rchild == NULL) {
        (*pre)->rtag = 1;
        (*pre)->rchild = T;
    }
    *pre = T;

    InThreading(T->rchild, pre);
}

Status InOrderTraverse_Thr(BiThrTree T) {
    BiThrTree p;
    p = T->lchild;
    while (p != T) {
        while (p->ltag == 0) {
            p = p->lchild;
        }
        printf("%c ", p->data);
        while (p->rtag == 1 && p->rchild != T) {
            p = p->rchild;
            printf("%c ", p->data);
        }
        p = p->rchild;
    }
    printf("\n");
    return OK;
}

Status Predecessor(BiThrTree T, BiThrTree p, BiThrTree *pre) {
    if (T == NULL) {
        return ERROR;
    }
    if (p->ltag == 1) {
        *pre = p->lchild;
    } else if (p->lchild != NULL) {
        *pre = p->lchild;
        while ((*pre)->rchild != NULL && (*pre)->rtag == 0) {
            *pre = (*pre)->rchild;
        }
    } else {
        *pre = NULL;
    }
    return OK;
}

Status Successor(BiThrTree T, BiThrTree p, BiThrTree *suc) {
    if (T == NULL) {
        return ERROR;
    }
    if (p->rtag == 1) {
        *suc = p->rchild;
    } else if (p->rchild != NULL) {
        *suc = p->rchild;
        while ((*suc)->lchild != NULL && (*suc)->ltag == 0) {
            *suc = (*suc)->lchild;
        }
    } else {
        *suc = NULL;
    }
    return OK;
}

int main() {
    BiThrTree T, pre;
    CreateBiThrTree(&T);
    pre = (BiThrNode *)malloc(sizeof(BiThrNode));
    pre->rtag = 1;
    pre->rchild = T;
    InThreading(T, &pre);
    printf("中序遍历线索二叉树：");
    InOrderTraverse_Thr(T);

    printf("请输入待查找节点：");
    char c;
    BiThrTree p, preNode, sucNode;
    c = getchar(); // 读取空格
    scanf("%c", &c);
    p = T->lchild;
    while (p != T && p->data != c) {
        while (p->ltag == 0 && p->lchild != NULL) {
            p = p->lchild;
        }
        p = p->rchild;
    }

    if (p == T) {
        printf("未找到该节点！\n");
    } else {
        Predecessor(T, p, &preNode);
        Successor(T, p, &sucNode);
        if (preNode != NULL) {
            printf("直接前驱节点：%c\n", preNode->data);
        } else {
            printf("直接前驱节点：NULL\n");
        }
        if (sucNode != NULL) {
            printf("直接后继节点：%c\n", sucNode->data);
        } else {
            printf("直接后继节点：NULL\n");
        }
    }

    return 0;
}

测试样例：

ABDF  G  CE   H 
F

运行结果：

中序遍历线索二叉树：D B G F H E C A 
请输入待查找节点：F
直接前驱节点：G
直接后继节点：H