以二叉链表作为二叉树的存储结构,用C++语言编写用层次顺序遍历二叉树的方法,统计树中度为1 的结点个数。
时间: 2023-06-14 10:06:31 浏览: 82
使用C++链表实现二叉树的存储及基本操作
以下是C++的代码实现:
```cpp
#include <iostream>
#include <queue>
using namespace std;
// 二叉树的结点结构体
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 统计二叉树中度为1的结点个数
int countDegreeOne(TreeNode* root) {
if (root == NULL)
return 0;
queue<TreeNode*> q;
q.push(root);
int count = 0;
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
if ((node->left == NULL && node->right != NULL) || (node->left != NULL && node->right == NULL))
count++;
if (node->left != NULL)
q.push(node->left);
if (node->right != NULL)
q.push(node->right);
}
return count;
}
int main() {
// 创建二叉树
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
root->right->left = new TreeNode(6);
root->right->right = new TreeNode(7);
// 统计度为1的结点个数
int count = countDegreeOne(root);
cout << "Degree 1 nodes count: " << count << endl;
return 0;
}
```
在这个代码中,我们使用了队列来进行层次顺序遍历二叉树。在遍历过程中,如果一个结点的左子树或右子树为空,但是另一侧子树不为空,那么这个结点的度为1,累加计数器即可。
阅读全文