根据带虚结点的先序序列建立二叉树,再统计输出二叉树中具有度为1的结点数目。 输入格式: 测试数据有多组,处理到文件尾。每组测试数据在一行中输入一个字符串(不含空格且长度不超过80),表示二叉树的先序遍历序列,其中字符*表示虚结点(对应的子树为空)。 输出格式: 对于每组测试,对所建立的二叉树,输出该二叉树中具有度为1的结点数目。输出格式为:“num: d”,其中d为二叉树中具有度为1的结点数目。 输入样例: HDA**C*B**GF*E*** A*B*C*D*E*F** 输出样例: num: 3 num: 5
时间: 2023-07-23 14:42:13 浏览: 64
以下是使用C语言编写的代码,实现根据带虚结点的先序序列建立二叉树,并统计输出二叉树中具有度为1的结点数目:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct TreeNode {
char data;
struct TreeNode *lchild, *rchild;
} TreeNode, *Tree;
// 创建二叉树
Tree CreateTree(char *str, int *pos) {
char ch = str[(*pos)++];
if (ch == '*') {
return NULL;
}
Tree T = (Tree)malloc(sizeof(TreeNode));
T->data = ch;
T->lchild = CreateTree(str, pos);
T->rchild = CreateTree(str, pos);
return T;
}
// 统计度为1的结点数目
int CountDegreeOneNodes(Tree T) {
if (T == NULL) {
return 0;
} else if (T->lchild == NULL && T->rchild != NULL) {
return 1 + CountDegreeOneNodes(T->rchild);
} else if (T->lchild != NULL && T->rchild == NULL) {
return 1 + CountDegreeOneNodes(T->lchild);
} else {
return CountDegreeOneNodes(T->lchild) + CountDegreeOneNodes(T->rchild);
}
}
int main() {
char str[100];
while (scanf("%s", str) != EOF) {
int pos = 0;
Tree T = CreateTree(str, &pos);
printf("num: %d\n", CountDegreeOneNodes(T));
}
return 0;
}
```
使用方法:
运行程序后,输入多组带虚结点的先序序列,例如:`HDA**C*B**GF*E***`和`A*B*C*D*E*F**`,其中字符`*`表示虚结点(对应的子树为空)。程序会每次读入一个字符串,根据该字符串建立二叉树,统计输出二叉树中具有度为1的结点数目,输出格式为:“num: d”,其中d为二叉树中具有度为1的结点数目。