c++按完全二叉树的顺序表示方式输入结点字母,建立二叉树。然后统计并输出度为1的结点数目。第一行给定一个整数T,代表T组测试数据。 从第二行开始,依次输入每组测试数据:按完全二叉树的顺序表示方式输入每个结点的字母,如果结点为空,则输入“#”字符。输出度为1的结点数目。
时间: 2024-05-14 20:18:14 浏览: 115
以下是C++的代码实现:
```c++
#include <iostream>
#include <queue>
using namespace std;
struct TreeNode {
char val;
TreeNode* left;
TreeNode* right;
TreeNode(char x) : val(x), left(NULL), right(NULL) {}
};
int countDegreeOne(TreeNode* root) {
if (root == NULL) return 0;
if (root->left == NULL && root->right == NULL) return 0;
if (root->left != NULL && root->right == NULL) return 1 + countDegreeOne(root->left);
if (root->left == NULL && root->right != NULL) return 1 + countDegreeOne(root->right);
return countDegreeOne(root->left) + countDegreeOne(root->right);
}
TreeNode* buildTree() {
char c;
cin >> c;
if (c == '#') return NULL;
TreeNode* root = new TreeNode(c);
root->left = buildTree();
root->right = buildTree();
return root;
}
int main() {
int T;
cin >> T;
while (T--) {
TreeNode* root = buildTree();
int degreeOne = countDegreeOne(root);
cout << degreeOne << endl;
}
return 0;
}
```
首先定义了一个 `TreeNode` 结构体表示二叉树的结点,其中包括结点的值 `val` 和左右子树指针 `left` 和 `right`。
然后定义了一个函数 `countDegreeOne` 统计度为1的结点数目。如果当前结点为叶子结点,则返回0;如果当前结点只有一个子结点,则返回1加上左右子树中度为1的结点数;否则返回左右子树中度为1的结点数之和。
接着定义了一个函数 `buildTree` 建立二叉树。按照完全二叉树的顺序表示方式输入每个结点的字符,如果结点为 `#` 则表示该结点为空,返回 NULL;否则创建一个新的结点并递归建立其左右子树。
最后在主函数中,先输入测试数据组数 T,然后对于每组测试数据,先调用 `buildTree` 建立二叉树,再调用 `countDegreeOne` 统计度为1的结点数目,并输出结果。
阅读全文