请用C语言双重指针实现二叉树层级遍历
时间: 2023-11-19 07:06:57 浏览: 86
```
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树结构体
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 定义队列结构体
typedef struct QueueNode {
TreeNode *node;
struct QueueNode *next;
} QueueNode;
typedef struct Queue {
QueueNode *front;
QueueNode *rear;
} Queue;
// 创建二叉树
TreeNode* createTree() {
int val;
scanf("%d", &val);
if (val == -1) { // -1 表示空节点
return NULL;
}
TreeNode *root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = val;
root->left = createTree();
root->right = createTree();
return root;
}
// 初始化队列
void initQueue(Queue **queue) {
*queue = (Queue*)malloc(sizeof(Queue));
(*queue)->front = (*queue)->rear = NULL;
}
// 判断队列是否为空
int isEmpty(Queue *queue) {
return !queue->front;
}
// 入队
void enQueue(Queue *queue, TreeNode *node) {
QueueNode *newNode = (QueueNode*)malloc(sizeof(QueueNode));
newNode->node = node;
newNode->next = NULL;
if (isEmpty(queue)) {
queue->front = queue->rear = newNode;
} else {
queue->rear->next = newNode;
queue->rear = newNode;
}
}
// 出队
TreeNode* deQueue(Queue *queue) {
if (isEmpty(queue)) {
return NULL;
}
QueueNode *frontNode = queue->front;
TreeNode *node = frontNode->node;
queue->front = queue->front->next;
if (queue->front == NULL) {
queue->rear = NULL;
}
free(frontNode);
return node;
}
// 层级遍历
void levelOrder(TreeNode *root, int **result, int *returnSize) {
if (root == NULL) {
return;
}
Queue *queue;
initQueue(&queue);
enQueue(queue, root);
while (!isEmpty(queue)) {
int size = queue->rear - queue->front + 1; // 当前层的节点个数
result[*returnSize] = (int*)malloc(sizeof(int) * size);
for (int i = 0; i < size; i++) {
TreeNode *node = deQueue(queue);
result[*returnSize][i] = node->val;
if (node->left != NULL) {
enQueue(queue, node->left);
}
if (node->right != NULL) {
enQueue(queue, node->right);
}
}
(*returnSize)++;
}
}
int main() {
TreeNode *root = createTree();
int **result = (int**)malloc(sizeof(int*) * 1000);
int returnSize = 0;
levelOrder(root, result, &returnSize);
for (int i = 0; i < returnSize; i++) {
for (int j = 0; j < (queue->rear - queue->front + 1); j++) {
printf("%d ", result[i][j]);
}
printf("\n");
}
return 0;
}
```
阅读全文