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

一、先解答上次的思考题Day12 已经给出练习答案这里不再重复我们直接进入层序遍历。二、今天学习目标理解层序遍历按一层一层打印用队列实现层序遍历BFS 思想递归 迭代两种方式求二叉树高度完整可运行代码直接复制就能用三、什么是层序遍历按从上到下、从左到右一层一层访问节点。示例树1 / \ 2 3 / \ 4 5层序遍历结果1 2 3 4 5四、层序遍历实现思路核心用队列保存每一层节点根节点入队队不空时出队一个节点并访问左孩子入队右孩子入队五、完整代码层序遍历 求树高#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七、核心知识点小结层序遍历 BFS 队列实现树高度 max (左子树高右子树高) 1前 / 中 / 后序是 DFS深度优先层序是 BFS广度优先八、今日小练习对下面这棵树10 / \ 20 30 \ 40求层序遍历结果树的高度答案层序10 20 30 40高度3九、明日预告二叉搜索树 BST增、删、查、中序遍历有序面试最常用树结构。