องค์ประกอบที่มากกว่าถัดไปใน n-ary tree ใน C++

โจทย์

n-ary tree คือต้นไม้ที่มีลูก n ตัวสำหรับแต่ละโหนด เราได้รับตัวเลข n และเราต้องหาองค์ประกอบที่มากกว่าถัดไปจาก n-ary tree

เราสามารถหาคำตอบได้โดยการท่องผ่าน n-ary tree และรักษาผลลัพธ์

อัลกอริธึม

สร้าง n-ary tree
กำหนดผลลัพธ์
เขียนฟังก์ชันหาองค์ประกอบที่มากกว่าถัดไป
- คืนค่าถ้าโหนดปัจจุบันเป็น null
- ตรวจสอบข้อมูลโหนดปัจจุบันว่ามากกว่าองค์ประกอบที่คาดหวังหรือไม่
- ถ้าใช่ ตรวจสอบว่าผลลัพธ์ว่างหรือผลลัพธ์มากกว่าข้อมูลโหนดปัจจุบัน
- ถ้าเงื่อนไขข้างต้นเป็นจริง ให้อัปเดตผลลัพธ์
- รับลูกของโหนดปัจจุบัน
- วนลูปผ่านลูก
  - เรียกฟังก์ชันเวียนเกิด

เราอัปเดตผลลัพธ์ทุกครั้งที่พบองค์ประกอบที่มากกว่าตัวเลขที่กำหนดและน้อยกว่าผลลัพธ์ปัจจุบัน มันรับประกันว่าเราจะได้องค์ประกอบที่มากกว่าถัดไปในที่สุด

การนำไปใช้งาน

ต่อไปนี้เป็นการนำไปใช้งานของอัลกอริธึมข้างต้นใน 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; 
}

ผลลัพธ์

หากคุณรันโค้ดข้างต้น คุณจะได้ผลลัพธ์ดังนี้