NOIP 2004 普及组 sdnu 1168.FBI树

本文主要是介绍NOIP 2004 普及组 sdnu 1168.FBI树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题链接：

http://210.44.14.31/problem/show/1168

考查树的构造和后序遍历。

代码如下：

#include<iostream>
#include<cmath>
#include<string>
#include<cstring>
using namespace std;
typedef struct node
{char fbi;struct node * leftchild, *rightchild;node() :leftchild(NULL), rightchild(NULL){}		//构造函数的简写
}*NODE;string numstr;void CreatFbiTree(int left,int right,NODE parent)
{if (left == right)		//递归结束条件{if (numstr[left] == '0')parent->fbi = 'B';else parent->fbi = 'I';return;}bool b = false, i = false;			//判断0，1for (int j = left; j <= right; j++){if (numstr[j] == '0'&&!b)b = true;else if (numstr[j] == '1'&&!i)i = true;if (i&&b) break;}if (i&&b)		parent->fbi = 'F';else if (!i&&b)		parent->fbi = 'B';else	parent->fbi = 'I';if (left <= (right + left) / 2){parent->leftchild = new node();CreatFbiTree(left, (right + left) / 2, parent->leftchild);}if ((right + left) / 2 + 1 <= right){parent->rightchild = new node();CreatFbiTree((right + left) / 2 + 1, right, parent->rightchild);}return;
}
void PostTraverseTree(NODE root)		//后序遍历
{if (NULL != root->leftchild)PostTraverseTree(root->leftchild);if (NULL != root->rightchild)PostTraverseTree(root->rightchild);cout << root->fbi;return;
}
int main()
{int n;cin >> n;NODE root=new node();cin >> numstr;CreatFbiTree(0, numstr.length() - 1, root);PostTraverseTree(root);cout << endl;return 0;
}

这篇关于NOIP 2004 普及组 sdnu 1168.FBI树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---