ในปัญหานี้ เราได้รับไบนารีทรีและจำนวนเต็ม N ภารกิจคือการค้นหาโหนดที่ n ในการสั่งซื้อล่วงหน้าของทรีไบนารี
ต้นไม้ไบนารีมีเงื่อนไขพิเศษที่แต่ละโหนดสามารถมีลูกได้สูงสุดสองคน
การข้ามผ่านเป็นกระบวนการในการเยี่ยมชมโหนดทั้งหมดของต้นไม้และอาจพิมพ์ค่าของพวกมันด้วย
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
N = 6
ผลลัพธ์
6
คำอธิบาย
Pre order traversal of tree : 1, 2, 4, 5, 3, 6, 7
แนวทางการแก้ปัญหา
แนวคิดคือการใช้การสั่งจองล่วงหน้าของไบนารีทรีซึ่งทำได้โดยใช้การเรียกซ้ำ ในการโทรแต่ละครั้ง เราจะไปที่โหนดรูท จากนั้นเรียก preOrder() สำหรับทรีย่อยด้านซ้ายก่อน จากนั้นจึงเรียก preOrder() ในระหว่างการข้ามผ่านนี้ เราจะนับจำนวนโหนดและพิมพ์โหนดที่นับเป็น N
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#include <iostream>
using namespace std;
struct Node {
int data;
Node *left, *right;
};
struct Node* createNode(int item){
Node* temp = new Node;
temp->data = item;
temp->left = NULL;
temp->right = NULL;
return temp;
}
void findPreOrderTraversalRec(struct Node* root, int N){
static int nodeCount = 0;
if (root == NULL)
return;
if (nodeCount <= N) {
nodeCount++;
if (nodeCount == N)
cout << root->data;
findPreOrderTraversalRec(root->left, N);
findPreOrderTraversalRec(root->right, N);
}
}
int main() {
struct Node* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
root->right->left = createNode(6);
root->right->right = createNode(7);
int N = 6;
cout<<N<<"th node in preorder traversal is ";
findPreOrderTraversalRec(root, N);
return 0;
} ผลลัพธ์
6th node in preorder traversal is 6
