用C语言求二叉树中的结点个数叶子结点个数某结点层次和二叉树宽度完整代码
时间: 2024-11-12 12:04:55 浏览: 11
使用C语言求二叉树结点的最低公共祖先的方法
在C语言中,我们通常会通过递归的方式来遍历二叉树并计算节点、叶节点以及特定层的节点个数。这里是一个基础的示例,展示了如何计算整个二叉树的节点总数和宽度(即最大层深)。首先,我们需要定义一个二叉树结构:
```c
typedef struct TreeNode {
int val; // 节点值
struct TreeNode* left; // 左孩子指针
struct TreeNode* right; // 右孩子指针
} TreeNode;
```
接下来是计算节点总数、叶节点个数和某一节点层次的方法:
```c
// 计算节点总数
int countNodes(TreeNode* root) {
if (root == NULL) return 0;
return 1 + countNodes(root->left) + countNodes(root->right);
}
// 计算叶节点个数
int countLeaves(TreeNode* root) {
if (root == NULL || (root->left == NULL && root->right == NULL)) return root ? 1 : 0;
return countLeaves(root->left) + countLeaves(root->right);
}
// 计算指定层次的节点个数(假设从根开始计数)
int nodesAtLevel(TreeNode* root, int level) {
if (root == NULL) return 0;
if (level == 0) return 1;
return nodesAtLevel(root->left, level - 1) + nodesAtLevel(root->right, level - 1);
}
// 计算二叉树的最大宽度(即最大层深)
int treeWidth(TreeNode* root) {
if (root == NULL) return 0;
int maxDepth = 0;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int size = q.size();
maxDepth = MAX(maxDepth, size); // 更新最大宽度
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);
}
}
return maxDepth;
}
```
以上代码中,`MAX`函数代表取两个数中的较大者,可以根据实际需要自定义。使用这个结构和函数,你可以很容易地在给定的二叉树上获取所需的统计信息。
阅读全文