[Powered by Google Translate] [Дел 7] [Помалку Комфорни] [Нејт Hardison] [Универзитетот Харвард] [Ова е CS50.] [CS50.TV] 

Добредојдовте во Дел 7. Благодарение на ураган Сенди, наместо да има нормален дел од оваа недела, ние сме прави оваа прошетка низ, преку дел од прашањата. Одам да се следат заедно со проблемот Намести 6 спецификација, и минува низ сите прашања во Дел на прашања секција. Ако има било какви прашања, Ве молиме пост овие на CS50 разговараат. 

Добро. Ајде да се почнати. Токму сега јас барам на страница 3 од Проблем Постави спецификација. Одиме прво да почнам да зборувам за бинарни дрва бидејќи тие имаат многу значење за проблемот сет оваа недела - Дрвото Хафман кодирање. Еден од првите структури на податоци зборувавме за CS50 е низа. Запомнете дека низа е низа од елементи - сите од ист тип - чуваат веднаш до едни со други во меморијата. Ако имам целобројна низа што јас може да нацрта со користење на овој кутии-броеви-броеви стил - Да речеме дека имам 5 во првата кутија, имам 7 во секунда, тогаш имам 8, 10, и 20 во финалето кутија. Запомнете, два навистина добри работи за оваа низа се што имаме оваа постојана време пристап до било особено елемент  во низата ако знаеме неговиот индекс. На пример, ако сакам да го зграби третиот елемент во низата - на индекс 2 користење на нашата нулта-базирани индексирање систем - Јас буквално само треба да се направи едноставна математичка пресметка, хоп на таа позиција во низа, извлечете го 8 кои се чуваат таму, и јас сум добро да отидевме. 

Еден од лоши работи за оваа низа - дека ние разговаравме за кога зборувавме поврзани листи - е дека ако сакате да вметнете елемент во оваа низа, Одам да мора да направи некои менувањето наоколу. На пример, оваа низа тука е во подредени цел - подредени во растечки редослед - 5, а потоа 7, тогаш 8, потоа 10, а потоа 20 - но ако сакате да го внесете бројот 9 во оваа низа, Одам да мора да се префрлат некои од елементите со цел да се направи простор. Можеме да извлечеме ова тука. Одам да мора да се преместат на 5, 7, а потоа и 8; создаде јаз каде што може да се стави на 9, а потоа на 10 и 20 може да оди на правото на 9. Ова е вид на болка, бидејќи во најлош случај - кога сме морале да вметнете или на почетокот или на крајот на низата, во зависност од тоа колку ние сме менувањето - ние може да заврши морале да ја префрлат сите елементи дека ние сме во моментов чување во низа. 

Значи, она што е начин околу ова? На начин да се заобиколи ова е да одиме во нашиот поврзани листа на метод каде - наместо за чување на елементите 5, 7, 8, 10 и 20 сите еден до друг во меморијата - она што ние наместо направив беше да ги сочувате вид на секаде каде што сакавме да ги чува во овие поврзани листа на јазли кои сум извлекувањето тука, вид на ад хок. А потоа ние ги поврзам заедно со користење на овие следните совети. Јас може да има покажувач од 5 до 7, покажувачот од 7 до 8, покажувачот од 8 до 10, и конечно, покажувачот од 10 до 20, а потоа е нулти покажувачот на 20 покажува дека нема ништо лево. Трампа дека ние имаме тука е дека сега ако сакаме да внесете го бројот 9 во нашата подредени листата, сите што треба да направите е да се создаде нов јазол со 9, жица до тоа да укаже на соодветно место, и потоа повторно жица на 8 до точка спушти до 9. Тоа е прилично брзо, претпоставувајќи ние точно знаеме каде сакаме да го вметнете 9. Но трампа во замена за ова е дека сега сме изгубиле постојана време пристап за некоја посебна елемент во нашите податоци структура. На пример, ако сакам да се најде на четвртиот елемент во овој поврзани листа, Одам да мора да почне уште на самиот почеток на листата и работам мојот начин преку броење јазол по јазол се додека не се најде на четвртата. 

Со цел да се добие подобар пристап перформанси од поврзани листа - но исто така и задржат некои од придобивките што ги имавме во однос на вметнување работно време од поврзани листа - бинарен дрво се случува да треба да се користи малку повеќе меморија. Особено, наместо да има само еден покажувач во бинарно дрво јазол - како поврзаните-листа јазол не - ние ќе додадете втора покажувачот на бинарно дрво јазол. Наместо само со еден покажувач кон следниот елемент, ние ќе имаат покажувач кон лево дете и право дете. 

Ајде да нацрта слика да видиме што всушност изгледа како. Повторно, јас ќе одам да ги користите овие кутии и стрели. А бинарно дрво јазол ќе започнете со само обичен кутија. Тоа се случува да имаат простор за вредност, и тогаш тоа е, исто така, ќе има простор за левото дете и право дете. Одам да ги означат тука. Ние ќе имаат левото дете, а потоа ние ќе имаме право дете. Постојат многу различни начини на тоа. Понекогаш за простор и погодност, Јас всушност ќе го подготви како што јас го правам тука на дното каде што ќе одам да имаат вредност на врвот, а потоа право дете на долниот десен, и на левата дете на дното-лево. Да се ​​вратам на оваа топ дијаграм, имаме вредноста на самиот врв, тогаш имаме левата дете покажувач, а потоа имаме право-дете покажувач. 

Во Проблем Постави спецификација, зборуваме за цртање јазол кој има вредност 7, а потоа и левата дете покажувач кој е нула, и право-дете покажувачот дека е нула. Ние или може да напише капитал NULL во просторот за и на левата детето и право дете, или можеме да извлечеме оваа дијагонала коса црта низ секоја од кутии за да се покаже дека тоа е нула. Одам да го стори тоа само затоа што тоа е поедноставно. Она што го гледате тука се два начина на diagramming многу едноставна бинарна дрво јазол каде што има вредност 7 и нула деца совети. 

Вториот дел од нашата спецификација зборува за тоа како со поврзани листи - Запомнете, само мораше да се одржи на првиот елемент во листата да се сеќавам на целата листа - и, исто така, со бинарно дрво, ние само треба да се одржи на еден покажувач на дрвото со цел да ја задржат контролата над целата структура на податоци. Оваа специјална елемент од дрвото се вика root јазол од дрвото. На пример, ако ова еден јазол - овој јазол содржи вредноста 7 со нула лево и десно-дете совети - беа единствените вредност во нашата дрво, тогаш ова ќе биде нашиот корен јазол. Тоа е почетокот на нашето дрво. Ние може да се види малку појасно штом ќе започнете додавајќи повеќе лимфни јазли на нашите дрво. Дозволете ми да се повлече до нова страница. 

