تالار گفتمان مانشت
تعداد درخت های دودویی که پیمایش های Pre و Post آن داده شده است - نسخه‌ی قابل چاپ
تعداد درخت های دودویی که پیمایش های Pre و Post آن داده شده است - netsupport - 02 بهمن ۱۳۹۰ ۰۲:۴۱ ب.ظ

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

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

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

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

تعداد درخت های دودویی که پیمایش های Pre و Post آن داده شده است - saba1000 - 02 بهمن ۱۳۹۰ ۰۳:۴۷ ب.ظ

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

تعداد درخت های دودویی که پیمایش های Pre و Post آن داده شده است - si.mozhgan - 02 بهمن ۱۳۹۰ ۰۳:۴۸ ب.ظ

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

RE: تعداد درخت های دودویی که پیمایش های Pre و Post آن داده شده است - netsupport - 02 بهمن ۱۳۹۰ ۰۴:۰۲ ب.ظ

(۰۲ بهمن ۱۳۹۰ ۰۳:۴۸ ب.ظ)si.mozhgan نوشته شده توسط:  در هر دو حالت درست می شه .
در پیمایش پس ترتیب ترتیب دوتایی های ed,gf,ih هستن . در پیش ترتیب de,fg,hi . یعنی گره های d و f و h تک فرزند دارن.طبق فرمول (دو یه توان تعداد گره های تک فرزندی) می شه دو به توان سه = هشت.
هر کدوم رو بگیرین فرقی نمیکنه جواب یکی در میآد چون با پیمایش دیگه مقایسه ش میکنین.

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

تعداد درخت های دودویی که پیمایش های Pre و Post آن داده شده است - si.mozhgan - 02 بهمن ۱۳۹۰ ۰۴:۲۶ ب.ظ

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

تعداد درخت های دودویی که پیمایش های Pre و Post آن داده شده است - fatima1537 - 02 بهمن ۱۳۹۰ ۰۶:۰۱ ب.ظ

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