数据结构实验五（二叉树的建立及遍历）题目和源程序

实验内容 1．编写程序任意输入二叉树的结点个数和结点值，构造一棵二叉树，采用三种递归遍历算法(前序、中序、后序)对这棵二叉树进行遍历并计算出二叉树的高度。 2 .编写程序生成下面所示的二叉树，并采用中序遍历的非递归算法对此二叉树进行遍历。 ### 数据结构实验五：二叉树的建立及遍历 #### 实验背景 在计算机科学领域，二叉树是一种常用的数据结构，具有丰富的应用场景。它不仅能够高效地存储和检索数据，还可以通过不同的遍历方式来满足不同业务需求。本实验旨在通过具体的编程实践加深学生对二叉树及其遍历算法的理解。 #### 实验目的 1. **理解二叉树的节点结构与基本操作**：学习如何定义二叉树的节点以及如何进行基本的操作，如插入、删除等。 2. **掌握递归方法的应用**：学习如何利用递归来处理二叉树这一递归数据结构，具体包括构建和遍历二叉树的过程。 #### 实验要求 1. **熟悉理论基础**：深入学习和理解教材中关于二叉树的章节内容。 2. **编写完整程序**：根据实验内容要求编写完整的C++程序，并确保能在实际环境中正确运行。 3. **提交实验报告**：将实验过程、结果及思考整理成文档形式提交。 #### 实验内容解析 1. **构造二叉树并遍历** - **步骤1：输入二叉树节点数量和值** - 使用控制台输入的方式，用户可以自由指定二叉树的节点数量和每个节点的值。 - 输入格式通常遵循某种规则，例如以空格或特殊字符（如`#`）作为分隔符来表示空节点。 - **步骤2：构造二叉树** - 根据输入的节点值，递归地创建二叉树结构。这里采用了递归的方式来构建二叉树，具体实现逻辑如下： ```cpp void CreateBiTree(BiTree &T) { charch = cin.get(); if (ch == '') { T = NULL; } else { // 生成根节点 T = (BiTNode*)malloc(sizeof(BiTNode)); if (!T) cout << "内存分配失败！" << endl; T->data = ch; // 构造左子树 CreateBiTree(T->lchild); // 构造右子树 CreateBiTree(T->rchild); } } ``` - **步骤3：遍历二叉树** - 对于构建好的二叉树，使用递归方式实现前序、中序和后序遍历。 ```cpp void PreOrderTraverse(BiTree T) { if (T != NULL) { PrintElement(T->data); // 打印结点的值 PreOrderTraverse(T->lchild); // 遍历左孩子 PreOrderTraverse(T->rchild); // 遍历右孩子 } } ``` 2. **非递归中序遍历** - 除了递归遍历之外，实验还要求实现非递归中序遍历。这种方法通常利用栈来辅助实现。具体实现时，需要手动管理一个栈来保存遍历过程中遇到的节点，直到栈为空或者遍历完整棵树为止。 #### 思考与提高 1. **计算二叉树中度数为1的节点数** - 度数为1的节点指的是只有左孩子或右孩子的节点。可以通过遍历整个二叉树，统计这类节点的数量。具体实现时，可以设计一个辅助函数来递归遍历整棵树，并在每个节点处检查其左右孩子是否只有一个存在。 2. **求从根节点到目标节点p的路径** - 为了求解从根节点到特定节点p的路径，可以采用递归的方法。每次递归调用时，判断当前节点是否为目标节点，如果不是，则继续在左右子树中寻找。若找到，则记录下路径；若未找到，则返回空路径。 #### 结论 通过本次实验，不仅可以深入了解二叉树的构造与遍历原理，还能进一步掌握递归与非递归算法的设计与实现技巧。这些技能对于解决实际问题非常有用，特别是在软件开发、算法优化等领域中。