پاورپوینت درختان و نود

دانلود پاورپوینت با موضوع  درختان و نود،

در قالب ppt و در 50 اسلاید، قابل ویرایش.

Binary Tree Implementation
پياده سازي آرايه اي:
parent(i) در محل i/2 قرار دارد (براي i!=1).
فرزند سمت چپ i در محل 2i و فرزند سمت راست در محل 2i+1 قرار دارد.
اگر 2i>n باشد، i فرزند سمت چپ ندارد.
اگر 2i+1>n باشد، i فرزند سمت راست ندارد.
Binary Tree Implementation
مثل قبل، نمايش آرايه اي بهترين راه حل نيست.
اندازه حافظه ثابت است:
براحتي قابل گسترش نيست.
اگر درخت بالانس نباشد، حافظه هدر مي رود.
راه بهتر: استفاده از ايده لينک پيوندي.
مي شود از راه حل استفاده از همزاد دوري کرد، چون تعداد فرزندان ثابت است و فقط به دو اشاره گر نيازمنديم.
Binary Tree Node
تنها مشکل نمايش پيوندي اين است که به پدر دسترسي نداريم.
اشکالي ندارد:
بسياري از الگوريتمها نيازي  به دانستن پدر ندارند.
اگر هم مهم باشد، وقتي که درخت را پيمايش مي کنيم، يک اشاره گر به پدر را نگهداري مي کنيم.
اگر خيلي مهم باشد، مي توان به تعريف نود اشاره  گر پدر را اضافه نمود.
Questions
در درخت باينري زير:
نودهاي انتهايي کدامند؟
نودهاي غير انتهايي کدامند؟
سطح هر نود چند است؟
Questions
حداکثر تعداد نودها در يک درخت k-ary با ارتفاع h چند است؟
براي k=3 داريم :  1 + 3 + 9 + 27 + 81 …
براي k=4 داريم : 1 + 4 + 16 + 64 …
براي k=k داريم : 1 + k + k2 + k3 …
مجموع فوق برابر است با: (kh-1) / (k-1)
اگر h=4 و k=3 :
(34 – 1) / (3-1) = 80/2 =