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

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

ارسال:
  

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 آن داده شده است

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



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  تعداد برگ درخت؟؟؟؟؟؟؟ rad.bahar ۴ ۳,۸۳۳ ۱۵ آذر ۱۴۰۲ ۱۱:۵۳ ق.ظ
آخرین ارسال: mohamadrra
  فیلم کامل آفلاین پایگاه داده استاد خلیلی فر mona64 ۶ ۵,۴۹۴ ۱۱ آذر ۱۴۰۲ ۱۰:۱۵ ق.ظ
آخرین ارسال: Noura9999
  جزوه اسکن شده " سیستم های توزیع شده " دکتر پدرام arash691 ۸ ۱۴,۰۹۴ ۱۰ آذر ۱۴۰۱ ۰۲:۵۵ ق.ظ
آخرین ارسال: negarrah
  فیلم قفل شده Mohammad_TeZaR ۰ ۰ ۰۵ شهریور ۱۴۰۱ ۰۸:۳۷ ب.ظ
آخرین ارسال: Mohammad_TeZaR
  استخدام کارشناس تحلیل داده zeinab_IT ۰ ۱,۰۰۵ ۱۷ بهمن ۱۴۰۰ ۱۲:۳۱ ب.ظ
آخرین ارسال: zeinab_IT
  تا به حال شده خدا فرصت زندگی کردن دوباره رو بهت بده؟مرگ از جلوی چشمات رد شده؟ abraham ۲۱ ۱۴,۴۹۷ ۲۰ دى ۱۳۹۹ ۱۰:۵۶ ب.ظ
آخرین ارسال: raam
  دو سوال در مورد درخت BST(درخت جستجوی دودویی) امیدوار ۳ ۵,۱۰۷ ۱۰ دى ۱۳۹۹ ۱۲:۰۴ ق.ظ
آخرین ارسال: marzi.pnh
  زمان جستجوی درخت fateme.sm ۰ ۱,۵۶۵ ۰۶ دى ۱۳۹۹ ۱۰:۴۱ ب.ظ
آخرین ارسال: fateme.sm
  مرتبه ایجاد درخت rad.bahar ۱ ۳,۰۲۳ ۳۰ مهر ۱۳۹۹ ۰۳:۳۴ ب.ظ
آخرین ارسال: rad.bahar
  عمق درخت ???? rad.bahar ۱ ۲,۰۸۱ ۱۱ مهر ۱۳۹۹ ۰۳:۳۱ ب.ظ
آخرین ارسال: عزیز دادخواه

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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