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

参考代码：

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

typedef struct BiThrNode {
    char data;
    struct BiThrNode *lchild, *rchild;
    int ltag, rtag; // 线索标志
} BiThrNode, *BiThrTree;

// 创建二叉树
void createBiTree(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;
        createBiTree(&((*T)->lchild));
        createBiTree(&((*T)->rchild));
    }
}

// 中序遍历线索化二叉树
void inOrderThreading(BiThrTree T, BiThrTree *pre) {
    if (T) {
        inOrderThreading(T->lchild, pre); // 线索化左子树
        if (!T->lchild) { // 建立前驱线索
            T->ltag = 1;
            T->lchild = *pre;
        }
        if (!(*pre)->rchild) { // 建立后继线索
            (*pre)->rtag = 1;
            (*pre)->rchild = T;
        }
        *pre = T;
        inOrderThreading(T->rchild, pre); // 线索化右子树
    }
}

// 查找节点的直接前驱
BiThrNode *inOrderPreNode(BiThrNode *p) {
    if (p->ltag == 1) { // 如果有左子树，则直接返回左子树的最右节点
        return p->lchild;
    } else {
        while (p->rtag == 0) { // 否则一直往父节点找，直到父节点是其父节点的左子树
            p = p->rchild;
        }
        return p->rchild;
    }
}

// 查找节点的直接后继
BiThrNode *inOrderSucNode(BiThrNode *p) {
    if (p->rtag == 1) { // 如果有右子树，则直接返回右子树的最左节点
        return p->rchild;
    } else {
        p = p->rchild;
        while (p->ltag == 0) { // 否则一直往左子树找，直到左子树为空
            p = p->lchild;
        }
        return p;
    }
}

int main() {
    BiThrTree T, pre;
    createBiTree(&T);
    pre = (BiThrNode *)malloc(sizeof(BiThrNode));
    pre->ltag = pre->rtag = 0;
    pre->rchild = pre; // pre指向头结点
    if (T) { // 如果二叉树不为空，则线索化二叉树
        inOrderThreading(T, &pre);
        pre->rchild = NULL; // 处理最后一个节点的后继指针
    }
    char c;
    scanf("\n%c", &c);
    BiThrNode *p = T;
    while (p && p->data != c) { // 找到要查找的节点
        p = (c < p->data) ? p->lchild : p->rchild;
    }
    if (!p) { // 如果节点不存在，则输出NULL
        printf("NULL\n");
    } else {
        BiThrNode *preNode = inOrderPreNode(p);
        if (preNode) {
            printf("%c ", preNode->data);
        } else {
            printf("NULL ");
        }
        BiThrNode *sucNode = inOrderSucNode(p);
        if (sucNode) {
            printf("%c\n", sucNode->data);
        } else {
            printf("NULL\n");
        }
    }
    return 0;
}

输入样例：

ABC..DE.G..F...
E

输出样例：

B G