تالار گفتمان مانشت

منتظر ارسال شماییم!!!

تعداد برگهای یک درخت دودویی برابر با نصف تعداد کل برگهاش کی شه!
به عبارت بهتر اگر n زوج بود = n/2
اگر n فرد بود = حد بالای تقسیم بالا
البته این مطلب برای درخت مورب و متوازن صدق نمی کنه

در یک درخت دودویی تعداد برگ‌ها برابر است با تعداد گره های درجه 2+1 یعنی:
n0=n2+1
و این مقدار به تعداد گره‌ها با درجه‌ی 1 بستگی نداره!
------------
تعداد کل گره‌ها‌ی یک درخت دودویی: 2n0-1

(n0 تعداد برگ ها)

(19 آبان 1390 05:24 ب.ظ)mosaferkuchulu نوشته شده توسط: [ -> ]در یک درخت دودویی تعداد برگ‌ها برابر است با تعداد گره های درجه ۲+۱ یعنی:
n0=n2+1
و این مقدار به تعداد گره‌ها با درجه‌ی ۱ بستگی نداره!
------------
تعداد کل گره‌ها‌ی یک درخت دودویی: ۲n0-1

(n0 تعداد برگ ها)

مورد دوم برای درخت های پر صحیح هست برای درخت مورب خودتون امتحان کنید .

اصطلاحات درخت ها

• درخت مجموعه محدودی از یک یا چند گره به صورت زیر می باشد:
  

۱)دارای گره خاصی به نام ریشه باشد.

۲)بقیه گره ها به n ≥ ۰ مجموعه مجزا T1,…, Tn تقسیم شده که هر یک از این مجموعه ها خود یک درخت هستند. T1,…, Tnزیر درختان ریشه نامیده می شوند.

• لیست ها برای ذخیره سازی داده هایی که ترتیب سریالی (پشت سر هم) دارند مناسب هستند ولی درخت برای نمایش ساختار داده سلسله مراتبی استفاده می شود.
  

• گره : گره به عنصر حاوی اطلاعات و انشعابات به دیگر عناصر، اطلاق می شود.
  

• درجه گره: تعداد زیر درخت های یک گره را درجه آن گره می نامند.
  

• والد: گره ای که دارای زیر درختانی است را والد ریشه های زیر درختان گویند.
  

• فرزندان گره: ریشه های زیر درختان، فرزندان آن گره نامیده می شوند.
  

• گره برگ: گره ای که هیچ فرزندی ندارد.
  

• گره های همزاد: فرزندان یک گره، گره های همزاد یا هم نیا نامیده می شوند.
  

• اجداد گره: اجداد یک گره، گره هایی هستند که در مسیر طی شده از ریشه تا آن گره وجود دارند.
  

• سطح گره: سطح یک گره بدین صورت تعریف می شود که ریشه در سطح یک قرار می گیرد. برای تمامی گره های بعدی، سطح گره برابر است با سطح والد به اضافه یک. (در بعضی از کتاب ها سطح ریشه درخت صفر در نظر گرفته می شود)
  

• ارتفاع درخت: ارتفاع یا عمق یک درخت به بیشترین سطح برای گره های آن درخت گفته می شود.
  

---

درخت های دودویی

• یک درخت دودویی یا تهی است یا حاوی مجموعه ای محدود از گره ها شامل یک ریشه و دو زیر درخت دودویی است. این درخت ها
  
  زیر درخت های چپ و راست نامیده می شوند.
  

• مشخصه اصلی یک درخت دودویی بدین شکل است که هر گره آن حداکثر دو انشعاب دارد یعنی گره هایی که درجه ای بیشتر از دو
  
  نداشته باشند.
  

خواص درخت دودویی

• در هیچ درخت عادی صفر گره وجود ندارد، اما درخت دودویی تهی وجود دارد.
  

• در یک درخت دودویی ترتیب فرزندان دارای اهمیت بوده در حالی که در درخت عادی به این صورت نیست.
  

• حداکثر تعداد گره ها در سطح i ام یک درخت دودویی [tex]2^{i-1}[/tex] است، بشرطی که i ≥ ۱، یعنی شماره سطح اول یک درنظر گرفته شود.
  

• حداکثر تعداد گره ها در یک درخت دودویی به عمق k، [tex]2^{k}-1[/tex] است بشرطی که k ≥ ۱
  

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

• یک درخت دودویی با n گره و عمق k کامل است، اگر و تنها اگر گره هایش مطابق با گره های شماره گذاری شده در یک درخت
  
  دودویی پر به عمق k باشد. (سطح آخر می تواند حداکثر گره را نداشته باشد)
  

• برای هر درخت دودویی غیر تهی مانند T، اگر n0 تعداد گره های پایانی (برگ) و n2 تعداد گره های درجه ۲ باشد، آنگاه خواهیم داشت:
  
  
  n0 = n2 + 1
  

• نکته۱: درختی که تعداد فرزندان هر گره بجز گره برگ دقیقا k باشد، درخت kتایی کامل نامیده می شود که اگر n گره داشته باشد
  
  تعداد فرزندان آن از رابطه زیر بدست می آید.
  
  
  تعداد برگ ها=[tex](n(k-1) 1)/k[/tex]
  

• نکته ۲: تعداد درخت های دودویی متمایز که می توان با nگره ساخت با استفاده از فرمول مقابل بدست می آید:
  
  [tex](1/(n 1))\binom{2n}{n}=(1/(n 1))((2n)!/(n!n!))[/tex]
  

• اگر یک درخت دودویی کامل با n گره (یعنی logn ] +1 ]= عمق) تعریف شده باشد، آنگاه برای هر گره با اندیس i داریم:
  
  (۱) اگر i≠۱، آنگاه پدر i در[i/2] است. اگر i=1 ، آنگاه i ریشه است و پدری نخواهد داشت.
  
  (۲) اگر۲i≤n ، آنگاه فرزند چپ i در ۲i است. اگر ۲i>n، آنگاه i فرزند چپ ندارد.
  
  (۳) اگر ۲i+1≤n، آنگاه فرزند راست i در۲i+1 است. اگر۲i+1>n ، آنگاه i فرزند راست ندارد.
  

• نکته: در بدترین حالت، یک درخت مورب به عمق k، به آرایه ای با [tex]2^{k}-1[/tex] خانه نیاز دارد که از این مقدار، فقط k محل اشغال می شود.
  

منابع : از منابع موجود در اینترنت گرفته بودم و قرار دادم حضور ذهم ندارم کدام منبع بود

یک درخت دودویی با n گره و عمق k کامل است، اگر و تنها اگر گره هایش مطابق با گره های شماره گذاری شده در یک درخت

دودویی پر به عمق k باشد. (سطح آخر می تواند حداکثر گره را نداشته باشد)
***********************
در درخت کامل گره های سطح آخر باید از چپ به راست قرار گیرند وگرنه دیگه کامل محسوب نمیشود