(۰۲ آذر ۱۳۹۲ ۰۲:۲۶ ب.ظ)tarane1992 نوشته شده توسط:  سلام

دوستان هر کسی میتونه این سوالو کامل برام توضیح بده.

من تو رسم شکل درخت مشکل دارم نمیدونم با پیمایش PREORDER و POSTORDER چطوری میشه شکلو رسم کرد چون حتی برگهاشم مشخص نیست که بشه رسم کرد.فقط میتونم با inorder و preorder شکلو رسم کنم حالا که inorder نداریم چطوری میشه؟


جواب گزینه ۱ میشه.

دوست عزیز

۱:با داشتن پیشوندی یا پسوندی یا سطحی که ریشه مشخص هست(یکی‌ از اینها)+ میانوندی می‌شه یک درخت واحد ترسیم کنی‌(برای دودویی) که از سمت ریشه در پیمایشی که ریشه مشخصه شروع و با میانوندی چپ یا راست بودن هر گره رو مشخص میکنی‌

۲:حالا اگه ۲ پیمایش پیشوندی و پسوندی داشتی فقط میتونی‌ برگ‌ها و ریشه و گره‌های تک فرزندی مشخص کنی‌ و تعداد درخت که میتونی‌ بسازی به تعداد گره‌های تک فرزندی بستگی داره و برابر ۲ به توان تعداد تک فرزند ها(دقت واحد نیست)

۳:اگه درخت کامل یا پر باشه با یک پیمایش که ریشه مشخص باشه هم می‌شه درخت واحد ساخت

۴:اگه درخت محض هم باشه و برچسب گره‌ها مشخص باشه هم مثل ۳

اینجا بر اساس مفروضات یک شکلی‌ که می‌شه ساخت اینه


که ۳تا گره تک فرزندی داره پس می‌شه ۸ درخت ساخت

برای ساختن درخت هم بعد رسم ریشه (a)در پیشوندی گره آخر در پیمایش سمت راست‌ترین برگ(j)

و در پسوندی گره اول چپترین برگ(d) و به همین ترتیب میتونی‌ با مقایسه ۲ پیمایش تشخیص بدی که کدوم گره در زیردرخت چپ ریشه و کدوم در زیر درخت راست(مثلا c) (همین ترتیب برای زیر درخت‌ها انجام بده) گره‌های تک فرزندی میتونی‌ هرجور دلت خواست بذار چپ یا راست اینجا درخت واحد نداریم

گفتم که باید مقایسه کنی‌ و حواست باشه که درخت واحد نیست وسواس بخرج ندی

خوب حالا که مشخص شد که d چپ‌ترین برگ هست می‌بینید که در پیمایش پیشوندی b قبل d اومده پس b پدر d هست بطور قطع چون پیشوندی به صورت VLR هست حالا پیمایش پستوندی نگاه می‌کنیم چون به طور LRV هست تمام گره‌های قبل b زیر درخت چپ a هستن

تا اینجا فهمیدیمabdefg // chij پیشوندی و dgfeb//ijhca پسوندی
حالا میبینیم در پیشوندیِ e بعد bd قرار گرفته پس چون dبرگ مسلما فرزند راست b هستش بعد نوبت f و g میرسه که در زیر درخت چپ پیشوندی میبینی‌ g آخریه پس برگ و f قبل اون اومده در پیشوندی پس پدرشه
c هم که اولین گره سمت راست پس جاش مشخص و j هم راست‌ترین برگ زیر درخت راست و‌ i هم چپترین برگ زیر درخت راست(az pos) h هم میمونه که می‌شه پدرشون

درخت رسم شد

خوب الان متوجه شدم کدوم گره ها زیر درخت چپ و کدومشون زیر درخت راستن.

حالا میشه در مورد ترتیب قرار دادنشون در زیر درخت چپ و راست توضیح بدی.
مثلا a ریشه میشه و j سمت راستترین عنصر میشه و d سمت چپ ترین عنصر میشه.
به همین ترتیب b ریشه و i سمت راستترین عنصر و g سمت چپ ترین عنصر خوب و....خوب حالا بگید من چطوری رسم کنم؟

دوست عزیز الان فهمیدم از توضیحات کاملت بسیار ممنونم

خیلی خوب توضیح دادی.

امیدوارم موفق باشی.