c/c++蓝桥杯经典编程题100道（17）二叉树遍历

二叉树遍历

->返回c/c++蓝桥杯经典编程题100道-目录

二叉树遍历

一、题型解释

二、例题问题描述

三、C语言实现

解法1：递归前序遍历（难度★）

解法2：迭代中序遍历（难度★★）

解法3：层次遍历（BFS，难度★★）

四、C++实现

解法1：递归后序遍历（难度★）

解法2：迭代前序遍历（难度★★）

解法3：锯齿形层次遍历（难度★★★）

五、总结对比表

六、特殊方法与内置函数补充

1. C++ STL容器

2. Morris遍历算法（C语言示例）

一、题型解释

二叉树遍历是按照特定顺序访问树中所有节点的操作。常见题型：

基础遍历：前序、中序、后序遍历（递归或迭代实现）。
层次遍历（BFS）：按层从上到下访问节点。
变种遍历：
- 锯齿形层次遍历（Zigzag遍历）。
- 垂序遍历（按列访问节点）。
Morris遍历：使用线索二叉树实现O(1)空间复杂度的遍历。

二、例题问题描述

例题1：输入二叉树：

    1  / \  2   3  / \  
4   5

前序遍历输出 1 2 4 5 3，中序遍历输出 4 2 5 1 3，后序遍历输出 4 5 2 3 1。

例题2：输入同上二叉树，层次遍历输出 1 2 3 4 5。
例题3：锯齿形层次遍历输出 1 3 2 4 5（第二层反向）。

三、C语言实现

解法1：递归前序遍历（难度★）

通俗解释：

像“根→左→右”的顺序探访每个房间，先访问根节点，再递归访问左右子树。

#include <stdio.h>
#include <stdlib.h>typedef struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;
} TreeNode;void preorderTraversal(TreeNode *root) {if (root == NULL) return;printf("%d ", root->val);  // 先访问根节点preorderTraversal(root->left);  // 递归左子树preorderTraversal(root->right); // 递归右子树
}int main() {// 构建例题1的二叉树TreeNode n4 = {4, NULL, NULL};TreeNode n5 = {5, NULL, NULL};TreeNode n2 = {2, &n4, &n5};TreeNode n3 = {3, NULL, NULL};TreeNode n1 = {1, &n2, &n3};printf("前序遍历：");preorderTraversal(&n1); // 输出 1 2 4 5 3return 0;
}

代码逻辑：

递归终止条件：当前节点为NULL时返回。
访问顺序：根节点→左子树→右子树。
时间复杂度：O(n)，每个节点访问一次。

解法2：迭代中序遍历（难度★★）

通俗解释：

用栈模拟递归过程，像“先深入左子树到底，再回溯访问根节点，最后处理右子树”。

#include <stdbool.h>
#define MAX_SIZE 100typedef struct Stack {TreeNode* data[MAX_SIZE];int top;
} Stack;void push(Stack *s, TreeNode *node) {s->data[++s->top] = node;
}TreeNode* pop(Stack *s) {return s->data[s->top--];
}bool isEmpty(Stack *s) {return s->top == -1;
}void inorderTraversal(TreeNode *root) {Stack s = { .top = -1 };TreeNode *curr = root;while (curr != NULL || !isEmpty(&s)) {while (curr != NULL) { // 深入左子树push(&s, curr);curr = curr->left;}curr = pop(&s);        // 回溯到父节点printf("%d ", curr->val);curr = curr->right;    // 处理右子树}
}int main() {printf("\n中序遍历：");inorderTraversal(&n1); // 输出 4 2 5 1 3return 0;
}

代码逻辑：

栈辅助：用栈保存未处理的节点。
左链入栈：不断将左子节点压栈，直到最左端。
回溯访问：弹出栈顶节点访问，转向右子树。

解法3：层次遍历（BFS，难度★★）

通俗解释：

像逐层扫描，用队列记录每层节点，先访问上层再下层。

#include <stdbool.h>
#define MAX_SIZE 100typedef struct Queue {TreeNode* data[MAX_SIZE];int front, rear;
} Queue;void enqueue(Queue *q, TreeNode *node) {q->data[q->rear++] = node;
}TreeNode* dequeue(Queue *q) {return q->data[q->front++];
}bool isEmpty(Queue *q) {return q->front == q->rear;
}void levelOrderTraversal(TreeNode *root) {if (root == NULL) return;Queue q = { .front = 0, .rear = 0 };enqueue(&q, root);while (!isEmpty(&q)) {TreeNode *node = dequeue(&q);printf("%d ", node->val);if (node->left) enqueue(&q, node->left);if (node->right) enqueue(&q, node->right);}
}int main() {printf("\n层次遍历：");levelOrderTraversal(&n1); // 输出 1 2 3 4 5return 0;
}

代码逻辑：

队列初始化：根节点入队。
循环处理：出队节点并访问，将其子节点入队。
逐层遍历：队列先进先出特性保证按层访问。

四、C++实现

解法1：递归后序遍历（难度★）

通俗解释：

按“左→右→根”顺序访问，先处理左右子树，最后访问根节点。

cpp

#include <iostream>
using namespace std;struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};void postorderTraversal(TreeNode *root) {if (!root) return;postorderTraversal(root->left);  // 先左子树postorderTraversal(root->right); // 再右子树cout << root->val << " ";        // 最后根节点
}int main() {TreeNode *root = new TreeNode(1);root->left = new TreeNode(2);root->right = new TreeNode(3);root->left->left = new TreeNode(4);root->left->right = new TreeNode(5);cout << "后序遍历：";postorderTraversal(root); // 输出 4 5 2 3 1return 0;
}

代码逻辑：

与C语言递归类似，但使用C++的类和指针语法。

解法2：迭代前序遍历（难度★★）

通俗解释：

用栈模拟递归，显式控制访问顺序（根→左→右）。

cpp

#include <stack>
void preorderIterative(TreeNode *root) {if (!root) return;stack<TreeNode*> s;s.push(root);while (!s.empty()) {TreeNode *node = s.top();s.pop();cout << node->val << " ";if (node->right) s.push(node->right); // 右子先入栈（后处理）if (node->left) s.push(node->left);   // 左子后入栈（先处理）}
}int main() {cout << "\n迭代前序遍历：";preorderIterative(root); // 输出 1 2 4 5 3return 0;
}

代码逻辑：

根节点入栈：栈顶为当前访问的根节点。
右子先入栈：利用栈的LIFO特性，确保左子先被处理。

解法3：锯齿形层次遍历（难度★★★）

通俗解释：

层次遍历的变种，偶数层反向输出（用双端队列控制方向）。

cpp

#include <queue>
#include <vector>
void zigzagLevelOrder(TreeNode *root) {if (!root) return;queue<TreeNode*> q;q.push(root);bool leftToRight = true;while (!q.empty()) {int size = q.size();vector<int> level(size);for (int i = 0; i < size; i++) {TreeNode *node = q.front();q.pop();int index = leftToRight ? i : size - 1 - i;level[index] = node->val;if (node->left) q.push(node->left);if (node->right) q.push(node->right);}leftToRight = !leftToRight;for (int num : level) cout << num << " ";}
}int main() {cout << "\n锯齿形遍历：";zigzagLevelOrder(root); // 输出 1 3 2 4 5return 0;
}

代码逻辑：

队列记录当前层：每次处理一层节点。
方向控制：根据层数奇偶性决定填充顺序。

五、总结对比表

方法	时间复杂度	空间复杂度	优点	缺点
递归遍历	O(n)	O(n)	代码简洁	栈溢出风险
迭代遍历	O(n)	O(n)	无栈溢出风险	需手动管理栈/队列
层次遍历（BFS）	O(n)	O(n)	直观，适合按层处理	空间占用较大
Morris遍历	O(n)	O(1)	无需额外空间	修改树结构，逻辑复杂

六、特殊方法与内置函数补充

1. C++ STL容器

stack<TreeNode*>：用于迭代遍历，支持 push(), pop(), top()。
queue<TreeNode*>：用于层次遍历，支持 push(), front(), pop()。

2. Morris遍历算法（C语言示例）

通俗解释：

通过修改树的指针，将空间复杂度降为O(1)。

void morrisInorder(TreeNode *root) {TreeNode *curr = root, *pre;while (curr != NULL) {if (curr->left == NULL) { // 无左子树，直接访问printf("%d ", curr->val);curr = curr->right;} else {pre = curr->left;while (pre->right != NULL && pre->right != curr) {pre = pre->right; // 找到左子树的最右节点}if (pre->right == NULL) { // 建立线索pre->right = curr;curr = curr->left;} else { // 删除线索并访问pre->right = NULL;printf("%d ", curr->val);curr = curr->right;}}}
}

代码逻辑：