7-3 求二叉树的叶子结点个数 (20分)

发表于 更新于 分类于 Disqus： 本文字数： 824 阅读时长 ≈ 1 分钟

以二叉链表作为二叉树的存储结构，求二叉树的叶子结点个数。

输入格式:

输入二叉树的先序序列。

提示：一棵二叉树的先序序列是一个字符串，若字符是‘#’,表示该二叉树是空树，否则该字符是相应结点的数据元素。

输出格式:

输出有两行：

第一行是二叉树的中序遍历序列；

第二行是二叉树的叶子结点个数。

输入样例:

ABC##DE#G##F###

输出样例:

CBEGDFA

3

需要三个函数：前序建立树，中序输出，计算叶子结点

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
37

//根据有#的前序遍历生成树
tree fcreate()
{
    tree t;
    char s;
    //按每个字符输入
    scanf("%c",&s);
    if(s=='#')return nullptr;
    else {
        t=(tree)malloc(sizeof(struct treenode));
        t->data = s;
        t->lchild = fcreate();
        t->rchild = fcreate();
        return t;
    }
}

//中序输出
void Inordertranverse(tree t)
{
    if(!t)return;
    Inordertranverse(t->lchild);
    cout<<t->data;
    Inordertranverse(t->rchild);
}

//计数树的根结点数
int count(tree t,int c)
{
    if(t) {
        if (t->lchild == nullptr && t->rchild == nullptr)c++;
        c=count(t->lchild, c);
        c=count(t->rchild, c);
    }
    return c;
}