#embody <bits/stdc++.h>
utilizing namespace std;
template <typename T> class Node {
public:
Node(T information);
Node* get_first_child() const;
Node* get_next_sibling() const;
void set_next_sibling(Node* node);
void set_next_child(Node* node);
T get_data();
non-public:
T information;
Node* first_child;
Node* next_sibling;
};
template <typename T> Node<T>::Node(T information)
{
first_child = NULL;
next_sibling = NULL;
this->information = information;
}
template <typename T>
Node<T>* Node<T>::get_first_child() const
{
return first_child;
}
template <typename T>
Node<T>* Node<T>::get_next_sibling() const
{
return next_sibling;
}
template <typename T>
void Node<T>::set_next_sibling(Node<T>* node)
{
if (next_sibling == NULL) {
next_sibling = node;
}
else {
next_sibling->set_next_sibling(node);
}
}
template <typename T> T Node<T>::get_data() { return information; }
template <typename T>
void Node<T>::set_next_child(Node<T>* node)
{
if (first_child == NULL) {
first_child = node;
}
else {
first_child->set_next_sibling(node);
}
}
template <typename T>
Node<T>* Assemble(T* post_order_arr, int dimension, int ok)
{
Node<T>* Root = new Node<T>(post_order_arr[size - 1]);
if (dimension == 1) {
return Root;
}
int height_of_tree
= ceil(log2(dimension * (ok - 1) + 1) / log2(ok)) - 1;
int nodes_in_last_level
= dimension - ((pow(ok, height_of_tree) - 1) / (ok - 1));
int tracker = 0;
whereas (tracker != (dimension - 1)) {
int last_level_nodes
= (pow(ok, height_of_tree - 1)
> nodes_in_last_level)
? nodes_in_last_level
: (pow(ok, height_of_tree - 1));
int nodes_in_next_subtree
= ((pow(ok, height_of_tree - 1) - 1) / (ok - 1))
+ last_level_nodes;
Root->set_next_child(
Assemble(post_order_arr + tracker,
nodes_in_next_subtree, ok));
tracker = tracker + nodes_in_next_subtree;
nodes_in_last_level
= nodes_in_last_level - last_level_nodes;
}
return Root;
}
template <typename T> void preorder(Node<T>* Root)
{
if (Root == NULL) {
return;
}
cout << Root->get_data() << " ";
preorder(Root->get_first_child());
preorder(Root->get_next_sibling());
}
int primary()
{
int M = 9, N = 3;
int arr[] = { 5, 6, 7, 2, 8, 9, 3, 4, 1 };
preorder(Assemble(arr, M, N));
return 0;
}
