构建二叉树并计算度为2的节点数

"该代码是用C++编写的，用于根据扩展二叉树的前序遍历序列构建二叉树，并计算其中度为2的结点数量。它定义了一个`Node`结构体来表示二叉树的结点，包含一个字符数据字段以及左右子结点的指针。同时，有一个`Tree`类，包含了创建二叉树、计算度为2的结点个数和打印结果的方法。" 在这段代码中，主要涉及了以下几个知识点： 1. **二叉树**：二叉树是一种每个结点最多有两个子结点的树形数据结构。这里的二叉树采用二叉链表（也称链式存储）的方式表示，每个结点包含一个字符数据和两个指向子结点的指针。 2. **扩展二叉树的前序遍历**：前序遍历的顺序是根结点 -> 左子树 -> 右子树。在输入的序列中，用'#'字符表示空结点。 3. **链式存储结构**：通过`Node`结构体，我们使用指针将结点连接起来，形成二叉链表。每个`Node`都有一个左子结点`lchild`和一个右子结点`rchild`的指针。 4. **递归**：`Creat()`函数采用递归方式根据前序遍历序列创建二叉树。首先读取一个字符，如果字符是'#'，则返回空指针；否则，创建一个新的结点，然后递归地创建左子树和右子树。 5. **类与对象**：`Tree`类包含了构建二叉树和计算度为2结点的方法。`root`是二叉树的根结点，`sum`是静态成员变量，用于累计度为2的结点数。 6. **方法实现**： - `Creat()`：递归函数，根据输入的前序遍历序列构建二叉树。 - `Num()`：遍历二叉树，计算度为2的结点个数。如果当前结点的左右子结点都存在，`sum`加一，然后递归地遍历左右子树。 - `Print()`：输出`sum`，即度为2的结点个数。 7. **主函数`main()`**：读取输入的测试用例数量`n`，对每个测试用例，创建`Tree`对象，调用`Num()`计算度为2的结点个数，并打印结果。 这段代码提供了一个完整且有效的解决方案，能够根据输入的扩展二叉树前序遍历序列构建二叉树，并统计其中度为2的结点数。