FBI树

FBI树

问题描述

问题描述 　　我们可以把由“0”和“1”组成的字符串分为三类：全“0”串称为B串，全“1”串称为I串，既含“0”又含“1”的串则称为F串。 　　FBI树是一种二叉树，它的结点类型也包括F结点，B结点和I结点三种。由一个长度为2N的“01”串S可以构造出一棵FBI树T，递归的构造方法如下： 　　1)T的根结点为R，其类型与串S的类型相同； 　　2)若串S的长度大于1，将串S从中间分开，分为等长的左右子串S1和S2；由左子串S1构造R的左子树T1，由右子串S2构造R的右子树T2。 　　现在给定一个长度为2N的“01”串，请用上述构造方法构造出一棵FBI树，并输出它的后序遍历序列。 输入格式 　　第一行是一个整数N（0 <= N <= 10），第二行是一个长度为2N的“01”串。 输出格式 　　包括一行，这一行只包含一个字符串，即FBI树的后序遍历序列。 样例输入 3 10001011 样例输出 IBFBBBFIBFIIIFF 数据规模和约定 　　对于40%的数据，N <= 2； 　　对于全部的数据，N <= 10。 　　注： 　　[1] 二叉树：二叉树是结点的有限集合，这个集合或为空集，或由一个根结点和两棵不相交的二叉树组成。这两棵不相交的二叉树分别称为这个根结点的左子树和右子树。 　　[2] 后序遍历：后序遍历是深度优先遍历二叉树的一种方法，它的递归定义是：先后序遍历左子树，再后序遍历右子树，最后访问根。

解题思路

将父串2分，给两个孩子赋值建立二叉树 然后后续遍历 整体思路不难，技术对指针引用需要主要。

#include#includeusing namespace std;struct Node{ string s; Node *left,*right; Node(string s){ this->s = s; this->left = NULL; this->right = NULL; }};//判断那种串int find(string s) //纯0返回0 纯1 返回1 10混合 返回2{ int flag1 = 1,flag0 = 1,size = s.size(); for(int i = 0;i < size;i++) { if(s[i]=='0') flag0 = 0; if(s[i]=='1') flag1 = 0; } if(flag0==0&&flag1==1) return 0; else if(flag0==1&&flag1==0) return 1; else { return 2; }}void dfs(Node *&r){ int size = r->s.size(); if(r->s.size()<=1) return ; int mid = size/2; //定义两个字符串 dfs(r->left = new Node(string(r->s.begin(),r->s.begin()+mid))); dfs(r->right = new Node(string(r->s.begin()+mid,r->s.end())));}//遍历输出void visit(Node *r){ if(r==NULL) { return ; } visit(r->left); visit(r->right); string str = r->s; if(find(str)==0) cout << "B"; else if(find(str)==1) cout << "I"; else cout << "F";}int main(){ freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int n;//2的n次方个 cin >> n; string s; cin >> s; Node root(s),*p; p = &root; dfs(p); visit(p); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。