इस समस्या में, हमें एक बाइनरी ट्री दिया जाता है और हमें उसके नोड के पूर्वज को बाइनरी ट्री में प्रिंट करना होता है।
बाइनरी ट्री एक विशेष पेड़ है जिसके प्रत्येक नोड में अधिकतम दो बच्चे नोड होते हैं। इसलिए, प्रत्येक नोड या तो लीफ नोड होता है या उसमें एक या दो चाइल्ड नोड होते हैं।
उदाहरण,
पूर्वज बाइनरी ट्री में एक नोड एक नोड होता है जो दिए गए नोड के ऊपरी स्तर पर होता है।
आइए पूर्वज नोड का एक उदाहरण लेते हैं -
इस बाइनरी ट्री में मान 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