用c语言用递归的方法统计二叉树的结点个数同时交换二叉树每个结点的左孩子和右孩子
时间: 2023-11-14 11:07:20 浏览: 40
可以使用递归函数来遍历二叉树,并统计结点个数和交换左右孩子。
下面是一个示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树结点结构体
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
// 统计二叉树结点个数的递归函数
int countNodes(struct TreeNode* root) {
if (root == NULL) {
return 0;
}
return 1 + countNodes(root->left) + countNodes(root->right);
}
// 交换二叉树结点左右孩子的递归函数
struct TreeNode* invertTree(struct TreeNode* root) {
if (root == NULL) {
return NULL;
}
struct TreeNode* tmp = root->left;
root->left = invertTree(root->right);
root->right = invertTree(tmp);
return root;
}
// 创建二叉树,并返回根结点
struct TreeNode* createTree() {
struct TreeNode* root = (struct TreeNode*) malloc(sizeof(struct TreeNode));
root->val = 1;
root->left = (struct TreeNode*) malloc(sizeof(struct TreeNode));
root->left->val = 2;
root->right = (struct TreeNode*) malloc(sizeof(struct TreeNode));
root->right->val = 3;
root->left->left = (struct TreeNode*) malloc(sizeof(struct TreeNode));
root->left->left->val = 4;
root->left->right = (struct TreeNode*) malloc(sizeof(struct TreeNode));
root->left->right->val = 5;
root->right->left = (struct TreeNode*) malloc(sizeof(struct TreeNode));
root->right->left->val = 6;
root->right->right = (struct TreeNode*) malloc(sizeof(struct TreeNode));
root->right->right->val = 7;
return root;
}
// 遍历二叉树的递归函数
void traverseTree(struct TreeNode* root) {
if (root == NULL) {
return;
}
printf("%d ", root->val);
traverseTree(root->left);
traverseTree(root->right);
}
int main() {
struct TreeNode* root = createTree();
printf("Original binary tree:\n");
traverseTree(root);
printf("\n");
int count = countNodes(root);
printf("Number of nodes in binary tree: %d\n", count);
root = invertTree(root);
printf("Inverted binary tree:\n");
traverseTree(root);
printf("\n");
return 0;
}
```
该程序会输出如下结果:
```
Original binary tree:
1 2 4 5 3 6 7
Number of nodes in binary tree: 7
Inverted binary tree:
1 3 7 6 2 5 4
```
在上面的示例中,我们使用了递归函数 `countNodes` 来统计二叉树的结点个数,使用递归函数 `invertTree` 来交换二叉树每个结点的左孩子和右孩子。同时,我们也定义了一个 `createTree` 函数来创建二叉树,以及一个 `traverseTree` 函数来遍历二叉树。