Сега ние ќе да се подготви дрво кое има 7 во коренот, и 3 внатрешноста на левата дете, и 9 внатрешноста на правото дете. Повторно, ова е прилично едноставна. Имаме 7, нацрта јазол за 3, јазол за 9, и јас одам да го поставите на левата дете покажувачот од 7 да се укаже на јазол кој содржи 3, и правото на дете покажувачот на јазол содржи 7 до јазол содржи 9. Сега, бидејќи 3 и 9 немаат деца, ние ќе постави сите на своето дете совети како да се биде нула. Еве, коренот на нашето дрво одговара на јазол содржи бројот 7. Можете да видите дека ако сите ние имаме е покажувачот во тој root јазол, потоа ќе можеме да одиме преку нашите дрво и пристап и дете јазли - и 3 и 9. Не треба да се одржи совети на секој јазол на дрво. Добро. Сега ние ќе да додадете друг јазол на овој дијаграм. Ние ќе додадете јазол содржи 6, и ние ќе го додадете ова како право дете на јазол содржи 3. Да го направите тоа, ќе одам да се избрише дека null покажувачот во 3-јазол и жица до точка на јазол содржи 6. Добро. 

Во овој момент, ајде да одиме во текот на еден малку терминологија. За почеток, од причина што тоа се нарекува бинарен дрво особено е тоа што има две деца совети. Постојат и други видови дрвја, кои имаат повеќе деца совети. Особено, си направил обидувал во Проблем Постави 5. Ќе забележите дека во тој обид, сте имале 27 различни покажувачи на различни деца - еден за секоја од 26 букви во англиска латиница, а потоа на 27 за апостроф - па, тоа е слично на видот на дрво. Но, тука, бидејќи тоа е бинарна, имаме само две деца совети. 

Во прилог на оваа root јазол дека ние зборувавме, ние сме, исто така, е фрлање околу овој термин 'дете'. Што значи тоа за еден јазол да се биде дете на друг јазол? Тоа буквално значи дека детето јазол е дете на друг јазол ако тоа друг јазол има една од своето дете совети во собата да се укаже на тој јазол. Да се ​​стави тоа во повеќе конкретни смисла, ако 3 се посочи на еден од дете покажувачи на 7, тогаш 3 е дете на 7. Ако бевме да дознаам што децата од 7 се - добро, можеме да видиме дека 7 има покажувач 3 и покажувач до 9, па 9 и 3 се деца од 7. Девет нема деца бидејќи нејзиниот дете покажувачи се нула, и 3 има само едно дете, 6. Шест, исто така, нема деца бидејќи и двете на покажувачи се нула, што ќе привлече токму сега. 

Покрај тоа, ние, исто така, зборува за родителите на одреден јазол, и тоа е, како што би очекувале, на реверсот на ова дете опис. Секој јазол има само еден родител - наместо два како што може да се очекува со луѓето. На пример, родител на 3 е 7. Родител на 9 е, исто така, 7 и родител на 6 е 3. Не многу за тоа. Ние исто така имаат смисла да се зборува за баби, дедовци и внуци, и поопшто зборуваме за предци и потомци на одреден јазол. Предок на еден јазол - или предци, туку на еден јазол - се сите јазли кои лежат на патот од коренот до тој јазол. На пример, ако јас сум во потрага по јазол 6, тогаш предци се случува да биде и 3 и 7. Предците на 9, на пример, се - ако јас сум во потрага по јазол 9 - тогаш предок на 9 е само 7. И потомци се сосема обратна. Ако сакате да се погледне во сите потомци на 7, тогаш мора да се погледне во сите јазли под него. Значи, имам 3, 9 и 6 сите како потомци на 7. 

Конечниот термин кој ние ќе зборуваме за е ова сфаќање дека е брат. Браќа и сестри - вид на по должината на овие семејни услови - се јазли кои се на исто ниво во дрвото. Значи, 3 и 9 се браќа и сестри, бидејќи тие се на исто ниво во дрвото. Тие и двете имаат ист родител, 7. 6-нема браќа и сестри, бидејќи 9 не имате било какви деца. И 7 не имате било какви браќа и сестри, бидејќи тоа е коренот на нашите дрво, и таму е само некогаш 1 корен. За 7 да имаат браќа и сестри не би требало да биде еден јазол над 7. Таму ќе мора да биде родител на 7, во кој случај 7 веќе нема да биде коренот на дрвото. Тогаш таа нова родител на 7 исто така ќе треба да имаат дете, и тоа дете тогаш ќе биде брат на 7. 

Добро. Преселба на. Кога почнавме нашата дискусија на бинарни дрва, ние разговаравме за тоа како ние се случува да ги користите за да стекнат предност во однос на двете низи и поврзани листи. И начинот на кој ние се случува да го направите тоа е со овој нарачување имот. Велиме дека бинарно дрво е наредено, според спецификацијата, ако за секој јазол во нашата дрво, за сите нејзини потомци на левата - левата детето и сите потомци на левата детето - имаат помала вредност, и сите јазли на правото - право дете и сите потомци на правото на детето - имаат јазли поголема од вредноста на тековната јазол дека ние барате. Само за едноставност, ние ќе да се претпостави дека не постојат никакви дупликат јазли во нашата дрво. На пример, во ова дрво ние нема да се справи со случајот каде што има вредност 7 во коренот  а потоа ние исто така има вредност 7 други места во дрво. Во овој случај, ќе забележите дека ова дрво е навистина нареди. Имаме вредноста 7 во коренот. Сè што лево од 7 - ако јас го вратите сите на овие мали белези тука - се лево од 7 - 3 и 6 - тие вредности се и помалку од 7, и сè на правото - што е само оваа 9 - е поголема од 7. 

Ова не е само нареди дрво содржат овие вредности, но ајде да привлече уште неколку од нив. Таму е, всушност целиот куп на начини на кои можеме да го направиме тоа. Одам да се користи стенографија само да го задржи нешта едноставно каде - наместо цртање од целиот кутии-и-стрелки - Јас сум само ќе исцртување на броеви и додадете стрели поврзување на нив. За почеток, ние едноставно ќе пишувам нашата изворна дрво повторно каде што имавме 7, а потоа и 3, а потоа 3 посочи назад кон правото на 6, и 7 има право дете беше 9. Добро. Што е уште еден начин што би можеле да ја напишам оваа дрво? Наместо 3 да биде на левата дете од 7, ние, исто така, би можеле да имаат 6 бидат левата дете од 7, а потоа 3 бидат левата дете на 6. Тоа ќе изгледа вака дрво токму тука, каде што имам 7, тогаш 6, а потоа 3 и 9 од десно. Ние исто така не мора да има 7 како нашата root јазол. Ние, исто така може да има 6 како наш корен јазол. Она што ќе изгледа? Ако ние ќе го задржат тоа нареди имот, сето кон лево од 6 треба да биде помалку од тоа. Има само една можност, а тоа е 3. Но, тогаш на правото дете од 6, имаме две можности. Прво, ние би можеле да имаат 7, а потоа 9, или би можеле да го нацрта тоа - како јас сум за да го направите тука - каде што имаме 9 како право дете од 6, а потоа 7 како на левата дете на 9. 

