顺序存储二叉树 用C语言实现
时间: 2024-05-25 19:06:35 浏览: 20
顺序存储二叉树是一种将二叉树的节点按照层次顺序存储在数组中的方法。下面是用C语言实现顺序存储二叉树的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
// 定义二叉树节点结构
typedef struct TreeNode {
int data;
} TreeNode;
// 创建二叉树节点
TreeNode* createNode(int data) {
TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
newNode->data = data;
return newNode;
}
// 获取左子节点的索引
int getLeftChild(int index) {
return 2 * index + 1;
}
// 获取右子节点的索引
int getRightChild(int index) {
return 2 * index + 2;
}
// 顺序存储二叉树的遍历
void inorderTraversal(TreeNode* tree, int index) {
if (tree == NULL || index >= MAX_SIZE) {
return;
}
inorderTraversal(tree, getLeftChild(index));
printf("%d ", tree[index].data);
inorderTraversal(tree, getRightChild(index));
}
int main() {
// 创建顺序存储二叉树的数组
TreeNode* tree[MAX_SIZE];
// 初始化数组
for (int i = 0; i < MAX_SIZE; i++) {
tree[i] = NULL;
}
// 插入节点
tree[0] = createNode(1);
tree[1] = createNode(2);
tree[2] = createNode(3);
tree[3] = createNode(4);
tree[4] = createNode(5);
// 遍历二叉树
printf("Inorder Traversal: ");
inorderTraversal(tree, 0);
return 0;
}
```
这段代码实现了顺序存储二叉树的创建、节点插入和中序遍历。首先,我们创建了一个大小为MAX_SIZE的数组来存储二叉树的节点。然后,通过getLeftChild和getRightChild函数来获取节点的左子节点和右子节点的索引。接下来,我们使用createNode函数创建了一些节点,并将它们插入到数组中。最后,我们使用inorderTraversal函数对二叉树进行中序遍历,并打印出节点的值。