Printable View
کدام گزینه در مورد یک درخت 5 تائی کامل با 95 گره صحیح می باشد؟با فرض اینکه ریشه گره اول باشدو در عمق گرههها به ترتیب از چپ به راست در نظر گرفته شوند.
الف- این درخت 76برگ داردو گره پانزدهم آن پدر گره هفتادو دوم آن است
ب- این درخت 76 برگ دارد و گره چهاردهم آن پدر گره هفتادو دوم آن است
ج- این درخت 77 برگ دارد و گره چهاردهم ان پدر گره هفتاد ودوم آن است
د- این درخت 77 برگ دارد و گره پانزدهم آن پدر گره هفتاد ودوم ان است.
با تشکر
یه سوال! تعریف درخت n تایی کامل چیه؟ مگه این نیست که هر نود یا دقیقا n تا فرزند داره یا هیچی؟ اگه این باشه به راحتی می شه ثابت کرد که هر درخت n تایی کامل همیشه تعداد راس هاش به هنگ n برابر ۱ ه!
اگه تعریف فرق داره ممنون می شم اگه یکی بهم بگه...
تعریف درخت کامل:اگر همه سطوح به جز احتمالا سطح آخر، حداکثر تعداد گره ممکن را داشته باشند. و گره های سطح آخر هم از چپ به راست پر شده باشند. در نتیجه در سطح ما فبل آخر لزومی نداره که هر گره دقیقا دقیقا 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 تا
البته در تکمیل پست قبل باید بگم که درخت پر هم درختی است که همه گره ها به جز گره های سطح آخر دقیقا N فرزند داشته باشند.نقل قول:
نوشته شده توسط 404_3140