145 lines
4.5 KiB
C++
145 lines
4.5 KiB
C++
#include <functional>
|
|
#include <iostream>
|
|
#include <vector>
|
|
|
|
using NodeIdx = std::size_t;
|
|
static constexpr NodeIdx NULL_IDX = static_cast<NodeIdx>(-1);
|
|
|
|
template <typename T>
|
|
class Tree {
|
|
public:
|
|
enum class FuncEntry { Pre, Post };
|
|
|
|
struct Node {
|
|
T value;
|
|
NodeIdx parent = NULL_IDX;
|
|
std::vector<NodeIdx> children;
|
|
};
|
|
|
|
std::vector<Node> nodes;
|
|
NodeIdx root = NULL_IDX;
|
|
|
|
NodeIdx add_node(const Node& node_obj) {
|
|
nodes.push_back(node_obj);
|
|
return nodes.size() - 1;
|
|
}
|
|
|
|
void init_with_dfs(const std::string& dfs_string) {
|
|
root = add_node({.value = T()});
|
|
init_with_dfs(dfs_string, 0, root);
|
|
}
|
|
|
|
int get_height() {
|
|
int depth = -1;
|
|
dfs([&depth](NodeIdx node, int dfs_depth) { depth = std::max(depth, dfs_depth); });
|
|
return depth;
|
|
}
|
|
|
|
protected:
|
|
void init_with_dfs(const std::string& dfs_string, std::size_t s_idx, NodeIdx node) {
|
|
if (s_idx >= dfs_string.size()) { return; }
|
|
if (dfs_string[s_idx] == 'd') {
|
|
auto new_node = add_node({.value = T(), .parent = node});
|
|
nodes[node].children.push_back(new_node);
|
|
init_with_dfs(dfs_string, s_idx + 1, nodes[node].children.back());
|
|
} else {
|
|
init_with_dfs(dfs_string, s_idx + 1, nodes[node].parent);
|
|
}
|
|
}
|
|
|
|
void dfs(const std::function<void(NodeIdx, int)>& func,
|
|
FuncEntry func_entry = FuncEntry::Post,
|
|
int depth = 0,
|
|
NodeIdx node = NULL_IDX
|
|
) {
|
|
if (depth == 0) { node = root; }
|
|
if (func_entry == FuncEntry::Pre) { func(node, depth); }
|
|
for (auto child : nodes[node].children) {
|
|
dfs(func, func_entry, depth + 1, child);
|
|
}
|
|
if (func_entry == FuncEntry::Post) { func(node, depth); }
|
|
}
|
|
};
|
|
|
|
template <typename T>
|
|
class BinaryTree {
|
|
public:
|
|
enum class FuncEntry { Pre, In, Post };
|
|
|
|
struct Node {
|
|
T value;
|
|
NodeIdx parent = NULL_IDX, left = NULL_IDX, right = NULL_IDX;
|
|
};
|
|
|
|
std::vector<Node> nodes;
|
|
NodeIdx root = -1;
|
|
|
|
NodeIdx add_node(Node node_obj) {
|
|
nodes.push_back(node_obj);
|
|
return nodes.size() - 1;
|
|
}
|
|
|
|
void init_from_tree(const Tree<T>& tree) {
|
|
root = add_node({});
|
|
init_from_tree(tree, tree.root, 0);
|
|
}
|
|
|
|
int get_height() {
|
|
int depth = -1;
|
|
dfs([&depth](NodeIdx node, int dfs_depth) { depth = std::max(depth, dfs_depth); });
|
|
return depth;
|
|
}
|
|
|
|
protected:
|
|
void init_from_tree(const Tree<T>& tree, NodeIdx binary_tree_node, NodeIdx tree_node) {
|
|
bool first_child = false;
|
|
NodeIdx current_parent = NULL_IDX;
|
|
for (auto child : tree.nodes[tree_node].children) {
|
|
if (!first_child) {
|
|
first_child = true;
|
|
NodeIdx new_node = add_node({.value = T(), .parent = binary_tree_node});
|
|
nodes[binary_tree_node].left = new_node;
|
|
current_parent = nodes[binary_tree_node].left;
|
|
init_from_tree(tree, nodes[binary_tree_node].left, child);
|
|
continue;
|
|
}
|
|
NodeIdx new_node = add_node({.value = T(), .parent = current_parent});
|
|
nodes[current_parent].right = new_node;
|
|
current_parent = nodes[current_parent].right;
|
|
init_from_tree(tree, current_parent, child);
|
|
}
|
|
}
|
|
|
|
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); }
|
|
}
|
|
};
|
|
|
|
struct ManualVoid {};
|
|
|
|
int main() {
|
|
std::ios::sync_with_stdio(false);
|
|
std::cin.tie(nullptr);
|
|
std::cout.tie(nullptr);
|
|
|
|
std::string dfs_string;
|
|
for (int i = 0; std::cin >> dfs_string && dfs_string != "#"; i++) {
|
|
Tree<ManualVoid> tree;
|
|
tree.init_with_dfs(dfs_string);
|
|
BinaryTree<ManualVoid> binary_tree;
|
|
binary_tree.init_from_tree(tree);
|
|
std::cout << "Tree " << i + 1 << ": " << tree.get_height() << " => " << binary_tree.get_height() << std::endl;
|
|
}
|
|
|
|
return 0;
|
|
}
|