[Powered by Google Translate] Раздел 7] [по-малко удобни] [Нейт Hardison] [Харвардския университет] [Това е CS50. [CS50.TV] 

Добре дошли в раздел 7. Благодарение на ураган Sandy, вместо като нормален раздел тази седмица, правим тази разходка през чрез секцията на въпроси. Аз ще бъда заедно с проблема Задайте 6 спецификация, и преминава през всички въпроси в Раздел раздел с въпроси. Ако има някакви въпроси, моля пускате тези CS50 Обсъждане. 

Добре. Нека да започнем. Точно сега съм на стр. 3 от спецификацията за Проблем Set. Отиваме първо да започнем да говорим за двоични дървета тъй като тези, които имат много значение за проблем набор тази седмица - Дървото Huffman кодиране. Един от първите структури от данни, ние говорихме за CS50 масива. Не забравяйте, че масив е последователност от елементи - от същия вид - се съхраняват в непосредствена близост една до друга в паметта. Ако имам цяло число масив, който може да се направи използването на този кутии числа, числа стил - Да кажем, че имам 5 в първото поле, имам 7 във втория, тогава имам 8, 10 и 20 в окончателния кутия. Не забравяйте, че двамата наистина добри неща за този масив са, че имаме тази константа време до всеки отделен елемент  в масива, ако знаем своя индекс. Например, ако искате да вземете третият елемент в масива - индекс 2 нулева индексиране система - Аз буквално просто трябва да направиш просто математическо изчисление, хоп за тази позиция в масива, извадя 8, която се съхранява там, и аз съм добре да тръгвам. 

Един от най-лошите неща за този масив - че ние говорихме за когато обсъждахме свързани списъци - е, че ако искате да вмъкнете елемент в този масив, Аз ще трябва да направя известно прехвърляне около. Например, този масив тук сортират за сортирани във възходящ ред - 5, 7, след 8, 10, и след това 20 - но ако искате да вмъкнете номер 9 в този масив, Отивам да трябва да смени някои от елементите, за да направи място. Можем да направим това тук. Аз ще трябва да се движат 5, 7 и 8; създаване на пропастта, където мога да сложа 9, и след това на 10 и 20 могат да отидат в правото на девет. Това е вид болка, защото в най-лошия случай - когато сме се налага да вмъкнете в началото или в края на на масива, в зависимост от това как ще променят - бихме могли в крайна сметка се налага да смени всички елементи , че ние сме в момента съхраняват в масива. 

Така че, това, което е начин около това? Начин около това е да отидете на свързан списък метод, при който - вместо за съхраняване на елементи 5, 7, 8, 10, и 20 всички един до друг в паметта - вместо това пък бе да ги съхранявате вид, където искахме да ги съхранявате в тези свързан списък възли, които съм изтегляне тук, на Ad Hoc. И след това те да са свързани заедно с използване на тези следващите насоки. Мога да имам показалеца от 5 до 7, указател от 7 до 8, указател от 8 до 10, и накрая, показалеца от 10 до 20, и след това с нулев указател на 20, което показва, че не е останало нищо. Компромисът, които имаме тук е, че сега, ако искате да вмъкнете номер 9 в сортират нашия списък, всичко, което трябва да направите е да създадете нов възел с 9, тел до точка на подходящо място, и след това ре-тел 8 сочи надолу до 9. Това е доста бързо, ако знаем къде точно искаме да вмъкнем 9. Но компромис в замяна на това е, че ние сега сме загубили постоянно времето за достъп за всеки отделен елемент в структурата на данни. Например, ако искате да намерите Четвъртият елемент в тази свързан списък, Аз ще трябва да започне в самото начало на списъка и да работят по моя начин чрез преброяване възел по възел, докато не намеря четвъртата. 

За да получите по-добра производителност в сравнение с достъп свързан списък - но също така да запазят някои от ползите, които сме имали от гледна точка на вмъкване време от свързан списък - двоично дърво ще трябва да използвате малко повече памет. По-специално, вместо просто да има един показалеца в двоичен възел дърво - като свързан списък възел - отиваме да добавите втори показалеца на двоичен възел дърво. Вместо просто да има един указател към следващия елемент, отиваме да имат показалеца на лявата детето и право дете. 

Да направи снимка, за да видите какво всъщност прилича. Отново, аз отивам да се използват тези кутии и стрели. Двоичен възел дърво ще започнем с едно просто кутия. Ще има място за стойността, и след това тя също ще има място за лявата детето и правото на детето. Отивам да ги обозначават тук. Отиваме в лявата дете, а след това отиваме да имат право дете. Има много различни начини за това. Понякога за простор и удобство, Всъщност аз ще го изготвя, както аз правя тук на дъното къде отивам да имат стойност в горната част, а след това и право дете на долния десен ъгъл, и лявата дете на долния ляв. Ако се върнем към това горната диаграма, имаме стойността на самия връх, тогава имаме дете показалеца на лявата, а след това ние имаме право дете показалеца. 

В спецификацията Проблем Set, говорим за съставяне възел, който е на стойност 7, а след това и показалеца на лявата дете, което е нулев, и право дете показалеца, че е празно. Могат да напишат NULL капитал в пространството за както отляво, детето и правото на дете, или можем да направим тази диагонална черта през всяка от кутиите, за да покаже, че това е нищожна. Отивам да направя това само защото е по-лесно. Това, което виждате тук, са два начина на диаграми един много прост възел двоично дърво където имаме стойност 7 и нулеви указатели за деца. 

Във втората част на нашите спецификации говори за това как със свързани списъци - Не забравяйте, че ние само трябваше да се държи на първия елемент в списък да си спомня целия списък - и също така, с двоично дърво, ние само трябва да се държат за показалеца на дървото за да се запази контрол върху цялата структура на данните. Този специален елемент на дървото се нарича коренът на дървото. Например, ако този възел - този възел, съдържащ стойност 7 с нулеви лявото и дясното дете указатели - са единствената ценност в нашето дърво, то това ще бъде нашия възел корен. Това е самото начало на нашето дърво. Можем да видим това малко по-ясно, след като започнете да добавяте повече възли в нашия дърво. Остави ме да извадя нова страница. 

Сега отиваме да се направи дърво, което има 7 в основата, и 3 вътрешната страна на лявата дете, и 9 вътрешността на правото дете. Отново, това е доста проста. Имаме 7, изготвя възел за 3 възел за 9, и аз ще поставите показалеца на лявата дете от 7 до точка възел, съдържащ 3, и десния дете показалеца на възела, съдържащ 7 възела, съдържаща девет. Сега, след три и девет нямат никакви деца, отиваме да зададете всички указатели на детето им да бъде нула. Тук основата на нашето дърво съответства на възел, съдържащ броя 7. Можете да видите, че ако всичко, което имаме е указател, че коренът тогава ще можем да минеш през нашето дърво и достъп до двете деца възли - 3 и 9. Не е необходимо да се поддържа указатели към всеки един възел на дървото. Добре. Сега отиваме да добавите друг възел за тази схема. Отиваме да добавите възел, съдържащ 6, и отиваме да добавите това право дете на възела, съдържаща 3. За да направите това, аз отивам да изтриете, че нулев указател в 3-възел и да го преведете да сочи към възел, съдържащ 6. Добре. 

В този момент, нека да отидем малко на терминологията. За да започнете, причината, поради която това се нарича двоично дърво по-специално е, че тя има две деца указатели. Има и други видове дървета, които имат повече деца указатели. По-специално, "опита" в Проблем Set 5. Ще забележите, че в този опит, има 27 различни указатели към различните деца - по един за всяка от 26-те букви на английската азбука, и след това 27 за апостроф така, че е подобен на вида на дървото. Но тук, тъй като това е двоичен, ние само две детски указатели. 

В допълнение към този корен възел, който ние говорихме за ние също се хвърлят около този термин "дете". Какво означава това за един възел да бъде дете на друг възел? Това буквално означава, че едно дете възел е дете на друг възел ако това друго възел има един от своите деца указатели, да сочи към този възел. За да поставите това в по-конкретен план, ако 3 се посочва по един на детето указатели на 7, а след това 3 е дете на 7 г. Ако бяхме да разбера какво са деца на 7 - добре, ще видим, че 7 има указател към 3 и показалеца до 9, така 9 и 3 са деца на 7. Девет няма деца, защото детето указатели са нула, и 3 има само едно дете, 6. Шест няма деца, защото и двете на своите указатели са нула, което ние ще направим точно сега. 

Освен това, ние говорим за родителите на даден възел, и това е, както можете да очаквате, обратната страна на това дете описание. Всеки възел има само един родител - вместо две, както можете да очаквате с хората. Например, майка на три е 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, и след това три посочи надясно до 6, и 7 имали право дете, което беше 9. Добре. Какво е друг начин, по който би могъл да напише това дърво? Вместо да се налага 3 лявата дете на 7 ние също може да има 6 лявата дете на 7, и след това три лявата дете на 6. Това ще изглежда като това дърво точно тук, където имам 7, след шест, а след това 3 и 9 на правото. Ние също така не трябва да има 7, както коренът ни. Ние също може да има 6, тъй като нашата коренът. Какво би изглеждало това? Ако ще да се запази тази поръча имот, всичко ляво на 6 трябва да бъде по-малко, отколкото. Има само една възможност и това е 3. Но тогава, както и право дете на 6, имаме две възможности. Първо, ние може да има 7 и 9, или можем да го изготви, като аз съм на път да направя тук - където имаме 9 правото дете на 6, и след това 7 като лявата дете на 9. 

Сега, 7 и 6 не са единствените възможни стойности за корена. Ние също може да има 3 да бъде в основата. Какво се случва, ако 3 е в основата? Тук нещата стават малко по-интересно. Три не са изпитали някакви стойности, които са по-малко, отколкото, така че цялата лява страна на дървото е просто ще бъде нула. Не щеше да бъде нещо там. В дясно, бихме могли да изброят неща във възходящ ред. Ние може да има 3, след 6, 7, а след това 9. Или, бихме могли да направим три, а след това шест, а след това девет, след това 7. Или, бихме могли да направим 3, 7, 6, след това 9. Или, 3, 7 - всъщност не, ние не може да направи седем повече. Това е нашата едно нещо там. Ние можем да направим 9, и след това от 9 можем да направим 6 и 7. Или можем да направим три, а след това девет, а след това 7, и след това 6. 

Едно нещо е да привлека вниманието ви тук е , че тези дървета са малко странно изглеждащ. По-специално, ако се вгледаме в четири дървета от дясната страна - Ще ги обикаля, тук - тези дървета изглеждат почти точно като свързан списък. Всеки възел има само едно дете, и затова не е нужно на тази дървовидна структура, която виждаме, например,  в това самотно дърво тук в долния ляв. Тези дървета са всъщност се нарича изродена двоични дървета, и ние ще говорим за тях повече в бъдеще - особено, ако отидете да предприемат други курсове по компютърни науки. Тези дървета са изродени. Те не са много полезни, защото, наистина, тази структура се поддава  да се намери пъти, подобни на тази на свързан списък. Ние не се получи да се възползват от допълнителната памет - това допълнително показалеца - защото от нашата структура е лошо по този начин. Вместо да продължи и изтеглете двоичните дървета, които са 9 в основата, е крайният случай, че щяхме да имаме, вместо това, ние сме в този момент, ще поговорим малко за този план , които ние използваме, когато говорим за дървета, която се нарича височина. 

Височината на дървото е разстоянието от корена до най-далечната възел, или по-скоро броя на отсечките, които ще трябва да се направи, за да започне от корена и след това до края на най-далечен възел в дървото. Ако се вгледаме в някои от тези дървета, които сме привлечени тук, можем да видим, че ако вземем това дърво в горния ляв ъгъл и ние започваме в 3 тогава ние трябва да направим едно хопа, за да стигнем до 6, втората хопа, за да стигнем до 7, и 1/3 хопа, за да стигнем до 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, така че ние бихме се придвижите наляво. Ако стойността на шест е бил по-голям от 7, бихме вместо това преместен в дясно. Тъй като ние знаем, че се дължи на структурата на поръчаните двоично дърво - всички стойности по-малко от 7 ще се съхраняват в ляво от 7 няма нужда да се притеснява дори през дясната страна на дървото. След като ние се движат в ляво и сега сме на възела, съдържаща 3, можем да направим това отново същото сравнение, когато ние сравняваме 3 и 6. И ние откриваме, че докато 6 - стойността търсим - е по-голяма от 3, можем да отидем към дясната страна на възела, съдържаща 3. Не е лявата страна, така че биха могли да игнорират. Но ние знаем само това, защото ние търсим в самото дърво, и можем да видим, че дървото няма деца. 

То също е доста лесно да търсите шест в това дърво, ако ние сме си го прави като хората, но нека да следи този процес механично като компютър ще направя наистина да разберем алгоритъма. В този момент, ние сме вече на възел, който съдържа 6 и ние не търсим за стойност 6, така, наистина, ние открихме подходящия възел. Намерихме стойност 6 в нашето дърво, и ние можем да спрем нашето търсене. В този момент, в зависимост от това какво се случва, можем да кажем, да, ние сме намерили стойност 6, тя съществува в нашето дърво. Или, ако планирате да вмъкнете възел или направи нещо, можем да направим това в този момент. 

Нека да направим още няколко заявки само за да видя как работи това. Нека да погледнем какво се случва, ако бяхме да се опитаме и да потърсите на стойност 10. Ако трябва да гледам на стойност 10, ние ще почнем към корена. Ние ще видите, че 10 е по-голямо от 7, така че ние ще се премести надясно. , Че ще стигнем до 9 и сравни 9 до 10 и да видим, че девет е наистина по-малко от 10. Така че отново ще се опита да се движи надясно. Но в този момент, ние ще забележите, че ние сме на нула възел. Там няма нищо. Няма нищо, при които 10 трябва да бъде. Това е мястото, където можем да докладва недостатъчност - че наистина няма 10 в дървото. И накрая, нека да минем през случаите, когато ние се опитваме да погледнете една в дървото. Това е подобно на това, което се случва, ако погледнем 10, с изключение вместо да ходят в дясно, ние ще тръгнем наляво. Започваме в 7 и се види, че 1 е по-малко от 7, така че ние се движат наляво. Качваме се на 3 и се види, че 1 е по-малко от три, така че отново ние се опитваме да се движат наляво. В този момент ние имаме нулева възел, така че отново можем да докладва недостатъчност. 

Ако искате да научите повече за двоични дървета, има цял куп забавни малки проблеми, които можете да направите с тях. Предлагам практикуване на изготвянето на тези диаграми една по една и след през всички на различните стъпки, защото това ще дойде в супер-удобен не само, когато правиш набор Huffman кодиране проблем но също така и в бъдещи курсове - просто се научите как да се направи на тези структури от данни и мисля, че през проблемите с писалка и хартия, или в този случай, IPAD и стилус. 

В този момент обаче, ние ще продължим да се направят някои кодиране практика и всъщност играят с тези бинарни дървета и ще видите. Отивам да се върнете към моя компютър. За тази част на раздела, вместо да използвате CS50 Run или CS50 пространства, Отивам да използвате уреда. 

След като заедно със спецификацията Проблем Set Виждам, че аз трябва да отворите уреда, преминете към моята папка Dropbox, създайте папка, наречена раздел 7, и след това да създадете файл, наречен binary_tree.c. Ето ни. Имам уреда вече е отворен. Аз ще дръпне един терминал. Отивам да отидете в папката Dropbox директория, наречена section7 и да видите, че е напълно празна. Сега аз ще да се отворят binary_tree.c. Добре. Ето ни - празен файл. 

Нека се върнем към спецификацията. Спецификацията иска да създаде ново определение на типа за двоичен възел дърво, съдържащ INT стойности - точно като ценности, които извади в нашата диаграми преди. Отиваме да използвате тази стереотипния typedef, че ние сме направили тук че трябва да се признае от Проблем Set 5 - ако си направил хеш таблица на завладяването на правопис програма. Вие също трябва да го признае от раздел миналата седмица където говорихме за свързани списъци. Имаме тази typedef на структурата на възел, и сме създали тази структура възел името на структурата възел предварително така че тогава ще можем да се отнасят към него, тъй като ще искат да имат указатели възел структура като част от нашата структура, но ние сме обграден това - или по-скоро, ограден това - в typedef , така че по-късно в кода, може да се отнася за тази структура просто като възел вместо структура възел. 

Това ще бъде много подобен на самостоятелно свързан списък определение, че видяхме миналата седмица. За да направите това, нека просто да започнете с писането на стереотипния. Ние знаем, че трябва да имаме целочислена стойност, така че ние ще поставим в INT стойност, а след това вместо да се налага само един указател към следващия елемент - както направихме с поединично свързани списъци - отиваме да има леви и десни указатели на детето. Това е доста проста - структура възел * левия дете; и структура възел * право дете. Cool. Това изглежда доста добро начало. Нека се върнем към спецификацията. 

Сега ние трябва да обяви глобална променлива * възел за корените на едно дърво. Започваш да се направи тази глобална точно както ние направихме първото показалеца в свързани нашия списък също толкова глобален. Това е така, че във функциите, които пишем ние не трябва да минава около този корен - въпреки че ние ще видите, че ако искаш да напиша тези функции рекурсивно, тя може да бъде по-добре дори да не го Заобикаля като глобален на първо място и вместо него се инициализира място в основната си функция. Но ние ще го направим в световен мащаб да се започне. Отново, ние ще дадем няколко места, и аз отивам да обяви възел * корен. Просто за да се уверите, че не оставите това неинициализирана, аз отивам да го определя като равна на нула. Сега, в основна функция - които ние ще напиша много бързо точно тук - INT главната (INT argc, Const знак * argv []) - и аз отивам да започне да обявява argv ми масив като строителство, така че аз знам че тези доводи са аргументи, които вероятно не искате да модифицирате. Ако искам да ги променяте, може би трябва да се направи копия от тях. Ще видите много код. Това е глоба или иначе. Това е добре да го оставите като пропуска на строителство, ако искате. Аз обикновено го сложи в просто така, че си напомням  , че вероятно не искате да промените тези аргументи. 

Както винаги, аз отивам да се включи тази връщането на 0 линия в края на основната. Ето, аз ще се инициализира моя възел корен. Както стоят нещата сега, имам указател, който присвоява така че се посочи нищо. За да започне изграждането на възела, Първо трябва да заделя памет за него. Отивам да направите това, като памет на купчината с помощта на изчистване. Отивам да зададете корен равен резултат от изчистване, и аз отивам да използвате sizeof оператора да изчисли размера на възел. Причината, поради която аз използвам sizeof възел, за разлика от, да речем, прави нещо подобно - изчистване (4 + 4 +4) или изчистване 12 - е, защото искам да ми код да бъде възможно най-съвместими. Искам да бъда в състояние да вземе в файл, да го компилирате на уреда, и след това да го събират на моя 64-битова Mac - или за напълно различна архитектура - и аз искам всичко това да работят по същия. 

Ако правя предположения за размера на променливи - размер на вътр или размера на показалеца - тогава аз също се правят предположения за вида на архитектури , на която моя код може успешно да съставят, когато тичам. Винаги използвайте sizeof, за разлика от ръчно сумиране на структурата на полета. Другата причина е, че може да има и подложка че компилаторът поставя в структурата. Дори само сумиране на отделните полета, не е нещо, което обикновено искате да направите, така, изтрийте тази линия. Сега, наистина да се инициализира този възел корен, Аз ще трябва да се включи в стойности за всяка от различните му области. Например, за стойност Знам, че искате да се инициализира 7, и за сега отивам да настроите ляво детето да бъде нула и правото на детето да бъде нула. Чудесно! Ние сме направили тази част от спецификациите. 

Спецификацията в долната част на страницата 3 ме пита за създаване на още три възли съдържа 3, съдържащ 6, и с 9 - и след това да ги свържем, така че тя изглежда точно като нашето дърво диаграма , че ние говорим за това по-рано. Да го направим доста бързо тук. Ще видите много бързо, че аз отивам да започнете да пишете куп от дублиране на кода. Отивам да се създаде възел *, и аз отивам да го три. Отивам да го зададете равен на изчистване (sizeof (възел)). Отивам да се определят три стойност = 3. Три -> left_child = NULL, три -> дясно _child = NULL;, както добре. Това изглежда доста подобен за инициализиране на корен, и това е точно това, което Аз ще трябва да направя, ако започне инициализиране на 6 и 9, както и. Аз ще направя това наистина бързо тук - всъщност, аз отивам да направя малко копиране и поставяне, и се уверете, че аз - добре.  Сега, аз имам да го копира и мога да отида напред и да зададете тази равно на 6. Можете да видите, че това отнема известно време и не е супер-ефективна. Само малко, ние ще напиша функция, която ще направи това за нас. Искам да се замени с 9, сменете с 6. 

Сега имаме всички наши възли създаден и се инициализира. Имаме корена ни, равен на 7, или съдържащи стойност 7, нашата възел съдържа 3, възел съдържащ 6, и нашата възел с 9. В този момент, всичко, което трябва да направим, е да тел всичко. Причината, поради която инициализира всички указатели към нула е точно, така че съм сигурен, че Аз не разполагат с никакви неинициализирани указатели там случайно. И също така, тъй като, в този момент, аз само трябва да свържете възлите един към друг - за тези, които те действително свързани с, че не е нужно да отидете и да сигурни, че всички нули на подходящите места. 

Започвайки в основата, знам, че лявата детето корен е 3. Знам, че правото на детето корен е 9. След това, единственото друго дете, което ми е останало да се притеснявате за е право дете на 3, което е с 6. В този момент, всичко това изглежда доста добре. Ще изтриете някои от тези линии. Сега всичко изглежда доста добре. Нека се върнем към нашата спецификация и да видим това, което ние трябва да направим следващата. 

В този момент, ние трябва да напишете функция, наречена "съдържа" с прототип на "BOOL съдържа (INT стойност). И това съдържа функция ще се върне вярно  ако дървото посочи от нашата глобална променлива на корен  съдържа стойността премина в функцията и лъжа в противен случай. Да вървим напред и да направим. Това ще бъде точно като справка, че ние направихме от страна на IPAD само преди малко. Да я увеличите малко и превъртете нагоре. Отиваме да се сложи тази функция точно над нашата основна функция така че не е нужно да правите всякакъв вид създаване на прототипи. Така че, булев съдържа (INT стойност). Точно така. Има нашата стереотипния декларация. Просто за да се уверите, че това ще се компилира, Отивам да вървим напред и просто го определя като равна на връщане фалшиви. В момента тази функция не ще направи нищо и винаги съобщават, че стойност, която търсим, не е в дървото. 

В този момент, това е може би добра идея - тъй като ние сме написал куп код и ние дори не се опитахме го тества още за да се уверите, че всичко това се съставя. Има няколко неща, които трябва да направите, за да се уверите, че това действително ще съставят. Първо, да видим дали ние сме били използване на каквито и да било функции в библиотеки, които ние все още не са включени. Функциите, които сте използвали досега са изчистване, и след това сме също така използването на този тип - този нестандартен тип, наречен "bool' която е включена в стандартната булев заглавен файл. Ние определено искаме да включим стандартен bool.h за булев тип, и ние също искаме да # включват стандартен lib.h за стандартните библиотеки които включват изчистване, и безплатно, и всичко това. Така че, отдалечаване, отиваме да се откажат. Нека се опитаме и се уверете, че това действително е компилация. Ние виждаме, че го прави, така че ние сме на прав път. 

Нека отворим binary_tree.c отново. Компилира. Нека да отидем и да сме сигурни, че вмъкнете някои разговори в нашия съдържа функция - само за да се уверите, че всичко това е много добре. Например, когато ние направихме някои заявки в нашето дърво по-рано, ние се опитахме да погледнем стойностите, 6, 10 и 1, и ние знаехме, че 6 е в дървото, 10 не е в дървото, а една не е в дървото. Нека използваме тези примерни разговори като начин да разбера дали или не ни съдържа функция работи. За да се направи това, аз отивам да се използва ФОРМАТ функция, и ние ще изведе резултата на поканата да съдържа. Отивам да се сложи в низ "съдържа (% г) = защото  отиваме да включите в стойността, която отива да търси, =% S \ N "и да използва това като наш формат низ. Ние просто ще видим - буквално отпечатате на екрана - това, което изглежда като извикване на функция. Това всъщност не е извикването на функцията.  Това е просто низ проектиран да изглежда като извикване на функция. 

Сега отиваме да се включите в стойностите. Ние ще се опитаме съдържа по 6, и след това, което ще направим тук, е да използвате този оператор третичния. Нека да видим - съдържа 6 - така, сега съм съдържат 6 и ако съдържа 6 е вярно, низ, който отива да изпрати във формат характер на% S ще бъде низ "истинска". Да сменя малко. В противен случай, ние искаме да прати стринга "фалшиви", ако съдържа шест връща фалшиви. Това е малко шантаво изглеждащи, но Предполагам, че може и да илюстрират третичния оператор прилича тъй като не съм го виждал за известно време. Това ще бъде хубаво, удобен начин да разбера, ако ни съдържа функция работи. Отивам да превъртате назад, наляво, и аз отивам да копирате и поставите този ред на няколко пъти. Той се е променил някои от тези стойности около така че това ще да бъде 1, и това ще бъде 10. 

В този момент ние имаме хубава функция съдържа. Имаме някои тестове и ще видим Ако всичко това работи. На този етап съм писал още малко код. Време е да излезете и да се уверите, че всичко все още съставя. Излезете, а сега нека се опитаме двоично дърво отново. Е, изглежда, че имаме грешка, и ние имаме това изрично обявяване на библиотека функция ФОРМАТ. Изглежда, че трябва да отидем и # включват standardio.h. И с това, всичко трябва да се компилира. Ние всички сме добре. Сега нека се опитаме работи двоично дърво и да видим какво ще се случи. Ние сме тук,. / Binary_tree, и ние виждаме, че, както очаквахме - защото ние не са приложили съдържа още или по-скоро, ние току-що пуснати в замяна фалшива - ние виждаме, че това е просто връщане фалшиви за всички от тях, така че всички те работят за по-голямата си част доста добре. 

Нека се върнем и реалното изпълнение съдържа в този момент. Отивам да превъртите надолу, увеличавате, и - помнете, алгоритъм, който използва, е, че ние започнахме в основата възел и след това на всеки възел, който се сблъскваме, правим сравнение, и въз основа на това сравнение да се премести в лявата дете или надясно дете. Това ще изглежда много подобно на двоичен код за търсене, която писахме по-рано в срока. Когато започнете, ние знаем, че искаме да се държат за текущия възел че ние търсим и текущия възел ще се инициализира да е коренът. И сега, ние ще продължим да става чрез дървото, и не забравяйте, че нашата спиране състояние -  , когато ние действително работи чрез примера на ръка - беше, когато открихме нулева възел, когато не погледна към нула дете, , а по-скоро, когато ние действително се премества в един възел в дървото и е установено, че ние сме на нула възел. Отиваме, за да превъртите до тек не е равна на нула. И какво ще правим? Отиваме да проверите дали (тек -> стойност == стойност), тогава ние знаем, че всъщност сме намерили възел, който ние търсим. Така че тук, можем да се върнем вярно. В противен случай, ние искаме да се види дали стойността е по-малка от стойността. Ако стойността на текущия възел е по-малко от стойността търсим, отиваме да се движи надясно. Така че, тек = тек -> right_child; и по друг начин, ние отиваме да се движат наляво. тек = тек -> left_child; Доста прост. 

Можете да признаят линия, която изглежда много подобно на това от двоично търсене по-рано в срока, освен тогава ние се занимавахме с нисък, среден и високо. Ето, ние просто трябва да погледнете по текущата стойност, така че е хубаво и лесно. Нека се уверим, че този код работи. Първо, уверете се, че тя компилира. Изглежда, че го прави. Нека се опитаме да я пуснете. И наистина, тя се отпечатва всичко, което сме очаквали. Тя намира 6 в дървото, не намери 10, защото 10 не е в дървото, и не намери една или защото 1 също не е в дървото. Готини неща. 

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

Да напишем функция, които действително ще изгради възел за нас и да го върне. Отивам да го наричат ​​build_node. Отивам да се изгради възел с определена стойност. Zoom тук. Първото нещо, което ще направя е действително да се създаде пространство за възел на куп. Така че, възел * N = изчистване (sizeof (възел)); N -> стойност = стойност; и след това тук, аз съм просто ще инициализира всички полета, за да бъдат подходящи стойности. И в самия край, ще се върнем нашата възел. Добре. Едно нещо е да се отбележи, че тази функция тук ще се върне указател към паметта, която е била купчина разпределени. Това, което е хубаво за това е, че този възел - ние трябва да го декларира на куп, защото ако го обявява в стека ние не ще бъде в състояние да го направи в тази функция като тази. Този спомен ще излязат от обхвата и ще бъде недействителна, ако ние се опитахме да получите достъп до него по-късно. Тъй като ние се обявяват куп заделената памет, ние ще трябва да се грижи за по-късно го освобождава за нашата програма да не изтече никаква памет. Ние сме били плоскодънни лодки, че за всичко останало в кода само за улеснение на времето, но ако някога напиша функция, която изглежда по този начин където имаш - някои я наричат ​​изчистване или презаделяне вътре - искате да се уверите, че сте поставили някакъв коментар тук, който казва, Хей, знаеш ли, връща купчина разпределени възел инициализира с издържал в стойност. И след това искате да се уверите, че сте поставили някаква бележка, която казва повикващия трябва да освободи връща паметта. По този начин, ако някой някога отива и използва тази функция, те знаят, че каквото и да се върна от тази функция в някакъв момент ще трябва да бъдат освободени. 

Ако приемем, че всичко е наред и е добре тук, можем да слизат в нашия код и да замени всички тези редове тук с разговори към нашата възел изграждане функция. Нека го направим много бързо. От една страна, че ние няма да замени тази част тук в дъното, където ние всъщност тел възли, за да се отбележи един към друг, защото това не можем да направим в нашата функция. Но, нека да го направим корен = 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? За да запазите всичко в съответния ред, ние знаем, че право дете на три е шест. Така че, ако отиваме да добавите 5, 5 също принадлежи в дясната страна на дървото, от които 3 е корен, така че 5 принадлежи като лявата дете на 6. Ние можем да направим това, като казва, шест -> left_child = пет; и след това на 8 принадлежи на лявата дете на 9, така че девет -> left_child = осем; и след това 2 е лявата дете на 3, така че можем да направим това тук - ти -> left_child = два. Ако не сте съвсем следват заедно с това, аз предлагам да го извади себе си. 

Добре. Да спасим това. Да излезем и се уверете, че тя компилира, и след това можем да добавим в нашите съдържа разговори. Изглежда, че всичко се компилира. Нека да отидем и да добавите в някои съдържа разговори. Отново, аз отивам да се направи малко на копиране и поставяне. Сега нека да търсите за 5, 8 и 2. Добре. Нека се уверим, че всичко това изглежда добре все още. Чудесно! Запазване и напусна. Сега нека направим, съставяне и сега да работи. От резултатите, изглежда, че всичко работи само хубаво и добре. Чудесно! Така че сега ние имаме нашите съдържа функция писмено. Нека продължим и да започнем да работим за това как да вмъкнете възли в дървото тъй като, както го правим сега, нещата не са много красиви. 

Ако се върнем на спецификацията, иска от нас да напише функция, наречена поставете отново, връщане на булев за това дали или не ние в действителност може да поставите възел в дървото - и след това стойността да вмъкнете в дървото е посочен като единственият аргумент в нашия вложка функция. Ние ще се върне вярно, ако наистина бихме могли да поставите на възела, съдържащ стойност на дървото, което означава, че ние, има достатъчно памет, и след това две, този възел не вече съществуват в дървото, тъй като - забравяйте, че ние не ще да има дублиращи се стойности на дървото, само за да направи нещата по-лесни. Добре. Обратно към кода. Отворете го. Увеличи малко, след което превъртете надолу. Нека сложим функция за вмъкване точно над съдържа. Отново, това ще се нарича булев вложка (INT стойност). Дай го малко повече пространство, а след това, по подразбиране, нека да поставим в замяна фалшиво в самия край. Сега надолу към дъното, да вървим напред и вместо ръчно изграждане на възлите в основната себе си и ги окабеляване да посоча един към друг, като правим, ние ще разчитаме на нашия вложка функция, за да го направя. Ние няма да разчита на ни вложка функция, за да изгради цялото дърво от нулата, просто все още, а по-скоро ще се отърве от тези линии - Ще коментират тези редове - , които изграждат възли 5, 8 и 2. И вместо това, ние ще вмъкнете повиквания към нашия вложка функция за да сте сигурни, че това наистина работи. Ето ни. 

Сега сме коментирали тези линии. Ние имаме само 7, 3, 9 и 6 в дърво в този момент. За да сте сигурни, че всичко това е работа, можем да я увеличите, направим дърво двоичен, го изпълним, и ние можем да видим, че съдържа сега ни казват, че ние сме напълно прав - 5, 8 и 2, вече не са в дървото. Върнете се в кода, и как ще да вмъкнете? Не забравяйте, това, което направихме, когато бяхме всъщност поставяте 5, 8 и 2 по-рано. Играхме тази игра Plinko там, откъдето започнахме в основата, слезе от дървото един по един по един докато намерим подходящ разликата, и след това сме вързани на възел на подходящо място. Отиваме да направят същото нещо. Това е основно като писане на код, който ние използвахме съдържа функция да намерите място, където възел трябва да бъде, и след това просто щяхме да вмъкнете възела точно там. Нека започнем от това. 

Така че ние имаме възел * тек = корен, ние просто ще следват съдържа код докато не открием, че не работят за нас. Отиваме да мине през дървото, докато текущия елемент не е празен, и ако намерим стойност, която тек е равна на стойността, която ние се опитваме да вмъкнете добре, това е един от случаите, в които не бихме могли вмъкване на възел в дървото, защото това означава, че ние имаме дубликат стойност. Тук ние всъщност ще се върне фалшиви. Сега е друго, ако стойността на тек, е по-малко от стойността, сега знаем, че се движим в дясно  , тъй като стойността принадлежи в дясната половина на текущата дърво. В противен случай, отиваме да се движат наляво. Това е основното ни съдържа функционира там. 

В този момент, след като сме завършили тази линия, докато тек показалеца ни ще бъдат насочени към нула ако функцията все още не е върнат. Ние сме като тек на мястото, където искате да вмъкнете нов възел. Това, което остава да се направи, е действително да се изгради нов възел, което можем да направим доста лесно. Ние можем да използваме нашите супер-удобен строителство функция възел, и нещо, което не сме направили по-рано - ние просто се приема за даденост, но сега ще направя, за да съм сигурен - ще тестваме за да се уверите, че всъщност е стойността, върната от нов възел не е нула, защото ние не искаме да започне достъп до тази памет, ако тя е нула. Ние можем да се тестват, за да се уверите, че нов възел не е равна на нула. Или вместо да се види, ако действително е нула, и ако тя е нула, тогава ние може просто връщане фалшиви рано. 

В този момент, ние трябва да свържете нов възел в своето подходящо място в дървото. Ако погледнем назад в основния и къде сме всъщност са кабелите в стойностите преди, ние виждаме, че начина, по който са го правили, когато искахме да се сложи 3 в дърво е достъп до лявата дете на корен. Когато ние поставяме 9 в дървото, имахме достъп до точните дете на корена. Ние трябваше да има указател на родителя, за да се сложи нова стойност в дървото. Превъртате назад да вмъкнете, че не става доста работа тук защото ние не разполагат с показалеца майка. Това, което искаме да бъдем в състояние да направи в този момент, е, проверите стойността майка и виж - добре, Боже, ако стойността на компанията-майка е по-малко от текущата стойност, правото на детето на родителите трябва да бъде нов възел; в противен случай, наляво дете на родител трябва да бъде новият възел. Но ние не трябва този указател майка доста още. 

За да го получи, ние всъщност ще трябва да го следите, тъй като ние преминаваме през дървото и да намерят подходящо място в нашата линия по-горе. Ние можем да направим това, като превъртате назад до върха на нашия вложка функция и проследяване на друга показалеца променлива, наречена майка. Отиваме да го определя като равна на нула първоначално, и след това всеки път, когато мине през дървото, отиваме да настроите показалеца на майка да съответства на сегашната показалеца. Задайте майка равна на тек. По този начин, всеки път, когато минават през отиваме да се гарантира, че тъй като сегашното показалеца получава увеличава показалеца майка следва - само една степен по-висока от текущата показалеца на дървото. Всичко това изглежда доста добре. 

Мисля, че единственото нещо, което ще искате да регулирате това е изграждане на възел връщане на нула. С цел да се изгради възел всъщност успешно се върне нула, ние ще трябва да се промени този код, защото тук, никога не сме тествани, за да се уверите, че изчистване върна валиден показалеца. Така че, ако (N = NULL), а след това - ако изчистване върна валиден показалеца, тогава ние ще го инициализира; в противен случай, ние просто ще се върнат и че ще приключи до връщане на нула за нас. Сега всичко изглежда доста добре. Нека се уверим, че това всъщност съставя. Направи двоично дърво, и о, ние имаме някои неща тук. 

Имаме имплицитно декларация на функцията изгради възел. Отново с тези компилатори, ние отиваме да започне най-отгоре. Какво трябва да означава, че Обаждам се изгради възел, преди да съм всъщност тя обяви. Нека се върнем към кода наистина бързо. Превъртете надолу, и разбира се, ми посочете функция е обявена над изграждане на възел функция, но аз се опитвам да се използва за изграждане на възел вътрешността на вложка. Аз ще отида и копие и след това поставете изграждане функция възел начин тук на върха. По този начин, да се надяваме, че ще работи. Нека дадем още веднъж. Сега всичко това се компилира. Всичко е добре. 

Но в този момент, ние не са всъщност се нарича ни вложка функция. Ние просто знам, че тя компилира, така че нека влезем вътре и сложи няколко обаждания. Да го направим в нашата основна функция. Ето, ние коментира 5, 8 и 2, и тогава ние не ги тел тук. Нека направим някои разговори да вмъкнете, и нека да използват един и същ вид неща, които ние използвахме когато ние направихме тези ФОРМАТ разговори, за да се уверите, че всичко се получи поставена правилно. Отивам да копирате и поставите, и вместо да съдържа ние ще направим вложка. И вместо на 6, 10 и 1, отива да се използва 5, 8 и 2. Това трябва да се надяваме вмъкнете 5, 8 и 2 на дървото. Съставете. Всичко е добре. Сега ние действително ще работи нашата програма. 

Всичко се връща фалшиви. Така че, 5, 8 и 2 не си отиват, и тя изглежда като съдържа не ги намерите. Какво става? Да намалите. Първият проблем е, че се добавя сякаш връщане фалшиви, и тя изглежда като това е така, защото ние напуснахме в нашето завръщане фалшиво повикване, и всъщност ние никога не връща вярно. Ние можем да го измисли. Вторият проблем е, че сега дори и ако ние не направим - освен това, се откажат от това, тичам направи отново, да го компилирате, след което го стартирате - ние виждаме, че нещо друго се е случило тук. 5, 8 и 2 все още никога не са били намерени на дървото. Така че, какво става? 

Нека да разгледаме това в кода. Нека видим дали ще мога да го разбера това. Започваме с майка не е нищожна. Текущата показалеца, равен на корен показалеца, и ние ще работим пътя ни през дървото. Ако текущият възел не е нула, а след това ние знаем, че можем да се движим малко. Ние си поставихме нашите майки показалеца, за да бъде равна на показалеца, провери стойност, ако стойностите са същите, ние се върнахме фалшива. Ако стойностите са по-малко, ние се премества надясно; В противен случай, ние се премества наляво. След това ние изграждаме възел. Ще я увеличите малко. И тук, ние ще се опитаме да свържете ценности, да бъде същата. Какво става? Нека видим дали евентуално Valgrind може да ни даде един намек. 

Обичам да използвам Valgrind, само защото Valgrind наистина бързо бяга и ви каже, ако има някакви грешки в паметта. Когато стартирате Valgrind на кода, както можете да видите право хит here--Valgrind./binary_tree--and влиза. Вие виждате, че ние не разполагаме с никаква грешка памет, така че да изглежда, че всичко е наред засега. Имаме някои изтичане на памет, което ние знаем, защото не сме случва да се освободи някой от нашите възли. Нека се опитаме работи GDB да се види какво всъщност се случва. Ние ще направим GDB. / Binary_tree. Заредил добре. Нека да критичната точка на вмъкване. Нека тече. Изглежда, че ние никога не сме всъщност се нарича вложка. Изглежда, че проблемът е само, че когато смених тук в основната всички тези ФОРМАТ обаждания от съдържа - Никога не съм се променили те да се обадя вложка. Сега нека да го пробвам. Нека състави. Всичко изглежда добре. Сега нека се опитаме да я пуснете, да видим какво ще стане. Добре! Всичко изглежда доста добре там. 

Крайният нещо да си помисля е, има ли някакви крайни случаи това се добавя? И се оказва, че, добре, единия край случай, че винаги е интересно да се мисли за е, какво ще се случи, ако вашето дърво е празна и наричате това се добавя функция? Ще проработи ли? Ами, нека да го опитам. - Binary_tree в. - Начинът, по който започваш да тествате това, ние ще отидем до нашата основна функция, и по-скоро от окабеляване тези възли като този, ние просто няма да коментирам цялото нещо, и вместо окабеляване сами възли, всъщност ние можем да вървим напред и да изтриете всичко това. Ние ще направим всичко покана да вмъкнете. Така че, нека да направим - вместо 5, 8 и 2, започваш да вмъкнете 7, 3 и 9. И тогава ние също ще искате да вмъкнете 6, както и. Запиши. Quit. Двоично дърво. Всичко това се компилира. Ние можем само да го изпълним както и да видим какво ще се случи, но тя също ще бъде наистина важно да се уверите, че ние не разполагат с никакви грешки в паметта, тъй като това е един от нашите крайни случаи, за които знаем. 

Нека се уверим, че той работи и под Valgrind, който ние ще направим от само Valgrind / binary_tree. Изглежда, че ние наистина имаме една грешка от един контекст - ние имаме това сегментиране вина. Какво се е случило? Valgrind всъщност ни казва къде се намира. Zoom малко. Изглежда, че това се случва в нашата вложка функция, където имаме невалиден четене с размер 4 на вложка, ред 60. Нека се върнем и да видим какво се случва тук. Zoom наистина бързо. Искам да се уверите, че той не отиде до ръба на екрана, за да можем да видим всичко. Издърпайте че в малко. Добре. Превъртете надолу, а проблемът е точно тук. Какво се случва ако се надолу и сегашната ни възел вече е нула, майка възел е нула, така че ако погледнем на самия връх, точно тук - ако никога тази линия, докато всъщност изпълнява защото нашата текущата стойност е нула - корена ни е нула, така че тек е нищожна - тогава нашите родители никога не се поставя към тек или валидна стойност, така, майка също ще бъде нула. Трябва да помним, за да проверите за това от време получаваме тук, и ние започваме достъп до стойността на родителя. Така че, какво се случва? Е, ако родителят е нулев (майка == NULL) - тогава знаем, че не трябва да има нищо в дървото. Ние трябва да се опитвате да го поставите в основата. Ние можем да направим това само с корена, равна на нов възел. След това, в този момент, ние не всъщност искат да мине през тези други неща. Вместо това, точно тук, можем да направим или друго, ако друго, или бихме могли да комбинирате всичко тук в друго, но тук ние просто ще използвате друг и да го направя по този начин. Сега отиваме да се тестват, за да се уверите, че нашите майки не е празен преди това всъщност се опитва да достъп до своите области. Това ще ни помогне да се избегне сегментирането вина. Така че, ние се откажат, отдалечаване, съставяне, стартирайте. 

Не грешки, но ние все още имаме куп изтичане на памет защото ние не освободи някой от нашите възли. Но, ако се върнем тук и ние с нетърпение в нашия разпечатка виждаме, че е добре, изглежда като всички от нашите вложки се връщат вярно, което е добре. Вложки са истина, и след това съответните призовава съдържа също е вярно. 

Добра работа! Изглежда, че ние успешно писмено вложка. Това е всичко, което имаме за уточняване на проблема тази седмица Set. Едно забавно предизвикателство да си помисля е как вие всъщност ще отиде в и безплатно всички възли в това дърво. Ние можем да направим така редица различни начини, но аз ще оставя, че до вас да експериментирате, и забавно предизвикателство, опитайте и се уверете, че можете да се уверите че този доклад Valgrind връща грешки и няма течове. 

Успех на Хъфман проблем тази седмица кодиране набор, и ние ще се видим следващата седмица! [CS50.TV]