تالار گفتمان مانشت

این تست IT88
تعداد درخت های دودویی که پیمایش های پیش ترتیب و پس ترتیب آنها برابر رشته های زیر است چقدر است؟
Pre:abdefgchijkl
Post:edgfbihkljca

فرمولشا تو پارسه گفته:[tex]2^{n1}[/tex] که n1 تعداد گره های تک فرزندی رو مشخص میکنه
برای بدست آوردن گره های تک فرزندی به این صورت عمل می کنیم:از سمت چپ یکی از پیمایش‌ها (برای مثال PRE) حرکت می کنیم و هر ترتیب دوتایی از گره‌ها (ترتیب های دوتایی دقیقا کنار هم) را درنظر گرفته و در پیمایش دیگر بررسی می کنیم. اگر دقیقا همین ترتیب دوتایی را به صورت معکوس عینا مشاهده کردیم، گره اول آن تک فرزندی است.

وقتی اول Pre را انتخاب کنی و دوتادوتا با هم بگیری و مثل روش پارسه بری جلو جواب درسته
ولی اگه اول Post را انتخاب کنی و دوتادوتا با هم بگیری و با روش پارسه بری جلو جواب درست نیس

اینو بی زحمت توضیح بدید برام

شما جواب سوال هم بگید تا اگه کسی براتون خل کرد اول ببینه درسته بعد توضیح بده براتون

در هر دو حالت درست می شه .
در پیمایش پس ترتیب ترتیب دوتایی های ed,gf,ih هستن . در پیش ترتیب de,fg,hi . یعنی گره های d و f و h تک فرزند دارن.طبق فرمول (دو یه توان تعداد گره های تک فرزندی) می شه دو به توان سه = هشت.
هر کدوم رو بگیرین فرقی نمیکنه جواب یکی در میآد چون با پیمایش دیگه مقایسه ش میکنین.

(02 بهمن 1390 03:48 ب.ظ)si.mozhgan نوشته شده توسط: [ -> ]در هر دو حالت درست می شه .
در پیمایش پس ترتیب ترتیب دوتایی های ed,gf,ih هستن . در پیش ترتیب de,fg,hi . یعنی گره های d و f و h تک فرزند دارن.طبق فرمول (دو یه توان تعداد گره های تک فرزندی) می شه دو به توان سه = هشت.
هر کدوم رو بگیرین فرقی نمیکنه جواب یکی در میآد چون با پیمایش دیگه مقایسه ش میکنین.

آها... اینجور که شما میگین؛ یعنی لزومی نداره که مثلا اگه اول Post رو انتخاب می کنیم حتما بیایم و از چپ به راست دقیقا دوتادوتا بگیریمشون؟؟!! که دوتایی‌ها اینجوری بشن: ed,gf,bi,hk,lj,ca
و یعنی مجاز هستیم که از هر جای پیمایش، دوتایی رو انتخاب کنیم؟!! الان روش شما اینه که i رو با b که بعد از f ،کنار هم هستن باهم نگرفتین و i رو با h با هم گرفتین

مثلا پس ترتیب رو از چپ به راست در نظر می گیریم.
زوج اول ed هست . حالا در پیش ترتیب از چپ به راست بررسی میکنیم که آیا زوج de وجود داره یا نه . اگه داشته باشه معنیش یک گره تک فرزندیه.
بعد dg در پس ترتیب رو داریم . پس در پیش ترتیب دنبال gd میگردیم .
بعد gf در پس ترتیب رو داریم . پس در پیش ترتیب دنبال fg میگردیم .که پیدا می شه.
بعد fb در پس ترتیب رو داریم . پس در پیش ترتیب دنبال bf میگردیم .
بعد bi در پس ترتیب رو داریم . پس در پیش ترتیب دنبال ib میگردیم .
بعد ih در پس ترتیب رو داریم . پس در پیش ترتیب دنبال hi میگردیم .که پیدا می شه.
بعد hk در پس ترتیب رو داریم . پس در پیش ترتیب دنبال kh میگردیم .
بعد kl در پس ترتیب رو داریم . پس در پیش ترتیب دنبال lk میگردیم .
بعد lj در پس ترتیب رو داریم . پس در پیش ترتیب دنبال jl میگردیم .
بعد jc در پس ترتیب رو داریم . پس در پیش ترتیب دنبال cj میگردیم .
بعد ca در پس ترتیب رو داریم . پس در پیش ترتیب دنبال ac میگردیم .
سه گره‌ی تک فرزندی پیدا کردیم . دو به توان سه می شه هشت . جواب هشته.

روشی که پارسه گفته(فرمول تک فرزندی ها)بهتره چون توی کتاب تست سنجش که نوشته به تصحیح و خطا !