استخدم Tree Tree Traversal لتحديد ما إذا كان BST أو كومة

Question

تعطى قوائم اجتياز هذه:
1. 53، 1، 64، 23، 3، 29، 17، 2، 9، 19
2. 49، 32، 51، 71، 32، 10، 21، 8، 13، 11، 41، 17

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

ما هي المؤشرات التي يمكنني استخدامها، إذا كان هناك أي، أو الطريقة لحل هذا سيكون الغارقة حرفيا تجبر كل خيار؟

Answer 1

لا أحد منهم يمكن أن يكون bst.يمر اجتياز داخل الترتيب ل BST القمم في ترتيب غير تقليل مفاتيحها (يسهل إثبات ذلك عن طريق الحث).

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

في المثال المحدد لا يمكن أن يكون التسلسل الأول عبارة عن اجتياز من كومة من الكومة لأن الشجرة الناتجة سيكون لها مسار مع مفاتيح 23 دولارا، 1، 53 $ (في زيادة ترتيب العمق). تنطبق الحجة نفسها على التسلسل الثاني للمسار مع المفاتيح 71 $، 32، 49 $ .