زمان کنونی: ۲۲ آذر ۱۳۹۶, ۰۲:۳۱ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)
ارسال:
  

netsupport پرسیده:

تعداد درخت های دودویی که پیمایش های Pre و Post آن داده شده است

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

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

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

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

۰
ارسال:
  

saba1000 پاسخ داده:

تعداد درخت های دودویی که پیمایش های Pre و Post آن داده شده است

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

۰
ارسال:
  

si.mozhgan پاسخ داده:

تعداد درخت های دودویی که پیمایش های Pre و Post آن داده شده است

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

ارسال:
  

netsupport پاسخ داده:

RE: تعداد درخت های دودویی که پیمایش های Pre و Post آن داده شده است

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

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

۰
ارسال:
  

si.mozhgan پاسخ داده:

تعداد درخت های دودویی که پیمایش های Pre و Post آن داده شده است

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

۰
ارسال:
  

fatima1537 پاسخ داده:

تعداد درخت های دودویی که پیمایش های Pre و Post آن داده شده است

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



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  نحوه یافتن پیمایش پس ترتیب یک درخت با داشتن پیمایش پیش ترتیب آن miss_samira ۲ ۱,۶۲۱ ۰۸ اسفند ۱۳۹۳ ۰۸:۵۶ ب.ظ
آخرین ارسال: shayesteb
  سوالاتی در مورد درخت Heap hejran_ha ۴ ۵,۳۹۹ ۱۵ مهر ۱۳۹۱ ۰۵:۰۴ ب.ظ
آخرین ارسال: hejran_ha
  ساخت درخت هیپ به روش جوانترین پدر shadi ۶ ۴,۵۶۰ ۱۷ شهریور ۱۳۹۱ ۱۰:۱۴ ب.ظ
آخرین ارسال: mfXpert
  زبان برنامه نویسی در ساختمان داده Alireza_1387 ۵ ۱,۸۰۲ ۲۱ مرداد ۱۳۹۱ ۰۹:۴۹ ب.ظ
آخرین ارسال: mosi70
  با عناصر تکراری در درخت هافمن چه می کنید؟ bijibuji ۱۳ ۳,۴۰۵ ۰۸ تیر ۱۳۹۱ ۰۵:۲۵ ق.ظ
آخرین ارسال: Masoud05
  نکات - مفاهیم اولیه درخت Masoud05 ۵ ۷,۰۳۷ ۰۶ تیر ۱۳۹۱ ۱۲:۰۰ ب.ظ
آخرین ارسال: cormen
  نکات - درخت دودویی ویژه Masoud05 ۳ ۵,۱۲۰ ۱۰ اردیبهشت ۱۳۹۱ ۰۹:۵۴ ب.ظ
آخرین ارسال: Masoud05
Exclamation مشکل در ساختمان داده jafar.sh ۱۹ ۵,۶۷۲ ۲۰ اسفند ۱۳۹۰ ۰۵:۰۳ ب.ظ
آخرین ارسال: fatima1537
  سوال ۳۹ ساختمان داده it88 Aurora ۱ ۱,۴۴۳ ۲۱ بهمن ۱۳۹۰ ۰۷:۲۷ ب.ظ
آخرین ارسال: mamat
  سوال پارسه -ساختمان داده mojgan ۱۸ ۴,۳۵۹ ۳۰ دى ۱۳۹۰ ۰۲:۴۰ ب.ظ
آخرین ارسال: variant20002000

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close