Xây dựng cây k-ary đầy đủ từ duyệt preorder trong C++

Cho mảng preorder của cây k-ary đầy đủ (mỗi nút có 0 hoặc k con). Xây dựng cây và in duyệt postorder.

Ví dụ

Input: arr[] = {2, 5, 1, 3, 6, 7, 2, 1}, k = 2

Postorder: 3 6 1 2 1 7 5 2

Ví dụ hoàn chỉnh

#include <bits/stdc++.h>
using namespace std;

struct Tree_Node {
    int address;
    vector<Tree_Node*> root;
};

Tree_Node* new_Node(int data) {
    Tree_Node* newNode = new Tree_Node;
    newNode->address = data;
    return newNode;
}

Tree_Node* create_tree(int arr[], int N, int k, int height, int& count) {
    if (N <= 0)
        return NULL;
    Tree_Node* newNode = new_Node(arr[count]);
    if (newNode == NULL)
        return NULL;
    for (int i = 0; i < k; i++) {
        if (count < N - 1 && height > 1) {
            count++;
            newNode->root.push_back(create_tree(arr, N, k, height - 1, count));
        } else {
            newNode->root.push_back(NULL);
        }
    }
    return newNode;
}

Tree_Node* create_tree(int* arr, int N, int k, int count) {
    int height = (int)ceil(log((double)N * (k - 1) + 1) / log((double)k));
    return create_tree(arr, N, k, height, count);
}

void postorder_traversal(Tree_Node* node, int k) {
    if (node == NULL)
        return;
    for (int i = 0; i < k; i++)
        postorder_traversal(node->root[i], k);
    cout << node->address << " ";
}

int main() {
    int arr[] = {2, 5, 1, 3, 6, 7, 2, 1};
    int size = 8;
    int children = 2;
    int count = 0;
    Tree_Node* node = create_tree(arr, size, children, count);
    cout << "Postorder: ";
    postorder_traversal(node, children);
    return 0;
}

Kết quả

Postorder: 3 6 1 2 1 7 5 2