C语言求二叉树的个数
时间: 2024-01-13 08:06:36 浏览: 21
假设二叉树有 $n$ 个节点,那么可以通过以下步骤求出二叉树的个数:
1. 从 $n$ 个节点中选出一个作为根节点,有 $n$ 种选法;
2. 将剩下的 $n-1$ 个节点分成左子树和右子树,假设左子树有 $i$ 个节点,右子树有 $n-1-i$ 个节点,那么左子树和右子树的组合方式共有 $f(i) \times f(n-1-i)$ 种,其中 $f(i)$ 和 $f(n-1-i)$ 分别表示左子树和右子树的个数;
3. 对于每个根节点,都可以得到不同的左右子树组合方式,所以最终二叉树的个数为所有根节点的组合之和,即 $f(n)=\sum_{i=0}^{n-1}f(i) \times f(n-1-i)$。
根据以上思路,可以使用递归的方式来实现求解二叉树个数的函数,示例代码如下:
```c
int countTrees(int n) {
if (n == 0) {
return 1;
}
int count = 0;
for (int i = 0; i < n; i++) {
count += countTrees(i) * countTrees(n - 1 - i);
}
return count;
}
```
其中,当二叉树节点个数为 0 时,返回 1,表示空树的个数为 1。否则,遍历每个节点作为根节点的情况,将左子树个数和右子树个数相乘,并将所有根节点的组合之和累加起来,即可得到二叉树的个数。
相关问题
c语言统计二叉树中结点的个数
统计二叉树中结点的个数可以使用递归的方法进行求解,具体实现如下:
```c
#include <stdio.h>
#include <stdlib.h>
// 二叉树结点结构体
typedef struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 创建二叉树
TreeNode* createBinaryTree() {
int data;
scanf("%d", &data);
if (data == -1) {
return NULL;
}
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->data = data;
root->left = createBinaryTree();
root->right = createBinaryTree();
return root;
}
// 统计二叉树中结点的个数
int countNodes(TreeNode* root) {
if (root == NULL) {
return 0;
}
return 1 + countNodes(root->left) + countNodes(root->right);
}
int main() {
printf("请输入二叉树的结点(-1表示空结点):\n");
TreeNode* root = createBinaryTree();
printf("二叉树中结点的个数为:%d\n", countNodes(root));
return 0;
}
```
输入样例:
```
请输入二叉树的结点(-1表示空结点):
1 2 4 -1 -1 5 -1 -1 3 -1 -1
```
输出样例:
```
二叉树中结点的个数为:5
```
C语言求二叉树中度为1的结点个数
要求二叉树中度为1的节点个数,可以通过遍历二叉树的方式来实现。以下是一个示例的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树结点结构体
typedef struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 创建一个新的二叉树结点
TreeNode* createNode(int value) {
TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// 递归方式遍历二叉树,统计度为1的结点个数
int countNodesWithDegreeOne(TreeNode* root) {
if (root == NULL) {
return 0;
}
int count = 0;
// 当前结点的度为1,判断左子树和右子树是否为空
if ((root->left == NULL && root->right != NULL) || (root->left != NULL && root->right == NULL)) {
count++;
}
// 递归遍历左子树和右子树
count += countNodesWithDegreeOne(root->left);
count += countNodesWithDegreeOne(root->right);
return count;
}
int main() {
// 创建一个示例二叉树
TreeNode* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
root->right->left = createNode(6);
// 统计度为1的结点个数
int count = countNodesWithDegreeOne(root);
printf("度为1的结点个数为:%d\n", count);
return 0;
}
```
在上面的示例代码中,我们使用了递归的方式遍历二叉树,并在遍历过程中统计度为1的结点个数。对于每个结点,我们检查其左子树和右子树是否为空,如果其中一个为空而另一个不为空,则该结点的度为1。最后返回统计的个数作为结果。在主函数中,我们创建了一个示例二叉树,并输出度为1的结点个数。