الأسئلة والأجوبة الأكثر شيوعًا لمقابلة الشجرة الثنائية [للمستجدين وذوي الخبرة]

مقدمة

تعد هياكل البيانات أحد المفاهيم الأساسية في البرمجة الشيئية. لشرح ذلك ببساطة ، فإن بنية البيانات هي طريقة خاصة لتنظيم البيانات في الكمبيوتر بحيث يمكن معالجتها بشكل فعال. هناك العديد من هياكل البيانات مثل المكدسات وقوائم الانتظار والأشجار التي لها خصائصها الفريدة.

تسمح لنا الأشجار بتنظيم البيانات بطريقة هرمية. تختلف بنية البيانات هذه اختلافًا كبيرًا عن هياكل البيانات الخطية مثل القوائم أو المصفوفات المرتبطة. تتكون الشجرة من عقد تحمل المعلومات.

الشجرة الثنائية هي نوع خاص من الأشجار يمكن أن يكون لها ما يصل إلى طفلين فقط. هذا يعني أن عقدة معينة في الشجرة الثنائية لا يمكن أن يكون لها طفل أو طفل واحد أو طفلان ولكن ليس أكثر. الشجرة الثنائية هي بنية بيانات مهمة يمكن أن تمكننا من حل المشكلات الصعبة وبناء أكواد معقدة.

إذا كنت تتقدم لوظيفة كمطور Java أو مهندس برمجيات ، فقد تحتوي مقابلتك على عدة أسئلة تدور حول هذا المفهوم. في كثير من الأحيان ، يجد المرشحون صعوبة في الإجابة على الأسئلة بناءً على الأشجار الثنائية وأشجار البحث الثنائية والبرامج ذات الصلة. في هذه المقالة ، سوف نستكشف بعض أسئلة المقابلة الأكثر شيوعًا المتعلقة بالأشجار الثنائية. ستساعدك هذه المقالة على فهم المفهوم بشكل أفضل وإعدادك حتى تتمكن من الحصول على وظيفة أحلامك!

أعلى أسئلة وأجوبة مقابلة شجرة ثنائية

يحتوي القسم التالي على كتالوج من الأسئلة وإجاباتها المتوقعة بناءً على مفهوم الشجرة الثنائية.

1) ما هي العقدة الورقية؟

تسمى أي عقدة في شجرة ثنائية أو شجرة ليس لها أي توابع عقدة ورقية.

2) ما هي عقدة الجذر؟

تسمى العقدة الأولى أو العقدة العلوية في الشجرة عقدة الجذر.

3) كيف تجد أدنى سلف مشترك (LCA) لشجرة ثنائية في جافا؟

لنفكر في عقدتين n1 و n2 تشكلان جزءًا من شجرة ثنائية.

أصغر سلف مشترك (LCA) لـ n1 و n2 هو الجد المشترك لـ n1 و n2 الذي يقع في الأبعد عن الجذر.

يمكنك اتباع الطريقة التالية للعثور على تقييم دورة الحياة.

1. أ) ابحث عن مسار من عقدة الجذر إلى n1 وقم بتخزينه في مصفوفة.
2. ب) ابحث عن مسار من عقدة الجذر إلى n2 وقم بتخزينه في مصفوفة.
3. ج) اجتياز كلا المسارين حتى تكون القيمة هي نفسها في كلا المصفوفتين.

4) كيف يمكنك التحقق مما إذا كانت الشجرة الثنائية هي شجرة فرعية لشجرة ثنائية أخرى؟

لنفترض أن لدينا شجرة ثنائية T. نريد الآن التحقق مما إذا كانت الشجرة الثنائية S هي شجرة فرعية لـ T.

للقيام بذلك ، أولاً ، حاول التحقق مما إذا وجدت عقدة في T موجودة أيضًا في S.

بمجرد العثور على هذه العقدة المشتركة ، تحقق مما إذا كانت العقد التالية هي أيضًا جزء من S.

إذا كانت الإجابة بنعم ، فيمكننا القول بأمان أن S هي شجرة فرعية لـ T.

يجب أن تقرأ: موضوعات وأفكار مشروع هيكل البيانات

5) كيف تجد المسافة بين عقدتين في شجرة ثنائية؟

ضع في اعتبارك عقدتين n1 و n2 تشكلان جزءًا من شجرة ثنائية.

المسافة بين n1 و n2 تساوي الحد الأدنى لعدد الحواف التي يجب اجتيازها للوصول من عقدة إلى أخرى.

من المهم ملاحظة أنك تجتاز أقصر مسافة بين العقد.

6) ما هي شجرة البحث الثنائية؟

شجرة البحث الثنائية (BST) هي نوع خاص من الشجرة الثنائية حيث تحتوي كل عقدة داخلية على مفتاح. بالنسبة لشجرة البحث الثنائية ، القاعدة هي:

1. أ) يمكن أن تحتوي العقدة على مفتاح أكبر من جميع المفاتيح الموجودة في الشجرة الفرعية اليسرى للعقدة.
2. ب) يمكن أن تحتوي العقدة على مفتاح أصغر من جميع المفاتيح الموجودة في الشجرة الفرعية اليمنى للعقدة.

وبالتالي ، إذا كانت n1 عبارة عن عقدة بها مفتاح 8 ، فستحتوي كل عقدة في الشجرة الفرعية اليسرى لـ n1 على مفاتيح أقل من 8 ، وستحتوي كل عقدة في الشجرة الفرعية اليمنى لـ n1 على مفاتيح أكبر من 8.

7) ما هي الشجرة المتوازنة ذاتيا؟

تحافظ أشجار البحث الثنائية المتوازنة ذاتيًا على ارتفاعها تلقائيًا قدر الإمكان عند حدوث عمليات مثل الإدراج والحذف.

