ساختمان داده-طول مسیر داخلی و خارجی

[MRG_VB]

سلام و درود.

طول مسیر خارجی و داخلی در درخت دودویی مثل این پاینی رو چطور باید حساب کرد؟!

[MRG_VB]

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

با تشکر.

[manoto1371]

باسلام

طول مسیر خارجی و داخلی در درخت گسترش یاقته (محض) دودویی مطرح می باشد (به طور کلی)
که این درخت هم برای ذخیره سازی عبارات محاسباتی استفاده می شود .
عملگرها در نودهای داخلی (Internal Node)(گره های دارای دو فرزند) و عملوندها در نودهای خارجی (External Node)(گره های بدون فرزند - برگ) ذخیره می شوند .
فرمول های قابل تامل در این قسمت :

تعداد گره های خارجی = تعداد گره های داخلی + 1
طول مسیر خارجی = مجموع طول مسیرها از ریشه تا گره های خارجی
طول مسیر داخلی = مجموع طول مسیرها از ریشه تا گره های داخلی
طول مسیر خارجی = طول مسیر داخلی + 2 * تعداد گره های داخلی
مجموع تعداد گره های هر سطح ضرب در طول مسیر از ریشه تا سطح مورد نظر که تا سطح آخر باید تکرار شود هم طول مسیر خارجی را می دهد .

[MRG_VB]

این مجموع طول مسیرها از ریشه تا گره های خارجی یعنی چی ؟!؟!؟!؟

برای این درخت طول مسیر داخلی و خارجی چطوری میشه!؟!؟

با تشکر از شما!

[manoto1371]

این مجموع طول مسیرها از ریشه تا گره های خارجی یعنی چی ؟!؟!؟!؟

برای این درخت طول مسیر داخلی و خارجی چطوری میشه!؟!؟

با تشکر از شما!

با یاد خدا و سلام ..

گره های خارجی همانهایی هستند که در تصویر با مستطیل نشان داده شده اند و گره های داخلی توسط دایره ..
ابتدا باید طول مسیر هر گره را به طور مجزا محاسبه و سپس سیگما آن ها را بدست آوری .
در تصویر این کار نشان داده شده است ، برای بررسی صحت کار کافی است آنها را در فرمول های بالا ذکر شده در پست قبلی همین بخش قرار دهی و تست کنید .
اگر مجموع طول مسیر خارجی را محاسبه کنی عدد 17 بدست خواهد آمد (اعداد قرمز رنگ)
حال با توجه به فرمول آخر :
تعداد گره های داخلی (5) * 2 = 10

10 + طول مسیر داخلی (حاصل جمع اعداد سبز رنگ = 7) = 17

که برابر با همان طول مسیر خارجی شده و در فرمول صادق است .
پس حاصل کار درست می باشد ..
" منظور از طول مسیر یعنی تعداد یال ها تا رسیدن به یک نود "

[MRG_VB]

یه دنیا ممنون