用顺序数组存储结构来存储一颗二叉树,编写c语言算法实现对该二叉树进行先序遍历,输出先序遍历序列。
时间: 2023-06-13 20:09:19 浏览: 114
实验五(包括顺序结构、先序遍历构造二叉树
假设二叉树结点的数据类型为 `int`,则顺序数组存储结构中,按照完全二叉树的方式存储二叉树结点,从根节点开始编号为1,假设数组名为 `arr`,则节点i的左子节点为 `arr[2*i]`,右子节点为 `arr[2*i+1]`,父节点为 `arr[i/2]`。
以下是基于顺序数组存储结构的先序遍历算法实现:
```c
#include <stdio.h>
#define MAXSIZE 100 // 数组最大长度
int arr[MAXSIZE] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; // 顺序数组存储结构
void preOrder(int i) {
if (i >= MAXSIZE) { // 超出数组范围
return;
}
if (arr[i] == 0) { // 空结点
return;
}
printf("%d ", arr[i]); // 输出结点数据
preOrder(2 * i); // 遍历左子树
preOrder(2 * i + 1); // 遍历右子树
}
int main() {
preOrder(1); // 从根节点开始遍历
return 0;
}
```
以上代码中,`preOrder()` 函数实现了对二叉树的先序遍历,从根节点开始遍历,输出每个结点的数据。如果当前结点超出了数组的范围,则返回;如果当前结点是空结点,则返回。在遍历左子树和右子树之前,先输出当前结点的数据。最后在 `main()` 函数中调用 `preOrder()` 函数,从根节点开始遍历整棵二叉树。
阅读全文