لكي تكون BST متوازنة ذاتيًا ، من المهم أن تتبع باستمرار قواعد BST بحيث تحتوي الشجرة الفرعية اليسرى على مفاتيح منخفضة القيمة بينما تحتوي الشجرة الفرعية اليمنى على مفاتيح عالية القيمة.

يتم ذلك باستخدام عمليتين:

- دوران لليسار

- حق الدوران

8) ما هي شجرة AVL؟

تم تسمية شجرة AVL على اسم مخترعيها: Adelson و Velski و Landis. شجرة AVL هي شجرة ثنائية ذاتية التوازن تتحقق من ارتفاع الشجرة الفرعية اليسرى والشجرة الفرعية اليمنى وتؤكد أن الفرق ليس أكثر من 1. يسمى هذا الاختلاف عامل التوازن

وبالتالي ، فإن BalanceFactor = الارتفاع (الشجرة الفرعية اليسرى) - الارتفاع (الشجرة الفرعية اليمنى)

إذا كان عامل التوازن أكثر من 1 ، تتم موازنة الشجرة باستخدام بعض الأساليب التالية:

- دوران لليسار

- حق الدوران

- دوران من اليسار إلى اليمين

- دوران لليمين

اقرأ أيضًا: الفرز في بنية البيانات

9) كيف يمكنك تحويل شجرة ثنائية إلى شجرة بحث ثنائية في Java؟

يتمثل الاختلاف الرئيسي بين الشجرة الثنائية وشجرة البحث الثنائية في أن BST يتبع الشجرة الفرعية اليسرى يجب أن تحتوي على قيم مفاتيح أقل والشجرة الفرعية اليمنى يجب أن تحتوي على قاعدة قيم أساسية أعلى. يمكن القيام بذلك باستخدام سلسلة من تقنيات المسح على النحو التالي:

1. قم بإنشاء مصفوفة مؤقتة تخزن اجتياز الداخل للشجرة
2. افرز المصفوفة المؤقتة. يمكنك استخدام أي خوارزمية الفرز هنا.
3. مرة أخرى قم بإجراء مسح داخلي على الشجرة.
4. انسخ عناصر المصفوفة واحدًا تلو الآخر لكل عقدة شجرة.

10) كيف تحذف عقدة من شجرة بحث ثنائية في جافا؟

يمكن أن تكون عملية الحذف لـ BST صعبة نظرًا لأنه يلزم الحفاظ على خصائصها بعد العملية. إليك نظرة على جميع الحالات الثلاث المحتملة:

1. العقدة المراد حذفها هي عقدة طرفية.
   ببساطة قم بإزالة العقدة.
2. العقدة المراد إزالتها لديها طفل واحد.

في هذه الحالة ، انسخ الطفل إلى العقدة واحذف الطفل.

1. العقدة المراد إزالتها لها طفلان.

في هذه الحالة ، ابحث عن الوريث بالترتيب للعقدة. يمكنك بعد ذلك نسخ محتواها إلى العقدة وحذف ما يليها.

11) ما هي بنية بيانات شجرة الأحمر والأسود؟

الشجرة ذات اللون الأحمر والأسود هي نوع خاص من شجرة التوازن الذاتي التي لها الخصائص التالية:

1. كل عقدة لها لون إما أحمر أو أسود.
2. الجذر أسود دائمًا.
3. لا يمكن أن تحتوي العقدة الحمراء على والد أحمر أو طفل أحمر.
4. كل مسار من عقدة الجذر إلى عقدة NULL له نفس عدد العقد السوداء.

يجب أن تقرأ: موضوعات وأفكار مشروع هيكل البيانات

12) كيف تجد شجرتين متطابقتين؟

شجرتان ثنائيتان متطابقتان إذا كان لديهم نفس البيانات والترتيب. يمكن القيام بذلك عن طريق اجتياز كل من الأشجار ومقارنة بياناتها وترتيباتها.

إليك الخوارزمية التي يمكنها أن تمكننا من القيام بذلك:

1. التحقق من بيانات عقدة الجذر (بيانات الشجرة 1 == بيانات الشجرة 2)
2. تحقق من الشجرة الفرعية اليسرى بشكل متكرر. استدعاء sameTree (الشجرة1-> اليسار الشجرة ، الشجرة2-> الشجرة الفرعية اليسرى)
3. وبالمثل ، تحقق من الشجرة الفرعية اليمنى
4. إذا كانت a ، b ، c صحيحة ، يتم إرجاع 1

الخروج: أنواع الشجرة الثنائية

افكار اخيرة

في هذه المقالة ، استكشفنا بعضًا من أكثر أسئلة مقابلة شجرة البحث الثنائية شيوعًا. يمكن أن يساعدك استكشاف المزيد حول هياكل البيانات في الحصول على فهم أفضل للمنطق والبرمجة. يمكنك محاولة إلقاء نظرة على الأمثلة المذكورة في هذه المقالة والممارسة عن طريق تغيير القيم لبناء الأساسيات الخاصة بك. مع بعض الممارسة ، ستكون في وضع جيد لاختراق مقابلتك.

إذا كنت مهتمًا بالتعرف على علوم البيانات ، فراجع برنامج IIIT-B & upGrad التنفيذي PG في علوم البيانات الذي تم إنشاؤه للمهنيين العاملين ويقدم أكثر من 10 دراسات حالة ومشاريع ، وورش عمل عملية عملية ، وإرشاد مع خبراء الصناعة ، 1 - في 1 مع موجهين في الصناعة ، أكثر من 400 ساعة من التعلم والمساعدة في العمل مع الشركات الكبرى.