已知二叉树采用二叉链存储结构存储,请用C语言设计一个算法,计算一棵给定二叉树b中的所有分支结点个数。二叉树为“A(B(D,E(G,H)),C(,F(I)))”
时间: 2024-11-09 10:29:08 浏览: 41
为了计算一棵给定二叉树中所有的分支节点(非叶子节点)个数,我们可以采用递归的方式遍历二叉树。以下是使用C语言的一个简单算法:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点结构体
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 计算分支节点的辅助函数
int countBranches(TreeNode* node) {
if (node == NULL) {
return 0; // 空节点没有分支
} else {
// 如果左、右孩子都存在,则是一个分支节点
return 1 + countBranches(node->left) + countBranches(node->right);
}
}
// 主函数,接收二叉树根节点
int main(int argc, char** argv) {
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = 'A'; // 根据给定的二叉树表示,这里设置根节点值
root->left = (TreeNode*)malloc(sizeof(TreeNode)); // 初始化左右子节点
root->left->val = 'B';
root->left->left = (TreeNode*)malloc(sizeof(TreeNode));
root->left->left->val = 'D';
// ... 同理继续构建剩余的节点
int branchCount = countBranches(root);
printf("给定二叉树中有 %d 个分支节点。\n", branchCount);
// 清理内存
free(root->left->left); // 和其他子节点
free(root->left);
free(root);
return 0;
}
```
在这个例子中,我们首先创建了一个`countBranches`函数,它接受一个节点作为参数并递归地检查它的左右子节点。如果节点为空,则返回0;否则,它返回1(当前节点本身是一个分支)加上其左右子节点分支的计数。
在`main`函数中,我们创建了对应的二叉树结构,并通过`countBranches`函数计算总的分支节点数。最后别忘了释放动态分配的内存,避免内存泄漏。
阅读全文
相关推荐


















