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

"数据结构北大上机实践考试试题4.1" 这篇资源涉及的是一个数据结构相关的编程题目，主要考察的是二叉树的构建和操作。具体来说，这道题目是关于从输入的前序遍历（Preorder Traversal）和后序遍历（Postorder Traversal）序列恢复一棵二叉树的过程。在这个过程中，还需要实现两个辅助函数：一个是前序遍历输出二叉树，另一个计算二叉树中所有叶子节点的个数。 首先，题目给出了一个C语言的代码框架，用于实现从前序和后序遍历序列构建二叉树的`MK`函数。这个函数接受五个参数：输入的前序遍历数组`in`、起始索引`is`、结束索引`ie`，后序遍历数组`post`、起始索引`posts`、结束索引`poste`，以及一个指向根节点的指针`r`。函数通过递归的方式，找到前序遍历中的根节点值，然后根据这个值在后序遍历序列中找到根节点的位置，进而划分左右子树的范围，分别递归构造左子树和右子树。 接下来，`preorder`函数用于进行前序遍历输出，按照“根-左-右”的顺序访问每个节点。这个函数是一个递归函数，如果当前节点不为空，它会先输出当前节点的值，然后递归地对左子树和右子树进行前序遍历。 `one`函数则是用来计算二叉树中所有叶子节点的数量。同样，这是一个递归函数。如果当前节点为空，返回0；如果当前节点是叶子节点（即没有左子树和右子树），返回1；如果当前节点有子节点，递归地计算左子树和右子树的叶子节点数量，并将结果相加。 此外，代码中还包含了一个`two`函数的开头部分，这个函数可能是用来计算二叉树中所有非叶子节点的个数，即具有至少一个子节点的节点数量。它的逻辑与`one`函数类似，但需要考虑的情况更为复杂，因为它需要区分只有一个子节点的节点和有两个子节点的节点。 在实际考试中，考生需要根据给定的前序和后序遍历序列，完成`MK`函数的编写，确保能正确构建出二叉树，同时理解并实现`preorder`、`one`和`two`函数的功能。这道题目不仅考察了二叉树的基本操作，还考察了递归思维和对二叉树特性的理解。