عدد أشقاء عقدة معينة في شجرة n-ary


مستوى الصعوبة الثابت
كثيرا ما يطلب في أمازون بلومبرغ CodeNation جوجل
N- آري-تري طابور البحث شجرة اجتياز الشجرة

المشكلة بيان

تشير مشكلة "عدد الأشقاء لعقدة معينة في شجرة n-ary" إلى أنك تحصل على n-ary Tree والعقدة المستهدفة. أوجد عدد أشقاء العقدة المستهدفة. افترض أن العقدة موجودة دائمًا في الشجرة وأن العقدة الأولى هي جذر الشجرة.

مثال

إدخال

عدد أشقاء عقدة معينة في شجرة n-ary

عقدة = 10
عقدة = 11

3
1

تفسير
أشقاء العشرة هم {10 ، 41 ، 6}
أشقاء 11 عامًا هم {9}

خوارزمية

أشقاء العقدة هم العقد الموجودة على نفس مستوى العقدة المعينة ، أو بعبارة أخرى ، يكون أشقاء العقدة أقل بمقدار واحد من عدد الأبناء لوالدها.

النظر في شجرة في المثال أعلاه ، ودع العقدة تكون 10
والد 10 = 51
الأطفال الذين يبلغون من العمر 51 عامًا هم {10 ، 41 ، 32 ، 6}
الأشقاء ذوو العشرة أعوام هم أبناء لوالديه باستثناء 10 ، أي أن الأشقاء لـ 10 أعوام هم {10 ، 41 ، 32}

نقطة مهمة: عدد أشقاء الجذر هو 0. لأنه لا يوجد والد للجذر.

تتمثل فكرة العثور على عدد الأشقاء في العقدة في عمل BFS على الشجرة المحددة ، إذا كانت العناصر الفرعية للعقدة هي نفسها العقدة المحددة ، فقم بإرجاع (عدد الأطفال التابعين لتلك العقدة - 1).

  1. إذا كانت العقدة المعطاة تساوي الجذر أو كان الجذر فارغًا ، فقم بإرجاع 0.
  2. قم بإنشاء قائمة انتظار من العقد لـ BFS ودفع الجذر إلى قائمة الانتظار.
  3. بينما قائمة الانتظار ليست فارغة كرر الخطوة 4.
  4. قم بإزالة عنصر من قائمة الانتظار ، وقم بالمرور عبر جميع العناصر الفرعية للعنصر الحالي ، إذا كان أي من العناصر التابعة له يساوي العقدة المعطاة ، قم بإرجاع (عدد العناصر التابعة للعقدة الحالية - 1) ، وإلا ادفع الأطفال إلى قائمة الانتظار.
  5. إذا لم تكن هناك عقدة تطابق العقدة المحددة ، فارجع -1.

رمز

كود Java للبحث عن عدد الأشقاء للعقدة المحددة في شجرة n-ary

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

#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

تحليل التعقيد

تعقيد الوقت

O (N) لأننا قمنا بعمل BFS للشجرة. لقد اجتزنا للتو جميع العقد التي جعلت الخوارزمية تعمل في الوقت الخطي.

تعقيد الفضاء

O (N) لقد كلفنا استخدام قائمة انتظار لـ BFS مساحة خطية. وبالتالي فإن تعقيد مساحة الخوارزمية هو O (N).