PTA（树和二叉树）1-1 统计度为1的结点数

1-1 统计度为1的结点数

分数 3

作者 黄龙军

单位 绍兴文理学院

要求实现函数，统计并返回二叉树中的度为1的结点数。二叉树采用二叉链表存储，结点结构如下：

1
2
3
4
struct BiTNode {               // 结点结构
    char data;                 // 结点数据域
    BiTNode *lchild, *rchild;  // 左、右孩子指针
};

函数接口定义：

1
int CountSingle(BiTNode *T);

其中参数 T是指向二叉树根结点的指针。

裁判测试程序样例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<iostream>
#include<string>
using namespace std;

struct BiTNode {
    char data;
    BiTNode *lchild, *rchild;
};

int CountSingle(BiTNode *T);         // 统计并返回度为1的结点数
BiTNode *CreateBiTree(string &s);  // 创建二叉树，s存放带虚结点的先序遍历序列

int main() {
    string s;
    while(cin>>s) {
        BiTNode* root=CreateBiTree(s);
        cout<<CountSingle(root)<<endl;
    }    
    return 0;
}

// 请在此处填写答案

// 按字符串s创建二叉树，返回根结点指针
BiTNode *CreateBiTree(string &s) {
    if(s[0]=='*') {
        s=s.substr(1);
        return NULL; 
    }
    BiTNode *p=new BiTNode;
    p->data=s[0];
    s=s.substr(1);
    p->lchild=CreateBiTree(s);
    p->rchild=CreateBiTree(s);
    return p;
}

输入样例：

1
2
HDA**C*B**GF*E***
-+a**xb**-c**d**/e**f**

输出样例：

1
2
3
0

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int CountSingle(BiTNode *T) {
    if (T == NULL) { // 如果是空指针，则度为零，返回0
        return 0;
    }
    // 叶子节点
    if (T->lchild == NULL && T->rchild == NULL) { 
        return 0;
    }
    // 度为1的结点
    if ((T->lchild != NULL && T->rchild == NULL) || (T->lchild == NULL && T->rchild != NULL)) {
        return 1 + CountSingle(T->lchild) + CountSingle(T->rchild);
    }
    // 度为2的结点
    if (T->rchild != NULL && T->lchild != NULL) {
        return 0 + CountSingle(T->lchild) + CountSingle(T->rchild);
    }
}
  1. 空树情况：若树为空（T == NULL），度为 1 的节点数为 0。
  2. 叶子节点：若节点的左、右子树都为空（T->lchild == NULL && T->rchild == NULL），度为 0，不计数。
  3. 度为 1 的节点：若节点的左、右子树中恰好有一个不为空（(T->lchild != NULL && T->rchild == NULL) || (T->lchild == NULL && T->rchild != NULL)），则计数 1，并递归统计其非空子树的度为 1 节点数。
  4. 度为 2 的节点：若节点的左、右子树都不为空，不计数，但需递归统计左、右子树的度为 1 节点数。