top1编程
← 返回题目
题解

FBI树

1 条题解

  • 0
    @ 2026-7-29 0:19:51
    #include <bits/stdc++.h>
    using namespace std;
    #define N 2050
    struct Node
    {
    	char val;//结点类型,可以是'F', 'B', 或'I' 
    	int left, right;
    };
    Node node[N];//结点池 
    int n, p;
    string s;
    int createTree(string fs)//根据FBI串fs构建二叉树,返回二叉树的根 
    {
    	int np = ++p;
    	if(fs.length() == 1)
    	{
    		if(fs[0]=='1')
    			node[np].val='I';
    		else 
    			node[np].val='B';
    		return np;	
    	}
    	string ls = fs.substr(0, fs.length()/2), rs = fs.substr(fs.length()/2);
    	int lp = createTree(ls), rp = createTree(rs);
    	node[np].left = lp, node[np].right = rp;
    	if(node[lp].val == node[rp].val)
    		node[np].val = node[lp].val;//如果二者相同,那么父节点等于孩子结点 
    	else
    		node[np].val = 'F';
    	return np;
    }
    void postOrder(int r)
    {
    	if(r == 0)
    		return;
    	postOrder(node[r].left);
    	postOrder(node[r].right);
    	cout << node[r].val;
    }
    int main()
    {
    	cin >> n >> s;
    	int root = createTree(s);
    	postOrder(root);
    	return 0;
    }
    
    • 1