完成二叉树层序遍历的实现 c语言运用队列 数据结构

实现二叉树的层序遍历需要用到队列这一数据结构，具体实现步骤如下：

1. 定义一个队列结构体，并实现队列的基本操作，包括入队、出队、队列是否为空等。

typedef struct QueueNode {
    TreeNode *val;
    struct QueueNode *next;
} QueueNode;

typedef struct {
    QueueNode *front;
    QueueNode *rear;
    int size;
} Queue;

Queue *createQueue() {
    Queue *q = (Queue*)malloc(sizeof(Queue));
    q->front = q->rear = NULL;
    q->size = 0;
    return q;
}

bool isEmpty(Queue *q) {
    return q->size == 0;
}

void enqueue(Queue *q, TreeNode *val) {
    QueueNode *newNode = (QueueNode*)malloc(sizeof(QueueNode));
    newNode->val = val;
    newNode->next = NULL;
    if (isEmpty(q)) {
        q->front = q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
    q->size++;
}

TreeNode *dequeue(Queue *q) {
    if (isEmpty(q)) {
        return NULL;
    }
    QueueNode *node = q->front;
    TreeNode *val = node->val;
    q->front = q->front->next;
    if (q->front == NULL) {
        q->rear = NULL;
    }
    free(node);
    q->size--;
    return val;
}

2. 实现二叉树的层序遍历，使用队列来存储当前层的节点，并逐层遍历。

void levelOrder(TreeNode *root) {
    if (root == NULL) {
        return;
    }
    Queue *q = createQueue();
    enqueue(q, root);
    while (!isEmpty(q)) {
        int levelSize = q->size;
        for (int i = 0; i < levelSize; i++) {
            TreeNode *node = dequeue(q);
            printf("%d ", node->val);
            if (node->left != NULL) {
                enqueue(q, node->left);
            }
            if (node->right != NULL) {
                enqueue(q, node->right);
            }
        }
        printf("\n");
    }
}

以上代码实现了二叉树的层序遍历，可以通过以下测试代码进行测试：

int main() {
    TreeNode *root = createTree();
    printf("层序遍历结果：\n");
    levelOrder(root);
    return 0;
}

其中，`createTree()` 是创建一个二叉树的函数，可以根据需要自行实现。