题解
FBI树
1 条题解
-
0
#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