数据结构上机实践：构建二叉树与遍历

"这是一份关于数据结构的北京大学上机实践考试试题，具体是试题3.1，包含了相关代码实现和部分解题思路。题目主要涉及二叉树的构造、后序遍历、叶子节点计数以及树的高度计算等概念。" 在数据结构中，二叉树是一种重要的非线性数据结构，它由结点（或称为节点）构成，每个节点最多有两个子节点，分别被称为左子节点和右子节点。在这个试题中，我们看到一个函数`MK`，它的目的是根据输入的一串字符（in[]）和四个指针范围（is, ie, pre[], pres, pree）构建一棵满二叉树。这个过程通常称为按前序遍历顺序构建二叉树，因为前序遍历的顺序是“根-左-右”。函数首先检查输入参数的有效性，然后通过递归调用自身来构建左子树和右子树。 接下来，有一个`postorder`函数，它实现了二叉树的后序遍历。后序遍历的顺序是“左-右-根”，这个函数主要用于打印树的后序遍历序列。这对于理解和检查二叉树的结构非常有用。 `leaf`函数用于计算二叉树中的叶子节点数量。如果节点为空，则返回0；若节点是叶节点（即没有左右子节点），则返回1；否则，递归地计算左子树和右子树的叶节点数并相加。 `height`函数计算二叉树的高度。树的高度定义为从根节点到最远叶节点的最长路径上边的数量。如果树为空，高度为0。否则，通过比较左子树和右子树的高度并取较大者，再加1得到树的高度。 这个试题涵盖了数据结构中的基本概念，包括二叉树的构建、遍历和特性分析。学生需要对二叉树的前序遍历、后序遍历有深入理解，并能熟练应用递归方法处理相关问题。同时，还需要掌握如何计算二叉树的高度和叶节点数量，这些都是评估二叉树性质的重要指标。通过这类练习，可以提升对二叉树操作的熟练度和问题解决能力。