【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() == 1) {
        if (str == "0") { cout << "B"; }
        else if (str == "1") { cout << "I"; }
        return;
    }
    string s1 = str.substr(0, str.size()/2);
    string s2 = str.substr(str.size()/2);
    init(s1);
    init(s2);
    if (str.find("0") != string::npos && str.find("1") != string::npos) {
        cout << "F";
    } else if (str.find("0") != 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 0;
}

 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()-1];
    TreeNode* root = new(TreeNode);
    root->val = c;
    int str1Pos = str1.find(c);
    string str1Left = str1.substr(0, str1Pos);

    string str1Right = str1.substr(str1Pos + 1);

    string str2Left = str2.substr(0, 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 0;
}

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>(3));
    for (int i = 0; i < n; ++i) {
        getchar();
        //scanf("%c%c%c", &info[i][0], &info[i][1], &info[i][2]);
        cin >> info[i][0] >> info[i][1] >> info[i][2];
        mp[info[i][0]]++, mp[info[i][1]]++, mp[info[i][2]]++;

    }
    char rootval = '=';
    for (auto ele : mp) {
        if (ele.second == 1) {
            rootval = ele.first;
        }
    }
    stk.push(rootval);
    int times = 0;
    while(!stk.empty()) {
        while (!stk.empty() && stk.top() == '*') { stk.pop(); }
        if (stk.empty()) { break; }
        char ch = stk.top();
        stk.pop();
        for (int i = 0; i < n; ++i) {
            if (info[i][0] == ch) {
                stk.push(info[i][2]);
                stk.push(info[i][1]);
            }
        }
        cout << ch ;
    }
    return 0;
}