Сега, 7 и 6 не се единствените можни вредности за root. Ние, исто така, би можеле да имаат 3 во коренот. Што се случува ако 3 е во коренот? Тука, работите се малку интересно. Три нема никакви вредности кои се помалку од тоа, така што целата левата страна на дрво е само ќе биде нула. Таму нема да биде ништо таму. На правото, ние би можеле листата нешта во растечки редослед. Ние би можеле да имаат 3, потоа 6, потоа 7, тогаш 9. Или, пак, би можеле да сториме 3, потоа 6, тогаш 9, потоа 7. Или, пак, би можеле да сториме 3, потоа 7, тогаш 6, тогаш 9. Или, 3, 7 - всушност, не, не можеме да правиме со 7 повеќе. Тоа е нашата едно нешто таму. Ние можеме да правиме 9, а потоа и од 9 можеме да направиме 6 и од 7. Или, пак, можеме да направиме 3, потоа 9, потоа 7, а потоа 6. 

Една работа е да привлече вашето внимание е тука дека овие дрва се малку чудно изглед. Особено, ако се погледне на 4 дрва на десната страна - Јас ќе им круг, тука - овие дрва изгледаат речиси исто како поврзани листа. Секој јазол има само едно дете, и така ние немаме ништо од тоа дрво како структура што можеме да видиме, на пример,  во овој осамен дрво над овде на долниот лев. Овие дрва се, всушност, наречен дегенерира бинарни дрва, и ние ќе зборуваме за овие повеќе во иднина - особено ако одат за да се преземат други компјутерски науки курсеви. Овие дрва се дегенерира. Тие не се многу корисни, бидејќи, навистина, оваа структура е подложна  да се побара пати слична на онаа на поврзани листа. Ние не се да ги искористат предностите на дополнителна меморија - тоа екстра покажувачот - бидејќи на нашата структура се лоши на овој начин. Наместо да одам на и извлече бинарни дрва кои имаат 9 во коренот, која е конечна случај дека ќе имаме, ние сме наместо тоа, во овој момент, ќе зборуваме малку за оваа друг термин дека ние ги користиме кога зборуваме за дрвјата, кој се нарекува височина. 

Висината на дрво е растојанието од коренот на повеќето далечна јазол, односно бројот на хмел, кои ќе треба да се направи со цел да се почне од корен, а потоа завршуваат во најголем далечни јазол во стеблото. Ако ги погледнеме некои од овие дрвја дека ние сме подготвени токму тука, можеме да видиме дека ако се земе ова дрво во горниот лев агол и ние започне на 3, тогаш ние треба да се направи 1 хоп да стигнете до 6, втор хоп да стигнете до 7, и една третина хоп да се дојде до 9. Значи, висината на ова дрво е 3. Ние може да го стори истото вежба за други дрвја наведени со оваа зелена, и можеме да видиме дека висината на сите овие дрвја е навистина 3. Тоа е дел од она што ги прави дегенерира - дека нивната висина е само еден помалку од бројот на јазли во целиот дрво. Ако ги погледнеме во овој друг дрво што е заокружено со црвено, од друга страна, можеме да видиме дека најголем далечни лист јазли се 6 и 9 - остава се оние јазли кои немаат деца. Значи, со цел да се добие од коренот јазол или 6 или 9, ние треба да се направи еден хоп да стигнете до 7, а потоа и втората хоп да се дојде до 9, и, исто така, само една секунда хоп од 7 да се стигне до 6. Значи, висината на ова дрво овде е само 2. Можете да се врати и да го направи тоа за сите други дрва што ние претходно споменатите почнувајќи од 7 и 6, и ќе најдете дека висината на сите оние дрвја е исто така 2. 

Причината ние сме биле зборува нареди бинарни дрва и зошто тие се кул е бидејќи можете да пребарувате низ нив многу сличен начин да се бараат преку подредени низа. Ова е местото каде што ние зборуваме за добивање дека подобрена пребарување време во текот на едноставни поврзани листа. Со поврзани листа - ако сакате да најдете одреден елемент - ти си во најдобар случува да се направи некој вид на линеарна пребарување каде што ќе започне на почетокот на листа и хоп еден-по-еден - еден јазол од еден јазол - во текот на целиот листата, додека не се најде она што го барате. Каде што, ако имате бинарно дрво што се чуваат во овој убав формат, вие всушност може да се добие повеќе од една бинарна пребарување случува каде што можете поделба и освојување и пребарување преку соодветен половина на дрвото во секој чекор. Ајде да видиме како тоа работи. 

Ако имаме - повторно, ќе се вратам на нашата изворна дрво - Започнуваме во 7, имаме 3 од левата страна, 9 на десната страна, и под 3 имаме 6. Ако сакаме да пребарувате за број 6 во ова дрво, би започне во коренот. Ние би споредуваат вредноста ние сме во потрага за, да речеме 6, на вредноста складирани во јазол дека ние сме во моментов во потрага на, 7, најде дека 6 е навистина помалку од 7, па ние ќе се движи кон лево. Ако вредноста на 6 била поголема од 7, ние би наместо пресели во право. Бидејќи знаеме дека - поради структурата на нашите нареди бинарно дрво - сите вредности помалку од 7 ќе се чуваат од лево на 7, нема потреба да се грижат ниту гледајќи низ десната страна на дрво. Откако ќе се движи лево и ние сме сега на јазол содржи 3, можеме да направиме истата споредба повторно каде што се споредат 3 и 6. И сметаме дека додека 6 - вредноста ние сме во потрага за - е поголем од 3, ние може да оди на десната страна на јазол содржи 3. Нема левата страна тука, па ние би можеле да го игнорираа тоа. Но, ние знаеме само затоа што ние сме во потрага на дрвото себе, и можеме да видиме дека дрвото нема деца. 

Тоа е исто така многу лесно да се погледне до 6 во ова дрво ако ние си го прави тоа себеси како луѓето, но, ајде да го следат овој процес механички како компјутер би го направил навистина да разбере алгоритам. Во овој момент, ние сме сега во потрага на еден јазол, која содржи 6, и ние сме во потрага за вредноста 6, Значи, навистина, ние Наидовме на соодветни јазол. Наидовме на вредноста 6 во нашата дрво, а ние може да го запре нашите пребарување. Во овој момент, во зависност од она што се случува, можеме да кажеме, да, сме го пронашле вредност 6, таа постои во нашата дрво. Или, ако сте планира да го вметнете јазол или направи нешто, можеме да го направи тоа во овој момент. 

Да направиме уште неколку пребарувања само за да видам како тоа функционира. Ајде да погледнеме во она што се случува ако ние требаше да се обиде и да се погледне до вредност 10. Ако бевме да се погледне на вредноста 10, ние ќе започне во коренот. Ние ќе видите дека 10 е поголема од 7, па ние ќе се движи кон десно. Ние би се стигне до 9 и споредете 9 до 10 и да види дека 9 е навистина помалку од 10. Значи, повторно, би се обиде да се движи кон десно. Но, во овој момент, ние ќе забележите дека ние сме на нула јазол. Нема ништо таму. Нема ништо каде што 10 треба да биде. Ова е местото каде што можеме да го пријавите профилот на неуспех - дека постои навистина нема 10 во дрво. И, конечно, ајде да одиме преку случајот каде што се обидуваш да се погледне до 1 во стеблото. Ова е слично на она што се случува ако се погледне до 10, освен наместо да одат на правото, ние ќе оди на лево. Ние започне на 7 и да видиме што 1 е помалку од 7, па ние се движи кон лево. Ние дојдеме до 3 и да видиме што 1 е помалку од 3, па повторно ќе се обидеме да се движи кон лево. Во овој момент ние имаме нула јазол, па повторно можеме да го пријавите профилот на неуспех. 

