以二叉链表作为二叉树的存储结构,在键盘上输入一个字符串 ①统计二叉树的叶子结点个数。 ②交换二叉树中每个结点的左孩子和右孩子,最后按先序遍历输出。 ③计算二叉树的最大宽度(所有层中结点个数的最大值)。 ④用层次遍历二叉树的方法,统计树中度为 1 的结点个数。C语言
时间: 2024-02-11 07:05:06 浏览: 56
好的,让我用 C 语言来回答你的问题。
1. 统计二叉树的叶子结点个数
```c
#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
int count_leaves(struct TreeNode *root) {
if (!root) {
return 0;
}
if (!root->left && !root->right) {
return 1;
}
return count_leaves(root->left) + count_leaves(root->right);
}
```
2. 交换二叉树中每个结点的左孩子和右孩子,最后按先序遍历输出。
```c
struct TreeNode *swap_tree(struct TreeNode *root) {
if (!root) {
return NULL;
}
struct TreeNode *tmp = root->left;
root->left = root->right;
root->right = tmp;
swap_tree(root->left);
swap_tree(root->right);
return root;
}
void preorder_traversal(struct TreeNode *root) {
if (!root) {
return;
}
printf("%d\n", root->val);
preorder_traversal(root->left);
preorder_traversal(root->right);
}
```
3. 计算二叉树的最大宽度
```c
int max_width(struct TreeNode *root) {
if (!root) {
return 0;
}
int max_width = 1;
struct TreeNode **queue = (struct TreeNode **)malloc(sizeof(struct TreeNode *) * 1000);
int front = 0, rear = 0;
queue[rear++] = root;
while (front < rear) {
int level_size = rear - front;
if (level_size > max_width) {
max_width = level_size;
}
for (int i = 0; i < level_size; i++) {
struct TreeNode *node = queue[front++];
if (node->left) {
queue[rear++] = node->left;
}
if (node->right) {
queue[rear++] = node->right;
}
}
}
free(queue);
return max_width;
}
```
4. 用层次遍历二叉树的方法,统计树中度为 1 的结点个数。
```c
int count_degree_1_nodes(struct TreeNode *root) {
if (!root) {
return 0;
}
int count = 0;
struct TreeNode **queue = (struct TreeNode **)malloc(sizeof(struct TreeNode *) * 1000);
int front = 0, rear = 0;
queue[rear++] = root;
while (front < rear) {
struct TreeNode *node = queue[front++];
int degree = 0;
if (node->left) {
queue[rear++] = node->left;
degree++;
}
if (node->right) {
queue[rear++] = node->right;
degree++;
}
if (degree == 1) {
count++;
}
}
free(queue);
return count;
}
```
注意,在 C 语言中,我们需要手动管理内存,需要使用 `malloc` 和 `free` 函数来分配和释放内存。另外,在使用队列时,我们需要使用数组来模拟队列的操作。
希望这些代码能够帮助到你。如果你还有其他问题,请随时提出。