استفسار شجرة البحث الثنائي الأساسية

Question

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

Answer 1

إذا كان الارتفاع $ 0 $ صحيح.

افترض أن جميع الأشجار الثنائية التي تم فرزها والارتفاع منها أقل من $ H $ هي BST.

النظر في شجرة مع الجذر $ x $ ، ارتفاع $ H $ ويتم فرزها. على وجه الخصوص، يتم فرز Instorder Interies من اليسار واليمين وتحصل على ارتفاع أصغر من $ H $ . ثم، من خلال الافتراض، هم BST. الآن، في Interorder من الشجرة المعينة، يتم سرد العقدة $ x $ بعد كل العقد من الشجرة الفرعية اليسرى. نظرا لأن In تراسيتها قد تم فرزها، فإن $ x $ غير أصغر من أي عقدة من الشجرة الفرعية اليسرى. وبالمثل، فإن $ x $ غير أكبر من أي عقدة من الفرد الفرعي الصحيح. لذلك، الشجرة هي BST.

وبالتالي، من خلال الحث على ارتفاع الأشجار الثنائية، يتم فرز جميع الأشجار الثنائية التي يتم فيها فرزها Interorder هي BST.