Ако не сакате да дознаете повеќе за бинарни дрва, постојат еден куп на забава малку проблеми кои можете да направите со нив. Предлагам практикување на цртеж од овие дијаграми еден-по-еден и следење преку сите различни чекори, бидејќи ова ќе дојде во супер-корисна не само кога правиш кодирање Хафман проблем сет но исто така и во иднина курсеви - само за учење како да се извлечеш овие структури на податоци и мислам низ проблеми со пенкало и хартија или, во овој случај, iPad и игла. 

Во овој момент, иако, ние ќе се движат за да направи некои кодирање пракса и всушност игра со овие бинарни дрва и да видиме. Одам да се вратиш назад во текот на мојот компјутер. За овој дел од делницата, наместо користење CS50 Стартувај или CS50 простори, Одам да го користите апаратот. 

По заедно со проблемот Постави спецификација, Гледам дека јас сум требало да се отвори на уредот, одат на мојот Dropbox папка, се создаде папка наречена Дел 7, а потоа се создаде фајл наречен binary_tree.c. Еве ќе одиме. Имам апаратот веќе отворен. Одам повлече до терминалот. Одам да одат во папката Dropbox, направи директориумот наречен section7, и да видиме што е сосема празна. Сега ќе одам да се отвори binary_tree.c. Добро. Еве ќе одиме - празна датотека. 

Да се ​​вратиме на спецификација. Спецификацијата бара да се создаде нова дефиниција на тип за бинарно дрво јазол содржи int вредности - исто како и вредностите кои ги извлече во нашата diagramming порано. Ние ќе ја користите оваа boilerplate typedef што ние го направивме токму тука дека треба да се признае од Проблем Постави 5 - ако не хеш табелата начин на освојување на правопис програма. Исто така треба да го признае тоа од делот минатата недела каде што зборуваше за поврзани листи. Ние го добивме ова typedef на struct јазол, и ние го дал овој struct јазол ова име на struct јазол однапред така што тогаш ние може да се однесува тоа, бидејќи ние ќе сакаат да имаат struct јазол совети како дел од нашата struct, но ние сме тогаш опкружена ова - или подобро кажано, даден ова - во typedef така што, подоцна во кодот, ние може да се однесува на овој struct како само еден јазол, наместо на struct јазол. 

Ова ќе биде многу сличен на одделно поврзани листа дефиниција што видовме минатата недела. Да го направите ова, ајде да започнете со пишување од boilerplate. Ние знаеме дека ние мора да имаме целобројна вредност, па ние ќе се стави во int вредност, а потоа наместо да има само еден покажувач кон следниот елемент - како што направивме со одделно поврзани листи - ние ќе имаме лево и десно дете покажувачи. Тоа е прилично едноставна премногу - struct јазол * левата дете; и struct јазол * во право дете;. Кул. Тоа изгледа како прилично добар почеток. Да се ​​вратиме на спецификација. 

Сега ние треба да се изјасни за глобалната јазол * променлива за коренот на едно дрво. Ние ќе се направи оваа глобална исто како што ние ги направивме првите покажувачот во нашата поврзани листа, исто така, глобална. Ова беше, така што во функции кои ние пишуваме ние не треба да се задржи поминува низ овој корен - иако ќе видиме дека ако не сакате да напишете овие функции рекурзивно, тоа би можело да биде подобро да дури и не го помине околу како глобален на прво место и наместо да се иницијализира на локално ниво во вашата главна функција. Но, ние ќе го направи тоа на глобално ниво да се започне. Повторно, ние ќе ви даде неколку простори, а јас одам да прогласи еден јазол * корен. Само за да бидете сигурни дека јас не го оставам овој деиницијализира, јас одам да го поставите еднакви на нула. Сега, во главната функција - која ќе пишувам навистина брзо, токму тука - int главната (int argc, const char * avg []) - и јас одам да се започне прогласување мојот argv низа како const само така што знам дека тие аргументи се аргументите дека јас веројатно не сакате да го измените. Ако сакам да ги менувате Јас веројатно ќе треба да се прават копии од нив. Ќе видите оваа многу во код. Тоа е во ред или начин. Тоа е во ред да го оставиме како - изостави const ако сакате. Јас обично го стави во само така што јас се потсетувам  дека јас веројатно не сакате да ја промените оние аргументи. 

Како и секогаш, јас одам да го вклучите ова враќање 0 линија на крајот од главната. Еве, јас ќе иницирам мојот root јазол. Како што стои во моментов, имам покажувач кој е поставен на нула, па тоа е покажувајќи кон ништо. Со цел да се всушност да почне изградба на јазол, Јас прво треба да се алоцира меморија за тоа. Одам да го направите тоа со тоа што меморијата на грамада користење Примерок. Одам да го поставите корен еднаков на резултатот од Примерок, и јас одам да го користите sizeof оператор да се пресмета големината на еден јазол. Причина што јас го користам sizeof јазол за разлика, да речеме, прави нешто како ова - Примерок (4 + 4 +4) или Примерок 12 - е затоа што сакам мојот код да биде компатибилен можно. Сакам да бидам во можност да ја искористам оваа. В датотеката, таа ги собира на апаратот, а потоа ги собира на мојот 64-битна Mac - или на сосема поинаква архитектура - и сакам сето ова да работи на истиот. 

Ако јас сум одлуки претпоставки за големината на променливи - големината на int или големината на покажувачот - тогаш јас сум исто така прави претпоставки за видови на архитектури на кој мојот код може успешно да ги собере кога работи. Секогаш користете sizeof наспроти рачно собирање на struct полиња. Од друга причина е тоа што, исто така, може да биде баласт дека компајлерот става во структурата. Дури и само собирање на поединечни полиња не е нешто што обично сакаат да се направи, така, избришете таа линија. Сега, навистина да го иницијализирате овој root јазол, Одам да мора да го приклучиш во вредности за секој од своите различни полиња. На пример, за вредност Знам дека сакате да го иницијализирате до 7, и сега ќе одам да го поставите на левата дете да биде нула и право дете исто така да биде нула. Одлично! Ние го направивме тој дел од спец. 

Спецификација надолу кон дното на страница 3 ме прашува да се создаде уште три јазли - една содржат 3, едната од 6, и еден со 9 - и потоа да ги жица до толку тоа изгледа токму како нашите дрво дијаграм дека ние се зборува за претходно. Да го стори тоа прилично брзо тука. Ќе видите навистина брзо што јас ќе одам да започнете со пишување на еден куп на дупликат код. Одам да се создаде еден јазол * и јас одам да го наречеме три. Одам да го поставите тоа еднаква на Примерок (sizeof (јазол)). Одам да го поставите три-> вредност = 3. Три -> left_child = NULL; три -> десно _child = NULL; како и. Тоа изгледа прилично слична на иницијализацијата на коренот, а тоа е токму она што Одам да треба да направите ако почнам иницијализацијата 6 и 9, како и. Јас ќе го направи тоа навистина брзо тука - всушност, ќе одам да се направи малку копирате и залепите, и бидете сигурни дека јас - в ред.  Сега, имам го копира и да одам напред и да го поставите на овој еднаква на 6. Можете да видите дека тоа е потребно некое време и не е супер-ефикасни. Во само малку, ќе напише функција која ќе го направи тоа за нас. Сакам да го замени тоа со 9, заменете дека со 6. 

