7-29 统计二叉树中具有度为1的结点数目

根据带虚结点的先序序列建立二叉树，再统计输出二叉树中具有度为1的结点数目。

输入格式:

测试数据有多组，处理到文件尾。每组测试数据在一行中输入一个字符串（不含空格且长度不超过80），表示二叉树的先序遍历序列，其中字符*表示虚结点（对应的子树为空）。

输出格式:

对于每组测试，对所建立的二叉树，输出该二叉树中具有度为1的结点数目。输出格式为：“num: d”,其中d为二叉树中具有度为1的结点数目。

输入样例:

HDA**C*B**GF*E***
A*B*C*D*E*F**

输出样例:

num: 3
num: 5

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

#define _CRT_SECURE_NO_WARNINGS
#include 
#include 
typedef struct TNode* Position;
typedef Position BinTree;
struct TNode {
    char Data;
    BinTree Left;
    BinTree Right;
};
int count = 0;
int index = 0;
char s[80];
void CreatBinTree(BinTree* BT) {
    char val;
    val=s[index++];
    if (val == '*') {
        *BT = NULL;
        return;
    }
    else {
        *BT = (BinTree)malloc(sizeof(struct TNode));
        (*BT)->Data = val;
        (*BT)->Left = (*BT)->Right = NULL;
        CreatBinTree(&(*BT)->Left);
        CreatBinTree(&(*BT)->Right);
    }
}
void InorderTraversal(BinTree BT) {
    if (BT) {
        if ((!BT->Left && BT->Right) || (BT->Left && !BT->Right))
            count++;
        InorderTraversal(BT->Left);
        InorderTraversal(BT->Right);
    }
}
void BTreeSetNull(BinTree* BT) {
    if (*BT == NULL) {
        return;
    }
    BTreeSetNull(&(*BT)->Left);
    BTreeSetNull(&(*BT)->Right);
    free(*BT);
}
int main() {
    while (~scanf("%s",s)) {
        BinTree BT = (BinTree)malloc(sizeof(struct TNode));
        CreatBinTree(&BT);
        InorderTraversal(BT);
        printf("num: %dn", count);
        index = 0;
        BTreeSetNull(&BT);
        count = 0;
    }
    system("pause");
    return 0;
}