【数据结构】树与二叉树（十一）：二叉树的层次遍历（算法LevelOrder）

文章目录

5.2.1 二叉树
- 二叉树性质
- 满二叉树、完全二叉树定义、特点及相关证明
5.2.2 二叉树顺序存储
5.2.3 二叉树链接存储
5.2.4 二叉树的遍历
- 1-3 先序、中序、后序遍历递归实现及相关练习
- 4. 中序遍历非递归
- 5. 后序遍历非递归
- 6. 先序遍历非递归
- 7. 层次遍历
- - a. 算法LevelOrder
  - b. 算法解读
  - c. 时间复杂度
  - d.代码实现
  - - levelOrder
    - create
    - enqueue
    - dequeue
- 8. 代码整合

5.2.1 二叉树

二叉树是一种常见的树状数据结构，它由结点的有限集合组成。一个二叉树要么是空集，被称为空二叉树，要么由一个根结点和两棵不相交的子树组成，分别称为左子树和右子树。每个结点最多有两个子结点，分别称为左子结点和右子结点。
在这里插入图片描述

二叉树性质

引理5.1：二叉树中层数为i的结点至多有 $2^i$ 个，其中 $\geq 0$ 。

引理5.2：高度为k的二叉树中至多有 $2^{k+1}-1$ 个结点，其中 $\geq 0$ 。

引理5.3：设T是由n个结点构成的二叉树，其中叶结点个数为 $n_0$ ，度数为2的结点个数为 $n_2$ ，则有 $n_0 = n_2 + 1$ 。

详细证明过程见前文：【数据结构】树与二叉树（三）：二叉树的定义、特点、性质及相关证明

满二叉树、完全二叉树定义、特点及相关证明

详细证明过程见前文：【数据结构】树与二叉树（四）：满二叉树、完全二叉树及其性质

5.2.2 二叉树顺序存储

二叉树的顺序存储是指将二叉树中所有结点按层次顺序存放在一块地址连续的存储空间中，详见：
【数据结构】树与二叉树（五）：二叉树的顺序存储（初始化，插入结点，获取父节点、左右子节点等）

5.2.3 二叉树链接存储

二叉树的链接存储系指二叉树诸结点被随机存放在内存空间中，结点之间的关系用指针说明。在链式存储中，每个二叉树结点都包含三个域：数据域（Data）、左指针域（Left）和右指针域（Right），用于存储结点的信息和指向子结点的指针，详见：
【数据结构】树与二叉树（六）：二叉树的链式存储

5.2.4 二叉树的遍历

遍历（Traversal）是对二叉树中所有节点按照一定顺序进行访问的过程。
通过遍历，可以访问树中的每个节点，并按照特定的顺序对它们进行处理。
对二叉树的一次完整遍历，可给出树中结点的一种线性排序。
- 在二叉树中，常用的遍历方式有三种：先序遍历、中序遍历和后序遍历。
- 这三种遍历方式都可以递归地进行，它们的区别在于节点的访问顺序。
  - 在实现遍历算法时，需要考虑递归终止条件和递归调用的顺序。
- 还可以使用迭代的方式来实现遍历算法，使用栈或队列等数据结构来辅助实现。
遍历是二叉树中基础而重要的操作，它为其他许多操作提供了基础，如搜索、插入、删除等。

1-3 先序、中序、后序遍历递归实现及相关练习

【数据结构】树与二叉树（七）：二叉树的遍历（先序、中序、后序及其C语言实现）

4. 中序遍历非递归

【数据结构】树与二叉树（八）：二叉树的中序遍历（非递归算法NIO）

5. 后序遍历非递归

【数据结构】树与二叉树（九）：二叉树的后序遍历（非递归算法NPO）

6. 先序遍历非递归

【数据结构】树与二叉树（十）：二叉树的先序遍历（非递归算法NPO）

7. 层次遍历

层次遍历按层数由小到大，即从第0层开始逐层向下，同层中由左到右的次序访问二叉树的所有结点。

a. 算法LevelOrder

在这里插入图片描述

b. 算法解读

