以二叉链表作为二叉树的存储结构,用C++编写用层次顺序遍历二叉树的方法,统计树中度为1 的结点个数。
时间: 2023-06-14 13:06:34 浏览: 112
二叉树的层次遍历可以使用队列来实现。具体步骤如下:
1. 首先将根节点入队。
2. 进入循环,判断队列是否为空,如果不为空,则执行以下步骤:
a. 取出队首元素,输出该元素的值。
b. 如果该元素有左子树,则将左子树入队。
c. 如果该元素有右子树,则将右子树入队。
3. 当队列为空时,遍历结束。
统计度为1的结点个数可以在遍历过程中进行统计。
代码如下:
```c++
#include <iostream>
#include <queue>
using namespace std;
// 二叉树结点定义
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 统计度为1的结点个数
int countDegreeOne(TreeNode* root) {
if (root == nullptr) {
return 0;
}
int cnt = 0;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
if (node->left == nullptr && node->right != nullptr) {
cnt++;
}
if (node->left != nullptr && node->right == nullptr) {
cnt++;
}
if (node->left != nullptr) {
q.push(node->left);
}
if (node->right != nullptr) {
q.push(node->right);
}
}
return cnt;
}
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->right = new TreeNode(6);
// 层次遍历
cout << "层次遍历结果为:";
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
cout << node->val << " ";
if (node->left != nullptr) {
q.push(node->left);
}
if (node->right != nullptr) {
q.push(node->right);
}
}
cout << endl;
// 统计度为1的结点个数
int cnt = countDegreeOne(root);
cout << "度为1的结点个数为:" << cnt << endl;
return 0;
}
```
输出结果为:
```
层次遍历结果为:1 2 3 4 5 6
度为1的结点个数为:2
```
阅读全文