C语言以扩展先序遍历序列建立一个二叉树,并将该二叉树中序线索化,输入一个节点,输出在该中序线索二叉树中,该节点的直接前驱及直接后继节点 【输入形式】 第一行为扩展先序遍历序列 第二行为待查找的节点 【输出形式】 如果该节点有直接前驱,则输出该节点的直接前驱的数据域;若无,则输出NULL 如果该节点有直接后继,则输出该节点的直接后继的数据域;若无,则输出NULL 【样例输入】 ABC..DE.G..F... E 【样例输出】 B G
时间: 2023-07-14 16:14:08 浏览: 20
下面是C语言的实现代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_TREE_SIZE 100 // 二叉树的最大节点数
typedef char ElemType;
typedef struct BiThrNode {
ElemType data;
struct BiThrNode *lchild, *rchild; // 左右孩子指针
int ltag, rtag; // 左右标志位
} BiThrNode, *BiThrTree;
// 创建二叉树
void CreateBiTree(BiThrTree *T) {
ElemType ch;
scanf("%c", &ch);
if (ch == '.') {
*T = NULL;
} else {
*T = (BiThrNode *)malloc(sizeof(BiThrNode));
(*T)->data = ch;
(*T)->ltag = 0;
(*T)->rtag = 0;
CreateBiTree(&((*T)->lchild));
CreateBiTree(&((*T)->rchild));
}
}
// 中序线索化
void InOrderThreading(BiThrTree p, BiThrTree *pre) {
if (p != NULL) {
InOrderThreading(p->lchild, pre);
if (p->lchild == NULL) { // 左孩子为空,建立前驱线索
p->lchild = *pre;
p->ltag = 1;
}
if (*pre != NULL && (*pre)->rchild == NULL) { // 前驱节点的右孩子为空,建立后继线索
(*pre)->rchild = p;
(*pre)->rtag = 1;
}
*pre = p;
InOrderThreading(p->rchild, pre);
}
}
// 寻找节点的直接前驱
BiThrNode *FindPreNode(BiThrNode *p) {
if (p->ltag == 0) { // 左孩子不是线索,返回左子树的最右孩子
p = p->lchild;
while (p->rtag == 0) {
p = p->rchild;
}
} else { // 左孩子是线索,直接返回
p = p->lchild;
}
return p;
}
// 寻找节点的直接后继
BiThrNode *FindNextNode(BiThrNode *p) {
if (p->rtag == 0) { // 右孩子不是线索,返回右子树的最左孩子
p = p->rchild;
while (p->ltag == 0) {
p = p->lchild;
}
} else { // 右孩子是线索,直接返回
p = p->rchild;
}
return p;
}
int main() {
BiThrTree T, pre;
pre = (BiThrNode *)malloc(sizeof(BiThrNode));
pre->rchild = NULL;
pre->rtag = 1; // 初始化pre结点
CreateBiTree(&T);
InOrderThreading(T, &pre);
char c;
scanf("%c", &c); // 读入回车
scanf("%c", &c); // 读入待查找的节点
BiThrNode *p = T;
while (p != NULL && p->data != c) { // 寻找该节点
if (p->data > c) {
p = p->lchild;
} else {
p = p->rchild;
}
}
if (p == NULL) { // 未找到该节点
printf("NULL\nNULL\n");
return 0;
}
if (p->ltag == 0) { // 节点有左孩子,输出前驱
BiThrNode *pre = FindPreNode(p);
printf("%c\n", pre->data);
} else { // 节点无左孩子,输出NULL
printf("NULL\n");
}
if (p->rtag == 0) { // 节点有右孩子,输出后继
BiThrNode *next = FindNextNode(p);
printf("%c\n", next->data);
} else { // 节点无右孩子,输出NULL
printf("NULL\n");
}
return 0;
}
```
输入样例:
```
ABC..DE.G..F...
E
```
输出样例:
```
B
G
```