请用c语言,给出层序遍历序列构建二叉树的代码
时间: 2023-11-20 12:06:59 浏览: 81
很高兴与您进行交流!对于您的问题,我很乐意为您提供帮助。以下是使用 C 语言进行层序遍历序列构建二叉树的代码示例:
```
#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
};
// 辅助队列的定义
struct Queue {
int front;
int rear;
int size;
struct TreeNode** array;
};
// 创建一个新的队列
struct Queue* createQueue(int size) {
struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));
queue->front = 0;
queue->rear = 0;
queue->size = size;
queue->array = (struct TreeNode**)malloc(size * sizeof(struct TreeNode*));
return queue;
}
// 判断队列是否为空
int isEmpty(struct Queue* queue) {
return queue->front == queue->rear;
}
// 添加元素到队列尾部
void enqueue(struct Queue* queue, struct TreeNode* item) {
if (queue->rear == queue->size) {
printf("队列已满,添加元素失败\n");
return;
}
queue->array[queue->rear++] = item;
}
// 从队列首部移除一个元素
struct TreeNode* dequeue(struct Queue* queue) {
if (isEmpty(queue)) {
printf("队列为空,移除元素失败\n");
return NULL;
}
struct TreeNode* item = queue->array[queue->front++];
return item;
}
// 通过层序遍历序列构建二叉树
struct TreeNode* createTree(int* levelOrder, int size) {
if (size == 0) {
return NULL;
}
struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->data = levelOrder[0];
root->left = NULL;
root->right = NULL;
struct Queue* queue = createQueue(size);
enqueue(queue, root);
int i = 1;
while (i < size) {
struct TreeNode* node = dequeue(queue);
if (i < size) {
struct TreeNode* left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
left->data = levelOrder[i++];
left->left = NULL;
left->right = NULL;
node->left = left;
enqueue(queue, left);
}
if (i < size) {
struct TreeNode* right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
right->data = levelOrder[i++];
right->left = NULL;
right->right = NULL;
node->right = right;
enqueue(queue, right);
}
}
return root;
}
// 打印二叉树的层序遍历序列
void printLevelOrder(struct TreeNode* root) {
if (root == NULL) {
printf("二叉树为空\n");
return;
}
struct Queue* queue = createQueue(100);
enqueue(queue, root);
printf("二叉树的层序遍历序列为:");
while (!isEmpty(queue)) {
struct TreeNode* node = dequeue(queue);
printf("%d ", node->data);
if (node->left) {
enqueue(queue, node->left);
}
if (node->right) {
enqueue(queue, node->right);
}
}
printf("\n");
}
// 主函数
int main() {
int levelOrder[] = {1, 2, 3, 4, 5, 6, 7};
int size = sizeof(levelOrder) / sizeof(levelOrder[0]);
struct TreeNode* root = createTree(levelOrder, size);
printLevelOrder(root);
return 0;
}
```
希望这段代码能够对您有所帮助!如果您还有其他问题需要解答,请随时向我提出。
阅读全文