หาจำนวนพี่น้องของโหนดที่กำหนดใน N-ary Tree ด้วย C++

ในบทความนี้ เราจะให้ข้อมูลครบถ้วนในการหาจำนวนพี่น้องของโหนดที่กำหนดใน N-ary Tree เราต้องหาพี่น้องของโหนดที่มีค่า key ตามที่ผู้ใช้กำหนด หากไม่มี ให้แสดงผลเป็น -1 มีเพียงวิธีเดียวที่เราสามารถใช้ได้:

วิธีการง่าย (Simple Approach)

ในวิธีนี้ เราจะตรวจสอบโหนดทุกตัว และตรวจสอบว่าลูกโหนดไหนมีค่าเท่ากับค่าที่ผู้ใช้กำหนด หากมี เราจะตอบเป็น จำนวนลูกโหนด - 1 (ค่าที่กำหนด)

ตัวอย่างโค้ด

#include <bits/stdc++.h>
using namespace std;

class Node {
    // โครงสร้างโหนดของต้นไม้
public:
    int key;
    vector<Node*> child;
    Node(int data) {
        key = data;
    }
};

int main() {
    // สร้างต้นไม้ (Building The Tree)
    Node* Base = new Node(50);
    (Base->child).push_back(new Node(2));
    (Base->child).push_back(new Node(30));
    (Base->child).push_back(new Node(14));
    (Base->child).push_back(new Node(60));
    (Base->child[0]->child).push_back(new Node(15));
    (Base->child[0]->child).push_back(new Node(25));
    (Base->child[0]->child[1]->child).push_back(new Node(70));
    (Base->child[0]->child[1]->child).push_back(new Node(100));
    (Base->child[1]->child).push_back(new Node(6));
    (Base->child[1]->child).push_back(new Node(1));
    (Base->child[2]->child).push_back(new Node(7));
    (Base->child[2]->child[0]->child).push_back(new Node(17));
    (Base->child[2]->child[0]->child).push_back(new Node(99));
    (Base->child[2]->child[0]->child).push_back(new Node(27));
    (Base->child[3]->child).push_back(new Node(16));
    
    int x = 30;
    queue<Node*> q;
    q.push(Base);
    bool flag = 0;
    int answer = -1;
    
    if(Base -> key != x) {
        while(!q.empty()) {
            auto parent = q.front();
            q.pop();
            for(int i = 0; i < parent -> child.size(); i++) {
                if(parent -> child[i] -> key == x) {
                    answer = parent -> child.size() - 1;
                    flag = 1;
                    break;
                }
                q.push(parent -> child[i]);
            }
            if(flag)
                break;
        }
        cout << answer << "\n";
    } else
        cout << "0\n";
    return 0;
}

ผลลัพธ์

3

คำอธิบายโปรแกรม

ในโปรแกรมนี้ เรารักษาคิว (queue) ที่จะมีโหนดที่ยังไม่ได้เยี่ยมชมอยู่ภายใน และโหนดที่เยี่ยมชมแล้วจะถูกนำออก (pop) ตอนนี้ เมื่อเราสำรวจโหนดหนึ่ง เราจะสำรวจลูกโหนดของมัน และหากค่าของลูกโหนดตรงกับ x แล้ว flag ของเราจะทำงาน และตัวแปร answer จะได้รับค่า child.size() - 1 และจากนั้นเราจะออกจาก for loop ตอนนี้เราตรวจสอบว่า flag ทำงานหรือไม่ หากทำงาน เราจะออกจาก while loop หลังจากนั้น เราจะพิมพ์คำตอบ ตอนนี้ หากไม่มีโหนดที่มีค่าตามที่กำหนด ตัวแปร answer จะไม่เปลี่ยนแปลง และผลลัพธ์จะเป็น -1 หากค่าของรูท (root) มีค่าเท่ากับค่าที่กำหนด มีคำสั่ง if ที่ตรวจสอบเรื่องนี้และรันโปรแกรมของเรา

สรุป

ในบทความนี้ เราแก้ปัญหาการหา จำนวนพี่น้องของโหนดที่กำหนดใน N-ary Tree ด้วยความซับซ้อนด้านเวลา O(N) เรายังเรียนรู้โปรแกรม C++ สำหรับปัญหานี้ และวิธีการแก้ปัญหาทั้งหมด สามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, Java, Python ได้เช่นกัน