二叉树实验

article/2025/8/7 8:01:40

引言

在数据结构的学习过程中，二叉树作为一种典型的非线性结构，其构造和操作方式具有高度的层次性和结构性。而递归正是处理这种结构最自然的方式之一。关于二叉树的基本结构如下图所示：
在这里插入图片描述

  • 递归的本质是函数调用自身的过程，这恰好与二叉树的定义相吻合——一个二叉树由根节点、左子树和右子树构成，而左右子树本身又是二叉树；
  • 在构建和遍历时，递归能够很好地模拟树的访问顺序，使得代码逻辑清晰简洁；
  • 此外，使用递归可以避免手动维护栈等复杂结构，降低实现难度。

因此，在本实验中，我们采用递归方法来完成二叉树的构建以及中序、前序、后序三种深度优先遍历的实现。整个过程不仅帮助我们理解递归与树结构之间的内在联系，也为后续更复杂的树操作打下坚实基础。

一、实验需求分析

1.1 功能目标

  1. 接收用户输入的一个字符串，该字符串表示一棵二叉树的先序遍历结果；
  2. 利用递归方法将该字符串还原为一棵完整的二叉树；
  3. 对这棵二叉树执行中序、前序、后序三种遍历；
  4. 输出每种遍历的结果；
  5. 最后释放整棵树所占用的内存。

1.2 输入格式

  • 使用字符 '#' 表示空节点；
  • 示例输入：ABD##E##CF###
  • 该字符串表示如下二叉树结构：
    A/ \B   C/ \   \
D   E   F

1.3 技术目标

  • 理解递归如何构建二叉树；
  • 掌握三种基本的深度优先遍历方式；
  • 学会设计递归函数；
  • 掌握动态内存分配与释放技巧，防止内存泄漏。

二、实验思路构建

为了实现上述功能，我们需要围绕以下关键步骤展开思考：

  1. 接受用户输入并进行合法性检测；
  2. 利用递归构建二叉树；
  3. 分别实现三种遍历的函数；
  4. 统一输出三种遍历的结果；
  5. 释放整棵树的内存。

2.1 接收用户输入并进行有效性检查

首先，我们需要让用户输入一个字符串，这个字符串是根据先序遍历生成的，并且其中用 # 表示空节点。例如，ABD##E##CF### 就是一个合法输入。

为什么需要先序输入？

因为先序遍历的顺序是“根 -> 左 -> 右”，这正好与递归构建树的过程一致。我们可以依次读取字符，遇到字母就创建节点，遇到 # 就返回 NULL，从而构建出整棵树。

为什么要对输入进行合法性检查？

防止程序因为非法字符或空输入崩溃，提升用户体验和程序鲁棒性。

2.2 递归构建二叉树

接下来，我们需要根据输入字符串递归地构建二叉树。这是整个程序的核心部分。

为什么使用递归？

因为二叉树的结构本身就是递归定义的。构建时，每个节点都可能有自己的左右子树，因此非常适合用递归的方法去处理。

如何设计递归函数？

函数每次取出一个字符：

  • 如果是 #，则返回 NULL；
  • 否则新建一个节点，然后递归构建它的左右子树。

2.3 实现三种遍历函数

构建完树之后，我们需要对它进行遍历。常见的三种遍历方式分别是：

  1. 前序遍历（根 -> 左 -> 右）
  2. 中序遍历（左 -> 根 -> 右）
  3. 后序遍历（左 -> 右 -> 根）

为什么用递归实现遍历？

这三种遍历方式天然适合递归描述，只需要改变访问节点的顺序即可。

2.4 统一输出三种遍历结果

为了让程序更加模块化，我们将三种遍历结果的输出封装成一个统一的函数。这样做的原因主要还是为了避免重复代码，提高可维护性；同时也能统一输出格式，增强可读性。

2.5 释放整棵树的内存

最后，由于我们构建二叉树时会动态分配内存，所以必须显式地释放这些内存，否则会导致内存泄漏。

三、代码编写

3.1 头文件引入

