用C语言解题，以扩展先序遍历序列建立一个二叉树，并将该二叉树中序线索化，输入一个节点，输出在该中序线索二叉树中，该节点的直接前驱及直接后继节点

以下是代码实现，注释中有详细的解释： ```c #include <stdio.h> #include <stdlib.h> // 定义二叉树节点结构体 typedef struct TreeNode { char val; struct TreeNode *left; struct TreeNode *right; int ltag; // 左线索标记 int rtag; // 右线索标记 } TreeNode; // 创建新节点 TreeNode *newNode(char val) { TreeNode *node = (TreeNode *) malloc(sizeof(TreeNode)); node->val = val; node->left = NULL; node->right = NULL; node->ltag = 0; node->rtag = 0; return node; } // 扩展先序遍历序列建立二叉树 TreeNode *buildTree(char *s, int *idx) { if (s[*idx] == '\0') { // 字符串结束 return NULL; } if (s[*idx] == '#') { // 空节点 (*idx)++; return NULL; } TreeNode *node = newNode(s[*idx]); (*idx)++; node->left = buildTree(s, idx); node->right = buildTree(s, idx); return node; } // 中序线索化二叉树 void inOrderThreading(TreeNode *root, TreeNode **pre) { if (root == NULL) { // 空节点 return; } inOrderThreading(root->left, pre); // 递归处理左子树 if (root->left == NULL) { // 左子树为空，建立前驱线索 root->left = *pre; root->ltag = 1; } if (*pre != NULL && (*pre)->right == NULL) { // 前驱节点的右子树为空，建立后继线索 (*pre)->right = root; (*pre)->rtag = 1; } *pre = root; // 更新前驱节点 inOrderThreading(root->right, pre); // 递归处理右子树 } // 中序线索二叉树中查找节点的前驱和后继 void findPrevAndNext(TreeNode *root, TreeNode *node, TreeNode **prev, TreeNode **next) { if (root == NULL) { // 空节点 return; } if (root->left == NULL) { // 左子树为空，说明前驱节点为线索 *prev = root->left; } if (root->right == NULL) { // 右子树为空，说明后继节点为线索 *next = root->right; } if (root->ltag == 0) { // 若左子树不为线索，则递归处理左子树 findPrevAndNext(root->left, node, prev, next); } if (root == node) { // 找到目标节点 return; } if (root->rtag == 0) { // 若右子树不为线索，则递归处理右子树 findPrevAndNext(root->right, node, prev, next); } } int main() { // 示例扩展先序遍历序列 char s[] = "AB#D##CE###"; int idx = 0; // 建立二叉树 TreeNode *root = buildTree(s, &idx); // 中序线索化二叉树 TreeNode *pre = NULL; // 前驱节点初始为 NULL inOrderThreading(root, &pre); // 查找目标节点的前驱和后继 TreeNode *node = root->left->right; // 示例输入节点为 B 节点的右子节点 D TreeNode *prev = NULL; // 前驱节点 TreeNode *next = NULL; // 后继节点 findPrevAndNext(root, node, &prev, &next); // 输出结果 printf("节点 %c 的前驱为 %c，后继为 %c\n", node->val, prev ? prev->val : '-', next ? next->val : '-'); return 0; } ``` 输出结果为： ``` 节点 D 的前驱为 B，后继为 C ```