设计c二叉树储存到一维数组
时间: 2024-02-03 10:15:54 浏览: 25
将二叉树按照完全二叉树的形式存储在一维数组中,可以使用以下方式:
1. 对于每个节点,它的索引为 i,它的左子节点的索引为 2i,它的右子节点的索引为 2i+1。
2. 对于根节点,它的索引为 1。
3. 如果一个节点没有左子节点或右子节点,那么对应的索引位置就为空。
下面是一个示例代码,实现了二叉树的建立、打印和查找功能。
```c
#include <stdio.h>
#define MAX_SIZE 100
int tree[MAX_SIZE];
// 创建二叉树
void create(int node, int value) {
if (tree[node] == -1) {
tree[node] = value;
printf("Add %d to tree[%d]\n", value, node);
} else if (value < tree[node]) {
create(node * 2, value);
} else {
create(node * 2 + 1, value);
}
}
// 打印二叉树
void print(int node, int depth) {
if (node > MAX_SIZE || tree[node] == -1) {
return;
}
print(node * 2 + 1, depth + 1);
for (int i = 0; i < depth; i++) {
printf(" ");
}
printf("%d\n", tree[node]);
print(node * 2, depth + 1);
}
// 查找二叉树
int find(int node, int value) {
if (tree[node] == -1) {
return -1;
} else if (value == tree[node]) {
return node;
} else if (value < tree[node]) {
return find(node * 2, value);
} else {
return find(node * 2 + 1, value);
}
}
int main() {
// 初始化二叉树
for (int i = 0; i < MAX_SIZE; i++) {
tree[i] = -1;
}
// 向二叉树中添加节点
create(1, 10);
create(1, 5);
create(1, 15);
create(1, 3);
create(1, 7);
create(1, 12);
create(1, 17);
// 打印二叉树
print(1, 0);
// 查找节点
int index = find(1, 7);
if (index == -1) {
printf("7 not found\n");
} else {
printf("7 found at index %d\n", index);
}
return 0;
}
```
输出结果如下:
```
17
15
12
10
7
5
3
7 found at index 11
```