c++按完全二叉树的顺序表示方式输入结点字母,建立二叉树。然后统计并输出度为1的结点数目。
时间: 2024-05-06 08:16:34 浏览: 61
这是一道二叉树的基本问题,可以使用递归的方法来解决。
算法步骤如下:
1. 从根节点开始,依次按照完全二叉树的顺序输入结点字母,如果输入的字母是字符 '#' 表示该结点为空,否则创建一个新的结点,并将该字母赋值给结点。
2. 对于每个非空结点,分别递归遍历其左右子树,统计其子树中度为1的结点数目。如果该结点的左右子树都为空,则该结点的度为0,直接返回0。如果只有一个子树为空,则该结点的度为1,返回1。如果两个子树都不为空,则该结点的度为2,返回0。
3. 将所有结点的度为1的结点数目累加起来,并输出结果。
C++代码如下:
```c++
#include <iostream>
using namespace std;
struct TreeNode {
char val;
TreeNode *left;
TreeNode *right;
TreeNode(char x) : val(x), left(NULL), right(NULL) {}
};
// 创建二叉树
void createTree(TreeNode* &root) {
char val;
cin >> val;
if (val == '#') {
root = NULL;
} else {
root = new TreeNode(val);
createTree(root->left);
createTree(root->right);
}
}
// 统计度为1的结点数目
int countDegree1(TreeNode* root) {
if (root == NULL) {
return 0;
}
int leftCount = countDegree1(root->left);
int rightCount = countDegree1(root->right);
if (root->left == NULL && root->right == NULL) {
return 0;
} else if (root->left == NULL || root->right == NULL) {
return leftCount + rightCount + 1;
} else {
return leftCount + rightCount;
}
}
int main() {
TreeNode* root;
createTree(root);
int count = countDegree1(root);
cout << count << endl;
return 0;
}
```
阅读全文