Uva 122 一棵稍微复杂的树

一、题意

在每组数据中有一棵树，
给出每个结点的val和从根节点到它的位置的路径path（由L和R组成）
要求输出树的层次遍历。

二、解析

构造树需要用到指针操作，递归生成。
层次遍历用bfs即可，bfs一般通过队列实现。

三、代码

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
using namespace std;
struct node {
    int has_val = 0;
    int val;
    node *l, *r;
    node(node* l, node* r) : l(l), r(r) {}
};

void addNode(node* & root, int val, string path) {
    if(root == nullptr) root = new node(nullptr, nullptr);
    if(path == "") root->val = val, root->has_val ++;
    else {
        if(path[0] == 'L') addNode(root->l, val, path.substr(1));
        else addNode(root->r, val, path.substr(1));
    }
}

bool inputTree(node* & root) {
    root = nullptr;
    string str;
    while(cin >> str) {
        if(str == "()") return 1;
        for(auto& ch : str) if(ch == ',' || ch == '(' || ch == ')') ch = ' ';
        stringstream ss(str);
        int val;
        string path;
        ss >> val >> path;
        addNode(root, val, path);
    }
    return 0;
}

void bfs(node* & root) {
    vector<int> ans;
    bool ok = 1;
    queue<node*> que;
    que.push(root);
    while(!que.empty()) {
        node* u = que.front();
        if(u->has_val != 1) ok = 0;
        ans.push_back(u->val);
        que.pop();
        if(u->l != nullptr) que.push(u->l);
        if(u->r != nullptr) que.push(u->r);
    }
    if(!ok) cout << "not complete";
    else for(int i = 0; i < ans.size(); i ++) {
        if(i) cout << " ";
        cout << ans[i];
    }
    cout << endl;
}

int main() {
    node* root = nullptr;
    while(inputTree(root)) bfs(root);
}

四、归纳

• 当程序代码量比较大时，要学会分块，如inputTree(), addNode(), bfs()
• root传参时注意加引用
• 递归写法：先用if语句写递归出口，然后再写递归式子。