用c语言写以二叉链表作为二叉树的存储结构,编写用层次顺序遍历二叉树的方法,统计树中度为1 的结点个数的完整代码
时间: 2023-06-13 21:09:13 浏览: 122
数据结构"采用二叉树链表作为存储结构"代码
以下是使用二叉链表作为二叉树存储结构,实现层次遍历并统计度为1结点个数的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *lchild, *rchild;
} Node, *Tree;
// 创建二叉树
void createTree(Tree *root) {
int data;
scanf("%d", &data);
if (data == -1) {
*root = NULL;
return;
}
*root = (Node *) malloc(sizeof(Node));
(*root)->data = data;
createTree(&(*root)->lchild);
createTree(&(*root)->rchild);
}
// 层次遍历并统计度为1结点个数
int levelOrder(Tree root) {
int count = 0;
Node **queue = (Node **) malloc(sizeof(Node *) * 100); // 初始化队列
int front = 0, rear = 0;
if (root) {
queue[rear++] = root;
}
while (front < rear) {
Node *node = queue[front++];
if (node->lchild && !node->rchild || !node->lchild && node->rchild) {
count++;
}
if (node->lchild) {
queue[rear++] = node->lchild;
}
if (node->rchild) {
queue[rear++] = node->rchild;
}
}
return count;
}
int main() {
Tree root = NULL;
printf("请输入二叉树的前序遍历序列,-1表示空结点:\n");
createTree(&root);
int count = levelOrder(root);
printf("度为1的结点个数为:%d\n", count);
return 0;
}
```
该代码中使用了队列实现层次遍历二叉树,同时在遍历过程中统计了度为1的结点个数。
阅读全文