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

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

ارسال:
  

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 تعداد برگ ها)

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



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  نحوه یافتن پیمایش پس ترتیب یک درخت با داشتن پیمایش پیش ترتیب آن miss_samira ۲ ۲,۴۹۰ ۰۸ اسفند ۱۳۹۳ ۰۹:۵۶ ب.ظ
آخرین ارسال: shayesteb
  سوالاتی در مورد درخت Heap hejran_ha ۴ ۷,۷۰۵ ۱۵ مهر ۱۳۹۱ ۰۶:۰۴ ب.ظ
آخرین ارسال: hejran_ha
  ساخت درخت هیپ به روش جوانترین پدر shadi ۶ ۵,۴۶۶ ۱۷ شهریور ۱۳۹۱ ۱۱:۱۴ ب.ظ
آخرین ارسال: mfXpert
  با عناصر تکراری در درخت هافمن چه می کنید؟ bijibuji ۱۳ ۳,۶۲۲ ۰۸ تیر ۱۳۹۱ ۰۶:۲۵ ق.ظ
آخرین ارسال: Masoud05
  نکات - لیست پیوندی Masoud05 ۴ ۸,۲۰۲ ۲۱ خرداد ۱۳۹۱ ۱۲:۰۰ ب.ظ
آخرین ارسال: liliana
  نکات - درخت دودویی ویژه Masoud05 ۳ ۵,۸۳۲ ۱۰ اردیبهشت ۱۳۹۱ ۱۰:۵۴ ب.ظ
آخرین ارسال: Masoud05
  [نکات] آرایه - صف و پشته Masoud05 ۳ ۹,۶۶۳ ۰۲ اردیبهشت ۱۳۹۱ ۰۱:۴۳ ق.ظ
آخرین ارسال: yaser_ilam_com
  نکات - مرتب سازی Masoud05 ۱ ۵,۹۵۷ ۲۰ فروردین ۱۳۹۱ ۰۸:۲۴ ب.ظ
آخرین ارسال: yaser_ilam_com
  تعداد درخت های دودویی که پیمایش های Pre و Post آن داده شده است netsupport ۵ ۲,۷۲۲ ۰۲ بهمن ۱۳۹۰ ۰۶:۰۱ ب.ظ
آخرین ارسال: fatima1537
  یک سوال از درخت Aurora ۱۲ ۴,۵۵۰ ۰۸ دى ۱۳۹۰ ۰۲:۰۲ ق.ظ
آخرین ارسال: Lantern

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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