创建一个队列Q。
将指针p指向二叉树T的根节点。
如果p不为空，则将p入队列Q。
当队列Q非空时，执行以下操作：
- 将队首元素p出队列。
- 打印p的数据。
- 如果p的左子节点不为空，则将左子节点入队列Q。
- 如果p的右子节点不为空，则将右子节点入队列Q。

使用队列来保存待访问的节点，保证按层次遍历的顺序进行访问。首先将根节点入队列，然后通过循环，每次从队列中取出一个节点，访问该节点的数据，并将其左右子节点（如果存在）依次入队列。这样就可以按照层次遍历的顺序逐层访问二叉树的节点。

c. 时间复杂度

这个算法的时间复杂度是O(n)，其中n是二叉树中节点的数量。因为每个节点都会入队列一次，出队列一次，所以总的入队和出队操作次数为2n，所以时间复杂度为O(n)。

d.代码实现

levelOrder

void levelOrder(struct Node* root) {
    if (root == NULL) {
        return;
    }

    struct Queue* front, * rear;
    create(&front, &rear);
    enqueue(&front, &rear, root);

    while (front != NULL) {
        struct Node* current = front->node;
        printf("%c ", current->data);

        if (current->left != NULL) {
            enqueue(&front, &rear, current->left);
        }
        if (current->right != NULL) {
            enqueue(&front, &rear, current->right);
        }

        dequeue(&front);
    }
}

其中，队列操作详解：【数据结构】线性表（九）队列：链式队列及其基本操作（初始化、判空、入队、出队、存取队首元素）

create

// 初始化队列
void create(struct Queue** front, struct Queue** rear) {
    *front = *rear = NULL;
}

enqueue

// 入队列
void enqueue(struct Queue** front, struct Queue** rear, struct Node* node) {
    struct Queue* temp = (struct Queue*)malloc(sizeof(struct Queue));
    if (temp == NULL) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    temp->node = node;
    temp->next = NULL;
    if (*rear == NULL) {
        *front = *rear = temp;
        return;
    }
    (*rear)->next = temp;
    *rear = temp;
}

dequeue

// 出队列
void dequeue(struct Queue** front) {
    if (*front == NULL) {
        return;
    }
    struct Queue* temp = *front;
    *front = (*front)->next;
    free(temp);
}

8. 代码整合

#include <stdio.h>
#include <stdlib.h>

// 二叉树结点的定义
struct Node {
    char data;
    struct Node* left;
    struct Node* right;
};

// 创建新结点
struct Node* createNode(char data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 创建队列
struct Queue {
    struct Node* node;
    struct Queue* next;
};

// 初始化队列
void create(struct Queue** front, struct Queue** rear) {
    *front = *rear = NULL;
}

// 入队列
void enqueue(struct Queue** front, struct Queue** rear, struct Node* node) {
    struct Queue* temp = (struct Queue*)malloc(sizeof(struct Queue));
    if (temp == NULL) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    temp->node = node;
    temp->next = NULL;
    if (*rear == NULL) {
        *front = *rear = temp;
        return;
    }
    (*rear)->next = temp;
    *rear = temp;
}

// 出队列
void dequeue(struct Queue** front) {
    if (*front == NULL) {
        return;
    }
    struct Queue* temp = *front;
    *front = (*front)->next;
    free(temp);
}

// 层次遍历二叉树
void levelOrder(struct Node* root) {
    if (root == NULL) {
        return;
    }

    struct Queue* front, * rear;
    create(&front, &rear);
    enqueue(&front, &rear, root);

    while (front != NULL) {
        struct Node* current = front->node;
        printf("%c ", current->data);

        if (current->left != NULL) {
            enqueue(&front, &rear, current->left);
        }
        if (current->right != NULL) {
            enqueue(&front, &rear, current->right);
        }

        dequeue(&front);
    }
}

int main() {
    // 创建一棵二叉树
    struct Node* root = createNode('a');
    root->left = createNode('b');
    root->right = createNode('c');
    root->left->left = createNode('d');
    root->left->right = createNode('e');
    root->left->right->left = createNode('f');
    root->left->right->right = createNode('g');

    // 层次遍历二叉树
    printf("层次遍历二叉树: \n");
    levelOrder(root);
    printf("\n");

    return 0;
}