پاورپوینت ساختمان داده‌ها و درختان دودویی

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

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

مسأله: چگونه ساختارهای غیر خطی را نگهداری کنیم؟
درخت دودویی:
مثل لیست پیوندی است اما هر نود دو فرزند دارد.
آهنگ رشد ارتفاع درخت دودویی لگاریتمی است.
در هنگام جستجو و مرتب سازی خواص جالبی دارد.
نودها همان اشیاء هستند.
ساختار درخت دودویی
درخت
شامل نودها ویالها است.
از بالا به پایین رسم می شود.
حلقه ندارد.
واژگان
در درخت دودویی ترتیب فرزندان مهم است.
هر نود حداکثر دو فرزند دارد.
عمق نود A برابر ۲ است.
ارتفاع درخت برابر ۲است.
نمایش درخت
مثالی از درخت
درختان دودویی
تعداد نودهای درخت دودویی به ارتفاع درخت و چگالی آن بستگی دارد.
درخت خطی: هر نود فقط یک فرزند داشته باشد.
درخت دودویی کامل:
تمام برگها در دو سطح آخر درخت هستند.
هر نود داخلی دقیقاً دو فرزند دارد. (به جز سمت چپ ترین نود سطح ما قبل آخر که می تواند یک فرزند داشته باشد. )
درخت دودویی کامل
Complete Binary Tree (CBT)
درخت دودویی
تمام سطوح بجز سطح آخر پر هستند و دارای 2i  نود هستند.
تمام نودهای سطح آخر در سمت چپ ترین قسمت ممکن قرار دارند.
چند مثال از درخت دودویی که CBT نیستند.
رابطه ی بین CBT و آرایه
اگر نودها را از بالا به پایین و از چپ به راست بشماریم یک آرایه خواهیم داشت.
array:   a b c d e f g h i j
index:   0 1 2 3 4 5 6 7 8 9
تبدیلCBT به آرایه
می توانیم آرایه را به راحتی تبدیل به یک CBT کنیم.
نودها را از بالا به پایین و از چپ به راست بخوانید.
حال یک آرایه داریم.
{ 3, 10, 23, 42, 7, 21, 15, 19, 30}
تبدیل آرایه به  CBT
اگر یک آرایه داشته باشیم می توانیم یک CBT درست کنیم.
آرایه:  3, 10, 23, 42, 7, 21, 15, 19, 30
عناصر را از بالا به پایین و از چپ به راست بچینید.