c语言实现,以二叉链表作为二叉树的存储结构,编写用层次顺序遍历二叉树的方法,统计树中度为1 的结点个数。
时间: 2023-06-14 11:06:19 浏览: 135
以下是C语言实现,使用队列实现层次遍历二叉树,并统计度为1的结点个数:
```c
#include <stdio.h>
#include <stdlib.h>
// 二叉树结点的定义
typedef struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 队列结点的定义
typedef struct QueueNode {
TreeNode* data;
struct QueueNode* next;
} QueueNode;
// 队列的定义
typedef struct Queue {
QueueNode* head;
QueueNode* tail;
} Queue;
// 初始化队列
void initQueue(Queue* queue) {
queue->head = NULL;
queue->tail = NULL;
}
// 判断队列是否为空
int isQueueEmpty(Queue* queue) {
return queue->head == NULL;
}
// 入队
void enqueue(Queue* queue, TreeNode* data) {
QueueNode* node = (QueueNode*)malloc(sizeof(QueueNode));
node->data = data;
node->next = NULL;
if (isQueueEmpty(queue)) {
queue->head = node;
queue->tail = node;
} else {
queue->tail->next = node;
queue->tail = node;
}
}
// 出队
TreeNode* dequeue(Queue* queue) {
if (isQueueEmpty(queue)) {
return NULL;
}
TreeNode* data = queue->head->data;
QueueNode* temp = queue->head;
queue->head = queue->head->next;
free(temp);
if (queue->head == NULL) {
queue->tail = NULL;
}
return data;
}
// 层次遍历二叉树
void levelOrderTraversal(TreeNode* root, int* count) {
if (root == NULL) {
return;
}
Queue queue;
initQueue(&queue);
enqueue(&queue, root);
while (!isQueueEmpty(&queue)) {
TreeNode* node = dequeue(&queue);
if (node->left != NULL) {
enqueue(&queue, node->left);
}
if (node->right != NULL) {
enqueue(&queue, node->right);
}
// 统计度为1的结点个数
if ((node->left == NULL && node->right != NULL) || (node->left != NULL && node->right == NULL)) {
(*count)++;
}
}
}
// 创建二叉树
TreeNode* createTree() {
int value;
printf("请输入结点的值(-1表示空结点):");
scanf("%d", &value);
if (value == -1) {
return NULL;
}
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->data = value;
node->left = createTree();
node->right = createTree();
return node;
}
int main() {
TreeNode* root = createTree();
int count = 0;
levelOrderTraversal(root, &count);
printf("度为1的结点个数为:%d\n", count);
return 0;
}
```
注意:此代码中未进行内存释放处理,实际使用时需要注意内存泄漏问题。
阅读全文