درخت 5 تائی کامل

[lvenoos]

کدام گزینه در مورد یک درخت 5 تائی کامل با 95 گره صحیح می باشد؟با فرض اینکه ریشه گره اول باشدو در عمق گرههها به ترتیب از چپ به راست در نظر گرفته شوند.

الف- این درخت 76برگ داردو گره پانزدهم آن پدر گره هفتادو دوم آن است
ب- این درخت 76 برگ دارد و گره چهاردهم آن پدر گره هفتادو دوم آن است
ج- این درخت 77 برگ دارد و گره چهاردهم ان پدر گره هفتاد ودوم آن است
د- این درخت 77 برگ دارد و گره پانزدهم آن پدر گره هفتاد ودوم ان است.
با تشکر

[404_3140]

یه سوال! تعریف درخت n تایی کامل چیه؟ مگه این نیست که هر نود یا دقیقا n تا فرزند داره یا هیچی؟ اگه این باشه به راحتی می شه ثابت کرد که هر درخت n تایی کامل همیشه تعداد راس هاش به هنگ n برابر ۱ ه!
اگه تعریف فرق داره ممنون می شم اگه یکی بهم بگه...

[rezvan_DP]

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


اما جواب سوال گزینه 1 میشه:
توی درخت 5 تایی کامل میشه این رابطه رو بین هر گره و فرزندانش پیدا کرد که برای گره K+1 ام فرزندانش از 5K+2 تا 5K+6 قرار می گیرن. در نتیجه برای گره 72 داریم: 14*5+2=72
پس 14+1=15 پدر 72 است.
تعداد برگها:
تعداد نودها در سطح اول: 1
تعداد نودها در سطح دوم : 5
تعداد نودها در سطح سوم:25
تعداد نودها در سطح چهارم : 12*5+ 4
یعنی در سطح سوم که از نود شماره 7 شروع میشه تا 18 کاملا پر میشن و از نود 19 هم 4 تا پر میشه => تعداد برگها=5*12+4+نود20 تا 31 که جمعا میشه 76 تا

[rezvan_DP]

یه سوال! تعریف درخت n تایی کامل چیه؟ مگه این نیست که هر نود یا دقیقا n تا فرزند داره یا هیچی؟

البته در تکمیل پست قبل باید بگم که درخت پر هم درختی است که همه گره ها به جز گره های سطح آخر دقیقا N فرزند داشته باشند.