在开始正式编码之前，我们需要先确定程序所需的基本结构和头文件支持。程序涉及字符串处理、输入输出、内存管理等多个方面，因此我们引入标准库中的 <stdio.h>、<stdlib.h>、<string.h> 和 <ctype.h> 头文件。

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

3.2 数据结构定义

接着，我们需要表示二叉树的节点，所以应该定义一个名为 TreeNode 的结构体。每个节点包含一个字符型数据字段，以及指向左右子节点的指针。这样的结构非常贴合二叉树的定义。

#define MAX_INPUT_SIZE 100      // 输入字符串最大长度// 二叉树节点结构体
typedef struct TreeNode 
{char data;struct TreeNode* left;struct TreeNode* right;
} TreeNode;

宏定义 MAX_INPUT_SIZE 是为了限制输入字符串的最大长度，防止缓冲区溢出，保证程序安全性。

3.3 遍历枚举定义

此外，我们为了标识不同的遍历方式，可以定义一个枚举类型 TraversalType。使用枚举提高了程序的可读性，也方便后续判断使用哪种遍历方式。

// 三种二叉树遍历方式枚举
typedef enum TraversalType
{INORDER = 1,    // 中序遍历PREORDER,       // 先序遍历POSTORDER       // 后序遍历
}TraversalType;

3.4 接收用户输入

接下来，我们来实现一个接收输入的函数，并进行有效性检查。考虑到用户可能输入错误格式的字符串，所以我们需要设计一个循环机制，直到输入合法为止。

首先我们可以输出明确的提示信息，告诉用户应该输入什么样的字符串，并提供示例。然后使用 fgets 读取输入，比 scanf 更加安全，不会导致缓冲区溢出。接着去除末尾的换行符，检查输入是否为空。如果为空，则提示用户重新输入。然后逐个字符检查是否为字母或 #，如果不是，则认为输入不合法，提示用户重新输入，并清空输入数组。

在整个过程中，始终循环直到输入合法为止，确保后续操作顺利进行。

/*** 输入二叉树先序字符串** @param input 存储输入字符串的数组*/
void InputBinaryTreeString(char input[])
{int isValid = 0;while (!isValid)    // 输入合法则结束{printf(" **提前说明**：\n\n\t请输入如 'ABD##E##CF###' 格式的字符串，其中 '#' 表示空节点\n");printf("\t输入后点击Enter回车，程序将输入根据用户输入字符串构建二叉树\n");printf("\t并输出该二叉树进行中序遍历、前序遍历和后序遍历后的结果。\n");printf("\n例如：\n    输入：\n\tABD##E##CF###\n");printf("\n    输出：\n\t中序遍历结果为：\tD B E A F C\n");printf("\t前序遍历结果为：\tA B D E C F\n");printf("\t后序遍历结果为：\tD E B F C A\n");printf("\n请输入先序遍历字符串构建二叉树:\t");/* 读取输入失败则退出 */if (fgets(input, MAX_INPUT_SIZE, stdin) == NULL){printf("错误：读取输入失败。\n");exit(EXIT_FAILURE);}/* 去除换行符 */input[strcspn(input, "\n")] = '\0';/* 检查输入是否为空 */if (strlen(input) == 0){printf("错误：输入不能为空，请重新输入。\n");continue;}/* 字符合法性检测：是否为字母或 '#' */isValid = 1;for (int i = 0; input[i] != '\0'; ++i){char ch = input[i];if (!(isalpha(ch) || ch == '#')){isValid = 0;break;}}/* 输入异常则清空重新输入 */if (!isValid){printf("错误：输入包含非法字符，请仅使用字母和 '#'。\n");printf("请重新输入。\n\n");memset(input, 0, MAX_INPUT_SIZE);  // 清空输入缓冲区内容}}
}

3.5 二叉树的构建

接着，我们来构建二叉树，这是整个程序的核心逻辑之一。我们通过递归的方式，根据用户输入的字符串逐步恢复出原始的树结构。这里，我们需要传入参数，即 input 是原始输入字符串，index 是当前解析位置的指针，便于树的“生长”。

