۲
subtitle
ارسال: #۱
  
رسم درخت با pre و post(مهم شدید)
سلام
با داشتن پیمایش های preorder,postorder چطور میشه درخت رو رسم کرد؟ مثلا با دو تا پیمایش زیر...
اگه گره های تک فرزند رو داده باشند چطور میشه رسم کرد؟چطور میتوان تک فرزندی و ۲ فرزندی را تشخیص داد و رسم کرد؟ کلا مشکل دارم باهاش دیگه خوندم ک تو pre اولی ریشه است تو post اخری ریشه بعد همینجوری بازگشتی میریم جلو...خب همین جلو رفتن چجوری میشه؟؟ لطفا با مثال زیر به من راهنمایی کنید ... خیلی ممنون
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
با داشتن پیمایش های preorder,postorder چطور میشه درخت رو رسم کرد؟ مثلا با دو تا پیمایش زیر...
اگه گره های تک فرزند رو داده باشند چطور میشه رسم کرد؟چطور میتوان تک فرزندی و ۲ فرزندی را تشخیص داد و رسم کرد؟ کلا مشکل دارم باهاش دیگه خوندم ک تو pre اولی ریشه است تو post اخری ریشه بعد همینجوری بازگشتی میریم جلو...خب همین جلو رفتن چجوری میشه؟؟ لطفا با مثال زیر به من راهنمایی کنید ... خیلی ممنون
pre :a b d e f g c h i j k l
۷
ارسال: #۲
  
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 ، از چپ به راست حرکت کنیم،و با توجه به درجه گره ها که مشخص شده،درخت رو رسم کرد(که ۸ درخت متمایز رسم میشه)
امیدوارم توضیحاتم خوب بوده باشه.
۱- برگ ها در هر ۳ پیمایش 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 ، از چپ به راست حرکت کنیم،و با توجه به درجه گره ها که مشخص شده،درخت رو رسم کرد(که ۸ درخت متمایز رسم میشه)
امیدوارم توضیحاتم خوب بوده باشه.
ارسال: #۳
  
RE: رسم درخت با pre و post(مهم شدید)
۳
ارسال: #۴
  
RE: رسم درخت با pre و post(مهم شدید)
خواهش میکنم
آره از preorder استفاده میکنیم و از چپ به راست میریم جلو.
گره اول a (ریشه) هستش.چون دو فرزندی بودش ،پس دو گره تو خالی بجای فرزنداش میکشیم.
گره بعدی b هستش.که میره تو گره ی تو خالی فرزند چپ نوشته میشه.که خود b چون دو فرزندی هستش.پس دو گره تو خالی به جا فرزنداش میکشیم.
بعدش گره d رو در مکان فرزند چپ b مینویسیم.و چون d گره تک فرزندی هستش،فرزندش میتونه در سمت چپ باشه،یا راست.
که من اینجا یه فرزند چپ واسش کشیدم.
حالا e رو بعنوان فرزند چپ d قرار میدیم،و چون e برگ هستش،دیگه فرزندی واسش رسم نمیکنیم.
گره بعدی f هستش،که میره فرزند راست b میشه.وچون تک فرزندی هستش.پس یا فرزند چپ داره یا راست.که من اینجا واسش فرزند راست میکشم.
گره بعدی g هستش.که میره بعنوان فرزند راست f انتخاب میشه.و چون برگ هستش،دیگه فرزندی نداره.
گره بعدی c هستش که میره بعنوان فرزند راست a قرار میگیره،چون دو فرزندی هستش،پس دو گره تو خالی به عنوان فرزنداش میکشیم.
و همینجور الی آخر...
که یکی از شکل هاش این میشه:
آره از preorder استفاده میکنیم و از چپ به راست میریم جلو.
گره اول a (ریشه) هستش.چون دو فرزندی بودش ،پس دو گره تو خالی بجای فرزنداش میکشیم.
گره بعدی b هستش.که میره تو گره ی تو خالی فرزند چپ نوشته میشه.که خود b چون دو فرزندی هستش.پس دو گره تو خالی به جا فرزنداش میکشیم.
بعدش گره d رو در مکان فرزند چپ b مینویسیم.و چون d گره تک فرزندی هستش،فرزندش میتونه در سمت چپ باشه،یا راست.
که من اینجا یه فرزند چپ واسش کشیدم.
حالا e رو بعنوان فرزند چپ d قرار میدیم،و چون e برگ هستش،دیگه فرزندی واسش رسم نمیکنیم.
گره بعدی f هستش،که میره فرزند راست b میشه.وچون تک فرزندی هستش.پس یا فرزند چپ داره یا راست.که من اینجا واسش فرزند راست میکشم.
گره بعدی g هستش.که میره بعنوان فرزند راست f انتخاب میشه.و چون برگ هستش،دیگه فرزندی نداره.
گره بعدی c هستش که میره بعنوان فرزند راست a قرار میگیره،چون دو فرزندی هستش،پس دو گره تو خالی به عنوان فرزنداش میکشیم.
و همینجور الی آخر...
که یکی از شکل هاش این میشه:
ارسال: #۵
  
RE: رسم درخت با pre و post(مهم شدید)
خیلی خیلی از شما ممنونم ..کامل متوجه شدم ...بهترین پرسش و پاسخی بود که تا حالا داشتم
فقط ی سوال: در واقع به صورت عمقی درخت ساختیم، درسته؟
فقط ی سوال: در واقع به صورت عمقی درخت ساختیم، درسته؟
ارسال: #۶
  
RE: رسم درخت با pre و post(مهم شدید)
(۲۵ دى ۱۳۹۴ ۰۴:۴۸ ب.ظ)shirin0101 نوشته شده توسط: خیلی خیلی از شما ممنونم ..کامل متوجه شدم ...بهترین پرسش و پاسخی بود که تا حالا داشتمخواهش میکنم
فقط ی سوال: در واقع به صورت عمقی درخت ساختیم، درسته؟
آره به بصورت پیمایش 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?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close