当前位置： 首页 > article >正文

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

article 2025/2/10 4:09:17

二叉树遍历

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

目录

二叉树遍历

一、题型解释

二、例题问题描述

三、C语言实现

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

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

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

四、C++实现

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

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

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

五、总结对比表

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

1. C++ STL容器

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

一、题型解释

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

  1. 基础遍历：前序、中序、后序遍历（递归或迭代实现）。

  2. 层次遍历（BFS）：按层从上到下访问节点。

  3. 变种遍历：

    • 锯齿形层次遍历（Zigzag遍历）。

    • 垂序遍历（按列访问节点）。

  4. 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：递归前序遍历（难度★）

通俗解释：

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

c

#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 3
    return 0;
}

代码逻辑：

  1. 递归终止条件：当前节点为NULL时返回。

  2. 访问顺序：根节点→左子树→右子树。

  3. 时间复杂度：O(n)，每个节点访问一次。

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

通俗解释：

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

c

#include <stdbool.h>
#define MAX_SIZE 100

typedef 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 3
    return 0;
}

代码逻辑：

  1. 栈辅助：用栈保存未处理的节点。

  2. 左链入栈：不断将左子节点压栈，直到最左端。

  3. 回溯访问：弹出栈顶节点访问，转向右子树。

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

通俗解释：

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

c

#include <stdbool.h>
#define MAX_SIZE 100

typedef 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 5
    return 0;
}

代码逻辑：

  1. 队列初始化：根节点入队。

  2. 循环处理：出队节点并访问，将其子节点入队。

  3. 逐层遍历：队列先进先出特性保证按层访问。

四、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 1
    return 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 3
    return 0;
}

代码逻辑：

  1. 根节点入栈：栈顶为当前访问的根节点。

  2. 右子先入栈：利用栈的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 5
    return 0;
}

代码逻辑：

  1. 队列记录当前层：每次处理一层节点。

  2. 方向控制：根据层数奇偶性决定填充顺序。

五、总结对比表

方法时间复杂度空间复杂度优点缺点
递归遍历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)。

c

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;
            }
        }
    }
}

代码逻辑：

  1. 线索化：将当前节点的前驱节点的右指针指向自己，实现回溯。

  2. 遍历与恢复：访问后删除线索，恢复树结构。

c/c++蓝桥杯经典编程题100道-目录-CSDN博客


http://www.kler.cn/a/538763.html

相关文章：

  • 基于机器学习的DDoS检测系统实战
  • Academy Sports + Outdoors EDI：体育零售巨头的供应链“中枢神经”
  • 嵌入式AI革命：DeepSeek开源如何终结GPU霸权，开启单片机智能新时代？
  • 【C#】一维、二维、三维数组的使用
  • 微信小程序如何使用decimal计算金额
  • 保姆级AI开发环境搭建
  • 网络安全 | F5 BIG-IP RESTful API 模块功能介绍
  • 如何精确掌控网页布局？深入解析 CSS 样式与盒模型
  • 程序员也可以这样赚钱
  • 【R语言】卡方检验
  • 微服务篇-深入了解索引库与文档 CRUD 操作、使用 RestCliet API 操作索引库与文档 CRUD（Java 客户端连接 Elasticsearch 服务端）
  • 递增三元组（蓝桥杯18F）
  • 如何在WPS和Word/Excel中直接使用DeepSeek功能
  • 网络通信的基石：深入理解 TCP/IP 协议栈与 TCP/UDP 协议
  • 在 Windows 上使用 ZIP 包安装 MySQL 的详细步骤
  • react高级面试题
  • Windows Docker笔记-制作、加载镜像
  • 前后端服务配置
  • 从运输到植保：DeepSeek大模型探索无人机智能作业技术详解
  • 【sqlite】python操作sqlite3（含测试）
  • Android 开发APP中参数配置与读取总结
  • Java语言的安全开发
  • DeepSeek 与 Transformer 架构的深度关联
  • springcloud中Seata-1.5.2的使用
  • deepseek v3网络结构源码分析笔记
  • 网络基础之IP