بخشی از پاورپوینت
اسلاید 1 :
درختها
اسلاید 2 :
مقدمه
بازنمايي درخت ها
درخت هاي دودويي
پيمايش درختهاي دودويي
عمليات ديگر روي درختهاي دودويي
درختهاي دودويي نخ کشي شده
Heap ها
درختان جستجوي دودويي
درختهاي انتخاب
جنگل ها
نمايش مجموعه ها
شمارش درخت هاي دودويي متمايز
دانشگاه کاشان دانشکده برق و کامپيوتر
اسلاید 3 :
ساختار درختي، مجموعه داده هاي سازمان دهي شده اي است که اقلام اطلاعاتي آن از طريق شاخه ها با هم ارتباط دارند.
اسلاید 4 :
تعريف درخت
تعريف: درخت مجموعه اي متناهي و غير تهي از يک يا چند گره است به طوريکه:
داراي گره خاصي به نام ريشه باشد.
بقيه گره ها به n ≥ 0 مجموعه مجزا T1,…,Tn تقسيم شده که هر يک از اين مجموعه ها خود يک درخت هستند. T1,…,Tn زير درختان ريشه ناميده مي شوند.
هر نود در درخت ريشه مجموعه اي از زير درختان است
اسلاید 5 :
اصطلاحات مربوط به درخت ها
درجه گره : تعداد زيردرختهاي يک گره
گره هاي پاياني (برگ): گرههايي که درجه صفر دارند برگ يا گره پاياني هستند.
درجه درخت: بزرگترين درجه گره هاي موجود در آن است
فرزندان گره : ريشه هاي زير درختهاي گره اي مانند x ، فرزندان x ناميده مي شوند.
والد : x والد بچه هايش است.
همزاد (برادر): بچه هايي که والد يکسان دارند همزاد ناميده مي شوند .
اسلاید 6 :
اصطلاحات مربوط به درخت ها
اجداد يک گره: تمامي گره هايي که در مسير ريشه تا يک گره قرار دارند اجداد آن گره ناميده مي شوند.
نسل هاي گره: اگر گره y جد گره x باشد، مي گوييم x نسل y است. تمام گره ها (به جز گره ريشه)، نسل هاي گره ريشه اند.
سطح گره : سطح يک گره بدين صورت تعريف مي شود که ريشه در سطح يک قرار مي گيرد. براي تمامي گره هاي بعدي، سطح گره برابر است با سطح والد به اضافه يک.
ارتفاع درخت : ارتفاع يا عمق يک درخت بزرگترين سطح گره هاي آن درخت است.
اسلاید 7 :
اصطلاحات مربوط به درخت ها
مثال
A گره ريشه است.
B والد D و E است.
C همزاد B است.
D و E فرزندان B هستند.
D، E، F، G و I گره هاي برگ هستند.
A، B، C و H گره هاي داخلي ( غير پاياني) هستند
سطح E برابر 3 است.
عمق (ارتفاع) درخت برابر 4 است.
درجه نود B برابر 2 است.
درجه درخت برابر 3 است.
اجداد I برابر A, C, H است.
نسل هاي C برابر F, G, H, I است.
سطح
1-تعداد گره =تعداد شاخه
اسلاید 8 :
ياد اوري (ليست تعميم يافته)
A=(a, (b,c) )
A(a, Z(b,c) )
اسلاید 9 :
بازنمايي درخت ها
نمايش درخت ها به صورت ليست هاي پيوندي
درخت روبرو را مي توان در قالب ليست به صورت زير نشان داد
(A(B(E(K ،L)،F)،C(G)،D(H(M)،I،J)))
اسلاید 10 :
بازنمايي درخت ها
نمايش خاص براي درخت ها با گره هاي به طول ثابت
براي نمايش هر گره درخت، از يک گره در حافظه استفاده شود که فيلدهايي براي داده ها و اشاره گرهايي براي بچه هاي اين گره دارد.
عيب: هدر رفت حافظه
اگر T درختي از درجه k با n گره به صورت بالا باشد آنگاه از nk اشاره گر بچه تعداد n(k-1)+1 تا صفر است که در آن n>=1 است.
بنابر اين دو نمايش ديگر با استفاده از گره هاي به طول ثابت ارائه مي دهيم.
اسلاید 11 :
نمايش بچه چپ همزاد راست
بازنمايي درخت ها
ساختار گره
اسلاید 12 :
نمايش درجه دو درخت (بچه چپ، بچه راست)
بازنمايي درخت ها
