สร้าง Full k-ary Tree จาก Preorder Traversal ใน C++

โจทย์: ให้ Preorder traversal ของ Full k-ary Tree (โหนดแต่ละตัวมีลูก 0 หรือ k ตัว) ต้องการสร้างต้นไม้กลับมาและพิมพ์ Postorder traversal

โครงสร้างโหนด k-ary Tree

struct Tree_Node {
    int address;
    vector<Tree_Node*> root;  // vector ของลูก k ตัว
};

การสร้างต้นไม้

ใช้ดัชนี count เดินผ่าน array preorder โดย:

1. สร้างโหนดจาก arr[count]
2. ถ้าความสูง > 1 ให้สร้างลูก k ตัวแบบเวียนเกิด
3. ถ้าไม่ ให้ใส่ NULL ให้ลูกทั้ง k ตัว

การคำนวณความสูง

int height = ceil(log(N * (k - 1) + 1) / log(k));

Postorder Traversal

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 << " ";
}

ตัวอย่างเต็ม (k=2)

#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 traversal: ";
    postorder_traversal(node, children);
    return 0;
}

ผลลัพธ์

Postorder traversal: 3 6 1 2 1 7 5 2