چه تعداد درخت دودویی برچسب دار متفاوت با n گره و با برچسب های ۱ تا n که دارای ترتیب های یکسان در دو روش پس ترتیب و بین ترتیب می باشند وجود دارد؟
جواب:!n
فرمول +اثبات :تعداد درخت های دودویی که با n کلید میتوان ساخت؟
(۱۶ مهر ۱۳۹۱ ۰۵:۲۹ ب.ظ)mahtab_rafiei نوشته شده توسط: چه تعداد درخت دودویی برچسب دار متفاوت با n گره و با برچسب های ۱ تا n که دارای ترتیب های یکسان در دو روش پس ترتیب و بین ترتیب می باشند وجود دارد؟
جواب:!n
سلام.
ببینید، گفته "ترتیب یکسان در دو روش پس ترتیب و پیش ترتیب"، تنها در صورتی این شرط امکان پذیر خواهد بود که درخت اریب باشد.
یعنی اگه درخت اریب به چپ باشد این اتفاق خواهد افتاد. توجه کن که درخت دودویی (درختی که یا حداکثر ۲ فرزند دارد) با درخت جستجوی دودویی(ترتیب عناصر در این درخت مهم است) تفاوت دارد.
حالا اگه درخت رو به ازای n=8 رسم کنیم، بصورت زیر خواهد بود:
۸
--۷
----۶
------۵
--------۴
----------۳
------------۲
--------------۱
پس یکی از حالات میتونه شکل بالایی باشه. در درخت دودویی برخلاف درخت جستجوی دودویی، ترتیب عناصر مهم نیست، یعنی مثلا جای ۷ و ۸ میتونه عوض بشه. با توجه به تعداد جایگشت های n عنصر، N! حالت می توان ایجاد کرد.
------------------------------------------------------------------------------------------------------------
توجه کن که اگه در صورت سوال می نوشت، تعداد درخت های جستجوی دودویی چندتا است، جواب ۱ میشد،(همون شکل بالا که رسم کردم) چون ترتیب عناصر مهم هستند و اینکه عدد بزرگتر باید پدر عدد کوچیکتر باشد.
موفق باشی.