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