Trong bài viết này, chúng tôi sẽ cung cấp thông tin đầy đủ để xác định số lượng nút anh chị em của một nút nhất định trong cây n-ary. Chúng ta cần tìm anh chị em của nút với giá trị của khóa do người dùng cung cấp; nếu nó không phải là khác, thì đầu ra là -1. Chỉ có một cách tiếp cận mà chúng tôi có thể sử dụng -
Cách tiếp cận đơn giản
Trong cách tiếp cận này, chúng tôi sẽ đi qua tất cả các nút và kiểm tra xem một phần tử con có cùng giá trị với người dùng hay không. Nếu nó tồn tại, chúng tôi trả lời một số con - 1 (giá trị đã cho).
Ví dụ
#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;
} Đầu ra
3
Giải thích về Chương trình trên
Trong chương trình này, chúng tôi duy trì một hàng đợi sẽ có các nút chưa được truy cập bên trong nó và nút đã truy cập sẽ được xuất hiện. Bây giờ, khi chúng ta khám phá một nút, chúng ta khám phá các nút con của nó và nếu giá trị của nút con khớp với x, thì cờ của chúng ta sẽ được kích hoạt và biến câu trả lời của chúng ta đã được gán giá trị của nút con.size () - 1, và sau đó chúng tôi vượt qua vòng lặp for, bây giờ chúng tôi kiểm tra xem cờ có được kích hoạt hay không. Nếu nó được kích hoạt, thì chúng ta sẽ thoát ra khỏi vòng lặp while. Sau đó, chúng tôi in câu trả lời ngay bây giờ nếu không tồn tại một nút với giá trị đã cho, vì vậy biến câu trả lời của chúng tôi sẽ không thay đổi và đầu ra sẽ là -1. Nếu giá trị gốc có cùng giá trị như đã cho, có một câu lệnh if sẽ kiểm tra điều đó và chạy chương trình của chúng tôi.
Kết luận
Trong bài viết này, chúng tôi giải quyết vấn đề để tìm số anh chị em của một nút nhất định trong cây n-ary theo thời gian phức tạp O (N). Chúng tôi cũng đã học chương trình C ++ cho vấn đề này và cách tiếp cận hoàn chỉnh mà chúng tôi đã giải quyết vấn đề này. Chúng ta có thể viết cùng một chương trình bằng các ngôn ngữ khác như C, java, python và các ngôn ngữ khác.