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

以下是代码实现，建议先理解二叉树的线索化再看代码：

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

// 二叉树结构体
typedef struct BiTNode {
    char data; // 数据域
    struct BiTNode *lchild, *rchild; // 左右子树指针
    int ltag, rtag; // 左右线索标记
} BiTNode, *BiTree;

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

// 扩展先序遍历序列建立二叉树
void CreateBiTree(BiTree &T) {
    char c;
    scanf("%c", &c);
    if (c == '#') {
        T = NULL;
    } else {
        T = (BiTree) malloc(sizeof(BiTNode));
        T->data = c;
        T->ltag = T->rtag = 0;
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }
}

// 查找节点的直接前驱
BiTree SearchPre(BiTree p) {
    if (p->ltag == 1) { // 如果节点的左线索标记为1，直接返回其前驱
        return p->lchild;
    }
    BiTree q = p->lchild;
    if (q == NULL) { // 如果左子树为空，返回NULL
        return NULL;
    }
    while (q->rtag == 0) { // 否则向右走到最右端
        q = q->rchild;
    }
    return q; // 返回最右端节点
}

// 查找节点的直接后继
BiTree SearchSuc(BiTree p) {
    if (p->rtag == 1) { // 如果节点的右线索标记为1，直接返回其后继
        return p->rchild;
    }
    BiTree q = p->rchild;
    if (q == NULL) { // 如果右子树为空，返回NULL
        return NULL;
    }
    while (q->ltag == 0) { // 否则向左走到最左端
        q = q->lchild;
    }
    return q; // 返回最左端节点
}

int main() {
    BiTree T, pre = NULL;
    CreateBiTree(T); // 建立二叉树
    InThread(T, pre); // 中序线索化
    char c;
    getchar(); // 处理输入缓冲区中的换行符
    scanf("%c", &c); // 输入待查找的节点
    BiTree p = T;
    while (p != NULL && p->data != c) { // 在二叉树中查找待查找的节点
        if (c < p->data) {
            p = p->lchild;
        } else {
            p = p->rchild;
        }
    }
    if (p == NULL) { // 如果节点不存在，输出NULL
        printf("NULL\nNULL\n");
        return 0;
    }
    BiTree preNode = SearchPre(p); // 查找直接前驱
    if (preNode == NULL) { // 如果不存在，输出NULL
        printf("NULL\n");
    } else {
        printf("%c\n", preNode->data);
    }
    BiTree sucNode = SearchSuc(p); // 查找直接后继
    if (sucNode == NULL) { // 如果不存在，输出NULL
        printf("NULL\n");
    } else {
        printf("%c\n", sucNode->data);
    }
    return 0;
}

测试样例：

输入：

AB#C##D## # // 建立二叉树：ABCD
B // 查找节点B的前驱和后继

输出：

A
C