c++按完全二叉树的顺序表示方式输入结点字母,建立二叉树。然后统计并输出度为1的结点数目。
时间: 2024-05-04 09:18:28 浏览: 92
二叉树的功能实现,用c++实现的。
实现这道题目,可以采用数组来存储完全二叉树,并且按照完全二叉树的顺序进行输入。具体操作步骤如下:
1. 定义一个结构体表示二叉树结点,包括结点值和左右子结点指针。
```c++
struct TreeNode {
char val;
TreeNode* left;
TreeNode* right;
};
```
2. 根据完全二叉树的性质,将结点顺序按照层次遍历的顺序存储在数组中。例如,第i个结点的左子结点为第2*i个结点,右子结点为第2*i+1个结点。
```c++
char nodes[MAX_SIZE]; // 存储结点值的数组
TreeNode* buildTree(int index, int n) {
if (index >= n || nodes[index] == '#') { // 超出数组范围或者当前结点为空
return nullptr;
}
TreeNode* root = new TreeNode{nodes[index], nullptr, nullptr}; // 创建当前结点
root->left = buildTree(2 * index + 1, n); // 创建左子树
root->right = buildTree(2 * index + 2, n); // 创建右子树
return root;
}
```
3. 统计度为1的结点数目。对于每个结点,判断其左右子树是否为空,若只有其中一个子树为空,则该结点为度为1的结点。
```c++
int countNodes(TreeNode* root) {
if (!root) {
return 0;
}
int count = 0;
if ((root->left && !root->right) || (!root->left && root->right)) { // 只有一个子树为空
count++;
}
count += countNodes(root->left); // 统计左子树的度为1的结点数目
count += countNodes(root->right); // 统计右子树的度为1的结点数目
return count;
}
```
完整代码如下:
阅读全文