用C语言写设二叉树中每个结点的元素均为一个字符,按先序遍历的顺序建立二叉链表,编写三个递归算法对二叉树的结点(度为0、1、2)个数进行统计。 输入格式: 多组数据。每组数据一行,为二叉树的前序序列(序列中元素为‘0’时,表示该结点为空)。当输入只有一个“0”时,输入结束。 输出格式: 每组数据输出一行,每行三个数分别为二叉树的度为0、1、2的结点个数。每两个数用空格分隔。
时间: 2023-06-16 10:04:05 浏览: 127
设一棵二叉树以二叉链表表示,试编写有关二叉树的递归算法
5星 · 资源好评率100%
以下是C语言代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct BiTNode {
char data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
void CreateBiTree(BiTree *T) {
char c;
scanf("%c", &c);
if (c == '0') {
*T = NULL;
} else {
*T = (BiTree) malloc(sizeof(BiTNode));
(*T)->data = c;
CreateBiTree(&(*T)->lchild);
CreateBiTree(&(*T)->rchild);
}
}
int count_0(BiTree T) {
if (T == NULL) {
return 0;
}
if (T->lchild == NULL && T->rchild == NULL) {
return 1;
}
return count_0(T->lchild) + count_0(T->rchild);
}
int count_1(BiTree T) {
if (T == NULL) {
return 0;
}
if (T->lchild == NULL && T->rchild == NULL) {
return 0;
}
if (T->lchild != NULL && T->rchild != NULL) {
return count_1(T->lchild) + count_1(T->rchild);
}
return count_1(T->lchild) + count_1(T->rchild) + 1;
}
int count_2(BiTree T) {
if (T == NULL) {
return 0;
}
if (T->lchild != NULL && T->rchild != NULL) {
return count_2(T->lchild) + count_2(T->rchild) + 1;
}
return count_2(T->lchild) + count_2(T->rchild);
}
int main() {
BiTree T;
while (1) {
CreateBiTree(&T);
if (T == NULL) {
break;
}
printf("%d %d %d\n", count_0(T), count_1(T), count_2(T));
}
return 0;
}
```
解析:
代码中的 `CreateBiTree` 函数用于创建二叉树,输入前序序列,按照先序遍历的顺序建立二叉链表。输入字符为 `'0'` 时,表示该结点为空。
代码中的 `count_0` 函数用于统计二叉树中度为0的结点个数。如果当前结点为空,则返回0;如果当前结点为叶子结点,则返回1;否则递归遍历当前结点的左右子树。
代码中的 `count_1` 函数用于统计二叉树中度为1的结点个数。如果当前结点为空,则返回0;如果当前结点为叶子结点,则返回0;如果当前结点的左右子树均不为空,则返回递归遍历当前结点的左右子树的度为1结点个数之和;否则返回递归遍历当前结点的左右子树的度为1结点个数之和加1。
代码中的 `count_2` 函数用于统计二叉树中度为2的结点个数。如果当前结点为空,则返回0;如果当前结点的左右子树均不为空,则返回递归遍历当前结点的左右子树的度为2结点个数之和加1;否则返回递归遍历当前结点的左右子树的度为2结点个数之和。
主函数中,不断创建二叉树并统计二叉树中度为0、1、2的结点个数,并输出结果。当输入字符为 `'0'` 时,结束输入并退出程序。
阅读全文