Сега имаме сите наши јазли создадена и иницијализира. Имаме нашиот корен постави еднаква на 7, или содржи вредноста 7, нашите јазол содржи 3, нашите јазол содржи 6, а нашите јазол содржи 9. Во овој момент, сите ние треба да направите е жица сè што. Причина јас иницијализира сите покажувачи на нула е само, така што можам да бидете сигурни дека Јас немам никакви деиницијализира совети таму случајно. И, исто така, бидејќи, во овој момент, јас само треба да всушност се поврзете јазли на секоја друга - на оние кои тие се всушност поврзани со - Јас не мора да одат преку и да сигурни дека сите NULLS се таму во соодветни места. 

Почнувајќи од коренот, знам дека левата дете коренот е 3. Знам дека право дете коренот е 9. После тоа, само други дете што ми остана да се грижи за е во право дете 3, кој е 6. Во овој момент, сето тоа изгледа прилично добро. Ќе избришете некои од овие линии. Сега сè изгледа прилично добро. Да се ​​вратиме на нашата спецификација и да видиме што имаме следно да направи. 

Во овој момент, ние треба да се напише функција наречена "содржи" со прототип на "bool содржи (int вредност). И ова содржи функција ќе се врати вистина  ако дрвото посочи од нашата глобална корен променлива  содржи вредноста поминаа во функција и лажни поинаку. Ајде да одиме напред и да го направи тоа. Ова ќе биде исто како збор што сме направиле со рака на iPad само малку пред. Ајде враќање во малку и движете нагоре. Ние ќе се стави оваа функција веднаш над нашите главни функција така што ние не треба да направите било кој вид на Текара. Значи, bool содржи (int вредност). Таму ќе одиме. Има нашите boilerplate декларација. Само за да бидете сигурни дека ова ќе ги собере, Одам да се оди напред и само го поставите еднаква да се врати лажни. Токму сега оваа функција само ќе не направи ништо и секогаш велат дека вредноста што ние барате не е на дрвото. 

Во овој момент, тоа е веројатно добра идеја - бидејќи ние сум напишал целиот куп на код и ние не се ни обиделе тестирање досега - да бидете сигурни дека сите компајлира. Постојат неколку работи што треба да направите за да бидете сигурни дека ова всушност ќе се компајлира. Прво, види дали ние сме биле користење на сите функции во која било библиотеки, кои сеуште не сме вклучени. Функциите што сум користел досега се Примерок, а потоа ние сме, исто така, е со користење на овој вид - оваа нестандардна тип наречен "bool' - која е вклучена во стандардната bool хедер датотека. Ние дефинитивно сакате да вклучуваат стандардни bool.h за bool тип, и ние исто така сакаме да # вклучуваат стандардни lib.h за стандардни библиотеки кои вклучуваат Примерок и слободни, и сите за тоа. Значи, одзумирате, ние ќе треба да се повлече. Ајде да се обидеме и бидете сигурни дека тоа всушност не компајлирате. Гледаме дека го прави тоа, па ние сме на вистинскиот пат. 

Да се ​​отвори binary_tree.c повторно. Се компајлира. Ајде да одиме надолу и да бидете сигурни дека ние вметнете некои повици кон нашите Содржи функција - само за да бидете сигурни дека тоа е добро и добро. На пример, кога ние не некои пребарувања во нашата дрво порано, се обидовме да се погледне до вредностите 6, 10 и 1, и знаевме дека 6 беше во дрво, 10 не беше во дрво, а 1 не беше во дрво или. Ајде да го користите оние примерок повици како начин да дознаам дали или не нашите Содржи функција е работа. Со цел да го направат тоа, јас ќе одам да ги користите printf функција, и ние ќе печати резултатот на повикот да ги содржи. Одам да се стави во серијата "содржи (% d) = бидејќи  ние ќе приклучок во вредност која ние ќе барате, и =% s \ n "и ја користат таа како наш формат стринг. Ние сме само ќе видиме - буквално печати на екран - она што изгледа како повик на функција. Ова не е всушност повик на функција.  Ова е само низа дизајниран да изгледа како повик на функција. 

Сега, ние ќе го приклучиш во вредности. Ние ќе се обидеме содржи на 6, а потоа она што се случува да го направите тука е да се користи дека троичен оператор. Ајде да видиме - содржи 6 - па, сега сум содржани 6 и ако содржи 6 е точно, стринг дека ние ќе испрати формат карактер% s ќе биде на стрингот "вистина". Ајде дојдете во текот на еден малку. Инаку, ние сакаме да се испрати стринг "лажни" ако содржи 6 враќа false. Ова е малку глупав изглед, но јас дознаам јас како и да ги илустрираат што троичен оператор изгледа како уште не сме го виделе за некое време. Ова ќе биде убав, удобен начин да дознаам ако нашите Содржи функција е работа. Одам да дојдете назад во текот на лево, и јас ќе одам да копирате и залепите оваа линија неколку пати. Тоа се промени некои од овие вредности наоколу, па ова ќе биде 1, и ова ќе биде 10. 

Во овој момент ние имаме убав Содржи функција. Имаме некои тестови, а ние ќе се види дали сето ова функционира. Во овој момент ние сум напишал некои код. Време е да се откажете од надвор и бидете сигурни дека сè уште компајлира. Напушти надвор, а сега ајде да се обидеме што бинарно дрво повторно. Па, изгледа дека имаме грешка, и ние го добивме ова експлицитно прогласување на библиотека функција printf. Тоа изгледа како ние треба да одиме и # вклучуваат standardio.h. А со тоа и сето тоа треба да се компајлира. Сите ние сме добри. Сега ајде пробајте да ја отворите бинарна дрво и да видиме што се случува. Тука сме,. / Binary_tree, и гледаме дека, како што се очекуваше - бидејќи не сме спроведува содржи сепак, или подобро кажано, ние сме само да ги ставите во замена лажни - можеме да видиме дека тоа е само враќање лажни за сите нив, Значи тоа е сите работи во најголем дел прилично добро. 

