c语言用顺序存储写完全二叉树找其中一个结点的双亲结点和左孩子结点和右孩子结点,输入时如果结点为空用#代替,第一行输入二叉树各结点的值,第二行输入要查找的结点
时间: 2024-05-08 15:18:09 浏览: 134
-1表示。
完全二叉树的顺序存储一般使用一维数组来表示,具体存储方式如下:
- 若某结点的下标是i,则它的左孩子下标是2i,右孩子下标是2i+1。
- 若某结点的下标是i,则它的双亲下标是i/2,当i为1时表示该结点为根节点,没有双亲。
因此,要求某个结点的双亲结点和左右孩子结点,只需根据上述公式计算即可。具体实现代码如下:
```c
#include <stdio.h>
#define MAXSIZE 100
int tree[MAXSIZE];
int main()
{
int i, j;
printf("请输入完全二叉树的结点,空结点用-1表示:\n");
i = 1;
// 输入所有结点,存储到数组中
while (scanf("%d", &tree[i]) != EOF) {
i++;
}
int k;
printf("请输入要查询的结点:\n");
scanf("%d", &k);
// 查找结点的下标
j = 1;
while (j < i && tree[j] != k) {
j++;
}
if (j >= i) {
printf("没有找到该结点\n");
return 0;
}
// 查找该结点的双亲结点和左右孩子结点
if (j > 1) {
printf("该结点的双亲结点是:%d\n", tree[j/2]);
}
if (2*j < i && tree[2*j] != -1) {
printf("该结点的左孩子结点是:%d\n", tree[2*j]);
}
if (2*j+1 < i && tree[2*j+1] != -1) {
printf("该结点的右孩子结点是:%d\n", tree[2*j+1]);
}
return 0;
}
```
注意在输入空结点时使用-1表示,查找时也要注意该结点是否存在,如果不存在则输出提示信息。
阅读全文