c语言编程完成通过二叉树的顺序存储输入,创建二叉链树
时间: 2023-06-12 16:04:56 浏览: 53
首先,我们需要了解二叉树的顺序存储和二叉链表存储的概念。
1. 顺序存储:将二叉树按照层次遍历的顺序依次存储在一维数组中,若节点在数组中的下标为i,则其左子节点在数组中的下标为2i,右子节点在数组中的下标为2i+1。
2. 链式存储:将二叉树的每个节点定义为一个结构体,包含左右子节点以及节点的值。
以下是C语言代码实现通过二叉树的顺序存储输入,创建二叉链树:
```c
#include <stdio.h>
#include <stdlib.h>
// 二叉树节点结构体
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 创建二叉树(顺序存储)
void createTree(int* arr, int len, TreeNode** root) {
TreeNode** queue = (TreeNode**)calloc(len, sizeof(TreeNode*)); // 队列存储节点
TreeNode* node = NULL;
for (int i = 0; i < len; i++) {
if (arr[i] == -1) { // 空节点
node = NULL;
} else { // 创建新节点
node = (TreeNode*)malloc(sizeof(TreeNode));
node->val = arr[i];
node->left = NULL;
node->right = NULL;
}
queue[i] = node; // 将节点存入队列
if (i > 0) { // 非根节点
int parent = (i - 1) / 2; // 计算父节点下标
if (queue[parent] != NULL) { // 父节点非空
if (i % 2 == 1) { // 左子节点
queue[parent]->left = node;
} else { // 右子节点
queue[parent]->right = node;
}
}
}
}
*root = queue[0]; // 返回根节点
free(queue); // 释放队列
}
int main() {
int arr[] = {1, 2, 3, 4, 5, -1, 6, -1, -1, 7}; // 示例输入
int len = sizeof(arr) / sizeof(int);
TreeNode* root = NULL;
createTree(arr, len, &root);
return 0;
}
```
在示例中,我们定义了一个长度为10的顺序数组,其中-1表示空节点。通过createTree函数,将其转换为二叉链表存储的二叉树,并返回根节点。