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

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

در قالب 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
عناصر را از بالا به پایین و از چپ به راست بچینید.
ایندکسهای آرایه
Array:  3, 10, 23, 42, 7, 21, 15, 19, 30
Index:  0   1   2   3  4   5   6   7  8
خواص CBT
نودی که ایندکس آن برابر i است را در نظر بگیرید.
پدر در محل (i-1)/2 دارد.
فرزند سمت چپ در محل (2*i+1) قرار دارد.
فرزند سمت راست در محل (2*i+2) قرار دارد.
اگر تعداد نودها برابر n باشد:
ارتفاع CBT برابر  log2(n + 1)  است.