C语言以扩展先序遍历序列建立一个二叉树,并将该二叉树中序线索化,输入一个节点,输出在该中序线索二叉树中,该节点的直接前驱及直接后继节点 【输入形式】 第一行为扩展先序遍历序列 第二行为待查找的节点 【输出形式】 如果该节点有直接前驱,则输出该节点的直接前驱的数据域;若无,则输出NULL 如果该节点有直接后继,则输出该节点的直接后继的数据域;若无,则输出NULL
时间: 2023-07-14 13:13:53 浏览: 28
下面是代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
char data;
struct TreeNode* left;
struct TreeNode* right;
int ltag;
int rtag;
} TreeNode;
TreeNode* createTree(char* str, int* index) {
if (str[*index] == '\0' || str[*index] == '#') {
return NULL;
}
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->data = str[*index];
root->left = createTree(str, ++(*index));
root->right = createTree(str, ++(*index));
return root;
}
void inorderThread(TreeNode* p, TreeNode** pre) {
if (p == NULL) {
return;
}
inorderThread(p->left, pre);
if (p->left == NULL) {
p->ltag = 1;
p->left = *pre;
}
if (*pre != NULL && (*pre)->right == NULL) {
(*pre)->rtag = 1;
(*pre)->right = p;
}
*pre = p;
inorderThread(p->right, pre);
}
TreeNode* findNode(TreeNode* p, char val) {
if (p == NULL) {
return NULL;
}
if (p->data == val) {
return p;
}
TreeNode* left = findNode(p->left, val);
if (left != NULL) {
return left;
}
return findNode(p->right, val);
}
TreeNode* findSuccessor(TreeNode* p) {
if (p->rtag == 1) {
return p->right;
}
TreeNode* cur = p->right;
while (cur != NULL && cur->ltag == 0) {
cur = cur->left;
}
return cur;
}
TreeNode* findPredecessor(TreeNode* p) {
if (p->ltag == 1) {
return p->left;
}
TreeNode* cur = p->left;
while (cur != NULL && cur->rtag == 0) {
cur = cur->right;
}
return cur;
}
int main() {
char str[100];
scanf("%s", str);
int index = 0;
TreeNode* root = createTree(str, &index);
TreeNode* pre = NULL;
inorderThread(root, &pre);
char val;
scanf("%*c%c", &val);
TreeNode* p = findNode(root, val);
TreeNode* predecessor = findPredecessor(p);
TreeNode* successor = findSuccessor(p);
if (predecessor != NULL) {
printf("%c ", predecessor->data);
} else {
printf("NULL ");
}
if (successor != NULL) {
printf("%c", successor->data);
} else {
printf("NULL");
}
return 0;
}
```
输入样例:
```
AB#D##CE#H##F##
H
```
输出样例:
```
E F
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)