首页 > 其他分享 >[2004年NOIP普及组] FBI树

[2004年NOIP普及组] FBI树

时间:2022-08-15 21:33:59浏览次数:78  
标签:遍历 string NOIP cout substr length 2004 FBI postorder

[2004年NOIP普及组] FBI树

思路:运用递归。已知“0”和“1”组成的字符串分为三类:全“0”串称为B串,全“1”串称为I串,既含“0”又含“1”的串则称为F串。

写一个后序遍历的函数,然后递归,自己调用自己就好了。每次输出根节点,直至全部输出。

代码如下:

#include<bits/stdc++.h>

using namespace std;

string s;

void postorder(string s)//后序遍历 

{ //左、右、根

    if(s.length()>1)

    {//递归函数,自己调用自己

     //substr函数第一个参数是起点下标,第二个参数是从起点开始截取几个字符(不是终点下标)!!!

     //也就是substr的用法,前面参数表示起始位置,后面那个参数表示长度

           postorder(s.substr(0,s.length()/2));//遍历左子树

        postorder(s.substr(s.length()/2,s.length()/2));//遍历右子树

      }

      //访问根,输出

      if(s==string(s.length(),'0'))//由0组成,输出B

        cout<<"B";

      else if(s==string(s.length(),'1'))//由1组成,输出I

        cout<<"I";

      else

        cout<<"F";

}

int main()

{

    int n;

      cin>>n>>s;

      postorder(s);

      return 0;

}

标签:遍历,string,NOIP,cout,substr,length,2004,FBI,postorder
From: https://www.cnblogs.com/xdzxyingrui/p/16589689.html

相关文章

  • [2001年NOIP普及组] 数的计算
    我们要求找出具有下列性质数的个数(包含输入的自然数n):先输入一个自然数n(n<=1000),然后对此自然数按照如下方法进行处理:1.不作任何处理;2.在它的左边加上一个自然数,但......
  • NC16681 [NOIP2003]加分二叉树
    题目链接题目题目描述​设一个n个节点的二叉树tree的中序遍历为(l,2,3,…,n),其中数字1,2,3,…,n为节点编号。每个节点都有一个分数(均为正整数),记第j个节点的分数为di,t......
  • [2007年NOIP普及组] 奖学金
    某小学最近得到了一笔赞助,打算拿出其中一部分为学习成绩优秀的前5名学生发奖学金。期末,每个学生都有3门课的成绩:语文、数学、英语。先按总分从高到低排序,如果两个同学总分......
  • [2009年NOIP普及组] 分数线划定
    世博会志愿者的选拔工作正在A市如火如荼的进行。为了选拔最合适的人才,A市对所有报名的选手进行了笔试,笔试分数达到面试分数线的选手方可进入面试。面试分数线根据计划录取......
  • [2007年NOIP普及组] 奖学金
    某小学最近得到了一笔赞助,打算拿出其中一部分为学习成绩优秀的前5名学生发奖学金。期末,每个学生都有3门课的成绩:语文、数学、英语。先按总分从高到低排序,如果两个同学总分......
  • [2007年NOIP普及组] Hanoi双塔问题
    分析:根据样例可得x(n)=2+2*2……运用高精乘进行乘#include<bits/stdc++.h>usingnamespacestd;intc[600000],jw[600000];inti,n,a[600000],j,b[600000]={0,2},bj;intma......
  • [2001年NOIP普及组] 求先序排列
    给出一棵二叉树的中序与后序排列。求出它的先序排列。(约定树结点用不同的大写字母表示,长度<=8)。输入第一行输入一个字符串表示二叉树的中序排列,第二行输入一个字符串表示......
  • [2004年NOIP普及组] FBI树
    我们可以把由“0”和“1”组成的字符串分为三类:全“0”串称为B串,全“1”串称为I串,既含“0”又含“1”的串则称为F串。FBI树是一种二叉树[1],它的结点类型也包括F结点,B结点和......
  • [2004年NOIP普及组] FBI树(从下往上推)
    分析:根据样例得下面每有二个,则往上输出一个,以此类推,递推如:下面为10001011先判断b【1】【1】在判断b【1】【2】此时【2】已是偶数,给b【2】【1】赋值(第一个数是在原有层数+......
  • [2004年NOIP普及组] FBI树
    后序遍历:先左儿子,后右儿子,最后根同理类推先序遍历:先根,再左儿子,后右儿子中序遍历:先左儿子,再根,最后右儿子 ......