DS二叉树--叶子数量

57 阅读 0 评论 38 点赞

我是靠谱客的博主炙热航空，最近开发中收集的这篇文章主要介绍DS二叉树--叶子数量，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题解

这里叶子数不能设置为函数PreOrder的形参然后返回，因为PreOrder是一个递归函数，在每一层PreOrder中的LeafNum都不是同一个变量，这里设为形参只能做到外层传到内层，而内层传不到外层，当内层递归结束后最外层中的LeafNum还是初始值，内层PreOrder改变的只是内层中LeafNum的值。
解决办法是把LeafNum设为全局变量，这样每层操作的就都是同一个变量，但要注意每组测试用例结束后要把LeafNum置0，不然LeafNum会叠加。

题目

问题 B: DS二叉树--叶子数量
时间限制: 1 Sec  内存限制: 128 MB
提交: 477  解决: 362
[提交][状态][讨论版]
题目描述
计算一颗二叉树包含的叶子结点数量。

提示：叶子是指它的左右孩子为空。

建树方法采用“先序遍历+空树用0表示”的方法，即给定一颗二叉树的先序遍历的结果为AB0C00D00，其中空节点用字符‘0’表示。则该树的逻辑结构如下图。

在这里插入图片描述

输入
第一行输入一个整数t，表示有t个测试数据

第二行起输入二叉树先序遍历的结果，空树用字符‘0’表示，输入t行

输出
逐行输出每个二叉树的包含的叶子数量

样例输入
3
AB0C00D00
AB00C00
ABC00D00E00
样例输出
2
2
3

代码1（AC）

#include <iostream>
using namespace std;

int LeafNum = 0;

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

typedef struct BiTree
{
    BiTNode *root;
} BiTree;

void CreateTree(BiTNode *&p)
{
    char c;
    cin>>c;
    if(c!='0')
    {
        p = new BiTNode;
        p->data = c;
        CreateTree(p->lchild);
        CreateTree(p->rchild);
    }
    else
        p = NULL;
}

void PreOrder(BiTNode *p)
{
    if(p)
    {
        if(!p->lchild && !p->rchild)
            LeafNum++;
        PreOrder(p->lchild);
        PreOrder(p->rchild);
    }
}

int main(void)
{
    int t;
    cin>>t;
    while(t--)
    {
        BiTree myTree;
        CreateTree(myTree.root);
        PreOrder(myTree.root);
        cout<<LeafNum<<endl;
        LeafNum = 0;
    }
    return 0;
}

代码2（WA）

#include <iostream>
using namespace std;

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

typedef struct BiTree
{
    BiTNode *root;
} BiTree;

void CreateTree(BiTNode *&p)
{
    char c;
    cin>>c;
    if(c!='0')
    {
        p = new BiTNode;
        p->data = c;
        CreateTree(p->lchild);
        CreateTree(p->rchild);
    }
    else
        p = NULL;
}

int PreOrder(BiTNode *p, int LeafNum)
{
    if(p)
    {
        if(!p->lchild && !p->rchild)
            LeafNum++;
        PreOrder(p->lchild, LeafNum);
        PreOrder(p->rchild, LeafNum);
    }
    return LeafNum;
}

int main(void)
{
    int t;
    cin>>t;
    while(t--)
    {
        BiTree myTree;
        CreateTree(myTree.root);
        int LeafNum = 0;
        cout<<PreOrder(myTree.root, LeafNum)<<endl;
    }
    return 0;
}