以二叉链表作为二叉树的存储结构,编写用层次顺序遍历二叉树的方法,统计树中度为1 的结点个数。
时间: 2023-06-13 16:08:37 浏览: 117
下面是使用二叉链表存储结构的二叉树层次遍历和统计度为1节点个数的代码实现(C++):
```c++
#include <iostream>
#include <queue>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 层次遍历二叉树
void levelOrder(TreeNode* root) {
if (root == NULL) return;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
TreeNode* node = q.front();
q.pop();
cout << node->val << " ";
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
cout << endl;
}
}
// 统计度为1节点个数
int countDegreeOne(TreeNode* root) {
if (root == NULL) return 0;
int count = 0;
if ((root->left == NULL && root->right != NULL) || (root->left != NULL && root->right == NULL)) {
count = 1;
}
count += countDegreeOne(root->left) + countDegreeOne(root->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);
// 层次遍历二叉树
levelOrder(root);
// 统计度为1节点个数
int count = countDegreeOne(root);
cout << "The number of nodes with degree 1 is: " << count << endl;
return 0;
}
```
这里我们使用了“层次遍历”算法来遍历二叉树。具体来说,我们使用队列来存储每一层的节点,然后依次访问队列中的节点,并将它们的子节点(如果有的话)入队。这样我们就可以按照从上到下、从左到右的顺序遍历整棵树。
统计度为1节点个数的算法非常简单。对于每个节点,如果它只有一个子节点(即左子节点或右子节点不为空),那么它就是度为1的节点。我们可以使用递归算法来遍历整棵树,并统计符合条件的节点个数。
以上就是使用二叉链表存储结构的二叉树层次遍历和统计度为1节点个数的代码实现。
阅读全文