আমাদের একটি অ্যারে arr[] দেওয়া আছে যেটি k-এরি ট্রির প্রিঅর্ডার ট্রভারসাল ধারণ করে। লক্ষ্য হলো একই k-এরি ট্রি পুনরায় নির্মাণ করা এবং এর পোস্টঅর্ডার ট্রভারসাল প্রিন্ট করা। একটি ফুল k-এরি ট্রি বলতে একে বুঝায় যেটিতে রুট নোডের ০ বা k সংখ্যক চাইল্ড থাকে।
ইনপুট
int arr[] = {2, 5, 1, 3, 6, 7, 2, 1}, int size = 8, int children = 2
আউটপুট
প্রিঅর্ডার ট্রভারসাল থেকে দুটি চাইল্ড বিশিষ্ট ফুল k-এরি ট্রি নির্মিত হলো:
ব্যাখ্যা
আমাদের k চাইল্ড = ২ দিয়ে একটি ট্রির প্রিঅর্ডার ট্রভারসাল দেওয়া আছে। তৈরি ট্রির পোস্টঅর্ডার ট্রভারসাল হবে: 3 6 1 2 1 7 5 2।
ইনপুট
int arr[] = {2, 5, 1, 3, 6, 7, 2, 1}, int size = 8, int children = 3
আউটপুট
প্রিঅর্ডার ট্রভারসাল থেকে তিনটি চাইল্ড বিশিষ্ট ফুল k-এরি ট্রি নির্মিত হলো:
ব্যাখ্যা
আমাদের k চাইল্ড = ৩ দিয়ে একটি ট্রির প্রিঅর্ডার ট্রভারসাল দেওয়া আছে। তৈরি ট্রির পোস্টঅর্ডার ট্রভারসাল হবে: 3 6 1 2 1 7 5 2।
প্রোগ্রামে ব্যবহৃত পদ্ধতি:
এই পদ্ধতিতে প্রথমে দেয়া অ্যারে থেকে প্রথম এলিমেন্টকে রুট নোড হিসেবে নিয়ে k-এরি ট্রি নির্মাণ করা হয়। লেফট সাবট্রি খালি হলে রাইট সাবট্রিও খালি হবে। রিকারসিভলি লেফট ও রাইট সাবট্রি কল করে লিঙ্ক করা হয়। পোস্টঅর্ডার ট্রভারসালের জন্য: লেফট সাবট্রি, তারপর রাইট সাবট্রি, তারপর নোডের ওজন প্রিন্ট করা হয়।
postorder(root->left)কল করা হয়postorder(root->right)কল করা হয়root->dataপ্রিন্ট করা হয়- ইনপুট অ্যারে হিসেবে
arr[]নেওয়া হয় - k ভেরিয়েবল হিসেবে
childrenনেওয়া হয় - স্টার্টিং ইনডেক্স হিসেবে
count=0নেওয়া হয় Tree_Node* node = create_tree(arr, size, children, count)দিয়ে ট্রি নির্মাণnew_Node(int data)ফাংশন নতুন ট্রি নোড জেনারেট করেcreate_tree(int arr[], int N, int k, int height, int& count)ফাংশন অ্যারে থেকে k-এরি ট্রি তৈরি করে- নোড সংখ্যা <=0 হলে NULL রিটার্ন
newNode = new_Node(arr[count])প্রথম এলিমেন্ট দিয়ে ইনিশিয়ালাইজ- ফর লুপ i=0 থেকে i<k পর্যন্ত ট্রভারস
- শর্তমতো কাউন্ট বাড়িয়ে রিকারসিভ কল এবং NULL পুশ
create_tree(int* arr, int N, int k, int count)ফাংশন ট্রির হাইট রিটার্ন করে- হাইট ক্যালকুলেশন:
ceil(log((double)N * (k-1) + 1) / log((double)k)) postorder_traversal(Tree_Node* node, int k)ফাংশন পোস্টঅর্ডার প্রিন্ট করে
উদাহরণ
#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) {
cout << "Code Dumped";
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 preorder_traversal(Tree_Node* node, int k) {
if (node == NULL) {
return;
}
for (int i = 0; i < k; i++) {
preorder_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 << "Construct the full k-ary tree from its preorder traversal are: ";
preorder_traversal(node, children);
return 0;
}
আউটপুট
Construct the full k-ary tree from its preorder traversal are: 3 6 1 2 1 7 5 2
