[سوال] درخت دو دویی در ساختمان داده ها

[Ghoghnus]

سلام دوستان
اگر درخت دو دویی مثل شکل زیر داشته باشیم و قرار باشه 75ملیون شماره در اینها قرار بدیم چند سانتی متر کاغذ احتیاج میشه؟(فاصله هر گره یک سانتی متر است)

با شتکر

[godvb]

حوصله محاسبات و ریاضیات رو ندارم ولی خوب تا اونجایی که یادمه :

اونطور که نشون میده درخت دودویی پر هستش، یعنی همه گره ها جز سطح آخر دقیقا دو فرزند دارند.

هر درخت پر نیز کامل هم هست، ولی هر درخت کامل، درخت پر نیست. (درخت پر،کامل و ... از انواع درخت دودویی)

1- یک درخت دودویی پر با n گره عمقش بدین صورت بدست میاد :

کد:

Log2(n+1)

در واقع عکس فرمول زیر هستش که میگیم : تعداد کل گره های یک درخت به عمق D برابر است با : ( 2 به توان D ) منهای 1 .

کد:

(2^D)-1

خوب عمق که بدست اومد حالا میمونه تعداد گره های سطح آخر. حداکثر تعداد گره های درسطح i ام از فرمول زیر محاسبه کنین:

2 به توان (i منهای 1)

کد:

2^ (i-1)

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