سلام.چند تا نکته در مورد این پیمایش ها میگم.بعد با این توضیحات حلش میکنم.
۱- برگ ها در هر ۳ پیمایش 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 ، از چپ به راست حرکت کنیم،و با توجه به درجه گره ها که مشخص شده،درخت رو رسم کرد(که ۸ درخت متمایز رسم میشه)
امیدوارم توضیحاتم خوب بوده باشه.

خواهش میکنم
آره از preorder استفاده میکنیم و از چپ به راست میریم جلو.
گره اول a (ریشه) هستش.چون دو فرزندی بودش ،پس دو گره تو خالی بجای فرزنداش میکشیم.

گره بعدی b هستش.که میره تو گره ی تو خالی فرزند چپ نوشته میشه.که خود b چون دو فرزندی هستش.پس دو گره تو خالی به جا فرزنداش میکشیم.

بعدش گره d رو در مکان فرزند چپ b مینویسیم.و چون d گره تک فرزندی هستش،فرزندش میتونه در سمت چپ باشه،یا راست.
که من اینجا یه فرزند چپ واسش کشیدم.

حالا e رو بعنوان فرزند چپ d قرار میدیم،و چون e برگ هستش،دیگه فرزندی واسش رسم نمیکنیم.

گره بعدی f هستش،که میره فرزند راست b میشه.وچون تک فرزندی هستش.پس یا فرزند چپ داره یا راست.که من اینجا واسش فرزند راست میکشم.

گره بعدی g هستش.که میره بعنوان فرزند راست f انتخاب میشه.و چون برگ هستش،دیگه فرزندی نداره.

گره بعدی c هستش که میره بعنوان فرزند راست a قرار میگیره،چون دو فرزندی هستش،پس دو گره تو خالی به عنوان فرزنداش میکشیم.

و همینجور الی آخر...
که یکی از شکل هاش این میشه: