以二叉链表作为二叉树的存储结构,用C语言编写用层次顺序遍历二叉树的方法,统计树中度为1 的结点个数。
时间: 2023-06-14 07:06:51 浏览: 131
二叉树的层次遍历可以用队列来实现,具体过程如下:
1. 将根节点入队;
2. 当队列不为空时,弹出队首元素,访问该节点;
3. 如果该节点有左孩子,将左孩子入队;
4. 如果该节点有右孩子,将右孩子入队;
5. 重复步骤2-4,直到队列为空。
统计度为1的结点个数,可以在层次遍历时判断当前节点是否是度为1的节点,如果是,则计数器加1。
以下是完整的代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
// 二叉树结点结构体
typedef struct Node {
char data;
struct Node *left;
struct Node *right;
} Node;
// 队列结构体
typedef struct Queue {
Node **data;
int front;
int rear;
} Queue;
// 初始化队列
void initQueue(Queue *queue, int maxSize) {
queue->data = (Node**)malloc(sizeof(Node*) * maxSize);
queue->front = queue->rear = 0;
}
// 入队
void enqueue(Queue *queue, Node *node) {
queue->data[queue->rear++] = node;
}
// 出队
Node *dequeue(Queue *queue) {
return queue->data[queue->front++];
}
// 判断队列是否为空
int isEmpty(Queue *queue) {
return queue->front == queue->rear;
}
// 层次遍历二叉树并统计度为1的节点个数
int levelOrder(Node *root) {
if (root == NULL) {
return 0;
}
int count = 0;
Queue queue;
initQueue(&queue, 100);
enqueue(&queue, root);
while (!isEmpty(&queue)) {
Node *node = dequeue(&queue);
// 访问该节点
printf("%c ", node->data);
// 统计度为1的结点个数
if ((node->left == NULL && node->right != NULL) || (node->left != NULL && node->right == NULL)) {
count++;
}
// 将左右孩子入队
if (node->left != NULL) {
enqueue(&queue, node->left);
}
if (node->right != NULL) {
enqueue(&queue, node->right);
}
}
return count;
}
// 构建二叉树
Node *buildTree() {
Node *root = (Node*)malloc(sizeof(Node));
root->data = 'A';
Node *nodeB = (Node*)malloc(sizeof(Node));
nodeB->data = 'B';
Node *nodeC = (Node*)malloc(sizeof(Node));
nodeC->data = 'C';
Node *nodeD = (Node*)malloc(sizeof(Node));
nodeD->data = 'D';
Node *nodeE = (Node*)malloc(sizeof(Node));
nodeE->data = 'E';
Node *nodeF = (Node*)malloc(sizeof(Node));
nodeF->data = 'F';
Node *nodeG = (Node*)malloc(sizeof(Node));
nodeG->data = 'G';
root->left = nodeB;
root->right = nodeC;
nodeB->left = nodeD;
nodeB->right = nodeE;
nodeC->left = NULL;
nodeC->right = nodeF;
nodeD->left = nodeG;
nodeD->right = NULL;
nodeE->left = NULL;
nodeE->right = NULL;
nodeF->left = NULL;
nodeF->right = NULL;
nodeG->left = NULL;
nodeG->right = NULL;
return root;
}
int main() {
Node *root = buildTree();
printf("层次遍历结果:");
int count = levelOrder(root);
printf("\n度为1的结点个数:%d\n", count);
return 0;
}
```
输出结果为:
```
层次遍历结果:A B C D E F G
度为1的结点个数:2
```
阅读全文