Да се ​​вратиме и да ги спроведе содржи во овој момент. Одам да дојдете, зум во и - Запомнете, алгоритам кој што се користи е дека почнавме на root јазол а потоа на секој јазол што ги среќаваме, тоа го правиме споредба, и врз основа на таа споредба ние или се движи лево дете или десно дете. Ова ќе изгледа многу слични на бинарни пребарување код кој ние ја напишал порано во овој термин. Кога ќе започнете, знаеме дека ние сакаме да се одржи на тековната јазол дека ние сме во потрага на, и сегашните јазол ќе се иницијализира на root јазол. И сега, ние ќе треба да продолжувам да одам низ дрво, и се сеќавам дека нашите запирање состојба -  кога ние всушност работел преку примерот со рака - беше кога се судри со нула јазол, кога не ние погледна е нулти дете, туку кога ние всушност се пресели во еден јазол во стеблото и сфатив дека ние сме на нула јазол. Ние ќе iterate до мом не е еднаква на нула. И што ќе правиме? Ние ќе тестира дали (мом -> вредноста == вредност), тогаш знаеме дека ние сме всушност се најде на јазол што го барате. Па еве, ние може да се врати вистина. Инаку, ние сакаме да видиме дали или не вредност е помала од вредноста. Ако вредноста на тековната јазол е помала од вредноста што го барате, ние ќе се движи кон десно. Значи, мом = мом -> right_child и спротивно, ние ќе треба да се движи кон лево. мом = мом -> left_child;. Прилично едноставна. 

Најверојатно го признае јамка што изгледа многу слично на тоа од бинарни пребарување порано во терминот, освен тогаш ние се занимаваат со ниска, средна и висока. Тука, ние само треба да се погледне во тековната вредност, па тоа е убав и едноставен. Ајде бидете сигурни дека овој код работи. Прво, бидете сигурни дека тоа компајлира. Изгледа како го прави тоа. Да се ​​обидеме тоа трчање. И навистина, тоа отпечатоци од сè што очекуваше. Утврди 6 во дрво, не се најде 10 бидејќи 10 не е во дрво, и не најде 1 или затоа што 1 е исто така, не во дрво. Кул работи. 

Добро. Да се ​​вратиме на нашата спецификација и да видиме што е следно. Сега, таа сака да додадете некои повеќе лимфни јазли на нашите дрво. Таа сака да додадете 5, 2 и 8, и бидете сигурни дека нашите содржи код уште работи како што се очекуваше. Ајде да одиме направите тоа. Во овој момент, наместо да прави дека досадни копирате и залепите повторно, нека напише функција за да всушност се создаде еден јазол. Ако ние дојдете сите на патот до главна, можеме да видиме дека ние сме правеле тоа многу сличен код одново и одново секој пат дека ние сакаме да се создаде еден јазол. 

Да се ​​напише функција која, всушност, ќе се изгради еден јазол за нас и да се врати. Одам да го наречеме build_node. Одам да се изгради еден јазол со одредена вредност. Зумирате тука. Првото нешто што јас ќе одам да направите е да всушност се создаде простор за јазол на грамада. Значи, јазол * n = Примерок (sizeof (јазол)), n -> вредност = вредност; а потоа тука, јас сум само ќе се иницијализира сите полиња да бидат соодветни вредности. И на самиот крај, ние ќе се вратат нашите јазол. Добро. Една работа е да се напомене е дека оваа функција токму тука се случува да се вратат покажувач на меморија што е грамада распределени. Што е убаво за ова е тоа што овој јазол сега - ние мора да го пријават на грамада, бидејќи ако ние го прогласи на магацинот ние не би биле во можност да го стори тоа во оваа функција се допаѓа ова. Дека меморијата ќе одат надвор од опсегот и ќе биде неважечко ако се обидовме да ја пристапите подоцна. Бидејќи ние се прогласи грамада распределени меморија, ние се случува да мора да се грижи за ослободување подоцна за нашата програма не да излегуваат во јавноста било меморија. Ние сме биле punting на тоа за сè друго во кодот само заради едноставноста во тоа време, но ако некогаш се напише функција која изгледа вака каде што имаш - некои го нарекуваат Примерок или realloc внатре - вие сакате да бидете сигурни дека ќе стави некој вид на коментар се тука што вели, еј, знаеш, се враќа куп распределени јазол иницијализира со донесените во вредност. И тогаш ќе сакате да бидете сигурни дека ќе се стави во некој вид на забелешка во која се вели повикувачот да го ослободиме врати меморијата. На тој начин, ако некој некогаш оди и користи таа функција, тие знаат дека она што се врати од таа функција во одреден момент ќе треба да бидат ослободени. 

Претпоставувајќи дека сè е добро и добро тука, можеме да одиме долу во нашиот код и да го замени сите на овие редови, токму тука со повици за нашите изгради јазол функција. Да го стори тоа навистина брзо. Оној дел што ние нема да го замени е овој дел овде на дното, каде што всушност жица до јазли за да се укаже на едни со други, затоа што ние не можеме да направиме во нашата функција. Но, ајде да направиме корен = build_node (7); јазол * три = build_node (3); јазол * шест = build_node (6); јазол * девет = build_node (9);. И сега, исто така сакавме да додадете јазли за - јазол * пет = build_node (5); јазол * осум = build_node (8); и она што беше друг јазол? Ајде да видиме овде. Сакавме да исто така, додаде 2 - јазол * два = build_node (2);. Добро. Во овој момент, ние знаеме дека ние го добивме 7, 3, 9 и 6 сите жичен до соодветно, но она што за 5, 8 и 2? Да задржи што е во соодветна цел, знаеме дека право дете три е 6. Значи, ако ние ќе додадете 5, на 5, исто така припаѓа на десната страна од дрво од кои 3 е коренот, па 5 припаѓа како на левата дете од 6. Ние можеме да го правиме ова преку велејќи шест -> left_child = пет; а потоа на 8 припаѓа како на левата дете од 9, па девет -> left_child = осум; а потоа 2 е лево дете од 3, па можеме да го направи тоа се тука - те -> left_child = двајца;. Ако не сте сосема следат заедно со тоа, јас Ви препорачуваме да го извлече себе. 

Добро. Ајде да го спаси ова. Ајде да одиме надвор и бидете сигурни дека тоа составува, и потоа можеме да додадете во нашата Содржи повици. Изгледа сè уште компајлира. Ајде да одиме и да го додадете во некои содржи повици. Повторно, јас ќе одам да направите малку копирате и залепите. Сега ајде да пребарувате за 5, 8, и 2. Добро. Ајде бидете сигурни дека сето ова изгледа добро уште. Одлично! Спаси и да престанам. Сега ајде да се направи, состави, а сега ајде да се кандидира. Од резултатите, тоа изгледа како сè е работи само убаво и добро. Одлично! Па сега ние го добивме нашиот Содржи функција напишана. Ајде да се оди натаму и да почне да работи за тоа како да вметнете јазли во дрво бидејќи, како што ние си го прави тоа токму сега, работите не се многу убава. 

