层序遍历二叉树的实验报告C语言

好的，下面是层序遍历二叉树的实验报告：

一、实验目的

通过本实验，了解二叉树的层序遍历算法，掌握用队列实现二叉树层序遍历的方法。

二、实验内容

1. 二叉树的层序遍历算法

层序遍历是按照从上到下、从左到右的顺序遍历二叉树的每个结点。具体实现方法是：从根结点开始，将根结点入队，然后依次取出队首结点，将其左右子结点入队，直到队列为空。

2. 用队列实现二叉树层序遍历的方法

为了实现层序遍历，需要用到队列的数据结构。具体实现方法是：将根结点入队，然后依次取出队首结点，将其左右子结点入队，直到队列为空。

三、实验步骤

1. 定义二叉树结构体

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

2. 定义队列结构体

struct QueueNode {
    struct TreeNode *node;
    struct QueueNode *next;
};

3. 实现队列的入队和出队操作

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

struct TreeNode* dequeue(struct QueueNode **front) {
    if (*front == NULL) {
        return NULL;
    } else {
        struct TreeNode *node = (*front)->node;
        struct QueueNode *temp = *front;
        *front = (*front)->next;
        free(temp);
        return node;
    }
}

4. 实现二叉树的层序遍历函数

void levelOrder(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }
    struct QueueNode *front = NULL, *rear = NULL;
    enqueue(&rear, root);
    while (front != NULL) {
        struct TreeNode *node = dequeue(&front);
        printf("%d ", node->val);
        if (node->left != NULL) {
            enqueue(&rear, node->left);
        }
        if (node->right != NULL) {
            enqueue(&rear, node->right);
        }
    }
}

四、实验结果

假设有如下二叉树：

    1
   / \
  2   3
 / \   \
4   5   6

层序遍历的结果应该是：1 2 3 4 5 6。

五、实验总结

本实验通过实现二叉树的层序遍历算法，加深了对二叉树的理解，同时也掌握了用队列实现二叉树层序遍历的方法。