زمان کنونی: ۰۲ آذر ۱۴۰۳, ۰۴:۰۷ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

رسم درخت با pre و post(مهم شدید)

ارسال:
  

shirin0101 پرسیده:

رسم درخت با pre و post(مهم شدید)

سلام Blush
با داشتن پیمایش های preorder,postorder چطور میشه درخت رو رسم کرد؟ مثلا با دو تا پیمایش زیر...
اگه گره های تک فرزند رو داده باشند چطور میشه رسم کرد؟چطور میتوان تک فرزندی و ۲ فرزندی را تشخیص داد و رسم کرد؟ کلا مشکل دارم باهاش دیگه Big Grin خوندم ک تو pre اولی ریشه است تو post اخری ریشه بعد همینجوری بازگشتی میریم جلو...خب همین جلو رفتن چجوری میشه؟؟ Big Grin لطفا با مثال زیر به من راهنمایی کنید ... خیلی ممنون Heart
pre :a b d e f g c h i j k l
post :e d g f b i h k l j c a
نقل قول این ارسال در یک پاسخ

۷
ارسال:
  

Iranian Wizard پاسخ داده:

RE: رسم درخت با pre و post(مهم شدید)

سلام.چند تا نکته در مورد این پیمایش ها میگم.بعد با این توضیحات حلش میکنم.
۱- برگ ها در هر ۳ پیمایش inorder ، perorder ، postorder ترتیبشون یکسانه.
۲- اولین گره در پیمایش preorder ، ریشه و آخرین گره،سمت راست ترین برگ هستش.
۳- اولین گره در پیمایش postorder ، سمت چپ ترین برگ،و آخرین گره،ریشه است.
۴- n=n0+n1+n2 تعداد گره های درخت دودویی،برابر تعداد برگ ها(گره های درجه ۰) + تعداد گره های تک فرزندی(گره های درجه ۱) + تعداد گره های دو فرزندی است.
۵- همواره در درخت دودویی،n0=n2+1 هستش.یعنی همواره تعداد برگ ها یکی از تعداد گره های دو فرزندی بیشتره.
۶- اگر دو گره در پیمایش preorder بصورت ab باشند،اگر در پیمایش postorder بصورت ba باشند،آنگاه a گره تک فرزندی هستش.
۷- همواره به تعداد (۲ بتوان گره های تک فرزندی) ما درخت دودویی متمایز خواهیم داشت.
حالا سوالو حل میکنم.ریشه رو با رنگ قرمز،گره های xy که بصورت yx هستند رو زیرشون خط کشیدم.و گره های تک فرزندی رو با رنگ آبی مشخص کردم.
pre : a b d e f g c h i j k l
post :e d g f b i h k l j c a
پس ۳ تا گره تک فرزندی داریم.یعنی ۹تا گره دیگه دو فرزندی و برگ هستند.تعداد برگ ها یکی از تعداد گره های دو فرزندی بیشتره،پس یعنی تعداد برگ ها ۵ تا و تعداد گره های دو فرزندی ۴ تاست.
حالا گره های تک فرزندی رو از پیمایش ها حذف میکنیم،تا تشخیص بقیه گره ها راحت تر باشه.
pre :a b e g c i j k l
post :e g b i k l j c a
چون سمت چپ ترین برگ همان اولین گره در postorder و سمت راست ترین برگ همان آخرین گره در preorder هستش و ترتیب برگ ها یکسان هستش. پس همواره برگ ها از سمت چپ ترین برگ ( e ) تا سمت راست ترین برگ( l ) هستند.
که در شکل بالا محدوده برگ ها زیرشون خط کشیده شده.
پس a , b, j, c حداقل در یکی از پیمایش ها در محدوده حضور برگ ها نیستند،پس برگ نیستند،چون گره های تک فرزندی هم قبلا مشخص شده بود،پس این۴ گره حتما دو فرزندی خواهند بود.
و ۵ گره بعدی (که به ترتیب هم هستند)،برگ خواهند بود. e , g , i ,k , l
pre :a b e g c i j k l
post :e g b i k l j c a
حالا که برگ ها ،گره های تک فرزندی و دو فرزندی مشخص شد،میتونیم در پیمایش preorder ، از چپ به راست حرکت کنیم،و با توجه به درجه گره ها که مشخص شده،درخت رو رسم کرد(که ۸ درخت متمایز رسم میشه)
امیدوارم توضیحاتم خوب بوده باشه.
نقل قول این ارسال در یک پاسخ

ارسال:
  

shirin0101 پاسخ داده:

RE: رسم درخت با pre و post(مهم شدید)

(۲۵ دى ۱۳۹۴ ۰۲:۱۳ ب.ظ)IranianWizard نوشته شده توسط:  امیدوارم توضیحاتم خوب بوده باشه.

سلام، مرسی عااااالی بود خیلی زحمت کشیدید واقعا ممنونم Blush...همشو متوجه شدم خوب...فقط اون دو خط اخر وقتی دارم درخت رسم میکنم فرمودید از pre شروع کنم و به ترتیب بچینم تو درخت ؟ میشه اخرشو یکم بیشتر برام توضیح بدین؟ Rolleyes
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

۳
ارسال:
  

Iranian Wizard پاسخ داده:

RE: رسم درخت با pre و post(مهم شدید)