具体流程即，一开始取出一个字符 ch，并将索引值增加 1。如果字符是 #，表示这是一个空节点，直接返回 NULL。否则，使用 malloc 分配一个新的 TreeNode 节点，设置其 data 字段为当前字符，然后递归调用函数分别构建其左子树和右子树。最终返回这个新创建的节点作为当前层的根节点。

需要注意的是，当 malloc 失败时，应立即报错并退出程序，防止继续运行造成不可预料的后果。

/*** 递归构建二叉树** @param input 字符串输入流* @param index 当前字符索引指针* @return 新建的子树根节点*/
TreeNode* BuildTree(const char* input, int* index)
{char ch = input[*index];(*index)++;if (ch == '#') {return NULL; // '#' 表示空节点}TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));if (!node){printf("错误：内存分配失败。\n");exit(EXIT_FAILURE);}node->data = ch;node->left = BuildTree(input, index);node->right = BuildTree(input, index);return node;
}

3.6 遍历方式的实现

前序遍历、中序遍历和后序遍历这三种遍历方式本质上都是通过递归来模拟树的访问顺序，它们之间的区别仅在于访问当前节点与递归访问子树的顺序不同：

遍历类型访问顺序特点说明
前序遍历根 → 左 → 右适合构建树结构、复制树
中序遍历左 → 根 → 右适合排序输出（在 BST 中）
后序遍历左 → 右 → 根适合释放资源、求表达式值

3.6.1 前序遍历

前序遍历的顺序的根左右，实际上这与我们构建二叉树时的顺序一致，因此非常适合用递归的方式实现。在递归过程中，我们先处理当前节点的数据，然后再依次递归访问左子树和右子树。

实现的逻辑大致为：如果当前节点为空（NULL），则直接返回；否则，首先打印当前节点的值；然后递归调用自身处理左子树；最后递归调用自身处理右子树。

这样就能按照“根左右”的顺序输出整棵树的所有节点。

/*** 前序遍历：根 -> 左 -> 右** @param root 树根节点*/
void PreorderTraversal(TreeNode* root)
{if (root != NULL){printf("%c ", root->data);PreorderTraversal(root->left);PreorderTraversal(root->right);}
}

注意事项

  1. 需要确保每次访问节点前都进行空指针判断，防止非法访问；
  2. 打印格式统一使用 "%c "，即每个字符后面加一个空格，便于阅读；
  3. 函数不返回任何值，仅用于输出结果。

3.6.2 中序遍历

3.6.3 后序遍历

中序遍历和后序遍历也是同理，只不过顺序不一样而已，则合理就不再赘述。

/*** 中序遍历：左 -> 根 -> 右** @param root 树根节点*/
void InorderTraversal(TreeNode* root)
{if (root != NULL){InorderTraversal(root->left);printf("%c ", root->data);InorderTraversal(root->right);}
}/*** 后序遍历：左 -> 右 -> 根** @param root 树根节点*/
void PostorderTraversal(TreeNode* root)
{if (root != NULL){PostorderTraversal(root->left);PostorderTraversal(root->right);printf("%c ", root->data);}
}

3.7 输出遍历结果

为了简化主函数中的重复调用逻辑，提高代码复用性，避免在主函数中多次调用相似的打印语句； 统一输出格式，提升可读性和一致性。我们将三种遍历方式封装在一个函数中，根据传入的枚举类型决定执行哪一种遍历。

使用 Switch分支语句传入的遍历类型，分别调用对应的遍历函数，并在前面加上描述信息即可。

/*** 输出二叉树遍历结果（中序、前序、后序）** @param root 指向树根节点的指针* @param type 遍历的方式枚举常量*/
void OutputTraverslResult(TreeNode* root, TraversalType type)
{switch (type){case INORDER:{printf("中序遍历结果为：\t");InorderTraversal(root);break;}case PREORDER:{printf("前序遍历结果为：\t");PreorderTraversal(root);break;}case POSTORDER:{printf("后序遍历结果为：\t");PostorderTraversal(root);break;}default:break;}printf("\n");
}

3.8 释放二叉树

由于我们在程序中使用了动态内存分配（malloc），因此必须手动释放所有节点占用的内存空间，否则会导致内存泄漏。因为只有先释放左右子树，才能安全地释放当前节点，否则会出现野指针或未释放的情况，所以我们采用后序释放。

void FreeBinaryTree(TreeNode** root)
{if (*root != NULL){FreeBinaryTree(&(*root)->left);FreeBinaryTree(&(*root)->right);free(*root);*root = NULL;}
}

3.9 主函数测试

现在我们已经完成了所有功能模块的实现，可以将它们整合到主函数中，形成完整的程序流程。

主函数依次完成以下任务：打印欢迎信→获取用户输入→构建二叉树→分别执行三种遍历并输出结果→释放整棵树内存→返回 0 结束程序。这样的组织方式使得主函数逻辑清晰，便于维护和扩展。

int main(void)
{printf("\n\t=== 二叉树构造与遍历程序 ===\n\n");/* 定义根节点和输入数组，并初始化树根 */char input[MAX_INPUT_SIZE];TreeNode* root = NULL;/* 获取用户输入 */InputBinaryTreeString(input);   /* 构建二叉树 */int index = 0;root = BuildTree(input, &index);            /* 前中后序遍历 */OutputTraverslResult(root, INORDER);OutputTraverslResult(root, PREORDER);OutputTraverslResult(root, POSTORDER);/* 释放二叉树 */FreeBinaryTree(&root);                    return 0;
}

四、实验总结

本次实验围绕“递归构建与遍历二叉树”这一核心任务，完整实现了从用户输入解析、树结构构建、三种遍历输出到内存释放的全过程。我们熟悉了递归在二叉树操作中的应用，理解了先序字符串如何还原出一棵树结构，并成功实现了中序、前序、后序三种遍历方式的递归实现。

当然，个人认为上述代码仍有较大的优化空间，因此大家也不必局限于此，更多的是带着批判性思维去学习，并且尝试独立编写代码，这样才能真正提高我们的代码编写能力和逻辑思维能力！

以上便是本次文章的所有内容，欢迎各位朋友在评论区讨论，本人也是一名初学小白，愿大家共同努力，一起进步吧！

鉴于笔者能力有限，难免出现一些纰漏和不足，望大家在评论区批评指正，谢谢！


http://www.hkcw.cn/article/PAjEdguQEk.shtml

相关文章

【空间光学系统与集成微纳光子学系统简介】

【空间光学系统与集成微纳光子学系统简介】

空间光学系统 空间光学系统指用于太空探测、遥感、通信等领域的光学仪器&#xff0c;通常具备高分辨率、轻量化、抗辐射等特性。主要应用包括&#xff1a; 天文观测&#xff1a;如哈勃望远镜、詹姆斯韦伯太空望远镜&#xff08;JWST&#xff09;&#xff0c;利用大口径主镜收集…
阅读更多...
开发一款IIS自动检测修复工具

开发一款IIS自动检测修复工具

目录 实现的功能 技术栈与依赖 DLL 实现细节 变量 初始化操作 自定义cpu阈值 检测IIS应用程序池 获取自定义阈值 获取某个应用程序池的占用率 获取性能计数器实例名 Kill 并重新启动应用池 写入日志到 Log 目录&#xff0c;并显示在文本框中 实际运行效果 此工具可…
阅读更多...
网络编程4-epoll

网络编程4-epoll

select底层原理 fd_set底层使用位图标记每个文件标识符有没有被使用&#xff0c;位图在c语言里靠数组实现。 select 流程 在用户态空间里&#xff08;栈、堆、数据段&#xff09;申请一个fd_set将fd_set从用户态拷贝到内核态&#xff08;在后面操作系统轮询会使用到&#xff09…
阅读更多...
SOC-ESP32S3部分：19-ADC模数转换

SOC-ESP32S3部分：19-ADC模数转换

飞书文档https://x509p6c8to.feishu.cn/wiki/XycAwmO6Niitdtka1RAcclYfnvf ESP32-S3 集成了两个 12 位 SAR ADC&#xff0c;共支持 20 个模拟通道输入。 SAR ADC 管脚通过 IO MUX 与 GPIO1 ~ GPIO20、RTC_GPIO1 ~ RTC_GPIO20、触摸传感器接口、UART 接口、SPI 接口、以及 USB…
阅读更多...
默克微生物培养基选择指南

默克微生物培养基选择指南

微生物学研究需要能在实验室提供各种不同种类的细菌、酵母或病毒。诸如发酵、蛋白质和疫苗生产的大规模过程需要大量处于生理活性状态的细菌。因此&#xff0c;针对各种应用需要有能提供适当的生化环境并保持微生物所有特征的合适的营养培养基。 任何微生物培养基都应包括营养…
阅读更多...
移动安全Android——解决APP抓包证书无效问题

移动安全Android——解决APP抓包证书无效问题

问题 通过Burpsuite和ProxyPin进行代理抓包Android APP的时候发现虽然已经正确添加了用户证书&#xff0c;但是还是会出现SSL握手错误&#xff0c;证书无效问题。这是因为Android 7 以上版本APP默认不信任用户证书&#xff0c;只信任系统证书&#xff0c;所以需要将用户证书移动…
阅读更多...
【数据库】数据库恢复技术

【数据库】数据库恢复技术

数据库恢复技术 实现恢复的核心是使用冗余&#xff0c;也就是根据冗余数据重建不正确数据。 事务 事务是一个数据库操作序列&#xff0c;是一个不可分割的工作单位&#xff0c;是恢复和并发的基本单位。 在关系数据库中&#xff0c;一个事务是一条或多条SQL语句&#xff0c…
阅读更多...
【学习笔记】深度学习-梯度概念

【学习笔记】深度学习-梯度概念

一、定义 梯度向量不仅表示函数变化的速度&#xff0c;还表示函数增长最快的方向 二、【问】为什么说它表示方向&#xff1f; 三、【问】那在深度学习梯度下降的时候&#xff0c;还要判断梯度是正是负来更新参数吗&#xff1f; 假设某个参数是 w&#xff0c;损失函数对它的…
阅读更多...
【ROS2实体机械臂驱动】rokae xCoreSDK Python测试使用

【ROS2实体机械臂驱动】rokae xCoreSDK Python测试使用

【ROS2实体机械臂驱动】rokae xCoreSDK Python测试使用 文章目录 前言正文配置环境下载源码配置环境变量测试运行修改点说明实际运行情况 参考 前言 本文用来记录 xCoreSDK-Python的调用使用1。 正文 配置环境 配置开发环境&#xff0c;这里使用conda做python环境管理&…
阅读更多...
深入浅出网络分析与故障检测工具

深入浅出网络分析与故障检测工具

目录 网络故障检测工具&#xff1a;别只靠“Ping 不通” 实战组合拳&#xff1a;分析 检测 问题闭环 四、选择工具的几个建议 五、总结&#xff1a;工具是手段&#xff0c;思维才是核心 在如今这个“数据就是生命线”的时代&#xff0c;网络的稳定性和性能直接决定着企业…
阅读更多...
使用Haproxy搭建Web群集

使用Haproxy搭建Web群集

目录 1&#xff0c;Haproxy简介 1&#xff0c;核心功能与特点 二&#xff0c;搭建haproxy群集 1&#xff0c;准备工作 2&#xff0c;修改haproxy的配置文件 3&#xff0c;准备网站 4&#xff0c;配置日志 5&#xff0c;验证 1&#xff0c;Haproxy简介 HAProxy 是一款高…
阅读更多...
Elasticsearch的写入流程介绍

Elasticsearch的写入流程介绍

Elasticsearch 的写入流程是一个涉及 分布式协调、分片路由、数据同步和副本更新 的复杂过程，其设计目标是确保数据一致性、可靠性和高性能。以下是写入流程的详细解析： 一、写入流程总览 二、详细步骤解析 1. 客户端请求路由 请求入口：客户端（如 Java 客户端、REST API）…
阅读更多...
记录一次apisix上cros配置跨域失败的问题

记录一次apisix上cros配置跨域失败的问题

安全要求不允许跨域请求&#xff0c;但是业务侧由于涉及多个域名&#xff0c;并且需要共享cookie&#xff0c;所以需要配置跨域。 在apisix上配置了cors如下。 结果安全漏扫还是识别到了跨域请求的漏洞。 调试了cors.lua的插件脚本&#xff0c;发现apisix上是如果不在allowOri…
阅读更多...
VSCode无法转到定义python源码（ctrl加单击不跳转）

VSCode无法转到定义python源码（ctrl加单击不跳转）

已经尝试的方案&#xff1a; 1.确保对应python环境正确激活 在 VSCode 中&#xff0c;打开命令面板&#xff08;CtrlShiftP&#xff09;&#xff0c;输入并选择 Python: Select Interpreter&#xff0c;然后从列表中选择正确的 Python 解释器。 2.重新卸载Python插件再重新安装…
阅读更多...
会议室钥匙总丢失？换预约功能的智能门锁更安全

会议室钥匙总丢失？换预约功能的智能门锁更安全

在企业日常运营中&#xff0c;会议室作为重要的沟通与协作场所&#xff0c;其管理效率与安全性直接影响着企业的运作顺畅度。然而&#xff0c;传统会议室管理方式中钥匙丢失、管理不便等问题频发&#xff0c;给企业带来了不少困扰。近期&#xff0c;某企业引入了启辰智慧预约系…
阅读更多...
漫画Android：事件分发的过程是怎样的？

漫画Android：事件分发的过程是怎样的？

当用户触摸屏幕时&#xff0c;硬件层会捕获触摸信号&#xff0c;并将其转化为内核事件。 Android系统会通过InputManagerService和WindowManagerService等服务将这些事件包装成MotionEvent对象&#xff0c;并将其传递给Activity的dispatchTouchEvent()方法中&#xff0c;Activi…
阅读更多...
【算法提升】分组 day_tow

【算法提升】分组 day_tow

1.分组 1.1 解析 个人认为这题最难的点在于如何想到使用二分的算法来解题。 正向求解&#xff1a;就是去看每一组中需要分多少个人&#xff0c;但是这样求解代码我根本写不出来。 所以根据正难则反的思想&#xff0c;我们可以从最终结果去倒推。 枚举最终的分配结果中&#xff…
阅读更多...
【笔记】Suna 部署之 Supabase 数据库 schema 暴露操作

【笔记】Suna 部署之 Supabase 数据库 schema 暴露操作

#工作记录 一、前置信息 在 Suna 部署过程中&#xff0c;Supabase 数据库设置已完成&#xff08;✅ Supabase database setup completed &#xff09;&#xff0c;但需要手动在 Supabase 平台暴露basejump模式&#xff08;schema&#xff09;。 Suna 部署过程中&#xff0c;S…
阅读更多...
【Linux 学习计划】-- 进程状态 | 进程运行、阻塞和挂起的本质 | 并行、并发与进程切换 | 进程优先级

【Linux 学习计划】-- 进程状态 | 进程运行、阻塞和挂起的本质 | 并行、并发与进程切换 | 进程优先级

目录 进程状态 五状态进程模型 运行、就绪状态的本质 阻塞状态的本质 挂起状态 并行与并发 进程切换 进程优先级 结语 进程状态 进程状态的本质是什么&#xff1f; 首先我们知道&#xff0c;在操作系统中&#xff0c;进程是需要被管理起来的&#xff0c;具体则是用一…
阅读更多...
自证式推理训练：大模型告别第三方打分的新纪元

自证式推理训练：大模型告别第三方打分的新纪元

1. 传统验证体系的困境与技术跃迁的必然性 1.1 传统验证器的局限性 现有强化学习框架依赖显式验证器对答案进行二值化判定&#xff0c;这种模式在数学、代码等可验证领域表现优异。某厂内部数据显示&#xff0c;传统R1-Zero方法在代码生成任务中准确率达92%&#xff0c;但切换…
阅读更多...
推荐文章

Copyright @ 2022~2023