ต้นไม้ n-ary คือต้นไม้ที่มีลูก n ตัวสำหรับแต่ละโหนด เราได้ตัวเลข n และเราต้องหาองค์ประกอบที่ใหญ่กว่าตัวถัดไปจากต้นไม้ n-ary
เราหาทางแก้ไขได้โดยข้ามผ่านต้นไม้ n-ary และรักษาผลลัพธ์ไว้
อัลกอริทึม
- สร้าง n-ary tree
- เริ่มต้นผลลัพธ์
- เขียนฟังก์ชันเพื่อให้ได้องค์ประกอบที่ใหญ่ขึ้นถัดไป
- ส่งคืนหากโหนดปัจจุบันเป็นโมฆะ
- ตรวจสอบว่าข้อมูลโหนดปัจจุบันมากกว่าองค์ประกอบที่คาดไว้หรือไม่
- ถ้าใช่ ให้ตรวจสอบว่าผลลัพธ์ว่างเปล่าหรือผลลัพธ์มากกว่าข้อมูลโหนดปัจจุบัน
- หากเป็นไปตามเงื่อนไขข้างต้น ให้อัปเดตผลลัพธ์
- รับโหนดลูกปัจจุบัน
- ย้ำกับเด็กๆ
- เรียกฟังก์ชันแบบเรียกซ้ำ
เรากำลังอัปเดตผลลัพธ์ทุกครั้งที่เราพบองค์ประกอบที่มากกว่าจำนวนที่กำหนดและน้อยกว่าผลลัพธ์ เพื่อให้แน่ใจว่าเราจะได้องค์ประกอบที่ใหญ่กว่าในตอนท้าย
การนำไปใช้
ต่อไปนี้เป็นการนำอัลกอริธึมข้างต้นไปใช้ใน C++
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
vector<Node*> child;
};
Node* newNode(int data) {
Node* newNode = new Node;
newNode->data = data;
return newNode;
}
void findNextGreaterElement(Node* root, int x, Node** result) {
if (root == NULL) {
return;
}
if (root->data > x) {
if (!(*result) || (*result)->data > root->data) {
*result = root;
}
}
int childCount = root->child.size();
for (int i = 0; i < childCount; i++) {
findNextGreaterElement(root->child[i], x, result);
}
return;
}
int main() {
Node* root = newNode(10);
root->child.push_back(newNode(12));
root->child.push_back(newNode(23));
root->child.push_back(newNode(45));
root->child[0]->child.push_back(newNode(40));
root->child[1]->child.push_back(newNode(33));
root->child[2]->child.push_back(newNode(12));
Node* result = NULL;
findNextGreaterElement(root, 20, &result);
cout << result->data << endl;
return 0;
} ผลลัพธ์
หากคุณเรียกใช้โค้ดด้านบน คุณจะได้ผลลัพธ์ดังต่อไปนี้
23
