以二叉链表作为二叉树的存储结构,用c语言编写用层次顺序遍历二叉树的方法,统计树中度为1 的结点个数。
时间: 2023-06-16 22:02:48 浏览: 100
以下是用c语言编写的层次顺序遍历二叉树并统计度为1的结点个数的方法:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树的结点结构
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 定义队列结构
typedef struct Queue {
TreeNode *data;
struct Queue *next;
} Queue;
// 入队
void enqueue(Queue **rear, TreeNode *node) {
Queue *newNode = (Queue *)malloc(sizeof(Queue));
newNode->data = node;
newNode->next = NULL;
if (*rear == NULL) {
*rear = newNode;
} else {
(*rear)->next = newNode;
*rear = newNode;
}
}
// 出队
TreeNode *dequeue(Queue **front) {
if (*front == NULL) {
return NULL;
} else {
TreeNode *node = (*front)->data;
Queue *temp = *front;
*front = (*front)->next;
free(temp);
return node;
}
}
// 层次顺序遍历二叉树并统计度为1的结点个数
int levelOrder(TreeNode *root) {
if (root == NULL) {
return 0;
}
Queue *front = NULL, *rear = NULL;
enqueue(&rear, root);
int count = 0;
while (front != NULL) {
TreeNode *node = dequeue(&front);
if (node->left == NULL && node->right != NULL) {
count++;
} else if (node->left != NULL && node->right == NULL) {
count++;
}
if (node->left != NULL) {
enqueue(&rear, node->left);
}
if (node->right != NULL) {
enqueue(&rear, node->right);
}
}
return count;
}
int main() {
// 创建二叉树
TreeNode *root = (TreeNode *)malloc(sizeof(TreeNode));
root->val = 1;
root->left = (TreeNode *)malloc(sizeof(TreeNode));
root->left->val = 2;
root->left->left = NULL;
root->left->right = (TreeNode *)malloc(sizeof(TreeNode));
root->left->right->val = 4;
root->left->right->left = NULL;
root->left->right->right = NULL;
root->right = (TreeNode *)malloc(sizeof(TreeNode));
root->right->val = 3;
root->right->left = NULL;
root->right->right = NULL;
// 层次顺序遍历二叉树并统计度为1的结点个数
int count = levelOrder(root);
printf("度为1的结点个数:%d\n", count);
return 0;
}
```
这里使用了队列来实现层次顺序遍历,统计度为1的结点个数时,只需要判断当前结点的左右子树是否存在即可。
阅读全文