已知二叉树采用二叉链存储结构存储,请设计一个算法,计算一棵给定二叉树b中的所有分支结点个数。C语言代码
时间: 2024-11-09 15:28:24 浏览: 40
在C语言中,我们可以使用递归的方式来计算二叉树中所有分支节点(即非叶子节点)的数量。这里提供一个简单的算法:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉链表节点结构体
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 计算分支节点的函数
int countBranchNodes(TreeNode* root) {
// 如果根节点为空,返回0
if (root == NULL) {
return 0;
}
// 如果根节点有左右子节点,则它是一个分支节点,计数加一
if (root->left != NULL || root->right != NULL) {
return 1 + countBranchNodes(root->left) + countBranchNodes(root->right);
} else {
// 如果根节点仅有一个子节点或者无子节点,它不是分支节点,计数不变
return countBranchNodes(root->left);
}
}
int main() {
// 创建示例二叉树
TreeNode* tree = // 根据实际二叉树构建
int branchCount = countBranchNodes(tree);
printf("二叉树中有 %d 个分支节点。\n", branchCount);
return 0;
}
```
在这个代码中,`countBranchNodes` 函数接受一个二叉树的根节点作为输入,并通过递归遍历每个节点,判断其是否有左或右子节点来确定是否为分支节点。
阅读全文