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

以下是代码实现：

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

// 定义二叉树结构体
typedef struct BiTreeNode {
    char data; // 数据域
    struct BiTreeNode *lchild, *rchild; // 左右孩子指针
    int ltag, rtag; // 左右标志位
} BiTreeNode, *BiTree;

// 创建二叉树
void CreateBiTree(BiTree *T) {
    char ch;
    scanf("%c", &ch);
    if (ch == '#') {
        *T = NULL;
    } else {
        *T = (BiTree)malloc(sizeof(BiTreeNode));
        (*T)->data = ch;
        (*T)->ltag = (*T)->rtag = 0; // 初始标志位为0
        CreateBiTree(&((*T)->lchild));
        CreateBiTree(&((*T)->rchild));
    }
}

// 中序线索化
void InOrderThread(BiTree T, BiTree *pre) {
    if (T != NULL) {
        InOrderThread(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; // 更新前驱
        InOrderThread(T->rchild, pre); // 右子树线索化
    }
}

// 查找节点的前驱和后继
void Search(BiTree T, char x) {
    BiTree p, pre = NULL;
    p = T;
    while (p != NULL && p->data != x) { // 查找节点x
        if (x < p->data) {
            p = p->lchild;
        } else {
            p = p->rchild;
        }
    }
    if (p == NULL) { // 查找失败
        printf("NULL NULL\n");
        return;
    }
    if (p->ltag == 0) { // 如果左标志位为0，说明有前驱
        BiTree q = p->lchild;
        while (q->rchild != NULL && q->rtag == 1) { // 找到左子树中最右侧的节点
            q = q->rchild;
        }
        printf("%c ", q->data); // 输出前驱
    } else {
        printf("NULL ");
    }
    if (p->rtag == 0) { // 如果右标志位为0，说明有后继
        BiTree q = p->rchild;
        while (q->lchild != NULL && q->ltag == 1) { // 找到右子树中最左侧的节点
            q = q->lchild;
        }
        printf("%c\n", q->data); // 输出后继
    } else {
        printf("NULL\n");
    }
}

int main() {
    BiTree T;
    CreateBiTree(&T); // 创建二叉树
    BiTree pre = NULL;
    InOrderThread(T, &pre); // 中序线索化
    char x;
    scanf("%*c%c", &x); // 输入待查找节点
    Search(T, x); // 查找节点的前驱和后继
    return 0;
}

输入示例：

AB#C##D##
C

输出示例：

B D