شمارش برگ های هر سطح در درخت [بایگانی]

maXXis

چهارشنبه 18 تیر 1393, 18:55 عصر

سلام دوستان
من یک درخت دارم میخوام بدونم تو هر سطح چند تا برگ دارم.؟؟
مثلا درخت زیر
120945
سطح یک : 1
سطح دو :2
سطح سه : 4
سطح چهار :3
الی آخر ....
برنامش چطوری میشه.

abbas.oveissi

جمعه 20 تیر 1393, 05:00 صبح

دوست عزیز حداقل مینوشتید ساختمان داده ای که اطلاعات رو باهاش نگه میدارید چیه.این خیلی توی الگوریتم مهم است.
در کل خیلی عجیب نیست کل درخت رو پیمایش میکنید بعدش اگر بچه نداشت شمارنده رو زیاد میکنید.اولین ایده ای هم که به ذهنم رسید اینه که درخت رو توی آرایه ذخیره کنید بعد وقتی توی اندیس i هستید بچه هاش باید توی 2i+1 و 2i باشند.اگر بچه نداشت شمارنده اون سطح رو زیاد کن.
برای اینکه بدونید درخت چه جوری توی آرایه ذخیره میشه به لینک روبرو بخش "نمایش درخت دودویی (توسط آرایه) مراجعه کنید : http://www.hpkclasses.ir/Courses/DataStructure/ds1100.html