এই সমস্যায়, আমাদের একটি বাইনারি ট্রি দেওয়া হয়েছে এবং আমাদের একটি বাইনারি গাছে একটি নোডের পূর্বপুরুষ প্রিন্ট করতে হবে৷
বাইনারি ট্রি হল একটি বিশেষ গাছ যার প্রতিটি নোডে সর্বোচ্চ দুটি চাইল্ড নোড থাকে। সুতরাং, প্রতিটি নোড হয় একটি লিফ নোড বা একটি বা দুটি চাইল্ড নোড রয়েছে৷
উদাহরণ,
পূর্বপুরুষ একটি বাইনারি গাছের একটি নোড হল একটি নোড যা প্রদত্ত নোডের উপরের স্তরে থাকে৷
পূর্বপুরুষ নোড -
-এর একটি উদাহরণ নেওয়া যাক
এই বাইনারি গাছে 3 মান সহ একটি নোডের পূর্বপুরুষ হল 8 ,
এই সমস্যা সমাধানের জন্য, আমরা রুট নোড থেকে লক্ষ্য নোডে যাবো। বাইনারি গাছে ধাপে ধাপে নিচের দিকে। এবং পথে আসা সমস্ত নোডগুলি মুদ্রণ করুন৷
৷এটি আদর্শভাবে রুট নোড থেকে লক্ষ্য নোডের পথে আসা প্রতিটি নোডের সাথে একই পদ্ধতির পুনরাবৃত্তিমূলক কলিংকে জড়িত করবে৷
সুতরাং, একটি অ-পুনরাবৃত্ত পদ্ধতির জন্য পুনরাবৃত্তিমূলক ট্রাভার্সাল এবং একটি স্ট্যাক ব্যবহার করা প্রয়োজন যা লক্ষ্য নোডের পূর্বপুরুষকে গাছে সংরক্ষণ করবে। আমরা বাইনারি গাছের পোস্টঅর্ডার ট্রাভার্সাল করব। এবং পূর্বপুরুষকে স্ট্যাকে সংরক্ষণ করুন এবং শেষ পর্যন্ত স্ট্যাকের বিষয়বস্তু প্রিন্ট করুন যা নোডের পূর্বপুরুষ হবে।
উদাহরণ
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
struct Node{
int data;
struct Node *left, *right;
};
struct Stack{
int size;
int top;
struct Node* *array;
};
struct Node* insertNode(int data){
struct Node* node = (struct Node*) malloc(sizeof(struct Node));
node->data = data;
node->left = node->right = NULL;
return node;
}
struct Stack* createStack(int size){
struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack));
stack->size = size;
stack->top = -1;
stack->array = (struct Node**) malloc(stack->size * sizeof(struct Node*));
return stack;
}
int isFull(struct Stack* stack){
return ((stack->top + 1) == stack->size);
}
int isEmpty(struct Stack* stack){
return stack->top == -1;
}
void push(struct Stack* stack, struct Node* node){
if (isFull(stack))
return;
stack->array[++stack->top] = node;
}
struct Node* pop(struct Stack* stack){
if (isEmpty(stack))
return NULL;
return stack->array[stack->top--];
}
struct Node* peek(struct Stack* stack){
if (isEmpty(stack))
return NULL;
return stack->array[stack->top];
}
void AncestorNodes(struct Node *root, int key){
if (root == NULL) return;
struct Stack* stack = createStack(MAX_SIZE);
while (1){
while (root && root->data != key){
push(stack, root);
root = root->left;
}
if (root && root->data == key)
break;
if (peek(stack)->right == NULL){
root = pop(stack);
while (!isEmpty(stack) && peek(stack)->right == root)
root = pop(stack);
}
root = isEmpty(stack)? NULL: peek(stack)->right;
}
while (!isEmpty(stack))
printf("%d ", pop(stack)->data);
}
int main(){
struct Node* root = insertNode(15);
root->left = insertNode(10);
root->right = insertNode(25);
root->left->left = insertNode(5);
root->left->right = insertNode(12);
root->right->left = insertNode(20);
root->right->right = insertNode(27);
root->left->left->left = insertNode(1);
root->left->right->right = insertNode(14);
root->right->right->left = insertNode(17);
printf("The ancestors of the given node are : ");
AncestorNodes(root, 17);
getchar();
return 0;
} আউটপুট
The ancestors of the given node are : 27 25 15
