زمان کنونی: ۰۹ فروردین ۱۴۰۳, ۱۱:۲۸ ب.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

نکات - مفاهیم اولیه درخت

ارسال:
  

Masoud05 پرسیده:

نکات - مفاهیم اولیه درخت

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

۵
ارسال:
  

yaser_ilam_com پاسخ داده:

نکات - مفاهیم اولیه درخت

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

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

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

۲)بقیه گره ها به 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 محل اشغال می شود.


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

ارسال:
  

cormen پاسخ داده:

RE: نکات - مفاهیم اولیه درخت

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

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

۰
ارسال:
  

mojgan پاسخ داده:

نکات - مفاهیم اولیه درخت

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

۰
ارسال:
  

mosaferkuchulu پاسخ داده:

نکات - مفاهیم اولیه درخت

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

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

ارسال:
  

Masoud05 پاسخ داده:

RE: نکات - مفاهیم اولیه درخت

(۱۹ آبان ۱۳۹۰ ۰۵:۲۴ ب.ظ)mosaferkuchulu نوشته شده توسط:  در یک درخت دودویی تعداد برگ‌ها برابر است با تعداد گره های درجه ۲+۱ یعنی:
n0=n2+1
و این مقدار به تعداد گره‌ها با درجه‌ی ۱ بستگی نداره!
------------
تعداد کل گره‌ها‌ی یک درخت دودویی: ۲n0-1

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

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



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  تعداد برگ درخت؟؟؟؟؟؟؟ rad.bahar ۴ ۳,۸۳۴ ۱۵ آذر ۱۴۰۲ ۱۱:۵۳ ق.ظ
آخرین ارسال: mohamadrra
  کارنامه نتایج اولیه کنکور کارشناسی ارشد HamidReza1 ۰ ۸۱۰ ۰۹ خرداد ۱۴۰۲ ۱۰:۵۵ ق.ظ
آخرین ارسال: HamidReza1
  جزوه خلاصه نکات مهم فصول ابتدایی درس مهندسی نرم افزار Happiness.72 ۱ ۳,۴۸۷ ۱۳ خرداد ۱۴۰۱ ۰۶:۲۸ ب.ظ
آخرین ارسال: M o h m m @ d
  کارنامه اولیه و نهایی دکتری رشته آیتی lotuss ۱۲ ۶,۱۷۷ ۱۷ بهمن ۱۳۹۹ ۰۲:۳۳ ق.ظ
آخرین ارسال: hmaryam567
  بحث در مورد نتایج اولیه ازمون دکتری ۹۲ mkiani ۳۷ ۲۹,۸۸۳ ۱۷ بهمن ۱۳۹۹ ۰۲:۱۹ ق.ظ
آخرین ارسال: hmaryam567
  دو سوال در مورد درخت BST(درخت جستجوی دودویی) امیدوار ۳ ۵,۱۰۷ ۱۰ دى ۱۳۹۹ ۱۲:۰۴ ق.ظ
آخرین ارسال: marzi.pnh
  زمان جستجوی درخت fateme.sm ۰ ۱,۵۶۵ ۰۶ دى ۱۳۹۹ ۱۰:۴۱ ب.ظ
آخرین ارسال: fateme.sm
  مرتبه ایجاد درخت rad.bahar ۱ ۳,۰۲۳ ۳۰ مهر ۱۳۹۹ ۰۳:۳۴ ب.ظ
آخرین ارسال: rad.bahar
  عمق درخت ???? rad.bahar ۱ ۲,۰۸۱ ۱۱ مهر ۱۳۹۹ ۰۳:۳۱ ب.ظ
آخرین ارسال: عزیز دادخواه
  محاسبه ارتفاع درخت.... baharkhanoom ۳ ۷,۴۵۰ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۸ ب.ظ
آخرین ارسال: mohsentafresh

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close