ในปัญหานี้ เราได้รับไบนารีทรีและเราต้องพิมพ์บรรพบุรุษของโหนดในไบนารีทรี
ต้นไม้ไบนารี เป็นต้นไม้พิเศษที่ทุกโหนดมีโหนดย่อยสูงสุดสองโหนด ดังนั้น ทุกโหนดจึงเป็นโหนดปลายสุดหรือมีโหนดย่อยหนึ่งหรือสองโหนด
ตัวอย่าง
บรรพบุรุษ ของโหนดในไบนารีทรีคือโหนดที่อยู่ในระดับบนของโหนดที่กำหนด
มาดูตัวอย่างโหนดบรรพบุรุษกัน −
บรรพบุรุษของโหนดที่มีค่า 3 ในไบนารีทรีนี้คือ 8
สำหรับการแก้ปัญหานี้ เราจะข้ามจากโหนดรูทไปยังโหนดเป้าหมาย ทีละขั้นตอนลงในไบนารีทรี และในเส้นทางให้พิมพ์โหนดทั้งหมดที่มา
ตัวอย่าง
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
struct node{
int data;
struct node* left;
struct node* right;
};
bool AncestorsNodes(struct node *root, int target){
if (root == NULL)
return false;
if (root->data == target)
return true;
if ( AncestorsNodes(root->left, target) || AncestorsNodes(root->right, target) ){
cout << root->data << " ";
return true;
}
return false;
}
struct node* insertNode(int data){
struct node* node = (struct node*) malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;
return(node);
}
int main(){
struct node *root = insertNode(10);
root->left = insertNode(6);
root->right = insertNode(13);
root->left->left = insertNode(3);
root->left->right = insertNode(8);
root->right->left = insertNode(12);
cout<<"Ancestor Nodes are " ;
AncestorsNodes(root, 8);
getchar();
return 0;
} ผลลัพธ์
Ancestor Nodes are 6 10
