二叉树遍历：非递归与递归实现

"二叉树的综合操作，包括先序非递归遍历、先序递归遍历、中序遍历和后序递归遍历。此外，还涉及二叉链表结构的构建以及计算树的高度和叶子节点数量。" 在本实验中，我们关注的是二叉树的各种遍历方法以及二叉链表的存储结构。二叉树是一种数据结构，每个节点最多有两个子节点，通常称为左子节点和右子节点。二叉链表是二叉树的一种常见存储方式，其中每个节点包含一个数据域和两个指向子节点的指针。 首先，实验要求我们建立一个二叉树，并采用二叉链表结构。在C语言中，我们定义了一个结构体`BiTNode`来表示二叉树的节点，包含一个字符型的数据域`data`和两个指向子节点的指针`lchild`和`rchild`。 接下来，我们来看四种遍历二叉树的方法： 1. **先序遍历**：先访问根节点，然后遍历左子树，最后遍历右子树。这里提供了两种实现方式：递归和非递归。递归版本的`DLR`函数按照"根-左-右"的顺序访问节点。非递归版本的`preorder`函数使用了栈来模拟递归过程，首先将根节点入栈，然后在循环中依次出栈并访问节点，再将未访问的子节点入栈。 2. **中序遍历**：先遍历左子树，然后访问根节点，最后遍历右子树。`LDR`函数实现了这一过程，按照"左-根-右"的顺序访问节点。 3. **后序遍历**：先遍历左子树，然后遍历右子树，最后访问根节点。`LRD`函数按照"左-右-根"的顺序访问节点。 4. **层序遍历**（广度优先遍历）：从根节点开始，按层次逐个访问节点。虽然在提供的代码中没有直接实现层序遍历，但通常可以使用队列来实现这一操作。 除了遍历，实验还要求计算二叉树的高度和叶子节点的数量。树的高度是指从根节点到最远叶子节点的最长路径上边的数目。而叶子节点是那些没有子节点的节点。这些操作通常需要通过递归或迭代的方式进行。 在给定的代码中，`CreateBiTree`函数用于根据先序遍历的结果递归地创建二叉树，它读取字符输入，如果字符是'!'则表示空节点，否则创建一个新的节点并将左右子树递归构造。 通过这个实验，我们可以深入理解二叉树的遍历算法，掌握如何利用栈和队列等数据结构解决问题，同时巩固了二叉链表存储结构的运用。这不仅对理解二叉树的基本概念至关重要，也为后续处理更复杂的数据结构和算法奠定了基础。