任务说明：由一个根节点分叉，越分越多，就成了树。树可以表示数据之间的从属关系
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 ;
}