اولا در کل یعنی به صورت همیشگی نمی شه با داشتن پری و پست درخت رو به صورت یکتا رسم کرد.

ثانیا وقتی دوتا گره هم تو پری و هم تو پست پشت سر هم باشن، گره اول تو پیمایش پری تک فرزنده و پدر گره دومه.

حالا با توجه به de و fg و hi تو پری و برعکسشون تو پست می شه گفت که هر کدوم از اینا می تونن دو حالت داشته باشن(تک فرزند اونها فرزند راست باشه یا چپ) و بنابراین حداقل ۸ حالت وجود داره. گزینه ی بی نهایت هم که از همون اول حذفه چون کلا تعداد درخت های دودویی محدوده بنابراین همون هشت تا گزینه ی سه.

(۱۲ بهمن ۱۳۹۲ ۰۸:۳۱ ب.ظ)hosein_khoshdel نوشته شده توسط:  اولا در کل یعنی به صورت همیشگی نمی شه با داشتن پری و پست درخت رو به صورت یکتا رسم کرد.

ثانیا وقتی دوتا گره هم تو پری و هم تو پست پشت سر هم باشن، گره اول تو پیمایش پری تک فرزنده و پدر گره دومه.

حالا با توجه به de و fg و hi تو پری و برعکسشون تو پست می شه گفت که هر کدوم از اینا می تونن دو حالت داشته باشن(تک فرزند اونها فرزند راست باشه یا چپ) و بنابراین حداقل ۸ حالت وجود داره. گزینه ی بی نهایت هم که از همون اول حذفه چون کلا تعداد درخت های دودویی محدوده بنابراین همون هشت تا گزینه ی سه.

سپاس گذارم

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