سلام
با داشتن پیمایش های preorder,postorder چطور میشه درخت رو رسم کرد؟ مثلا با دو تا پیمایش زیر...
اگه گره های تک فرزند رو داده باشند چطور میشه رسم کرد؟چطور میتوان تک فرزندی و ۲ فرزندی را تشخیص داد و رسم کرد؟ کلا مشکل دارم باهاش دیگه
خوندم ک تو pre اولی ریشه است تو post اخری ریشه بعد همینجوری بازگشتی میریم جلو...خب همین جلو رفتن چجوری میشه؟؟ لطفا با مثال زیر به من راهنمایی کنید ... خیلی ممنون 
pre :a b d e f g c h i j k l
سلام.چند تا نکته در مورد این پیمایش ها میگم.بعد با این توضیحات حلش میکنم.
۱- برگ ها در هر ۳ پیمایش 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 ، از چپ به راست حرکت کنیم،و با توجه به درجه گره ها که مشخص شده،درخت رو رسم کرد(که ۸ درخت متمایز رسم میشه)
امیدوارم توضیحاتم خوب بوده باشه.
(۲۵ دى ۱۳۹۴ ۰۲:۱۳ ب.ظ)IranianWizard نوشته شده توسط: امیدوارم توضیحاتم خوب بوده باشه.
سلام، مرسی عااااالی بود خیلی زحمت کشیدید واقعا ممنونم
...همشو متوجه شدم خوب...فقط اون دو خط اخر وقتی دارم درخت رسم میکنم فرمودید از pre شروع کنم و به ترتیب بچینم تو درخت ؟ میشه اخرشو یکم بیشتر برام توضیح بدین؟ 
خواهش میکنم
آره از preorder استفاده میکنیم و از چپ به راست میریم جلو.
گره اول a (ریشه) هستش.چون دو فرزندی بودش ،پس دو گره تو خالی بجای فرزنداش میکشیم.
![[تصویر: 394814_1.jpg]](https://img.manesht.ir/394814_1.jpg)
گره بعدی b هستش.که میره تو گره ی تو خالی فرزند چپ نوشته میشه.که خود b چون دو فرزندی هستش.پس دو گره تو خالی به جا فرزنداش میکشیم.
![[تصویر: 394814_2.jpg]](https://img.manesht.ir/394814_2.jpg)
بعدش گره d رو در مکان فرزند چپ b مینویسیم.و چون d گره تک فرزندی هستش،فرزندش میتونه در سمت چپ باشه،یا راست.
که من اینجا یه فرزند چپ واسش کشیدم.
![[تصویر: 394814_3.jpg]](https://img.manesht.ir/394814_3.jpg)
حالا e رو بعنوان فرزند چپ d قرار میدیم،و چون e برگ هستش،دیگه فرزندی واسش رسم نمیکنیم.
![[تصویر: 394814_4.jpg]](https://img.manesht.ir/394814_4.jpg)
گره بعدی f هستش،که میره فرزند راست b میشه.وچون تک فرزندی هستش.پس یا فرزند چپ داره یا راست.که من اینجا واسش فرزند راست میکشم.
![[تصویر: 394814_5.jpg]](https://img.manesht.ir/394814_5.jpg)
گره بعدی g هستش.که میره بعنوان فرزند راست f انتخاب میشه.و چون برگ هستش،دیگه فرزندی نداره.
![[تصویر: 394814_6.jpg]](https://img.manesht.ir/394814_6.jpg)
گره بعدی c هستش که میره بعنوان فرزند راست a قرار میگیره،چون دو فرزندی هستش،پس دو گره تو خالی به عنوان فرزنداش میکشیم.
![[تصویر: 394814_7.jpg]](https://img.manesht.ir/394814_7.jpg)
و همینجور الی آخر...
که یکی از شکل هاش این میشه:
![[تصویر: 394814_8.jpg]](https://img.manesht.ir/394814_8.jpg)
خیلی خیلی از شما ممنونم ..کامل متوجه شدم
...بهترین پرسش و پاسخی بود که تا حالا داشتم فقط ی سوال: در واقع به صورت عمقی درخت ساختیم، درسته؟
(۲۵ دى ۱۳۹۴ ۰۴:۴۸ ب.ظ)shirin0101 نوشته شده توسط: خیلی خیلی از شما ممنونم ..کامل متوجه شدمخواهش میکنم
فقط ی سوال: در واقع به صورت عمقی درخت ساختیم، درسته؟
آره به بصورت پیمایش preorder، درخت رو ساختیم.یعنی اول ریشه،سپس گره بعدی در سمت چپ ریشه،بعدش گره بعدی در سمت چپ گره فعلی،
که اگه گره فعلی گره سمت چپ نداشته باشه،گره بعدی در سمت راست گره فعلی نوشته میشه و همینجور الی آخر.