二叉树操作：遍历、高度计算与哈夫曼编码

"二叉树的常见操作" 二叉树是一种特殊的树形数据结构，每个节点最多有两个子节点，通常分为左子节点和右子节点。在计算机科学中，二叉树被广泛应用于各种算法和数据结构的设计中，如搜索、排序、压缩编码等。本实验主要涉及二叉树的存储、建立、遍历以及相关算法的实现。 1. **二叉链表的建立**：通过输入字符序列，可以创建一个二叉链表。这个过程通常涉及到读取输入，解析字符，然后根据字符创建相应的二叉树节点，连接它们形成二叉链表。 2. **中序遍历**：二叉树的遍历有三种基本方式，分别是前序遍历、中序遍历和后序遍历。中序遍历是按照“左子树-根节点-右子树”的顺序访问所有节点。递归算法是直接调用自身来实现，而非递归算法通常使用栈来模拟递归的过程。 3. **先序遍历与后序遍历（非递归）**：先序遍历顺序是“根节点-左子树-右子树”，后序遍历则是“左子树-右子树-根节点”。非递归实现可以使用栈来保存待访问的节点，控制遍历顺序。 4. **求二叉树的高度**：高度是指从根节点到最远叶子节点的最长路径上的边数。可以通过比较左右子树的高度并取较大者加一来计算。 5. **求二叉树的叶子个数**：叶子节点是没有子节点的节点。可以通过递归或迭代的方式遍历二叉树，统计没有左右子节点的节点数量。 6. **森林中叶子个数的计算**：当二叉链表被视为森林的孩子兄弟链表时，森林是由多个二叉树组成的集合。计算森林中叶子个数需要遍历整个森林，对于每个树，计算其叶子节点的数量，最后累加。 7. **中序线索二叉树**：线索二叉树是在二叉链表的基础上添加线索，用于非递归遍历。在中序线索二叉树中，左线索指向中序前驱，右线索指向中序后继。建立线索二叉树后，可以方便地进行中序遍历。 8. **层次遍历**：也称为广度优先遍历，使用队列作为辅助数据结构，从根节点开始，逐层访问所有节点。 9. **菜单驱动的程序设计**：在主函数中设置一个简单的菜单，让用户选择执行上述不同操作，便于调试和测试各个算法。 10. **哈夫曼编码**：哈夫曼编码是一种可变长度的前缀编码，用于数据压缩。给定N个权值，构建哈夫曼树，然后为每个权值生成唯一的二进制编码。这个过程包括构造哈夫曼树和生成编码两部分。 在实验过程中，需要注意以下几点： - 理解递归算法的工作原理，特别是如何在非递归情况下使用栈模拟递归过程。 - 对于字符输入，要确保正确处理，避免因输入格式不正确导致的错误。 - 在实现线索二叉树时，要确保线索的正确链接，避免循环引用。 实验代码中提供了栈的数据结构定义，`SqStack` 包含了栈底 `base`、栈顶 `top` 和栈大小 `stacksize`。初始化栈的函数 `InitStack` 使用动态内存分配创建栈空间。这些是实现非递归遍历的基础。