链式存储二叉树：计算叶子节点数量与详解

在本实验报告中，我们探讨了如何利用链式存储结构计算给定二叉树中叶子节点的数目。实验的核心目标是设计并实现一个算法，针对采用链式表示的二叉树结构，这种结构每个节点包含一个整数值"data"，以及两个指向子节点的指针'lchild'和'rchild'，如果节点是叶子节点，其子节点指针将为NULL。 首先，问题分析部分强调了链式存储结构的重要性，并指出在遍历过程中，叶子节点的特点是其子节点地址为NULL。在设计阶段，我们需要创建一个二叉树数据类型（Bitree），并定义一个队列Q来存放节点地址，同时提供一个Creatree函数用于手动输入节点，输入过程中使用'#'表示结束，'@'表示虚节点。在Creatree函数中，用户按顺序输入节点值，根据输入构建二叉树，确保每个父节点的指针正确指向其子节点。 接下来的详细设计部分，给出了伪代码来实现关键功能： 1. **二叉树数据类型**：定义了一个结构体Node，包含整型数据成员'data'和两个指向子节点的指针'lchild'和'rchild'。 2. **Creatree函数**：用于构建二叉树，初始化根节点T为NULL，记录父节点数front和子节点数rear。用户输入节点值，新节点s被创建并添加到队列Q中，根据节点数量调整父节点指针，并更新front和rear。当输入的字符为'#'时，跳出循环，返回根节点T。 3. **countleaf函数**：这个核心函数接收二叉树的根节点T作为参数。它递归地检查节点，如果节点为空，返回0；如果只有一个子节点为空，另一个存在，返回1；否则，递归地计算左子树和右子树的叶子节点数目之和。 4. **main函数**：作为程序的入口点，调用Creatree函数构建二叉树，并将结果传递给countleaf函数，最后输出叶子节点的总数。 在整个过程中，需要注意边界情况和错误处理，例如处理虚节点、结束符输入，以及正确计算叶子节点。此外，实验报告可能还包含了错误示例和调试过程，以帮助读者理解可能出现的问题和解决方法。这项任务着重于链式存储结构在二叉树遍历中的应用，以及递归算法在计算叶子节点数目中的运用。