خواهش میکنم
آره از preorder استفاده میکنیم و از چپ به راست میریم جلو.
گره اول a (ریشه) هستش.چون دو فرزندی بودش ،پس دو گره تو خالی بجای فرزنداش میکشیم.
[تصویر:  394814_1.jpg]
گره بعدی b هستش.که میره تو گره ی تو خالی فرزند چپ نوشته میشه.که خود b چون دو فرزندی هستش.پس دو گره تو خالی به جا فرزنداش میکشیم.
[تصویر:  394814_2.jpg]
بعدش گره d رو در مکان فرزند چپ b مینویسیم.و چون d گره تک فرزندی هستش،فرزندش میتونه در سمت چپ باشه،یا راست.
که من اینجا یه فرزند چپ واسش کشیدم.
[تصویر:  394814_3.jpg]
حالا e رو بعنوان فرزند چپ d قرار میدیم،و چون e برگ هستش،دیگه فرزندی واسش رسم نمیکنیم.
[تصویر:  394814_4.jpg]
گره بعدی f هستش،که میره فرزند راست b میشه.وچون تک فرزندی هستش.پس یا فرزند چپ داره یا راست.که من اینجا واسش فرزند راست میکشم.
[تصویر:  394814_5.jpg]
گره بعدی g هستش.که میره بعنوان فرزند راست f انتخاب میشه.و چون برگ هستش،دیگه فرزندی نداره.
[تصویر:  394814_6.jpg]
گره بعدی c هستش که میره بعنوان فرزند راست a قرار میگیره،چون دو فرزندی هستش،پس دو گره تو خالی به عنوان فرزنداش میکشیم.
[تصویر:  394814_7.jpg]
و همینجور الی آخر...
که یکی از شکل هاش این میشه:
[تصویر:  394814_8.jpg]
نقل قول این ارسال در یک پاسخ

ارسال:
  

shirin0101 پاسخ داده:

RE: رسم درخت با pre و post(مهم شدید)

خیلی خیلی از شما ممنونم ..کامل متوجه شدم Blush...بهترین پرسش و پاسخی بود که تا حالا داشتم Heart

فقط ی سوال: در واقع به صورت عمقی درخت ساختیم، درسته؟
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

ارسال:
  

Iranian Wizard پاسخ داده:

RE: رسم درخت با pre و post(مهم شدید)

(۲۵ دى ۱۳۹۴ ۰۴:۴۸ ب.ظ)shirin0101 نوشته شده توسط:  خیلی خیلی از شما ممنونم ..کامل متوجه شدم Blush...بهترین پرسش و پاسخی بود که تا حالا داشتم Heart

فقط ی سوال: در واقع به صورت عمقی درخت ساختیم، درسته؟
خواهش میکنمBlush
آره به بصورت پیمایش preorder، درخت رو ساختیم.یعنی اول ریشه،سپس گره بعدی در سمت چپ ریشه،بعدش گره بعدی در سمت چپ گره فعلی،
که اگه گره فعلی گره سمت چپ نداشته باشه،گره بعدی در سمت راست گره فعلی نوشته میشه و همینجور الی آخر.
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  تعداد برگ درخت؟؟؟؟؟؟؟ rad.bahar ۴ ۴,۷۸۷ ۱۵ آذر ۱۴۰۲ ۱۱:۵۳ ق.ظ
آخرین ارسال: mohamadrra
  جزوه خلاصه نکات مهم فصول ابتدایی درس مهندسی نرم افزار Happiness.72 ۱ ۳,۸۳۰ ۱۳ خرداد ۱۴۰۱ ۰۶:۲۸ ب.ظ
آخرین ارسال: M o h m m @ d
  تصمیم گیری مهم درباره مکان سرور سایت admin ۴ ۴,۸۵۶ ۲۸ دى ۱۴۰۰ ۰۳:۵۹ ب.ظ
آخرین ارسال: mahsa3323
  دو سوال در مورد درخت BST(درخت جستجوی دودویی) امیدوار ۳ ۵,۵۸۲ ۱۰ دى ۱۳۹۹ ۱۲:۰۴ ق.ظ
آخرین ارسال: marzi.pnh
  زمان جستجوی درخت fateme.sm ۰ ۱,۷۷۵ ۰۶ دى ۱۳۹۹ ۱۰:۴۱ ب.ظ
آخرین ارسال: fateme.sm
  مرتبه ایجاد درخت rad.bahar ۱ ۳,۳۷۵ ۳۰ مهر ۱۳۹۹ ۰۳:۳۴ ب.ظ
آخرین ارسال: rad.bahar
  سوال مهم از کمتازیا jamshid51 ۰ ۱,۹۸۸ ۲۹ مهر ۱۳۹۹ ۱۰:۰۷ ب.ظ
آخرین ارسال: jamshid51
  عمق درخت ???? rad.bahar ۱ ۲,۳۹۳ ۱۱ مهر ۱۳۹۹ ۰۳:۳۱ ب.ظ
آخرین ارسال: عزیز دادخواه
  محاسبه ارتفاع درخت.... baharkhanoom ۳ ۸,۰۹۲ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۸ ب.ظ
آخرین ارسال: mohsentafresh
  رسم مدار انکدر ۴ به ۲ moslemrahmati ۰ ۱,۹۰۵ ۲۶ اسفند ۱۳۹۸ ۰۲:۰۷ ب.ظ
آخرین ارسال: moslemrahmati

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close