二叉树考研重点：递归与非递归解题方法

"二叉树的考研常见问题代码，包括递归和非递归方法的实现，涵盖了二叉树的基本操作如前序遍历、后序遍历、中序遍历、查找最大值、计算0、1、2子树的数量、高度以及宽度等。" 在计算机科学中，二叉树是一种基本的数据结构，由节点（或称为顶点）和边构成，每个节点最多有两个子节点，通常分为左子节点和右子节点。二叉树在很多算法和数据结构问题中都有广泛的应用，特别是在搜索、排序和编译器设计等领域。 这段代码主要涉及以下几个二叉树的相关知识点： 1. **二叉树节点定义**：`btrnode<T>` 类定义了一个模板化的二叉树节点，包含一个类型为 T 的元素、一个指向左子节点的指针和一个指向右子节点的指针。还提供了默认构造函数和带参数的构造函数。 2. **二叉树类**：`btr<T>` 类代表了二叉树本身，拥有一个根节点指针和一个计数器，用于记录树中的节点数量。这个类还包含了多种操作二叉树的方法，如创建树、查找、遍历、修改和删除。 3. **前序遍历**：`preorder(btrnode<T>*root)` 方法实现了递归的前序遍历，顺序是根节点 -> 左子树 -> 右子树。这是通过调用 `visit(btrnode<T>*cur)` 方法访问当前节点并递归遍历其子节点实现的。 4. **中序遍历**：虽然代码中没有直接给出中序遍历的实现，但根据描述，这个二叉树类应该也包含了中序遍历的实现。中序遍历的顺序是左子树 -> 根节点 -> 右子树，通常用于对二叉搜索树进行排序。 5. **后序遍历**：同样，代码中没有直接给出后序遍历的实现，它通常是左子树 -> 右子树 -> 根节点，对于打印表达式树或者计算节点值很有用。 6. **0、1、2子树的计数**：`num0(btrnode<T>*root)`, `num1(btrnode<T>*root)` 和 `num2(btrnode<T>*root)` 方法分别计算二叉树中叶子节点数量为0、1和2的子树的数量，这对于理解和分析树的形状很有帮助。 7. **树的高度**：`btrhigh(btrnode<T>*root)` 方法计算二叉树的最大深度，即树的最高层节点到根节点的距离，反映了树的“瘦高”程度。 8. **树的宽度**：`btrwidth(btrnode<T>*root)` 方法计算树在某一层次的最大节点数量，即树的“胖宽”。 9. **查找最大值**：`max(btrnode<T>*root)` 方法找到树中元素值最大的节点，通常在二叉搜索树中用于查找最大值。 10. **改变二叉树结构**：`change(btrnode<T>*root)` 方法可能是用来调整树的结构，比如平衡二叉树的平衡操作。 11. **删除节点**：`del(btrnode<T>*&root)` 方法删除给定的节点，这是二叉树操作中比较复杂的一部分，需要考虑多个子节点的情况。 12. **前缀表示法和后缀表示法构建二叉树**：`pib(string preod, string inod)` 方法可能是基于前缀表示法（前序遍历的顺序）和后缀表示法（后序遍历的顺序）来构建二叉树。这是一种常见的树构造问题，需要理解两种遍历方式与树结构的关系。 在准备408考试或其他相关考试时，这些二叉树的题目和代码实现是非常有价值的复习材料，涵盖了二叉树的常用操作和问题。熟练掌握这些概念和实现方法，对于解决实际问题和提高编程能力都大有裨益。