تعداد خواهران و برادرهای یک گره داده شده در n-ary Tree  


سطح دشواری سخت
اغلب در آمازون بلومبرگ CodeNation گوگل
N-arry-tree صف جستجو درخت عبور از درخت

بیان مسأله  

مسئله "تعداد خواهران و برادرهای یک گره داده شده در n-ary Tree" بیان می کند که یک درخت n-ary و یک گره هدف به شما داده می شود. تعداد خواهر و برادرهای گره هدف را پیدا کنید. فرض کنید گره همیشه در درخت وجود داشته باشد و گره اول ریشه درخت باشد.

مثال  

ورودی

تعداد خواهران و برادرهای یک گره داده شده در n-ary Tree

گره = 10
گره = 11

3
1

توضیح
خواهر و برادر 10 ساله {41 ، 6 ، 32} هستند
خواهر و برادر 11 ساله {9} هستند

الگوریتم  

خواهر و برادرهای گره ، گره هایی هستند که در همان سطح گره داده شده وجود دارند ، یا به عبارت دیگر ، خواهر و برادرهای یک گره ، یک تعداد کمتر از تعداد فرزندان والدین آن هستند.

در نظر بگیرید درخت در مثال بالا ، و اجازه دهید گره 10 باشد
والد 10 = 51
کودکان 51 ساله {10 ، 41 ، 32 ، 6} ساله هستند
خواهر و برادر 10 فرزند به جز 10 فرزند هستند ، یعنی خواهر و برادر 10 ساله {41 ، 32 ، 6} هستند

نکته مهم: تعداد خواهر و برادرهای ریشه 0 است. زیرا والدین ریشه وجود ندارد.

ایده یافتن تعداد خواهر و برادرهای یک گره انجام BFS بر روی درخت داده شده است ، اگر فرزندان گره همان گره داده شده باشد ، برگردانید (تعداد فرزندان آن گره - 1).

  1. اگر گره داده شده برابر ریشه باشد یا ریشه تهی باشد ، 0 را برگردانید.
  2. برای گره ها صف ایجاد کنید BFS و ریشه را به صف فشار دهید.
  3. در حالی که صف خالی نیست مرحله 4 را تکرار کنید.
  4. یک عنصر را از صف خارج کنید ، از بین تمام فرزندان عنصر فعلی عبور کنید ، اگر هر یک از فرزندان آن برابر با گره داده شده باشد ، برگردانید (تعداد فرزندان گره فعلی - 1) ، در غیر این صورت کودکان را به صف فشار دهید.
  5. اگر گره ای با گره داده شده مطابقت ندارد ، -1 را برگردانید.
همچنین مشاهده کنید
بررسی کنید که آیا یک باینری درخت کامل است یا خیر

رمز  

جاوا کد برای یافتن تعداد خواهران و برادرهای یک گره داده شده در n-ary Tree

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

class NumberOfSiblingsOfAGivenNodeInNAryTree {
    // class representing node of n-ary tree
    static class Node {
        
        ArrayList<Node> child;
        int data;
        public Node(int data) {
            this.data = data;
            this.child = new ArrayList<>();
        }
    }

    private static int siblings(Node root, int target) {
        // if the given node is equals to the root or root is null, return 0
        if (root == null || root.data == target) {
            return 0;
        }

        // create a queue of nodes
        Queue<Node> queue = new LinkedList<>();
        // push the root to queue
        queue.add(root);

        // do a BFS of the tree
        while (!queue.isEmpty()) {
            // remove one element from the queue
            Node curr = queue.poll();
            // traverse its children
            for (int i = 0; i < curr.child.size(); i++) {
                // current child
                Node currChild = curr.child.get(i);
                // if current child is the target, return (parent's children count - 1)
                if (currChild.data == target) {
                    return (curr.child.size() - 1);
                }
                // add the child to the queue
                queue.add(currChild);
            }
        }

        // if there is no match, return -1
        return -1;
    }

    public static void main(String[] args) {
        // Example n-ary tree
        Node root = new Node(51);
        // children of 51
        root.child.add(new Node(10));
        root.child.add(new Node(41));
        root.child.add(new Node(6));
        root.child.add(new Node(32));
        // children of 10
        root.child.get(0).child.add(new Node(53));
        // children of 41
        root.child.get(1).child.add(new Node(95));
        // children of 6
        root.child.get(2).child.add(new Node(28));
        // children of 32
        root.child.get(3).child.add(new Node(9));
        root.child.get(3).child.add(new Node(11));
        // children of 53
        root.child.get(0).child.get(0).child.add(new Node(5));
        root.child.get(0).child.get(0).child.add(new Node(7));
        // children of 11
        root.child.get(3).child.get(1).child.add(new Node(3));
        root.child.get(3).child.get(1).child.add(new Node(8));

        System.out.println(siblings(root, 10));
        System.out.println(siblings(root, 11));
    }
}
3
1

C ++ کد برای یافتن تعداد خواهران و برادرهای یک گره داده شده در n-ary Tree

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

// class representing node of a n-ary tree
class Node {
    public:
    int data;
    vector<Node*> child;
    
    Node(int d) {
        data = d;
    }
};

int siblings(Node *root, int target) {
    // if the given node is equals to the root or root is null, return 0
    if (root == NULL || root->data == target) {
        return 0;
    }
    
    // create a queue of nodes
    queue<Node*> q;
    // push the root to queue
    q.push(root);
    
    // do a BFS of the tree
    while (!q.empty()) {
        // remove one element from the queue
        Node *curr = q.front();
        q.pop();
        // traverse its children
        for (int i = 0; i < curr->child.size(); i++) {
            // current child
            Node *currChild = curr->child[i];
            // if current child is the target, return (parent's children count - 1)
            if (currChild->data == target) {
                return (curr->child.size() - 1);
            }
            // add the child to the queue
            q.push(curr->child[i]);
        }
    }
    
    // if there is no match, return -1
    return -1;
}

int main() {
    // Example n-ary tree
    Node *root = new Node(51);
    // children of 51
    root->child.push_back(new Node(10));
    root->child.push_back(new Node(41));
    root->child.push_back(new Node(6));
    root->child.push_back(new Node(32));
    // children of 10
    root->child[0]->child.push_back(new Node(53));
    // children of 41
    root->child[1]->child.push_back(new Node(95));
    // children of 6
    root->child[2]->child.push_back(new Node(28));
    // children of 32
    root->child[3]->child.push_back(new Node(9));
    root->child[3]->child.push_back(new Node(11));
    // children of 53
    root->child[0]->child[0]->child.push_back(new Node(5));
    root->child[0]->child[0]->child.push_back(new Node(7));
    // children of 11
    root->child[3]->child[1]->child.push_back(new Node(3));
    root->child[3]->child[1]->child.push_back(new Node(8));

    cout<<siblings(root, 10)<<endl;
    cout<<siblings(root, 11)<<endl;
    
    return 0;
}
3
1

تحلیل پیچیدگی  

پیچیدگی زمان

بر)، زیرا ما BFS را برای درخت انجام داده ایم. ما فقط تمام گره هایی را که باعث شده الگوریتم در زمان خطی اجرا شود ، مرور کردیم.

همچنین مشاهده کنید
حداقل تعداد عناصر مشخص پس از حذف m مورد

پیچیدگی فضا

بر)، استفاده از یک صف برای BFS برای ما فضای خطی هزینه دارد. بنابراین پیچیدگی فضایی الگوریتم O (N) است.