FBI树

青旅半醒 2023-02-13 11:13 32阅读 0赞

[题目传送门][Link 1]  
时间限制:1000MS 代码长度限制:10KB  
提交次数:0 通过次数:0

题型: 编程题 语言: 不限定  
Description  
我们可以把由“0”和“1”组成的字符串分为三类：全“0”串称为B串，全“1”串称为I串，既含“0”又含“1”的串则称为F串。  
FBI树是一种二叉树，它的结点类型也包括F结点，B结点和I结点三种。一个长度为2^n的“01”串S可以构造出一棵FBI树T，递归的构造方法如下：  
1)T的根结点为R，其类型与串S的类型相同；  
2)若串S的长度大于1，将串S从中间分开，分为等长的左右子串S1和S2；由左子串S1构造R的左子树T1，由右子串S2构造R的右子树T2。  
现在给定一个长度为2的n次幂的“01”串，请用上述构造方法构造出一棵FBI树，并输出它的后序遍历\*2序列。

输入格式  
第一行是一个整数N（0 ≤ N ≤ 10），第二行是一个长度为2^N的“01”串。

输出格式  
一行，这一行只包含一个字符串，即FBI树的后序遍历序列。

输入样例  
3  
10001011

输出样例  
IBFBBBFIBFIIIFF

提示  
两种方法：  
（1）二叉树首选算法，二分递归。即建树的同时后序遍历  
（2）利用完全二叉树性质存储和构造二叉树，再后序遍历。

来源 NOIP 2004

解题思路：可以模拟建树，也可以不建树，直接用数组存储，因为有些题是考察了树，但是不需要建树。  
**特别注意：如若建树，要对指针进行引用，否则会发生无法察觉的错误。（本人wa的点）**

#include<iostream>
    using namespace std;
    int n,count;
    typedef struct node
    { 
    	struct node *lchild,*rchild;
    	char ch;//表明该串是何串 
    }Tree,*PTree;
    void CreateTree (PTree &T,int h)//h表示深度n后就归 
    { 
        T= new Tree;
    	if(h==n)
    	{ 
    		char s;
    		T->lchild=NULL;
    		T->rchild=NULL;
    		cin>>s;
    		if(s=='0')
    		T->ch='B';
    		else
    		T->ch='I'; 
    		cout<<T->ch;
    	}
    	else
    	{ 
    		CreateTree(T->lchild,h+1);
    		CreateTree(T->rchild,h+1);
    		if(T->lchild->ch=='I'&&T->rchild->ch=='I')
    		T->ch='I';
    		else if(T->lchild->ch=='B'&&T->rchild->ch=='B')
    		T->ch='B';
    		else
    		T->ch='F';
    		cout<<T->ch;
    	}
    }
    int main()
    { 
    	PTree T;
    	cin>>n;
    	CreateTree(T,0);
    	return 0;
     }

[Link 1]: https://www.luogu.com.cn/problem/P1087