108 lines
3.1 KiB
C++
108 lines
3.1 KiB
C++
#include <functional>
|
|
#include <iostream>
|
|
#include <vector>
|
|
|
|
class BinaryTree {
|
|
public:
|
|
using NodeIdx = int;
|
|
|
|
struct Node {
|
|
char value;
|
|
NodeIdx left = -1, right = -1;
|
|
};
|
|
|
|
enum class FuncEntry { Pre, In, Post };
|
|
|
|
NodeIdx root = -1;
|
|
std::vector<Node> nodes;
|
|
|
|
void init_with_lines(const std::vector<std::string>& lines) {
|
|
nodes.reserve(lines.size());
|
|
std::vector<int> lines_dashes(lines.size());
|
|
int idx = 0;
|
|
root = init_with_lines(lines, 0, idx);
|
|
}
|
|
|
|
std::string prefix_traverse() {
|
|
std::string traverse;
|
|
traverse.reserve(nodes.size());
|
|
dfs([&traverse, this](NodeIdx node, int dfs_depth) {
|
|
traverse += nodes[node].value;
|
|
}, FuncEntry::Pre);
|
|
return traverse;
|
|
}
|
|
|
|
std::string infix_traverse() {
|
|
std::string traverse;
|
|
traverse.reserve(nodes.size());
|
|
dfs([&traverse, this](NodeIdx node, int dfs_depth) {
|
|
traverse += nodes[node].value;
|
|
}, FuncEntry::In);
|
|
return traverse;
|
|
}
|
|
|
|
std::string postfix_traverse() {
|
|
std::string traverse;
|
|
traverse.reserve(nodes.size());
|
|
dfs([&traverse, this](NodeIdx node, int dfs_depth) {
|
|
traverse += nodes[node].value;
|
|
}, FuncEntry::Post);
|
|
return traverse;
|
|
}
|
|
|
|
protected:
|
|
NodeIdx init_with_lines(const std::vector<std::string>& lines,
|
|
int depth, int& idx) {
|
|
if (idx >= lines.size() || lines[idx].size() - 1 < depth) { return -1; }
|
|
char value;
|
|
if ((value = lines[idx][lines[idx].size() - 1]) == '*') {
|
|
idx++;
|
|
return -1;
|
|
}
|
|
const NodeIdx node_idx = nodes.size();
|
|
nodes.push_back(Node{value});
|
|
idx++;
|
|
nodes[node_idx].left = init_with_lines(lines, depth + 1, idx);
|
|
nodes[node_idx].right = init_with_lines(lines, depth + 1, idx);
|
|
return node_idx;
|
|
}
|
|
|
|
void dfs(const std::function<void(NodeIdx, int)>& func,
|
|
FuncEntry func_entry = FuncEntry::Pre,
|
|
int dfs_depth = 0,
|
|
NodeIdx node = -1
|
|
) {
|
|
if (dfs_depth == 0) { node = root; }
|
|
if (func_entry == FuncEntry::Pre) { func(node, dfs_depth); }
|
|
if (nodes[node].left != -1) { dfs(func, func_entry, dfs_depth + 1, nodes[node].left); }
|
|
if (func_entry == FuncEntry::In) { func(node, dfs_depth); }
|
|
if (nodes[node].right != -1) { dfs(func, func_entry, dfs_depth + 1, nodes[node].right); }
|
|
if (func_entry == FuncEntry::Post) { func(node, dfs_depth); }
|
|
}
|
|
};
|
|
|
|
int main() {
|
|
std::ios::sync_with_stdio(false);
|
|
std::cin.tie(nullptr);
|
|
|
|
int n;
|
|
std::cin >> n;
|
|
|
|
while (n--) {
|
|
std::vector<std::string> lines;
|
|
std::string s;
|
|
while (std::cin >> s && s != "0") {
|
|
lines.push_back(s);
|
|
}
|
|
|
|
BinaryTree binary_tree;
|
|
binary_tree.init_with_lines(lines);
|
|
|
|
std::cout << binary_tree.prefix_traverse() << std::endl
|
|
<< binary_tree.postfix_traverse() << std::endl
|
|
<< binary_tree.infix_traverse() << std::endl << std::endl;
|
|
}
|
|
|
|
return 0;
|
|
}
|