আমাদের একটি অ্যারে অ্যারে দেওয়া হয়েছে [] যাতে কে-আরি গাছের ক্রমানুসারে প্রি-অর্ডার ট্রাভার্সাল রয়েছে। লক্ষ্য হল এটি থেকে একই কে-আরি গাছ তৈরি করা এবং এর পোস্টঅর্ডার ট্রাভার্সাল প্রিন্ট করা। একটি পূর্ণ k−ary গাছ হল যেটির রুট নোডে 0 বা k শিশু থাকে অর্থাৎ সর্বাধিক k শিশু থাকে।
উদাহরণস্বরূপ
ইনপুট
int arr[] = {2, 5, 1, 3, 6, 7, 2, 1 }, int size = 8, int children = 2 আউটপুট
পূর্ব-অর্ডার ট্রাভার্সাল থেকে দুটি শিশুকে নিয়ে যে সম্পূর্ণ k−ary গাছটি তৈরি করা হবে তা নীচে দেওয়া হল -
ব্যাখ্যা
আমাদেরকে পূর্ণসংখ্যার মানের একটি অ্যারে দেওয়া হয়েছে বা k বাচ্চাদের সাথে অ্যাট্রির প্রি-অর্ডার ট্রাভার্সাল দেওয়া হয়েছে যা 2। সুতরাং, গঠিত গাছটির পোস্টঅর্ডার ট্রাভার্সাল থাকবে 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−ary গাছটি তৈরি করা হবে তা নীচে দেওয়া হল -
ব্যাখ্যা
আমাদেরকে পূর্ণসংখ্যার মানের একটি অ্যারে দেওয়া হয়েছে বা k বাচ্চাদের সাথে অ্যাট্রির প্রি-অর্ডার ট্রাভার্সাল দেওয়া হয়েছে যা 3। সুতরাং, গঠিত গাছটির পোস্টঅর্ডার ট্র্যাভার্সাল থাকবে 3 6 1 2 1 7 5 2 যা নিয়ম অনুসারে তৈরি করা হয়েছে সমস্ত বাম সাবট্রি নোড দেখুন তারপর সমস্ত ডান সাবট্রি নোড দেখুন এবং তারপর সমস্ত রুট নোড দেখুন৷
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি −
এই পদ্ধতিতে আমরা প্রথমে রুট নোড হিসাবে প্রথম উপাদানটি নিয়ে প্রদত্ত অ্যারে থেকে k-ary ট্রি তৈরি করব। যদি বাম সাবট্রি খালি থাকে তবে ডানটিও খালি থাকবে। বারবার বাম এবং ডান সাবট্রিগুলির জন্য কল করুন এবং তাদের লিঙ্ক করুন৷ পোস্টঅর্ডার ট্রাভার্সালের জন্য আমরা বাম সাবট্রি, তারপর ডান সাবট্রি এবং তারপর নোডের ওজন প্রিন্ট করি৷
-
পোস্টঅর্ডারে কল করুন(root−>বামে)
-
পোস্টঅর্ডারে কল করুন(root−>ডানে)
-
রুট->ডেটা
প্রিন্ট করুন -
প্রি-অর্ডার ট্রাভার্সাল ধারণকারী একটি ইনপুট অ্যারে হিসাবে arr[] নিন।
-
পরিবর্তনশীল শিশু হিসাবে k কে নিন।
-
সূচনা সূচকটিকে গণনা=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) অ্যারে অ্যারে[] থেকে ক্যারি ট্রি তৈরি করে।
-
যদি নোডের সংখ্যা <=0 হয় তাহলে NULL রিটার্ন করুন, কোন গাছ তৈরি করা যাবে না।
-
শুরু করুন newNode =new_Node(arr[count]), arr[] এর প্রথম উপাদান।
-
যদি (newNode ==NULL) ফলাফল সত্য হয় তাহলে কোনো গাছ সম্ভব নয়।
-
ট্রাভার্স arr[] i=0 থেকে i
-
যদি (গণনা
1) তাহলে পরবর্তী সূচকের জন্য সংখ্যা বৃদ্ধি করুন এবং newNode−>root.push_back(create_tree(arr, N, k, height − 1, count)) ব্যবহার করে এই নোডটিকে ট্রিতে যোগ করুন। -
অন্যথায় newNode−>root.push_back(NULL);
ব্যবহার করে NULL পুশ করে ট্রি শেষ করুন -
শেষে পয়েন্টারটিকে নোডে ফিরিয়ে দিন।
-
ফাংশন create_tree(int* arr, int N, int k, int count) গাছের উচ্চতা প্রদান করে।
-
উচ্চতা =(int)সিল(লগ((ডাবল)N * (k − 1) + 1) / লগ((ডাবল)k));
-
উপরে গণনা করা উচ্চতায় গাছের জন্য রিটার্ন স্টেটমেন্টে create_tree(arr, N, k, height, count) কল করুন।
-
ফাংশন postorder_traversal(Tree_Node* node, int k) নোডে রুট করা k−ary গাছের প্রিঅর্ডারট্রাভার্সাল প্রিন্ট করে।
-
যদি নোডটি NULL হয় তাহলে কিছুই ফেরত দিন।
-
i=0 থেকে i
রুট[i], কে); -
প্রিন্ট নোড−>লুপের শেষে ঠিকানা।
উদাহরণ
#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
