【Luogu】【关卡2-14】树形数据结构（2017年10月）【AK】

任务说明：由一个根节点分叉，越分越多，就成了树。树可以表示数据之间的从属关系

P1087 FBI树

给一个01字符串，0对应B，1对应I，F对应既有0子节点又有1子节点的根节点，输出这棵树的后序遍历。字符串长度小于等于2^10。

心情好，写代码一次ac了

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <stack>

 #include <map>

 #include <vector>

 #include <string>

 using namespace std;

 void init(string& str) {

     if (str.empty()) {

         return;

     }

     if (str.size() == ) {

         if (str == "") { cout << "B"; }

         else if (str == "") { cout << "I"; }

         return;

     }

     string s1 = str.substr(, str.size()/);

     string s2 = str.substr(str.size()/);

     init(s1);

     init(s2);

     if (str.find("") != string::npos && str.find("") != string::npos) {

         cout << "F";

     } else if (str.find("") != string::npos) {

         cout << "B";

     } else {

         cout << "I";

     }

     return;

 }

 int main() {

     int n;

     cin >> n;

     string str;

     cin >> str;

     init(str);

     cout << endl;

     //system("pause");

     return ;

 }

P1030 求先序排列

给两个字符串，表示一棵树的中序遍历和后序遍历，要求输出这棵树的先序遍历。

我是模拟了这棵树，先建树，然后先序遍历的。

但是还可以有更好的解法，不用建树，直接dfs就ok！！！！

 #include <iostream>

 #include <cstdio>

 #include <string>

 using namespace std;

 struct TreeNode {

     char val;

     TreeNode* left = nullptr;

     TreeNode* right = nullptr;

 };

 TreeNode* initTree(string& str1, string& str2) {

     if  (str1.empty() && str2.empty()) {

         return nullptr;

     }

     char c = str2[str2.size()-];

     TreeNode* root = new(TreeNode);

     root->val = c;

     int str1Pos = str1.find(c);

     string str1Left = str1.substr(, str1Pos);

     string str1Right = str1.substr(str1Pos + );

     string str2Left = str2.substr(, str1Pos);

     string str2Right = str2.substr(str1Pos, str1Right.size());

     root->left = initTree(str1Left, str2Left);

     root->right = initTree(str1Right, str2Right);

     return root;

 }

 string strans = "";

 void visitTree(TreeNode* root) {

     if (!root) { return; }

     strans += root->val;

     visitTree(root->left);

     visitTree(root->right);

     return;

 }

 int main() {

     string s1, s2;

     cin >> s1 >> s2;

     TreeNode* root = initTree(s1, s2);

     visitTree(root);

     cout << strans << endl;

     return ;

 }

P1305 新二叉树

这个题目写segment fault了，要用gdb看堆栈....orz

Linix 查看core文件配置方法如下： http://www.jianshu.com/p/5549a6e71a1d

怎么用gdb看堆栈，看内存这里还是需要强化...最后发现问题的方法还是输出屏幕看log。。orz

segment fault 的原因是：

 //没有判断top是否存在就pop了，踩内存了orz

 while ( stk.top() == '*') { stk.pop(); } //wrong

 while (!stk.empty() &&  stk.top() == '*') { stk.pop(); } //correct

以后要注意，判断一个值的时候一定要先写这个值能不能存在orz

题目是：输入一串二叉树，用遍历前序打出。

输入格式：

第一行为二叉树的节点数n。

后面n行，每一个字母为节点，后两个字母分别为其左右儿子。

空节点用*表示

输出格式：前序排列的二叉树

想法就是先找根节点，然后用个栈来保存左右儿子。左儿子先pop，然后递归的找左儿子的儿子进栈。

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <stack>

 #include <map>

 #include <vector>

 using namespace std;

 int n;

 map<char, int> mp;

 stack<char> stk;

 int main() {

     cin >> n;

     vector<vector<char>> info(n, vector<char>());

     for (int i = ; i < n; ++i) {

         getchar();

         //scanf("%c%c%c", &info[i][0], &info[i][1], &info[i][2]);

         cin >> info[i][] >> info[i][] >> info[i][];

         mp[info[i][]]++, mp[info[i][]]++, mp[info[i][]]++;

     }

     char rootval = '=';

     for (auto ele : mp) {

         if (ele.second == ) {

             rootval = ele.first;

         }

     }

     stk.push(rootval);

     int times = ;

     while(!stk.empty()) {

         while (!stk.empty() && stk.top() == '*') { stk.pop(); }

         if (stk.empty()) { break; }

         char ch = stk.top();

         stk.pop();

         for (int i = ; i < n; ++i) {

             if (info[i][] == ch) {

                 stk.push(info[i][]);

                 stk.push(info[i][]);

             }

         }

         cout << ch ;

     }

     return ;

 }

巴特西

【Luogu】【关卡2-14】树形数据结构（2017年10月）【AK】

最新文章

热门文章

巴特西

【Luogu】【关卡2-14】 树形数据结构（2017年10月）【AK】

最新文章

热门文章

【Luogu】【关卡2-14】树形数据结构（2017年10月）【AK】