首页 / 算法 / DS二叉树--叶子数量

DS二叉树--叶子数量

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了DS二叉树--叶子数量，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1386字，纯文字阅读大概需要2分钟。

内容图文

题目描述

 

计算一颗二叉树包含的叶子结点数量。

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

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

 

 

 

输入

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

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

 

 

输出

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

样例输入

3 AB0C00D00 AB00C00 ABC00D00E00

样例输出

2 2 3

提示

 

  
#include<iostream>
#include<string>
#include<queue>
usingnamespace std;
class BiTreeNode
{
public:
    char data;
    BiTreeNode *Left;
    BiTreeNode *Right;
    BiTreeNode()
    {
        Left=NULL;
        Right=NULL;
    }
    ~BiTreeNode()
    {
        delete Left;
        delete Right;
    }
};
  
class BiTree
{
public:
    BiTreeNode *Root;
    int pos;
    string strTree;
    BiTree(string str)
    {
        pos=0;
        strTree=str;
        Root=CreateBiTree();
    }
    BiTreeNode *CreateBiTree()
    {
        char ch=strTree[pos];
        pos++;
        if(ch==‘0‘)
        {
            return NULL;
        }
        else
        {
            BiTreeNode *T;
            T=new BiTreeNode();
            T->data=ch;
            T->Left=CreateBiTree();
            T->Right=CreateBiTree();
            return T;
        }
    }
    int countleaves()
    {
        int count=0;
        queue<BiTreeNode*>Q;
        if(Root==NULL)
            return0;
        Q.push(Root);
        while(!Q.empty())
        {
            int flag=0;
            BiTreeNode *temp=Q.front();
            if(temp->Left!=NULL)
            {
                flag++;
                Q.push(temp->Left);
            }
            if(temp->Right!=NULL)
            {
                flag++;
                Q.push(temp->Right);
            }
            Q.pop();
            if(flag==0)
                count++;
        }
        return count;
    }
};
  
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        string str;
        cin>>str;
        BiTree tree(str);
        cout<<tree.countleaves()<<endl;
    }
    return0;
}

 

原文：https://www.cnblogs.com/SZU-DS-wys/p/12180794.html

内容总结

以上是互联网集市为您收集整理的DS二叉树--叶子数量全部内容，希望文章能够帮你解决DS二叉树--叶子数量所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1083658.html

来源：【匿名】