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

تعداد درخت های دودویی که پیمایش های 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 آن داده شده است

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



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

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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