سلام دوستان
الگوریتم رسم درخت از روی پیمایش پری وپست چطوری هست و کلا اینکه چطوری میشه گره های تک فرزندی رو از روی این دو پیمایش تشخیص داد
به عنوان مثال این سوالی که ضمیمه کردم رو اگه دوستان با توضیح جامع حل کنن ممنون میشم
اولا در کل یعنی به صورت همیشگی نمی شه با داشتن پری و پست درخت رو به صورت یکتا رسم کرد.
ثانیا وقتی دوتا گره هم تو پری و هم تو پست پشت سر هم باشن، گره اول تو پیمایش پری تک فرزنده و پدر گره دومه.
حالا با توجه به de و fg و hi تو پری و برعکسشون تو پست می شه گفت که هر کدوم از اینا می تونن دو حالت داشته باشن(تک فرزند اونها فرزند راست باشه یا چپ) و بنابراین حداقل ۸ حالت وجود داره. گزینه ی بی نهایت هم که از همون اول حذفه چون کلا تعداد درخت های دودویی محدوده بنابراین همون هشت تا گزینه ی سه.
تعداد درخت های دودوئی که پیمایش های preorder و postorder آنها برابر با رشته های مشخص زیر باشد برابر است با ۲ به توان n که n تعداد گره های تک فرزندی در درخت است .
برای به دست آوردن گره های تک فرزندی به این صورت عمل میکنیم:
از سمت چپ یکی از پیمایش ها مثلا preorder حرکت میکنیم و هر ترتیب دوتایی از گره ها (ترتیب های دوتایی دقیقا کنار هم)در نظر گرفته و در پیمایش دیگر بررسی میکنیم اگر دقیقا همین ترتیب دوتایی را به صورت معکوس عینا مشاهده کردیم گره اول ترتیب تک فرزندی است.
اینجا f,g و d,e و h,i داریم که میشه دو به توان ۳ ------> درنتیجه ۸ تا میشه
(۱۲ بهمن ۱۳۹۲ ۰۸:۳۱ ب.ظ)hosein_khoshdel نوشته شده توسط: اولا در کل یعنی به صورت همیشگی نمی شه با داشتن پری و پست درخت رو به صورت یکتا رسم کرد.سپاس گذارم
ثانیا وقتی دوتا گره هم تو پری و هم تو پست پشت سر هم باشن، گره اول تو پیمایش پری تک فرزنده و پدر گره دومه.
حالا با توجه به de و fg و hi تو پری و برعکسشون تو پست می شه گفت که هر کدوم از اینا می تونن دو حالت داشته باشن(تک فرزند اونها فرزند راست باشه یا چپ) و بنابراین حداقل ۸ حالت وجود داره. گزینه ی بی نهایت هم که از همون اول حذفه چون کلا تعداد درخت های دودویی محدوده بنابراین همون هشت تا گزینه ی سه.