编写函数 void LeafInEachLevel(BinTree root),计算并输出: ① 计算二叉树的每个节点的层次; ② 计算二叉树的每个层上的叶节点数; ③ 输出显示。
时间: 2024-03-09 13:47:11 浏览: 67
好的,以下是实现该功能的代码:
```
#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 LeafInEachLevel(TreeNode* root) {
if (!root) return;
queue<TreeNode*> q;
q.push(root);
int level = 0;
while (!q.empty()) {
int size = q.size();
int leafCount = 0;
for (int i = 0; i < size; i++) {
TreeNode* node = q.front();
q.pop();
if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
if (!node->left && !node->right) leafCount++;
cout << node->val << " ";
}
cout << " (level " << level << ", leafCount " << leafCount << ")" << endl;
level++;
}
}
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);
LeafInEachLevel(root);
return 0;
}
```
函数 `LeafInEachLevel` 中,我们使用了一个队列 `q` 来进行层序遍历,同时记录了当前节点的层数 `level` 和当前层的叶节点数 `leafCount`。在遍历每一层节点时,我们输出节点的值,并更新 `leafCount`,最后输出当前层的层数和叶节点数。
阅读全文