Ако се вратиме на спецификација, тоа бара од нас да се напише функција наречена вметнете - повторно, враќајќи се на bool за тоа дали или не ние всушност би можеле да вметнете јазол во дрвото - и тогаш вредноста да се вметне во дрво е наведен како единствен аргумент на нашите вметнете функција. Ние ќе се вратат точно ако ние навистина би можеле да вметнете јазол содржи вредност во дрво, што значи дека ние, еден, имаше доволно меморија, а потоа две, тој јазол не веќе постојат во дрво од - Запомнете, не се случува да имаат дупликат вредности во дрво, само за да се направат нештата едноставни. Добро. Назад кон код. Отвори го. Зум во малку, потоа движете се надолу. Ајде стави вметнете функција веднаш над содржи. Повторно, тоа се случува да се нарече bool вметнете (int вредност). Го даде малку повеќе простор, а потоа, како стандардно, да се стави во замена лажни на самиот крај. Сега одредување на дното, ајде да одиме напред и наместо рачно изградба на јазли во главниот себе и жици за нив да се укаже на едни со други како што го правиме, ние ќе се потпираат на нашата вметнете функција да го стори тоа. Ние не ќе се потпираат на нашата вметнете функција да се изгради целата дрво од нула само уште, туку ќе се ослободи од овие линии - we'll Коментар од овие линии - кои градат јазли 5, 8, и 2. И наместо тоа, ние ќе внесете повици кон нашите вметнете функција да бидете сигурни дека тоа всушност се работи. Еве ќе одиме. 

Сега сме коментира надвор овие линии. Ние имаме само 7, 3, 9 и 6 во нашата дрво во овој момент. Да бидете сигурни дека тоа е сите работи, можеме да одзумирате, направи нашиот бинарно дрво, работи, и можеме да видиме дека содржи е сега ни кажува дека ние сме сосема во право - 5, 8 и 2 веќе не се во дрво. Оди назад во кодот, и како ќе се дојде да вметнете? Запомни она што го правевме кога бевме всушност вметнување 5, 8 и 2 од претходно. Игравме таа игра Plinko каде што почнавме во коренот, слезе од дрвото, еден по еден по еден додека не се најде соодветна јаз, и тогаш жичен во јазол на соодветно место. Ние ќе го прават истото. Ова е во основа како пишување на код кој што се користи во содржи функција да се најде на местото каде што јазол треба да биде, и тогаш ние само ќе го вметнете јазол право таму. Да почнеме прави тоа. 

Значи имаме еден јазол * мом = корен, ние сме само ќе го следат содржи код додека сметаме дека тоа сосема не работат за нас. Ние ќе оди преку дрво додека тековната елемент не е нула, и ако најдеме вредност мом е еднаква на вредноста што ние се обидуваме да се вметне - Па, ова е еден од случаите во кој ние, всушност, не може да го вметнете јазол во дрво, бидејќи тоа значи дека имаме дупликат вредност. Еве ние всушност ќе се врати лажни. Сега друго, ако вредноста мом е помалку од вредност, сега знаеме дека се движи на десно  затоа што вредноста му припаѓа на десната половина на мом дрво. Во спротивно, ние ќе треба да се движи кон лево. Тоа е основа на нашите Содржи функционира право таму. 

Во овој момент, откако ќе завршиме овој додека јамка, нашата мом покажувачот ќе се укажува на нула Ако функцијата не е веќе вратени. Ние сме тоа има мом на местото каде што сакате да го вметнете нов јазол. Она што останува да се направи е да се всушност изградба на нов јазол, кои можеме да направиме многу лесно. Можеме да го користиме нашите супер корисна изгради јазол функција, и нешто што ние не го стори порано - ние само вид на земав здраво за готово, но сега ние ќе направиме само за да бидете сигурни - ние ќе се тестираат за да бидете сигурни дека вредноста се врати со нов јазол е всушност не нула, бидејќи ние не сакаме да почнат што пристапуваат дека меморијата ако тоа е нула. Ние може да го тестира да бидете сигурни дека нов јазол не е еднаков на нула. Или наместо тоа, ние само може да се види дали тој навистина е нула, и ако е нула, тогаш ние само може да се врати лажни рано. 

Во овој момент, ние треба да жица нов јазол во своето соодветно место во дрво. Ако ги погледнеме назад во главната и каде што ние, всушност биле ожичување во вредности пред, можеме да видиме дека начинот на кој ние се тоа го правам кога сакавме да се стави 3 во дрво е ние пристапи левата дете на коренот. Кога ќе стави 9 во дрво, моравме да пристапите на правото дете на коренот. Моравме да имаат покажувач на родителот со цел да се стави нова вредност во дрво. Лизгање назад за да вметнете, дека нема да доста работа тука бидејќи ние немаме родител покажувач. Она што сакаме да биде во можност да направите е, во овој момент, провери вредноста на родителите и види - и, боже, ако вредноста на родителите е помалку од сегашната вредност, потоа десен детето на родителот треба да биде новиот јазол; инаку, лево детето на родителот треба да биде новиот јазол. Но, ние не ја имаат оваа родител покажувачот уште доста. 

Со цел да го добие, ние всушност ќе треба да го пратите како одиме преку дрвото и да се најде соодветно место во нашиот јамка погоре. Ние можеме да го направите тоа со лизгање назад до врвот на нашата вметнете функција и следење на друг покажувачот променлива нарекува родител. Ние ќе го постави еднакви на нула на почетокот, и тогаш секој пат одиме низ дрво, ние ќе се постави на родител покажувачот да одговара на тековната покажувач. Постави родител еднаква мом. На овој начин, секој пат кога ќе одиме преку, ние ќе се осигура дека како тековната покажувачот добива зголемува родителот покажувачот следува - само едно ниво повисоко од сегашните покажувачот на дрвото. Дека сите изгледа прилично добро. 

Мислам дека едно нешто што ќе сакате да се прилагоди ова е да се изгради јазол враќа нула. Со цел да се изгради јазол всушност успешно се врати нула, ние ќе мора да се промени тој код, бидејќи тука, ние никогаш не се тестираат за да бидете сигурни дека Примерок врати валидна покажувач. Значи, ако (n = NULL!), Потоа - ако Примерок врати валидна покажувач, тогаш ние ќе го иницијализирам; Во спротивно, само ќе се врати и дека ќе заврши враќа нула за нас. Сега сето тоа изгледа прилично добро. Ајде бидете сигурни дека ова всушност компајлира. Направи бинарни дрво, и ох, имаме некои работи се случува тука. 

Имаме имплицитна изјава на функцијата изгради јазол. Повторно, со овие компајлери, ние ќе треба да почнат на врвот. Она што мора да кажам е дека јас сум повикувајќи се изгради јазол пред јас сум всушност го прогласи. Да се ​​вратиме на кодот навистина брзо. Скролувајте надолу, и секако, мојата вметнете функција е прогласена над јазол изгради функција, но јас се обидувам да го користите изгради јазол внатрешноста на внесување. Одам да одат во и копија - и потоа ставете јазол изгради функција пат до тука на врвот. На тој начин, се надевам дека ќе работат. Да даде ова уште одат. Сега сето тоа компајлира. Сите се добри. 

Но, во овој момент, не сме всушност се нарекува нашата вметнете функција. Ние само знам дека подготвува, па ајде да одиме и да стави некои повици внатре Да го стори тоа во нашиот главен функција. Тука, ние коментира надвор 5, 8 и 2, и тогаш ние не ги жица горе долу тука. Ајде да направи некои повици за да вметнете, и ајде да ги користите ист вид на работи кои што се користат кога ние ги направивме овие printf повици за да бидете сигурни дека сè не се вметнати правилно. Одам да копирате и залепите, и наместо содржи ние ќе го стори внесување. И наместо 6, 10 и 1, ние ќе треба да се користи 5, 8, и 2. Ова се надевам дека треба вметнете 5, 8 и 2 во дрво. Компајлирате. Сите се добри. Сега ние всушност ќе се кандидира нашата програма. 

