ساختمان داده ها (درختان و درختان دودویی)

صفحه 1:
ساختمان داده‌ها درختان و درختان دودویی بو # 

صفحه 2:
مرور *مسأله: چگونه ساختارهای غیر خطی را نگهداری کنیم؟ ؟درخت دودویی: *مثل لیست پیوندی است اما هر نود دو فرزند دارد. *آهنگ رشد ارتفاع درخت دودویی لگاریتمی است. »در هنگام جستجو و مرتب سازی خواص جالبی دارد. *نودها همان اشیاء هستند. 

صفحه 3:
ساختار درخت دودویی 

صفحه 4:
درخت ؟شامل نودها ویالها است. ريشه *از بالا به پایین رسم می شود. 0 “ حلقه ندارد. 

صفحه 5:
واژگان uly: A, B, D, G ‏نفرزند‎ B,C, D, E, F,G,H Sibling: {B, C, D}, {E, F} Sy: C, E, F,H 

صفحه 6:
درخت جستجوی دودویی ؟درخت دودویی * ريشه * زیردرخت سمت چپ » ووددرعت عت رافيت ؟ در درخت دودویی ترتیب فرزندان مهم است. د ۲ 558 © @ هر نود حداكثر دو فرزند دارد. * عمق نود 8 برابر ا است. ارتفاع درخت برابر ۲است. 

صفحه 7:
نمایش درخت *مثالی از درخت 

صفحه 8:
درختان دودویی " تعداد نودهای درخت دودویی به ارتفاع درخت و چگالی آن بستگی دارد. * درخت خطی: هر نود فقط یک فرزند داشته باشد. * درخت دودویی کامل: - تمام برگها در دو سطح آخر درخت 

صفحه 9:
درخت دودویی کامل ° Complete Binary Tree (CBT) ‏*درخت دودویی‎ ‏تمام سطوح بجز سطح آخر پر هستند و دارای 21 نود هستند.‎ * * تمام نودهای سطح آخر در سمت چپ ترین قسمت ممکن قرار دارند. 

صفحه 10:
چند مثال از درخت دودویی که ]8) نیستند. 

صفحه 11:
رابطه ی بین 31 و آرایه *اگر نودها را از بالا به پایین و از چپ به راست بشماریم یک آرایه خواهیم داشت. ‎°array: a Dae diver f ig. fh 2: j‏ ‎index: 81234 759‏ ° 

صفحه 12:
تبديل0871© به آرايه * مى توانيم آرايه را به راحتى تبديل به یک 68۲ كنيم. * نودها را از بالا به بايين و از جب به راجت تخوادیج: * حال یک آرایه داریم. ۰ ) 3, 10, 23, 42, 7, 21, 15, 19, 30} 

صفحه 13:
تبدیل آرایه به ‎CBT‏ *اگر یک آرایه داشته باشیم می توانیم یک ‎CBT‏ ‏درست كنيم. "آرایه: 3, 10, 23, 42, 7, 21, 15, 19, 30 " عناصر را از بالا به پایین و از چپ به راست بچینید. 

صفحه 14:
ایندکسهای آرایه °Array: 3, 10, 23, 42, 7, 21, 15, 19, 30 Left child index = 2*i+1 ? Right child index = 2*i+2? 

صفحه 15:
خواص 63۲ *نودی که ایندکس آن برابر آ است را در نظر بگیرید. *پدر در محل ‎2/i-1)‏ دارد. * فرزند سمت جب در محل (1*2+) قرار دارد. * فرزند سمت راست در محل (2*2+) قرار دارد. ؟اگر تعداد نودها برابر 0 باشد: ‎٠‏ ارتفاع 687 برابر [ (1 + 0),و۱۵ ] است. 

صفحه 16:
مثالهاى از درخت دودویی item = "a giraffe" 17پ item = "Have you eaten one?” BinaryNode ~~ ‏مرج‎ po | Tom = "an apple pia? | fem — Taga | 

صفحه 17:
درختان دودویی * ۱ t guess. Gather Hing to an incorre je is a leaf * information from the user and add two children to node System.out.print("what is it?" String correct = INPUT.nextLine() System.out.printIn("I need a question to distinguish that from 1 2 3 4 Sprotected void learn(BinaryNode<String> node) { 6 7 8 9 + node.getItem() + "." 10 System.out.printIn("The answer for " + correct 1 +" should be yes."); 12. System.out.print¢"Enter the question: "); 13. String question = INPUT.nextLine() ; 14 node, setLeft (new BinaryNode<String> (correct)) ; 15 node. setRight (new BinaryNode<String> (node. getItem())); 16 node. setItem(question) ; 

صفحه 18:
خلاصه *؟ درختان دودویی برای نمایش داده خیلی ‎date‏ ‏هستند. *ارتفاع 8۲ برابر (۲ 0۱09 است که ‎n‏ تعداد نودها است. ۴ هارا به راحتی‌میت وان‌به آرلیه تبدیل کرد. ؟ما از درختان دودویی برای جستجو و مرتب سازی استفاده می کنیم.