c++计算二叉树的结点数
时间: 2023-12-20 19:06:24 浏览: 34
计算二叉树的结点数可以使用递归的方法,对于每个节点,它的结点数为左子树的结点数加上右子树的结点数再加上1(因为它本身也是一个节点)。下面是一个示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int value;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
int countNodes(TreeNode *root) {
if (root == NULL) {
return 0;
}
int leftCount = countNodes(root->left);
int rightCount = countNodes(root->right);
return leftCount + rightCount + 1;
}
int main() {
// 构造一棵二叉树
TreeNode *root = (TreeNode*)malloc(sizeof(TreeNode));
root->value = 1;
root->left = (TreeNode*)malloc(sizeof(TreeNode));
root->left->value = 2;
root->left->left = (TreeNode*)malloc(sizeof(TreeNode));
root->left->left->value = 4;
root->left->left->left = NULL;
root->left->left->right = NULL;
root->left->right = (TreeNode*)malloc(sizeof(TreeNode));
root->left->right->value = 5;
root->left->right->left = NULL;
root->left->right->right = NULL;
root->right = (TreeNode*)malloc(sizeof(TreeNode));
root->right->value = 3;
root->right->left = NULL;
root->right->right = NULL;
// 计算结点数
int count = countNodes(root);
printf("The number of nodes in the binary tree is %d\n", count);
// 释放内存
free(root->left->left);
free(root->left->right);
free(root->right);
free(root->left);
free(root);
return 0;
}
```
输出:
```
The number of nodes in the binary tree is 5
```