通过C语言,实现二叉树的顺序存储结构,并实现其创建,前序,中序,后续遍历等基本操作。
时间: 2024-05-15 15:14:53 浏览: 11
二叉树的顺序存储结构是一种将二叉树以数组的方式存储的方法,具体实现如下:
1. 二叉树的根节点存放在数组下标为1的位置,其左子节点存放在下标为2的位置,其右子节点存放在下标为3的位置;
2. 对于任意一个节点i,其左子节点存放在下标为2i的位置,其右子节点存放在下标为2i+1的位置;
3. 如果某个节点不存在,则对应的数组元素值为0。
根据上述存储方式,我们可以实现二叉树的创建、前序遍历、中序遍历、后序遍历等基本操作,具体代码如下:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
typedef struct TreeNode {
int val;
} TreeNode;
typedef struct BinaryTree {
TreeNode *data;
int size;
} BinaryTree;
// 创建二叉树
void createBinaryTree(BinaryTree *bt, int arr[], int n) {
bt->size = n;
bt->data = (TreeNode *) malloc((n+1) * sizeof(TreeNode));
for (int i = 1; i <= n; i++) {
bt->data[i].val = arr[i-1];
}
}
// 前序遍历
void preOrder(BinaryTree *bt, int i) {
if (i <= bt->size && bt->data[i].val != 0) {
printf("%d ", bt->data[i].val);
preOrder(bt, 2*i);
preOrder(bt, 2*i+1);
}
}
// 中序遍历
void inOrder(BinaryTree *bt, int i) {
if (i <= bt->size && bt->data[i].val != 0) {
inOrder(bt, 2*i);
printf("%d ", bt->data[i].val);
inOrder(bt, 2*i+1);
}
}
// 后序遍历
void postOrder(BinaryTree *bt, int i) {
if (i <= bt->size && bt->data[i].val != 0) {
postOrder(bt, 2*i);
postOrder(bt, 2*i+1);
printf("%d ", bt->data[i].val);
}
}
int main() {
int arr[] = {1, 2, 3, 4, 5, 6, 7};
int n = sizeof(arr) / sizeof(int);
BinaryTree bt;
createBinaryTree(&bt, arr, n);
printf("前序遍历结果:");
preOrder(&bt, 1);
printf("\n中序遍历结果:");
inOrder(&bt, 1);
printf("\n后序遍历结果:");
postOrder(&bt, 1);
printf("\n");
return 0;
}
```
上述代码中,我们首先定义了一个二叉树结构体 BinaryTree,其中包含一个 TreeNode 类型的数组 data 和一个整数 size,分别表示二叉树的节点数据和节点数。接着,我们实现了 createBinaryTree 函数,用于根据给定的数组创建二叉树;preOrder、inOrder 和 postOrder 函数分别表示二叉树的前序遍历、中序遍历和后序遍历操作。最后,在 main 函数中调用 createBinaryTree 函数创建了一个二叉树,并分别调用 preOrder、inOrder 和 postOrder 函数进行遍历操作,输出遍历结果。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)