Ditulis dalam C++, cari bilangan adik-beradik bagi nod yang diberikan dalam pepohon N-ary

Dalam artikel ini, kami akan memberikan maklumat lengkap untuk menentukan bilangan adik-beradik bagi nod yang diberikan dalam pokok n-ary. Kita perlu mencari nod adik-beradik nod ini menggunakan nilai kunci yang diberikan oleh pengguna, jika tidak, keluaran -1. Hanya ada satu kaedah yang boleh kita gunakan -

Kaedah mudah

Dalam kaedah ini kita akan melelang melalui semua nod dan menyemak sama ada nod anak mempunyai nilai yang sama dengan pengguna. Jika ada, kami menjawab bilangan nod anak - 1 (nilai yang diberikan).

Contoh

#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;
}

Output

3

Penerangan program di atas

Dalam program ini, kami mengekalkan baris gilir yang mengandungi nod yang tidak dilawati dan akan memunculkan nod yang dilawati. Sekarang apabila kita meneroka nod kita meneroka anak-anaknya dan jika nilai kanak-kanak itu sepadan dengan x maka bendera kita dicetuskan dan pembolehubah jawapan kita telah diberikan nilai child.size() - 1 dan Kemudian kita keluar dari gelung for dan sekarang kami menyemak sama ada bendera dicetuskan. Jika ia menyala, maka kita keluar dari gelung while. Selepas itu, jika tiada nod dengan nilai yang diberikan, kami kini mencetak jawapan, jadi pembolehubah jawapan kami tidak berubah dan output akan menjadi -1. Jika nilai akar adalah sama dengan nilai yang diberikan, terdapat pernyataan if yang menyemak nilai dan menjalankan program kami.

Kesimpulan

Dalam kertas ini, kami menyelesaikan masalah untuk mencari bilangan adik-beradik nod yang diberikan dalam pokok n bercabang dengan kerumitan masa O(N). Kami juga mempelajari program C++ untuk menyelesaikan masalah ini dan kaedah lengkap untuk menyelesaikan masalah ini. Kita boleh menulis program yang sama dalam bahasa lain, seperti C, java, python dan bahasa lain.

Atas ialah kandungan terperinci Ditulis dalam C++, cari bilangan adik-beradik bagi nod yang diberikan dalam pepohon N-ary. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!