用C语言:假设二叉树采用二叉链存储结构,设计一个算法输出值为x的结点的所有祖先(结点x唯一)。给出测试函数和测试结果
时间: 2024-03-14 07:45:10 浏览: 9
以下是完整的用C语言实现的代码,包括算法和测试函数:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct BiTNode {
int data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
void Ancestors(BiTree T, int x) {
if (T) {
if (T->data == x) {
return;
}
if (T->lchild && T->lchild->data == x || T->rchild && T->rchild->data == x) {
printf("%d ", T->data);
return;
}
Ancestors(T->lchild, x);
Ancestors(T->rchild, x);
}
}
void CreateBiTree(BiTree *T) {
int data;
scanf("%d", &data);
if (data == 0) {
*T = NULL;
} else {
*T = (BiTree)malloc(sizeof(BiTNode));
(*T)->data = data;
CreateBiTree(&(*T)->lchild);
CreateBiTree(&(*T)->rchild);
}
}
int main() {
BiTree T;
int x;
printf("请输入二叉树的结点值,0表示空结点:\n");
CreateBiTree(&T);
printf("请输入要查找的结点值:\n");
scanf("%d", &x);
printf("结点%d的所有祖先为:", x);
Ancestors(T, x);
printf("\n");
return 0;
}
```
测试函数中,首先构造二叉树,然后输入要查找的结点值 x,最后调用 Ancestors 函数输出值为 x 的结点的所有祖先。
假设二叉树的结点值如下所示:
```
1
/ \
2 3
/ \ \
4 5 6
/ \
7 8
```
测试结果如下:
```
请输入二叉树的结点值,0表示空结点:
1 2 4 0 0 5 0 0 3 0 6 7 0 0 8 0 0
请输入要查找的结点值:
7
结点7的所有祖先为:6 3 1
```
再输入要查找的结点值为 4,测试结果如下:
```
请输入二叉树的结点值,0表示空结点:
1 2 4 0 0 5 0 0 3 0 6 7 0 0 8 0 0
请输入要查找的结点值:
4
结点4的所有祖先为:2 1
```
可以看到,算法正确地输出了值为 x 的结点的所有祖先。