实验3二叉树的物理实现报告-201908010705-杨杰1

实验3的报告主要围绕二叉树的物理实现展开，涵盖了二叉树的基础知识、递归函数的应用、二叉树的抽象类（ADT）以及二叉链表的实现。以下是这些知识点的详细说明： 二叉树是一种数据结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树可以用来表示具有两种可能状态或分支的问题，如文件系统的目录结构。在回顾二叉树基础知识时，通常会涉及的概念包括：根节点、叶节点、度、深度、高度、完全二叉树和满二叉树等。 递归函数是实现二叉树遍历的重要工具。递归是函数在其定义中调用自身的一种方法，常用于解决分治问题。在二叉树中，递归可用于实现前序遍历（根-左-右）、中序遍历（左-根-右）和后序遍历（左-右-根）。递归函数通过改变参数传递的状态来追踪遍历过程，对于理解和解决问题非常有用。 接下来，二叉树的抽象数据类型（ADT）是一种理论模型，它定义了二叉树应该具有的操作，而不关注其具体的实现。在二叉树的ADT中，常见的操作包括插入节点、删除节点、查找节点、遍历等。通过定义二叉树的接口，我们可以独立于实现来使用和设计算法。 在二叉链表的物理实现中，每个节点包含一个数据元素、一个指向前一个节点的指针和一个指向下一个节点的指针。这种实现方式使得插入和删除操作相对简单，但需要额外的存储空间。实验中，学生完成了BinNode.h和BinTree.h两个文件，可能是定义了二叉树节点类和二叉树类，包括必要的成员变量和成员函数。 在11月7日，学生学习了层次遍历，这是通过队列实现的，因为队列先进先出的特性非常适合处理二叉树的层次结构。同时，完成了BinLListTree.h文件，可能是实现了基于链表的二叉树结构。 在11月8日，学生遇到并解决了指针未初始化的问题。在C++中，未初始化的指针可能会导致程序崩溃或不可预测的行为。正确的做法是通过构造函数创建对象并让指针指向该对象，以确保指针的有效性。 学生通过CSDN进一步深化了对二叉树的理解，还了解到递归可以使用堆栈来模拟。堆栈是另一种数据结构，具有后进先出的特性，常用于实现递归。 实验心得表明，通过实际操作和错误修正，学生不仅巩固了理论知识，也提高了编程技能，特别是对指针的使用和递归的理解。此外，将理论知识应用于实际问题的能力也得到了提升。 这个实验是一个综合性的学习过程，涉及二叉树的基本概念、递归、ADT以及实际编码，旨在提升学生的理论知识和实践能力。