ในบทความนี้ เราจะให้ข้อมูลที่สมบูรณ์เพื่อกำหนดจำนวนพี่น้องของโหนดที่กำหนดในแผนผัง n-ary เราจำเป็นต้องค้นหาพี่น้องของโหนดด้วยค่าของคีย์ตามที่ผู้ใช้กำหนด หากไม่ใช่ ให้ส่งออกเป็น -1 มีทางเดียวเท่านั้นที่เราสามารถใช้ได้ -
แนวทางง่ายๆ
ในแนวทางนี้ เราจะตรวจสอบโหนดทั้งหมดและตรวจสอบว่าลูกมีค่าเท่ากับผู้ใช้หรือไม่ หากมี เราจะตอบจำนวนลูก - 1(ค่าที่กำหนด)
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
class Node { // structure of nodes of our tree.
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
คำอธิบายของโปรแกรมข้างต้น
ในโปรแกรมนี้ เรารักษาคิวที่จะมีโหนดที่ยังไม่ได้เยี่ยมชมอยู่ภายใน และโหนดที่เยี่ยมชมจะถูกเปิดออกมา ตอนนี้ เมื่อเราสำรวจโหนด เราจะสำรวจลูกของมัน และหากค่าของเด็กตรงกับ x แฟล็กของเราจะถูกทริกเกอร์ และตัวแปรคำตอบของเราได้รับการกำหนดค่าของ child.size() - 1 และ จากนั้นเราเจาะผ่าน for a loop ตอนนี้เราตรวจสอบว่าแฟล็กถูกทริกเกอร์หรือไม่ ถ้ามันถูกทริกเกอร์ เราก็ออกมาจากลูป while หลังจากนั้น เราจะพิมพ์คำตอบทันที หากไม่มีโหนดที่มีค่าที่กำหนด ดังนั้นตัวแปรคำตอบของเราจะไม่เปลี่ยนแปลง และผลลัพธ์จะเป็น -1 หากค่ารูทมีค่าเท่ากับที่กำหนด จะมีคำสั่ง if ที่ตรวจสอบค่านั้นและรันโปรแกรมของเรา
บทสรุป
ในบทความนี้ เราแก้ปัญหาเพื่อค้นหา จำนวนพี่น้องของโหนดที่กำหนดในทรี n-ary ในความซับซ้อนของเวลา O(N) นอกจากนี้เรายังได้เรียนรู้โปรแกรม C ++ สำหรับปัญหานี้และแนวทางที่สมบูรณ์ซึ่งเราแก้ไขปัญหานี้ เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, java, python และภาษาอื่นๆ
