用c语言写以二叉链表作为二叉树的存储结构,编写用层次顺序遍历二叉树的方法,统计树中度为1 的结点个数。
时间: 2023-06-13 17:09:17 浏览: 103
二叉树的二叉链表存储结构定义如下:
```c
typedef struct BiTNode {
int data; // 数据域
struct BiTNode *lchild, *rchild; // 左右孩子指针
} BiTNode, *BiTree;
```
其中 `data` 为结点的数据域,`lchild` 和 `rchild` 分别为左右孩子结点的指针。当一个结点没有左孩子或右孩子时,对应指针的值为 `NULL`。
接下来是层次遍历的代码实现:
```c
void LevelOrder(BiTree root) {
if (root == NULL) {
return;
}
// 定义一个队列,用于存储每一层的结点
Queue queue;
InitQueue(&queue);
// 将根结点入队
EnQueue(&queue, root);
while (!IsEmpty(queue)) {
// 取出队头结点
BiTree node = DeQueue(&queue);
printf("%d ", node->data);
// 如果左右孩子不为空,分别入队
if (node->lchild != NULL) {
EnQueue(&queue, node->lchild);
}
if (node->rchild != NULL) {
EnQueue(&queue, node->rchild);
}
}
}
```
其中 `Queue` 是一个队列结构体,其中包含一个数组和队头、队尾指针等信息,这里不再赘述。
最后是统计度为1的结点个数的代码实现:
```c
int CountDegree1(BiTree root) {
if (root == NULL) {
return 0;
}
int count = 0;
// 如果当前结点的度为1,统计个数加1
if ((root->lchild == NULL && root->rchild != NULL) ||
(root->lchild != NULL && root->rchild == NULL)) {
count++;
}
// 递归处理左右子树
count += CountDegree1(root->lchild);
count += CountDegree1(root->rchild);
return count;
}
```
以上就是用 C 语言实现二叉树的存储结构和层次遍历,以及统计度为1的结点个数的方法。
阅读全文