二叉树层序遍历与高度计算详解

一、先解答上次的思考题

Day12 已经给出练习答案，这里不再重复，我们直接进入层序遍历。

二、今天学习目标

1. 理解层序遍历（按一层一层打印）
2. 用队列实现层序遍历（BFS 思想）
3. 递归 + 迭代两种方式求二叉树高度
4. 完整可运行代码，直接复制就能用

三、什么是层序遍历？

按从上到下、从左到右，一层一层访问节点。

示例树：

1 / \ 2 3 / \ 4 5

层序遍历结果：1 2 3 4 5

四、层序遍历实现思路

核心：用队列保存每一层节点

1. 根节点入队
2. 队不空时：
   • 出队一个节点并访问
   • 左孩子入队
   • 右孩子入队

五、完整代码（层序遍历 + 求树高）

#include <stdio.h> #include <stdlib.h> // 二叉树节点结构 struct TreeNode { int data; struct TreeNode *left; struct TreeNode *right; }; // 队列节点（用于层序遍历） struct QueueNode { struct TreeNode *node; struct QueueNode *next; }; // 简单队列结构 struct Queue { struct QueueNode *front; struct QueueNode *rear; }; // 创建树节点 struct TreeNode* createNode(int val) { struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode)); node->data = val; node->left = NULL; node->right = NULL; return node; } // 初始化队列 struct Queue* createQueue() { struct Queue *q = (struct Queue*)malloc(sizeof(struct Queue)); q->front = q->rear = NULL; return q; } // 入队 void enQueue(struct Queue *q, struct TreeNode *node) { struct QueueNode *newNode = (struct QueueNode*)malloc(sizeof(struct QueueNode)); newNode->node = node; newNode->next = NULL; if (q->rear == NULL) { q->front = q->rear = newNode; return; } q->rear->next = newNode; q->rear = newNode; } // 出队 struct TreeNode* deQueue(struct Queue *q) { if (q->front == NULL) return NULL; struct QueueNode *temp = q->front; struct TreeNode *res = temp->node; q->front = q->front->next; if (q->front == NULL) q->rear = NULL; free(temp); return res; } // 判断队列空 int isQueueEmpty(struct Queue *q) { return q->front == NULL; } // ==================== 1. 层序遍历 ==================== void levelOrder(struct TreeNode *root) { if (root == NULL) return; struct Queue *q = createQueue(); enQueue(q, root); while (!isQueueEmpty(q)) { struct TreeNode *cur = deQueue(q); printf("%d ", cur->data); if (cur->left != NULL) enQueue(q, cur->left); if (cur->right != NULL) enQueue(q, cur->right); } } // ==================== 2. 求二叉树高度（递归） ==================== int treeHeight(struct TreeNode *root) { if (root == NULL) return 0; int leftH = treeHeight(root->left); int rightH = treeHeight(root->right); return (leftH > rightH ? leftH : rightH) + 1; } // ==================== 主函数测试 ==================== int main() { // 构建二叉树 struct TreeNode* root = createNode(1); root->left = createNode(2); root->right = createNode(3); root->left->left = createNode(4); root->left->right = createNode(5); printf("层序遍历："); levelOrder(root); printf("\n树的高度：%d\n", treeHeight(root)); return 0; }

六、运行结果

层序遍历：1 2 3 4 5 树的高度：3

七、核心知识点小结

1. 层序遍历 = BFS = 队列实现
2. 树高度 = max (左子树高，右子树高) + 1
3. 前 / 中 / 后序是 DFS（深度优先），层序是 BFS（广度优先）

八、今日小练习

对下面这棵树：

10 / \ 20 30 \ 40

求：

1. 层序遍历结果
2. 树的高度

答案：

• 层序：10 20 30 40
• 高度：3

九、明日预告

二叉搜索树 BST增、删、查、中序遍历有序，面试最常用树结构。