هي الهياكل اللازمة في أشجار البحث الثنائية

Question

لقد بحثت في بعض الكود ل BSTS وأستطيع أن أرى أن كل عقدة هي بنية. هل هذا ضروري؟

Answer 1

int flat_tree[ 1000 ][ 3 ];
    // for each tree node, value is stored in element [id][0]
                        // id of left_child stored in element [id][1]
                        // id of right_child stored in element [id][2]

…

لن أذهب إلى أبعد من ذلك.

بشكل عام، structس/classيتم استخدام وفاق لأي نوع من هيكل البيانات المرتبطة. أيضا بشكل عام، قد يتم هزيمة أي ميزة لنظام النوع أو تجاهلها ويمكنك القيام بكل شيء (تخصيص كومة، إلخ) في مجموعة واحدة من intفي الأزياء مؤلمة جدا.

Answer 2

لا، يمكن أن يكون فئة. لا يمكن أن تكون بدائية، لأنها تحتاج إلى تخزين قيمة وأشير أيضا إلى الأطفال.

حسنا، أود أن أقول أنه يمكنك أيضا تمثيل BST الخاص بك كصفيف، حيث الأطفال الأيسر والأيمن من العقدة في الموقف i في المراكز 2 * i + 1 و 2 * i + 2, ، على التوالى. ولكن بعد ذلك، عليك أن تقلق بشأن تغيير حجمه، وستحتاج إلى قيمة خاصة لتمثيل الاختلاف، وحذف العمليات تصبح معقدة للغاية. لا أوصي بهذا النهج كأي شيء آخر غير ممارسة أكاديمية.

Answer 3

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

Answer 4

لا، لا يتحدث بدقة. في أيام Fortran، استخدم الأشخاص صفائف متوازية، أو صفائف ثنائية الأبعاد.

تحدث قسم توني هوراري من "البرمجة المهيكلة" من قبل Dahl، Dijkstra، والأرجح، عن هيكلة البيانات وأنواع السجلات.

Answer 5

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

payload_type a[tree_size];

مجرد مجموعة مسطحة طويلة تحتوي على قيم حمولة فقط، مع وضع في ترميز الصفيف بنية الارتباط:

• a[0] هو الجذر
• a[1] هو الجذر-> اليسار
• a[2] هو الجذر> الحق
• a[3] هو الجذر-> اليسار-> اليسار
• a[4] هو الجذر> اليسار> الحق
• ...

بالنسبة للعقدة في الموضع الأول، انتقل إلى 2 * I + 1 لليسار و 2 * i + 2 لليمين

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