Сè што враќа false. Значи, 5, 8 и 2 не оди, и тоа изгледа како Содржи не ги најде било. Што се случува? Ајде да одзумирате. Првиот проблем беше тоа што вметнете чинеше да се врати лажни, и тоа изгледа како тоа е затоа што ни го остава во враќање лажни повик, и никогаш не сме всушност се врати вистина. Ние може да се постави дека до. Вториот проблем е, сега, дури и ако тоа го правиме - освен тоа, да престанам ова, кандидира направи повторно, го состави, потоа изврши тоа - можеме да видиме дека нешто друго се случило овде. На 5, 8 и 2 никогаш не биле уште се наоѓаат во дрво. Значи, она што се случува? 

Ајде да ги погледнеме во овој во кодот. Ајде да видиме дали можеме да дознаам ова. Започнуваме со родителот не е нула. Ние во собата на тековната покажувачот еднаква на коренот покажувач, и ние ќе работиме на нашите патот надолу низ дрвото. Ако тековната јазол не е нула, тогаш знаеме дека ние може да се движи надолу малку. Ние во собата нашата матична покажувачот да биде еднаков на тековната покажувач, проверено на вредноста - ако вредности се исти ние се врати лажни. Ако вредностите се помалку ќе се пресели на правото; инаку, ќе се пресели кон лево. Тогаш се изградат еден јазол. Ќе зумирате малку. И тука, ние ќе се обидеме да жица до вредности да бидат исти. Што се случува? Ајде да видиме дали можеби Valgrind може да ни даде совет. 

Ми се допаѓа да го користите Valgrind само затоа Valgrind навистина брзо бега и ви кажува дали има било какви меморија грешки. Кога трчаме Valgrind на кодот, како што можете да видите во право here--Valgrind./binary_tree--and притиснете ентер. Ќе видите дека ние не се имате било какви меморија грешка, така што изгледа како и сè е во ред досега. Ние немаме некои меморија протекување, кои знаеме, затоа што ние не сме се случува да се ослободи било кој од нашите јазли. Ајде пробајте да GDB да се види она што всушност се случува. Ние ќе направиме се gdb. / Binary_tree. Тоа стартува само парична казна. Да се ​​постави брејк за внесување. Ајде да се кандидира. Тоа изгледа како никогаш не сме всушност, наречен внесување. Тоа изгледа како проблем беше само дека кога ќе се смени овде во главниот - сите овие printf повици од содржи - Јас всушност никогаш не се промени овие да се јавите внесување. Сега ајде да пробвам. Ајде да ги собере. Сите изгледа добро таму. Сега ајде пробајте тоа, да видиме што се случува. Добро! Сè што изгледа прилично добро таму. 

Конечниот нешто да се размислува за е, дали има работ случаи на оваа вметнете? И излегува дека, добро, еден раб случај тоа е секогаш интересно да се размислува за е, она што се случува ако вашиот дрво е празна и ти се јавам овој вметнете функција? Дали тоа ќе функционира? Па, ајде да пробвам. - Binary_tree в. - Начинот на кој ние се случува да се тестираат ова, ние ќе одиме надолу кон нашата главна функција, и наместо жици овие јазли се допаѓа ова, ние сме само ќе да коментира надвор целата работа, и наместо жици до јазли себе, можеме да всушност само се оди напред и да го избришете сето ова. Ние ќе направи сè што е повик да го внесете. Значи, ајде да направиме - наместо 5, 8 и 2, ние ќе треба да вметнете 7, 3 и 9. И тогаш исто така ќе сакате да вметнете 6, како и. Зачувај. Откажам. Направете бинарно дрво. Се компајлира. Ние само може да се кандидира како е и да видиме што се случува, но тоа е, исто така, ќе биде навистина важно да бидете сигурни дека ние немаме меморија грешки, бидејќи ова е еден од нашите работ случаи кои ние знаат. 

Ајде да бидете сигурни дека тоа работи добро под Valgrind, што ќе правиме со само трчање Valgrind. / binary_tree. Изгледа ние навистина имаат една грешка од еден контекст - имаме оваа сегментација на вина. Што се случи? Valgrind всушност ни кажува каде е. Одзумирате малку. Тоа изгледа како тоа се случува во нашата вметнете функција, каде што имаме погрешна читање на големината 4 во вметнете, линија 60. Да се ​​вратиме и да видиме што се случува овде. Одзумирате навистина брзо. Сакам да бидете сигурни дека тоа не оди до работ на екранот за да можеме да види сè. Повлечете дека во малку. Добро. Скролувајте надолу, и проблемот е во право тука. Што се случува ако се фаќате и нашите сегашни јазол е веќе нула, нашата матична јазол е нула, па ако гледаме нагоре во самиот врв, токму тука - ако ова никогаш не додека јамка всушност извршува бидејќи нашата сегашна вредност е нула - нашиот корен е null така мом е нула - тогаш никогаш нашата матична добива собата да мом или да валидна вредност, така, родител, исто така, ќе биде нула. Ние треба да се запамети да се провери за што од страна на време ние се фаќате тука, и ние започнуваме пристап вредноста на родителите. Значи, она што се случува? Па, ако родителот е нула - ако (родител == NULL) - тогаш знаеме дека не смее да постои нешто во дрво. Ние мора да се обидува да го вметнете во коренот. Ние можеме да го направи тоа само со поставување на коренот еднаква на нов јазол. Потоа во овој момент, ние всушност не сакаат да одат низ овие други работи. Наместо тоа, токму тука, можеме да направиме ниту една друго-ако-друго, или би можеле да се комбинираат што се тука во друг, но тука ние само ќе користи друго и направете го тоа на тој начин. Сега, ние ќе треба да се тестира за да се осигураме дека нашите родител не е null пред тоа всушност се обидува да пристапите до своите ниви. Ова ќе ни помогне да се избегне сегментација грешка. Значи, ние се откажат, одзумирате, состави, работи. 

Нема грешки, но имаме уште еден куп на меморија протекување бидејќи ние не ослободи било кој од нашите јазли. Но, ако ние одиме таму и ќе погледнеме во нашите отпечатоците, можеме да видиме дека, добро, изгледа како сите наши инсерти се враќаат точно, што е добро. На инсерти се точни, а потоа соодветно Содржи повици се исто така точно. 

Добра работа! Изгледа ние сме успешно запишана внесување. Тоа е се што имаме за проблемот оваа недела Постави спецификација. Еден забавен предизвик да се размислува за тоа како вие всушност ќе одат во и слободни на сите јазли во ова дрво. Ние можеме да правиме така голем број на различни начини, но јас ќе го оставиме тоа на вас да експериментирате, и како забавен предизвик, обидете се и бидете сигурни дека можете да бидете сигурни дека овој извештај Valgrind враќа без грешки и без протекување. 

Среќно на Хафман оваа недела кодирање проблем во собата, и ќе се видиме следната недела! [CS50.TV]