ในปัญหานี้ เราได้รับไบนารีทรีและเราต้องพิมพ์บรรพบุรุษของโหนดในไบนารีทรี
Binary Tree เป็นต้นไม้พิเศษที่ทุกโหนดมีโหนดย่อยสูงสุดสองโหนด ดังนั้น ทุกโหนดจึงเป็นโหนดปลายสุดหรือมีโหนดย่อยหนึ่งหรือสองโหนด
ตัวอย่าง
บรรพบุรุษ ของโหนดในไบนารีทรีคือโหนดที่อยู่ในระดับบนของโหนดที่กำหนด
มาดูตัวอย่างโหนดบรรพบุรุษกัน −
บรรพบุรุษของโหนดที่มีค่า 3 ในไบนารีทรีนี้คือ 8 ,
สำหรับการแก้ปัญหานี้ เราจะข้ามจากโหนดรูทไปยังโหนดเป้าหมาย ทีละขั้นตอนลงในไบนารีทรี และในเส้นทางให้พิมพ์โหนดทั้งหมดที่มา
สิ่งนี้จะเกี่ยวข้องกับการเรียกซ้ำของเมธอดเดียวกันกับแต่ละโหนดที่มาในเส้นทางจากโหนดรูทไปยังโหนดเป้าหมาย
ดังนั้น วิธีการแบบไม่เรียกซ้ำจะต้องใช้การข้ามผ่านแบบวนซ้ำและสแต็กที่จะจัดเก็บบรรพบุรุษของโหนดเป้าหมายในแผนผัง เราจะทำการข้ามผ่าน postorder ของไบนารีทรี และเก็บบรรพชนไว้ที่สแต็ก และสุดท้ายให้พิมพ์เนื้อหาของสแต็กซึ่งจะเป็นบรรพบุรุษของโหนด
ตัวอย่าง
#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
