数据结构层次遍历二叉树用C语言完成代码

以下是使用C语言实现二叉树层次遍历的代码:

#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;

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

int isQueueEmpty(Queue *queue) {
    return queue->front == NULL;
}

void enqueue(Queue *queue, TreeNode *node) {
    QueueNode *newNode = (QueueNode *) malloc(sizeof(QueueNode));
    newNode->node = node;
    newNode->next = NULL;
    if (queue->rear) {
        queue->rear->next = newNode;
        queue->rear = newNode;
    } else {
        queue->front = newNode;
        queue->rear = newNode;
    }
}

TreeNode *dequeue(Queue *queue) {
    if (isQueueEmpty(queue)) {
        return NULL;
    }
    QueueNode *node = queue->front;
    queue->front = node->next;
    if (!queue->front) {
        queue->rear = NULL;
    }
    TreeNode *treeNode = node->node;
    free(node);
    return treeNode;
}

void levelOrder(TreeNode *root) {
    if (!root) {
        return;
    }

    Queue *queue = createQueue();
    enqueue(queue, root);

    while (!isQueueEmpty(queue)) {
        int levelSize = queueSize(queue);
        for (int i = 0; i < levelSize; i++) {
            TreeNode *node = dequeue(queue);
            printf("%d ", node->val);
            if (node->left) {
                enqueue(queue, node->left);
            }
            if (node->right) {
                enqueue(queue, node->right);
            }
        }
        printf("\n");
    }
}

int main() {
    TreeNode *root = (TreeNode *) malloc(sizeof(TreeNode));
    TreeNode *node1 = (TreeNode *) malloc(sizeof(TreeNode));
    TreeNode *node2 = (TreeNode *) malloc(sizeof(TreeNode));
    TreeNode *node3 = (TreeNode *) malloc(sizeof(TreeNode));
    TreeNode *node4 = (TreeNode *) malloc(sizeof(TreeNode));
    root->val = 3;
    node1->val = 9;
    node2->val = 20;
    node3->val = 15;
    node4->val = 7;
    root->left = node1;
    root->right = node2;
    node2->left = node3;
    node2->right = node4;
    node1->left = NULL;
    node1->right = NULL;
    node3->left = NULL;
    node3->right = NULL;
    node4->left = NULL;
    node4->right = NULL;

    levelOrder(root);

    return 0;
}

这段代码中，我们定义了一个 `TreeNode` 结构体来表示二叉树节点，定义了一个 `QueueNode` 结构体来表示队列节点，定义了一个 `Queue` 结构体来表示队列。我们使用 `createQueue` 函数创建一个队列，使用 `enqueue` 和 `dequeue` 函数来实现队列的入队和出队操作，并使用 `isQueueEmpty` 函数来判断队列是否为空。我们使用 `levelOrder` 函数来实现二叉树的层次遍历，其中使用队列来辅助遍历。在 `main` 函数中，我们构建了一棵二叉树，并调用 `levelOrder` 函数来进行层次遍历。