[Powered by Google Translate] [Раздел 7: по-комфортно] [Роб Bowden] [Харвардския университет] [Това е CS50 [CS50.TV] Добре. Така че, както казах в моя имейл, това ще бъде двоично дърво-интензивно раздел. Но там не са толкова много въпроси. Така че ние ще се опитаме да извади всеки въпрос и в болезнен детайл от най-добрите начини за правене на нещата. Така че още в самото начало, ние преминаваме през примерни чертежи на двоични дървета и такива неща. Така че тук, "Не забравяйте, че двоичен дърво има възли, подобни на тези на свързан списък, с изключение вместо на една показалеца има два: един за "дете" ляво и един за правото "дете". Двоично дърво е точно като свързан списък, с изключение на структурата ще има две указатели. Има тройна дървета, които ще има три указатели, има N-ARY дървета, които просто трябва родово показалеца , че след това трябва да изчистване, за да бъде достатъчно голям, за да има достатъчно указатели към всички възможни деца. Така двоично дърво просто се случва да има постоянен брой на две. Ако искате, можете да дадете свързан списък унарен дърво но аз не мисля, че някой го нарича, че. "Начертайте кутии и стрелки схема на двоичен възел дърво съдържащи Нейт Любим номер, 7, където всяко дете показалецът е нищожна. " Така че IPAD режим. 

Ще бъде доста ясен. Ние просто ще трябва възел, аз ще го привлече като квадрат. И аз ще се направят стойностите тук. Така стойността ще отидете тук, и след това тук ще има лявата показалеца на лявата и дясната показалеца върху правото. И това е много, така конвенцията, да го наречем наляво и надясно, показалецът имена. Двете от тях ще бъде нула. Това просто ще бъде нула, и че просто ще бъде нула. Добре. Да се ​​върнем тук. "С свързан списък, ние само трябва да се съхранява указател на първия възел в списъка, за да си спомнят за целия свързан списък, или целия списък. По същия начин, с дървета, ние само трябва да се съхранява указател един възел, за да запомнят цялото дърво. Този възел е Calle "корен" на дървото. Надграждат вашата схема от преди или изготви нов такава, че имате кутии и стрелки изображение на двоично дърво на стойност 7, след това 3 в ляво, след 9 от дясната страна, а след това 6 на правото на три. " Нека видим дали мога да си спомня всичко това в главата ми. Така че това ще бъде нашият корен тук. Ще има някои показалеца някъде, нещо, което ние ще се обадя корен, и тя сочи към този човек. Сега, за да създадете нов възел, какво имаме 3 на ляво? Така че един нов възел с три и първоначално посочва нула. Аз просто ще сложи Н. Сега ние искаме да направим това отидете в ляво от 7. Така че ние променяме този указател да сочи към този човек. И ние правим същото. Искаме 9 тук която първоначално просто казва нула. Отиваме да се промени този указател, точка 9, и сега искаме да вложим 6 до правото на 3. Така че ще направи 6. И този човек ще посочи. Добре. Така че това е всичко, което иска от нас да се направи. 

Сега нека вървим по някои терминологията. Ние вече говорихме за това как корена на дървото е най-горната възел в дървото. Единственото, съдържащи 7. Възли в долната част на дървото се наричат ​​листата. Всеки възел, който просто има нищожна като своите деца, е листо. Така че е възможно, ако двоично дърво ни е само един възел, че дървото е листа, и това е всичко. "" Височина "на дървото е броя на стъпките, които трябва да направите да получите от върха на листа. " Ще получите, а във втория, разликата между балансирани и небалансирани двоични дървета, но за сега, общата височина на това дърво Бих казал, е 3, въпреки че ако се преброят на хмел трябва да се направи, за да стигнем до 9, а след това е наистина само на височина 2. Точно сега това е небалансирано дърво двоичен, но ние ще говори за балансиран, когато тя може да бъде от значение. Така че сега можем да говорим за възли в дърво по отношение на в сравнение с другите възли в дървото. Така че сега имаме родители, деца, братя и сестри, предци и потомци. Те са доста здрав разум, какво означават те. Ако попитаме родителите. Така че това, което е майка на три? [Студенти] 7. >> Да. Родителят е просто ще бъде това, което сочи към вас. Тогава какви са децата от 7? [Студенти] 3 и 9. >> Да. Забележете, че "деца" буквално означава деца, така 6 няма да се прилагат, защото това е като внук. Но след това, ако отидем потомци, така че това, което са потомци на 7? [Студенти] 3, 6 и 9. >> Да. Потомците на корен възел ще бъде всичко в дървото, с изключение може би на корен възел, ако не искате да се помисли, че е потомък. И накрая, предци, така че е в обратната посока. Така че какви са предците на 6? [Студенти] 3 и 7. >> Да. 9 не е включена. Това е просто директен задната линия до корена ще бъде вашите предци. 

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

Ще направя няколко, но основната идея е, това е по никакъв начин не уникално представяне на двоично дърво, съдържащ тези стойности. Всичко, от което се нуждаем, е някои двоичен дърво, което съдържа 7, 3, 6 и 9. Друг възможен валиден ще бъде основата е 3, отиди на ляво и това е 6, отиди на ляво и това е 7, отиди на ляво и това е 9. Това е напълно валидни двоично търсене дърво. Това не е много полезно, защото тя е точно като на свързан списък и всички тези насоки са само нищожна. Но това е валидно дърво. Да? Студентски стойности не трябва да бъде по-голяма от дясната? Или е това? >> Това исках да отидете на друг начин. Има също така - Да, нека да превключите че. 9, 7, 6, 3. Добър улов. Все още трябва да се подчиним на двоично дърво за търсене е трябвало да направя. Така че всичко, на ляво трябва да бъде по-малко от всеки един възел. Ние можем просто да се движат, да речем, това 6 и я тури тук. Не, ние не можем. Защо продължавате да вършите това? Нека да направим - тук е 6, тук е 7, 6 пункта до 3. Това все още е валидно двоично търсене дърво. Какво не е наред, ако I - нека видим дали ще може да излезе със споразумението. Да, добре. Така че, какво не е наред с това дърво? Предполагам, че вече ви е дал намек, че има нещо нередно с него. Защо продължавате да вършите това? Добре. Това изглежда разумно. Ако погледнем на всеки възел, както и 7, а след това в ляво от 7 3. Така че ние имаме три, нещо, което трябва да правото на 3 6. И ако се вгледате в 6, нещо, което трябва да правото на 6 е 9. Така че, защо не е валиден двоично търсене дърво? [Студенти] 9 все още е в ляво от 7. >> Да. Тя трябва да е вярно, че всички стойности, евентуално може да достигне, като ще ляво на 7 са по-малко от 7. Ако тръгнем от ляво на 7, ще стигнем до три и все още можем да стигнем до 6, все още можем да стигнем до 9, но е отишла по-малко от 7, ние не трябва да бъде в състояние да получи номер, който е по-голям от 7. Така че това не е валидно двоично търсене дърво. 

Брат ми действително е имало интервю въпрос това е в общи линии това, просто код нещо за валидиране дали дървото е двоично дърво за търсене, и така първото нещо, което направи беше просто проверете ако ляво и дясно са правилни, и след това обхождане там. Но не може просто да направите това, вие трябва да следят от факта, че сега съм го оставил на 7, всичко в тази поддърво трябва да бъде по-малко от 7. Правилния алгоритъм трябва да следите на границите, че стойностите е възможно да попадат инча Ние няма да мине през всички от тях. Налице е хубава връзка повторение, въпреки че не са стигнали до тези, или ние няма да стигнем до тези, определяне колко всъщност са. Така че там са 14 от тях. Математически е като идея как да го направя, можете да изберете всеки един от тях да бъде корен възел, и тогава, ако мога да взема 7 да бъде корен възел, тогава там са, да речем, някои цифри, които могат да отидат на лявата ми възел, и има някои номера, които могат да бъдат дясната ми възел, Но ако имам N общия брой, а след това сумата, която може да отидете в ляво плюс сумата, която може ида надясно N - 1. Така че, останалите цифри, те трябва да бъдат в състояние да отиде наляво или надясно. Изглежда трудно, че ако сложа 3 първи, след това всичко трябва да отидете в ляво, но ако сложа 7, а след това някои неща могат да отидат на левия и някои неща, които могат да отидат в правото. И от 3 първия "имам предвид всичко може да отиде в дясно. Това е наистина, просто трябва да се мисли за него, както, колко много неща могат да отидат на следващото ниво на дървото. А то идва, за да бъде 14, или можете да рисувате всички от тях, и тогава вие ще получите 14. 

Ако се върнем тук, "Заповядва двоични дървета са готини, защото чрез тях можем да търсим по подобен начин за търсене над сортиран масив. За да направите това, ние започваме в основата и нашия начин дървото към листа, проверка на стойностите на всеки възел в разрез с ценностите, които ни търсят. Ако стойността на текущия възел е по-малко от стойността търсим, отидете до правото на детето възел. В противен случай, отиваш на ляво на детето възел. В един момент, или ще намерите стойност, което търсите, или ще работи в нула, посочване на стойността не е в дървото. " Трябва да се прекрои дърво сме имали преди, че ще вземе второто. Но искаме да погледнем дали 6, 10 и 1 са в дървото. Така че, това, което беше, 7, 9, 3, 6. Добре. Номерата, които искат да изглеждат, искаме да изглеждаме 6. Как работи този алгоритъм за работа? Е, ние също имаме някои корен показалеца на нашето дърво. И ние ще отидем до корена и да кажа, е тази стойност, равна на стойността, която търсиш? Така че ние търсим за 6, така че не е равен. Така че продължавай, и сега ние казваме, нали, така че шест е по-малко от 7. Означава ли това, че искаме да отидем в ляво, или не искаме да отидем в дясно? [Student] левицата. >> Да. Това е значително по-лесно, всичко, което трябва да направите, е да изготвя един възможен възел на дървото и след това не ... - вместо да се опитва да мисли в главата си, добре, ако това е по-малко, мога да ида наляво или отидете на правото, просто гледам на тази снимка, това е много ясно, че трябва да отида в ляво ако този възел е по-голяма от стойността, която търся. Така че отиди на ляво, сега съм в 3. Искам да - 3 е по-малко от стойността Търся, което е с 6. Така че ние в дясно, а сега в 6, , която е стойността, търся, така че връщане вярно. Следващата стойност, аз отивам да се търси, е 10. Добре. Така 10, сега става - отсече, че ще следват корен. Сега, 10 се ще да е по-голяма от 7, така че аз искам да гледам надясно. Отивам да дойда тук, 10 ще бъде по-голям от 9, така че аз ще искате да погледнете надясно. Дойда тук, но тук сега съм на нула. Какво мога да направя, ако удари нула? [Student] Назад невярно? >> Да. Аз не намирам 10. 1 ще бъде почти идентичен случай, с изключение на това, че просто ще се обърна, вместо да търсят надолу по дясната страна, аз отивам да гледам надолу от лявата страна. 

Сега мисля, че всъщност става дума за код. Ето къде - отвори CS50 уреда и се движите пътя си там, но също така просто да го направя в пространството. Вероятно това е идеален да го направя в пространството, защото ние можем да работим в пространството. "Първо ще имаме нужда от нов тип за дефиниране двоичен възел дърво, съдържащ INT стойности. Използвайки на стереотипния typedef-долу, създаване на нов тип за дефиниране възел в двоичен дърво. Ако можете да заседнат. . . - Дрън, дрън, дрън. Добре. Така че нека да поставим стереотипния тук, typedef структура възел и възел. Да, добре. Така че какви са полетата, които ние ще искате в нашия възел? [Student] Int и след това два указатели? >> Int стойност, две указатели? Как да напиша указатели? [Student] структура. >> Аз трябва да я увеличите инча Да, така структурата възел * оставил, и структура възел * прав. И не забравяйте дискусията от последния път, че това няма смисъл, това няма смисъл, това няма никакъв смисъл. Трябва всичко, което има, за да се определи тази рекурсивна структура. Добре, така че това, което нашето дърво ще изглежда. Ако сме направили тройна дърво, а след това може да изглежда като възел В1, В2, структура възел * b3, където б е клон - всъщност, аз съм по-чух, че левия, средния, нали, но каквото. Ние само се грижи за двоичен, дясно, ляво. "Сега обявява глобална променлива * възел за корена на дървото". Така че ние няма да направим това. За да направим нещата малко по-трудно и по-общо, няма да имаме глобална променлива възел. Вместо това, в основната ние ще декларират всички наши възли неща, и това означава, че по-долу, когато започнат да се показват ни съдържа функция и функцията му за вмъкване, вместо нашите съдържа функционират само с помощта тази глобална променлива възел, отива да го вземе като аргумент дървото, че искаме да обработва. Като глобалната променлива е трябвало да направи нещата по-лесни. Отиваме да направи нещата по-трудно. Сега вземете една минута или така просто да направи този вид на нещо, където в рамките на основната искате да се създаде това дърво, и това е всичко, което искате да направите. Опитайте и изграждане на това дърво в основната си функция. 

Добре. Така че дори не трябва да са изградили дървото целия път още. Но някой има нещо, което може да тегли да покаже как може да започне изграждането на такова дърво? [Student] Някой чука, опитвайки се да се измъкне. [Bowden] Всеки комфортно с тяхното дърво строителство? [Student] Разбира се. Това не е направено. >> Всичко е наред. Ние можем само да довърша - О, можеш ли да го спаси? Ура. Така че тук имаме - О, аз съм леко отрязани. Съм увеличени? Увеличаване, превъртете. >> Аз имам един въпрос. >> Да? [Student] Когато дефинирате структурата, са неща, като инициализира с нещо? [Боудън, бр. >> Добре. Така че ще трябва да се инициализира [Bowden] Не Когато дефинирате, или когато обяви структура, не се инициализира по подразбиране, това е просто хареса, ако Вие декларирате, вътр. Това е точно същото нещо. Това е като всяка от отделните области може да има боклук стойност в него. >> И това е възможно да се определят - или да обяви структура начин, че да ги инициализира? [Bowden Да. Така че, синтаксис пряк път инициализация ще изглежда - Има два начина да направите това. Мисля, че трябва да го компилирате да се уверите, звъня също прави това. Редът на аргументите, че идва в структурата, поставите реда на спорове вътре в тези фигурни скоби. Така че, ако искате да я инициализираме на 9 и се оставя да бъде нула, а след това право е нула, би било девет, нула, нула. Алтернативата е и редактор не харесва този синтаксис, и мисли, че искам нов блок, но алтернативата е нещо подобно - тук, ще го сложа на нов ред. Можете изрично да кажа, не помня точния синтаксис. Така че можете да изрично справяне с тях по име, и да кажа, В или стойност = 9, ляво NULL =. Предполагам, че те трябва да бъдат запетаи. Надясно = NULL, така че по този начин не всъщност трябва да знаят реда на структурата, и когато вие четете това, то е много по-ясен за каква е стойността се инициализира. 

Това се случва да бъде едно от нещата, които - така, в по-голямата си част, C + + е надмножество на C. Можете да вземете C код, да го преместите на C + +, и то трябва да състави. Това е едно от нещата, които C + + не поддържа, така че хората не са склонни да го направя. Аз не знам дали това е единствената причина хората не са склонни да го направя, но случаите, когато имах нужда да го използвате, трябва да се работи с C + + и така че не биха могли да използват този. Друг пример за нещо, което не работи с C + + е как изчистване връща "нищожен *," технически но вие може просто да се каже, Чар * х = каквото изчистване, и тя автоматично ще се преобразува в знак *. Това автоматичен глас не се случва в C + +. Това не би съставят, а вие ще трябва изрично да се каже Чар *, изчистване, каквото и да е, да се хвърли на знак *. Не са много неща, че C и C + + не са съгласни на но това са две. Така че ние ще отидем с този синтаксис. Но дори и да не отиде с този синтаксис, това, което е - може да се обърка с това? [Student] Нямам нужда да го сочен? >> Да. Не забравяйте, че стрелката има мълчаливо и сочен, и така, когато ние просто се занимават със структура, искате да използвате. да се доберат до вътрешността на областта на структурата. И единственият път, когато използвате стрелката е, когато искаме да направим - добре, стрелката е еквивалентно на това е какво би означавало, ако аз използвах стрелка. Всички стрелка средства, сочен това, сега съм на структура, и мога да получа тази област. Или се полето пряко или сочен и да получите областта - Предполагам, че това трябва да бъде стойност. Но тук аз се занимавам само с една структура, а не показалеца на структурата, и така не мога да използвам на стрелката. Но този вид на нещо, което можем да направим за всички възли. О, Боже мой. Това е 6, 7 и 3. Тогава ще можем да се създаде клонове в нашето дърво, можем да имаме 7 - Ние можем да имаме, лявата му трябва да сочи към 3. Е, как да го направим? [Студенти, неразбираем] >> Да, Адрес от node3, и ако не е имал адрес, а след това просто няма да се компилира. Но не забравяйте, че това са указатели към следващите възли. Правото трябва да сочи към 9, и 3 следва точка на правото на 6. Мисля, че това е всичко е готово. Всякакви коментари или въпроси? [Student, неразбираем] корен ще да бъде 7. Ние можем само да кажа възел * PTR = или корен, = & node7. 

За нашите цели, ние ще трябва да се занимава с вложка, така че ние ще искате да напишете функция, за да вмъкнете в този двоично дърво и поставете неизбежно ще се обадя на изчистване да се създаде нов възел за това дърво. Така че нещата ще се разхвърлян с факта, че някои възли в момента са на стека и други възли ще свърши на куп, когато ние ги вмъкнете. Това е напълно валиден, но единствената причина ние сме в състояние да направите това на стека е така, защото това е измислен пример, че ние знаем дървото е трябвало да бъдат изградени 7, 3, 6, 9. Ако ние не разполагаме с това, тогава ние не би трябвало да изчистване на първо място. Както ще видим малко по-късно, ние трябва да се malloc'ing. Точно сега е напълно разумно да се постави на стека, но нека променим това с изпълнението на изчистване. Така че всеки от тях е сега ще бъде нещо като възел * node9 = изчистване (sizeof (възел)). И сега ние ще трябва да направим проверка. (node9 == NULL) - аз не искам това - върне 1, а след това можем да направим node9-> защото сега това е показалеца, стойност = 6, node9-> наляво = NULL, node9-> надясно = NULL, и ние ще трябва да се направят, че за всеки един от тези възли. Така че, вместо да го постави вътре в отделна функция. Нека наречем възел * build_node и това е донякъде подобна на API, ние предлагаме за Huffman кодиране. Ние ви даваме инициализатор функции за дърво deconstructor "функции" за тези дървета и съща за горите. 

Така че тук ние ще имат функция за инициализация просто да се изгради на възел за нас. И това ще изглежда доста точно така. И аз дори да бъде мързелив и не се променя името на променливата, въпреки че node9 няма смисъл вече. О, предполагам, че не е трябвало да бъде шест стойност node9. Сега можем да се върнем node9. И тук трябва да се върнем нула. Всички са съгласни, че Build-A-възел функция? Така че сега можем само да се обадя, че за да се изгради възел с определена стойност и нулеви указатели. Сега можем да извикаме, че можем да направим възел * node9 = build_node (9). И нека го направим. . . 6, 3, 7, 6, 3, 7. И сега искаме да се създаде едни и същи насоки, с изключение на сега всичко е вече по отношение на указатели така че вече не е необходимо адреса на. Добре. И така, какво е последното нещо, което искам да направя? Има грешка при проверка, че аз не правя. Какво се гради връщане възел? [Student, неразбираем] >> Да. Ако изчистване се провали, ще се върне празно. Така че аз отивам да мързеливо го остави тук, вместо да правиш условие за всеки. Ако (node9 == NULL, или - още по-лесно, това е еквивалентно само ако не node9. Така че, ако не node9, или не node6, или не node3, или не node7, върнете 1. Може би трябва да отпечатате изчистване се провали, или нещо. [Student] е фалшива равна на нула, както и? [Bowden Всяко нулева стойност е фалшива. Така че нищожна е с нулева стойност. Нулата е нулева стойност. False е нулева стойност. Any - почти единствените две нулеви стойности са нула и нула, фалшивото е само хеш определя като нула. Това важи и ако ние не декларират глобална променлива. Ако имахме корен * възел тук след това - хубавото на глобални променливи е, че те винаги имат начална стойност. Това не е вярно от функции, как вътре тук ако имаме, като възел * или х възел. Ние нямаме представа какво x.value, x.whatever, или можем да ги отпечатате и те могат да бъдат произволни. Това не е вярно на глобалните променливи. Така възел корен или х възел. По подразбиране, всичко, което е в световен мащаб, ако изрично не е инициализирана с някаква стойност, има нулева стойност, като стойността му. Така че тук, възел корен *, ние не изрично се инициализира с нищо, така стойността му по подразбиране ще бъде нула, която е нулева стойност от указатели. По подразбиране стойността на х ще означава, че x.value е нула, x.left е нулев, и е нула x.right. Така че, тъй като тя е структура, всички полета на структурата ще бъде нулеви стойности. Ние не трябва да използвате, че тук все пак. [Студентски] structs са различни в сравнение с други променливи, както и други променливи са боклук стойности, те са нула? [Прекъснати] Други стойности. Така че в X, X ще бъде нула. Ако това е най-глобален обхват, тя има първоначална стойност. >> Добре. [Bowden] Или първоначалната стойност или нула. Мисля, че се грижи за всичко това. 

Добре. Така че следващия част на въпроса пита "Сега искаме да напише функция, наречена съдържа с прототип на булев съдържа INT стойност. " Ние няма да го булев съдържа INT стойност. Нашият прототип ще изглежда булев съдържа (INT стойност. И тогава ние сме също така ще премине на дърво че трябва да се проверка, за да се види дали има тази стойност. Така възел * дърво). Добре. И тогава ще можем да го наречем с нещо като може би ще искате да ФОРМАТ или нещо. Съдържа 6, нашият корен. Това трябва да се върне, или вярно, като има предвид, че съдържа пет корена трябва да се върне фалшиви. Така че да се второ неговото прилагане. Можете да го направите итеративно или рекурсивно. Хубавото за начина, по който сте задали нещата е, че се поддава на рекурсивни нашето решение много по-лесно от глобалната променлива начин. Защото, ако ние просто трябва да съдържа INT стойност, тогава имаме никакъв начин на recursing поддървета. Ние би трябвало да има отделна функция помощник, че recurses поддървета за нас. Но тъй като ние сме го променил на дървото като аргумент, които винаги са били на първо място, Сега можем да самоизвиква по-лесно. Така че итеративен или рекурсивен, ние ще отидем двете, но ще видим, че рекурсивни в крайна сметка е доста лесно. Добре. Някой има ли нещо, което може да работи с? 

[Student] Имам един повтарящ решение. >> Добре, повтарящ се. Добре, това изглежда добре. Така че, искат да ни минеш през нея? [Student] Разбира се. Така че аз временно променлива, за да получите първата възел на дървото. И тогава аз просто препредаден докато темп не е равно на нула, така че, докато е все още в дървото, предполагам. И ако стойността е равна на стойността, че темп сочат, след това го връща тази стойност. В противен случай, той проверява, ако това е от дясната страна, или от лявата страна. Ако някога сте се получи ситуация, в която има не повече дърво, след това той се връща след излизането на цикъла и връща. [Bowden Добре. Така че изглежда добре. Всеки, който има някакви коментари за нещо? Аз нямам коректност коментари. Единственото нещо, което можем да направим е този човек. О, това ще да отида малко продълговата. Ще поправим това. Добре. 

Всеки трябва да си спомня как третичния работи. Има определено е викторини в миналото , които ви дават функция с третичния оператор, и да кажа, превежда това, направете нещо, което не се използва третичния. Така че това е много често срещан случай, когато щях да мисля, да използвате трикомпонентна, където, ако някои условия променлива нещо, друго, че една и съща променлива към нещо друго. Това е нещо, което много често могат да бъдат трансформирани в този вид на нещо където тази променлива до това - или, добре, това е вярно? След това, в противен това. [Student] Първият от тях е, ако е вярно, нали? [Bowden Да. Начинът, по който винаги съм го прочете, температура се равнява на стойност, по-голяма от темп стойност, след това, в противен това. Задаване на въпрос. Ли е по-голяма? След това направи първото нещо. Друго второто нещо. Аз почти винаги - на дебелото черво, аз просто - в главата ми, чета друго. 

Някой има ли рекурсивно решение? Добре. Това отива - тя вече може да бъде велик, но ние ще направим още по-добре. Това е почти същото точна представа. Това е просто, добре, не искате да обясните? [Student] Разбира се. Така че ние сме като се уверите, че дървото не е празен първо, защото ако дървото е празно, то тогава ще се върне фалшиви, защото не сме го намерили. И ако има още едно дърво, да отидем в - ние първо ще проверим дали стойността е текущият възел. Връщане вярно, ако е така, и ако ние не самоизвиква наляво или надясно. Това звучи ли подходящо? >> Аха. (Споразумение) Така ще забележите, че това е почти структурно много подобен на повтарящ решение. Това е просто, че вместо да recursing, имахме линия, докато. И базовия модел тук, където дървото не е равно на нула е условие, при което избухва на линия, докато. Те са много сходни. Но ние ще вземем това още една крачка напред. Сега, ние правим едно и също нещо тук. Забележете Връщаме едно и също нещо и в двете от тези линии, с изключение на един аргумент е различно. Така че ние ще направим, че в третичния. Удари опция нещо, и го прави символ. Добре. Така че ние ще се върне съдържа. Това става няколко линии, добре, увеличени в него е. Обикновено, като стилистично нещо, аз не мисля, че много хора сложи интервал след стрелката, но предполагам, ако сте последователни, всичко е наред. Ако стойността е по-малко от дърво стойност, ние искаме да самоизвиква на дървото в ляво, друго искаме да самоизвиква правото на дървото. Така че това е една стъпка от този вид по-малък. Стъпка две от този вид по-малък - могат да се разделят на няколко линии. Добре. Втора стъпка от карайки я да изглежда по-малък е тук, върнатата стойност се равнява на дърво стойност, или съдържа каквото. 

Това е важно нещо. Аз не съм сигурен дали той заяви, че изрично в клас, но тя се нарича късо съединение оценка. Идеята тук е стойност == стойност дърво. Ако това е вярно, то това е вярно, и ние искаме да "или", че с каквото и да е тук. Така че, без дори да мисля за каквото и да е тук, какво е целият израз ще се върне? [Student] True? >> Да, защото важи и за всичко, на or'd - или истинска or'd с нещо е непременно вярно. Така че веднага щом виждаме връщане стойност = стойност на дърво, ние просто ще се върне вярно. Дори няма да самоизвиква допълнително съдържа установяване на ред. Ние можем да вземем това една стъпка по-нататък. Върни дърво, което не е равно на нула и всичко това. Това го прави един ред функция. Това също е пример за късо съединение оценка. Но сега това е една и съща идея - вместо - така че ако дървото не е равно на нула - или, както ако дървото е равно на нула, което е лошо, ако дървото се равнява на нула, а след това първото условие ще бъде фалшива. Така фалшиви anded с нищо няма да бъде това, което? [Студентски False. >> Да. Това е другата половина от късо съединение оценка, където ако дървото не е равно на нула, а след това ние не ще дори да отидете - или ако дървото е равно на нула, тогава ние не ще да направя стойност == дърво стойност. Ние просто ще незабавно връщане фалшиви. Което е важно, тъй като, ако тя не е късо съединение оценка, след това, ако дървото е равно на нула, това второ условие се случва по вина на сегмента, защото дървото-> стойност се dereferencing нула. Така че е това. Могат да направят това - смени веднъж през. Това е много често срещано нещо, не го прави един съответствие с това, но това е често срещано нещо в условия, може би не точно тук, но ако (дърво! = NULL, и дървета> стойност == стойност), направете каквото. Това е много често срещано състояние, където вместо да се налага да се разбие на две IFS, където искате, е дървото нула? Добре, това не е нула, така че сега е дърво стойност, равна на стойността? Направете това. Вместо това състояние, това никога няма да Seg вина , защото тя ще се прекъсне, ако това се случи да бъде нула. Е, предполагам, че ако си дърво е напълно невалидни показалеца, тя все още може да Seg вина, но не може да Seg виновен, ако дървото е нищожна. Ако беше нула, може да се счупи, преди да сте някога dereferenced показалеца на първо място. Студентски] наречен мързелив оценка? 

[Bowden] Мързел оценка е нещо отделно. Мързел оценка е по-скоро ви попитам за стойност, ви помоля да изчисли стойност, вид, но не го е необходимо веднага. Така че, докато всъщност се нуждаят от нея, тя не се оценява. Това не е точно същото нещо, но в Хъфман pset, се казва, че ние "мързеливо" пишат. Причината да направим това е така, защото ние всъщност буфериране на обезценката - ние не искаме да пишат отделни битове в даден момент, или отделни байта наведнъж, вместо това искат да получат парче от байтове. Тогава, след като имаме парче от байтове, тогава ние ще го напиша. Въпреки че го помоли да пиша и неуспешно и fread направете същото нещо. Те буферирате чете и пише. Дори и да сте ги помоли да напиша веднага, най-вероятно няма. И не можеш да бъдеш сигурен, че нещата ще бъдат написани , докато ти се обадя hfclose или каквото и да е, които след това казва, добре, аз съм затвори досието ми, това означава, че по-добре да напиша всичко, аз все още не са писали. Няма нужда да напиша всичко , докато при затварянето на файла, и след това се нуждае от нея. Така че това е точно това, което мързелив - той изчаква, докато тя трябва да се случи. - Взема 51 и ще отидат в по-подробно, защото OCaml и всичко в 51, всичко е рекурсия. Има не са повтарящ решения, основно. Всичко е рекурсия, и мързеливи оценка ще бъде важно за много обстоятелства където, ако не сте лениво оценка, това би означавало - Примерът е потоци, които са безкрайно дълга. На теория, можеш да се сетиш на естествените числа като поток от 1-2-3-4-5-6-7 Така лениво оценени нещата са добре. Ако кажа, че искам десетия брой, тогава може да се оцени до десети номер. Ако искам стотен брой, а след това може да се оцени до стотен брой. Без мързелив оценка, а след това ще се опита да оцени всички номера веднага. Вие оценка на безкрайно много числа, а това просто не е възможно. Така че има много обстоятелства, когато мързеливи оценка е от съществено значение за получаване на неща, които трябва да работят. 

Сега искаме да напишете вложка, където ще бъде вложка подобно промяна в нейното определение. Така че точно сега е булев вложка (INT стойност). Отиваме да се промени, че да булев вложка (INT стойност, възел * дърво). Ние всъщност няма да се промени, че отново след малко, ще видим защо. И нека да преминем build_node, само за по дяволите от нея, горе поставете така че ние не трябва да се пишат прототип на функция. Което е намек, че ти започваш да се използва build_node в вложка. Добре. Вземете една минута за това. Мисля, че аз спасих преразглеждане, ако искате да дръпнете от това, или най-малкото, аз го направих. Исках лека почивка, за да се мисли за логиката на вложка, ако не можеш да мислиш за него. По принцип, вие само ще бъде някога поставите в листата. Например, ако вмъкна една, а след това аз неизбежно ще се поставите един - Ще промените в черно - Ще поставите 1 тук. Или ако вмъкнете 4, искам да се поставите 4 тук. Така че без значение какво правиш, ти започваш да се поставите на листо. Всичко, което трябва да направите, е да превъртите надолу по дървото, докато не стигнем до възела която трябва да бъде майка възел, нов възел майка, и след това да промените наляво или надясно показалеца, в зависимост от това дали това е по-голямо или по-малко от сегашния възел. Промяна че показалеца да сочи към новия си възел. Така обхождане на дървото, да отбележа листа на нов възел. Също така мисля защо това забранява вид на ситуацията преди, къде съм конструира двоично дърво, където е правилно ако погледна само един възел, но 9 е в ляво на 7, ако повтори целия път. Така че това е невъзможно в този сценарий, тъй като мисля за вмъкване на 9 или нещо такова, при първия възел, Отивам да видя 7 и аз съм просто ще ида надясно. Така че без значение какво правя, ако аз съм поставите като ще лист, и на листа с помощта на подходящ алгоритъм, , че ще бъде невъзможно за мен да вмъкнете 9 в ляво от 7 защото веднага след като удари 7 аз ще ида надясно. Някой има ли нещо, което да се започне с? [Student правя. >> Разбира се. [Student, неразбираем] [Other студент, неразбираем] [Bowden] оценявам. Добре. Искате ли да обясни? 

[Student] Тъй като ние знаем, че сме били вмъкване нови възли в края на дървото, Препредаден дървото итеративно , докато аз имам възел, който посочи нула. И тогава аз реших да ги сложа или от дясната страна или от лявата страна използва това право променлива, тя ми каза къде да го сложи. И тогава, по същество, аз току-що направихте, че миналата този момент темп възел на нов възел, който го е създавал, или на лявата или от дясната страна, в зависимост от това каква е стойността право. И накрая, новата стойност възела, към стойността на тестването. [Bowden Добре, така че не виждам един въпрос тук. Това е като 95% от пътя там. Един въпрос, който аз виждам, добре, не някой друг е проблем? Каква е обстоятелство, при които те се измъкне от примката? Студентски] Ако температура е нула? >> Да. Така че, как да се измъкне от примката е ако темп е празен. Но какво да правя тук? Сочен темп, което е неизбежно нула. Така че друго нещо, което трябва да направите, е не просто следи, докато темп е нула, искате да следите на родителя по всяко време. Ние също искаме майка възел *, предполагам, че можем да поддържаме, че нула в първата. Това ще има странно поведение за корена на дървото, но ние ще стигнем до това. Ако стойността е по-голяма от каквото TEMP = темп право. Но преди да направим това, родител = темп. Или родители, които винаги ще равен темп? Така ли е? Ако температура не е празен, тогава аз ще се премести надолу, без значение какво, възел, за които темп е родител. Така че родител ще бъде температура, а след това се преместя темп надолу. Сега темп е нулев, но майки точки родител на нещо, което е нищожна. Така че тук, аз не искам да зададете равен на 1. Така че аз се премества надясно, така че ако надясно = 1, и аз предполагам, че вие ​​също искате да направите - ако се движите наляво, искате да зададете равен на 0. Или пък, ако някога се движи надясно. Така надясно = 0. Ако надясно = 1, сега ние искаме да направим майка правото newnode показалеца, друго, което искате да направите майка ляв newnode показалеца. Въпроси за това? Добре. Така че това е начин ние - Ами, всъщност, вместо да прави това, 1/2 очаква можете да използвате build_node. И тогава, ако newnode се равнява на нула, връщане фалшиви. Това е. Сега, това е това, което очаквахме да направиш. 

Това е, което на персонала решения. Не съм съгласен с това като "правилен" начин за това но това е съвършено глоба и тя ще работи. Едно нещо, което е малко странно точно сега е ако дървото започва като унищожаем, ние минаваме в нулева дърво. Предполагам, че това зависи от това как да се определи поведението на преминаване в нулева дърво. Аз мисля, че ако премине в нулева дърво, след поставянето на стойност в нулева дърво просто трябва да се върне дървото, където единствената ценност е, че един възел. Ли хора са съгласни с това? Може, ако искаш, ако премине в нулева дърво и искате да въведете стойност в нея, връщане фалшиви. Това е до вас, за да определи това. За да направите първото нещо, което каза и след това - добре, ще има проблеми с това, защото , че ще бъде по-лесно, ако имахме глобален указател към нещо, но ние не, така че ако дървото е празно, няма нищо не можем да направим за това. Ние можем само да се върне фалшиви. Така че аз няма да се промени вложка. Технически може просто да промените това право, как се итерации над нещата, но аз няма да се промени посочете възел ** дърво. Двойни указатели. Какво означава това? Вместо да се занимават с указатели към възли, нещо, аз отивам да се манипулира, е този указател. Отивам да се манипулира този указател. Отивам да се манипулира указатели директно. Това има смисъл, тъй като си помисля надолу - добре, точно сега това показва нула. Това, което искам да направя, е да манипулира това показалеца, за да посоча да не нула. Искам да сочи към моя нов възел. Ако просто следи от указатели към указатели ми, тогава не е нужно да следите на показалеца родител. Мога само да следим, за да видите, ако показалецът е насочена към нула, и ако показалецът е насочена към нула, промените е да се отбележи възел Искам. И аз мога да го промените, тъй като имам показалеца на показалеца. Нека видим това точно сега. Всъщност можете да го направите рекурсивно доста лесно. Искаме ли да направите това? Да, ние правим. 

Нека го видя рекурсивно. Първо, каква е нашата база случай ще бъде? Почти винаги нашата база случай, но всъщност, това е вид сложно. Първо най-важното, ако (дърво == NULL) Предполагам, че просто ще се върне фалшиви. Това е различно от вашето дърво е нищожна. Това е показалеца на показалеца на основната си е нула което означава, че показалеца корен не съществува. Така че тук, ако го направя * възел - нека просто да използвате отново този. Node * корен = NULL, и тогава аз ще се обадя на вмъкване, като прави нещо подобно, вмъкнете 4 в & корен. Така и корен, ако основата е възел * след това и корен ще бъде възел **. Това е валидно. В този случай, дърво, тук, дървото не е нула - или поставете. Ето Дървото не е нищожна; * дървото е нула, което е добре , защото ако * дървото е нула, а след това мога да го манипулира до сега сочи към това, което искам да сочи към. Но ако дървото е нула, това означава, че аз просто дойдох тук и каза нула. В това няма смисъл. Не мога да направя нищо с това. Ако дървото е нула, връщане фалшиви. Така че в общи линии вече казах какво е истински случай база. И това, което е, че ще бъде? [Student, неразбираем] [Bowden Да. Така че, ако (* дърво == NULL). Това се отнася за случая тук където, ако ми червената стрелка е показалеца съм фокусиран, така, сякаш съм фокусиран върху този указател, сега съм фокусиран върху този указател. Сега съм фокусиран върху този указател. Така че, ако ми червената стрелка, които са моите възли **, е винаги - ако *, червената стрелка, някога е нула, това означава, че аз съм в случаите, когато съм се фокусира върху показалеца, който сочи това е указател, който принадлежи към едно листо. Искам да променя този указател да сочи към моя нов възел. Върни се тук. Моят newnode просто ще бъде възел * N = build_node (стойност) N, ако N = NULL, връщане фалшиви. Иначе ние искаме да променим това, което показалецът се посочи до сега сочи към новопостроен възел. Ние действително можем да правим така. Вместо да казвате N, ние казваме * = * дърво дърво. Всеки се разбере, че? Това, че се занимават с указатели към указатели, ние можем да променим нулеви указатели, за да сочи към нещата, които искаме да посочат. Това е нашата база случай. 

Сега нашата рецидив, или рекурсия ще бъде много подобен на всички останали recursions ние сме били прави. Отиваме да искате да вмъкнете стойност, и сега аз отивам да използвате третичния отново, но какво е нашето състояние ще бъде? Какво е да търсим, за да реши дали искаме да отидем наляво или надясно? Да го направим в отделни стъпки. Ако (стойност) какво? [Студентски] стойност на дървото? [Bowden] Така че не забравяйте, че аз съм в момента - [Студенти, неразбираеми] [Bowden] Да, точно тук, нека кажем, че тази зелена стрелка е пример за това какво в момента е дърво, е указател към този указател. Така че това означава, че съм указател към указател към 3. Сочен два пъти звучеше добре. Какво ми е - как мога да го направя? [Student] и сочен веднъж, и след това направете стрелката по този начин? [Bowden] (* дърво) е сочен веднъж -> стойност ще ми даде стойността на възела, че аз съм косвено посочи. Така че мога да го напиша ** tree.value, ако предпочитате, че. Или работи. Ако случаят е такъв, тогава искам да се обадя го поставете със стойност. И какъв е моят обновява възел ** ще бъде? Искам да отида на ляво, така че ще бъде ** tree.left е лявата ми страна. И аз искам показалеца на това нещо така че ако левият е нулев указател, Мога да го променя да сочи към моя нов възел. 

И друг случай могат да бъдат много сходни. Нека всъщност правят, че ми третичния точно сега. Поставете стойност, ако стойността <(** дърво). Стойност. След това ние искаме да актуализираме ** наляво, друго, което искате да актуализирате нашите ** надясно. [Student] ли това, че се показалеца на показалеца? [Bowden] Не забравяйте, че - ** tree.right е възел звезда. [Student, неразбираем] >> Да. ** Tree.right е като този указател или нещо такова. Така че, като като показалеца на това, че ми дава това, което искам на показалеца на този човек. [Student] Може да отидем отново защо ние използваме двете указатели? [Bowden Да. Така че - не, можете и това решение пред е начин да го прави без две указатели. Трябва да сте в състояние да разберат използват две указатели, и това е по-чиста решение. Също така, забележете, че това, което се случва, ако моето дърво - какво ще се случи, ако Коренът ми е нула? Какво се случва, ако направя това тук? Така възел * главната = NULL, поставете четири в & корен. Какво е корен ще бъде след това? [Student, неразбираем] >> Да. Root стойност ще бъде 4. Root ляво ще бъде нула, корен правото ще бъде нула. В случаите, когато не е преминала корен по адрес, ние не може да изменя корен. В случаите, когато дърво - корен се оказва нищожна, ние просто трябваше да се върне фалшиви. Няма нищо, което можем да направим. Ние не можем да вмъкнете възел в празна дърво. Но сега можем, ние просто празен дърво в един възел дърво. Която обикновено е по очаквания начин, че тя е трябвало да работи. 

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

И това, което е специално за тази рекурсивна функция? Това е опашката рекурсивен, толкова дълго, колкото се събират с някои оптимизация тя ще признае, че и никога няма да се получи препълване на стека от това, дори и ако нашето дърво е с височина от 10 000 или 10 милиона. [Student, неразбираем] [Bowden] Мисля, че това го прави най-Dash - или какво оптимизация ниво се изисква за опашката рекурсия, да бъдат признати. Мисля, че тя признава - GCC и звъня също да имат различни значения за тяхното оптимизиране нива. Искам да кажа, че е DashO 2, сигурни, че ще признае опашката рекурсия. Но ние може да се изгради като например Fibonocci или нещо. Не е лесно да тествам с това, защото е трудно да се пресметне двоично дърво, което е толкова голям. Но да, мисля, че е DashO 2, ако вие компилирате с DashO 2, тя ще изглежда за опашката рекурсия и да се оптимизира, че Нека се върнем към поставете буквално последното нещо, от което се нуждае. Нека се върнем към вложката тук къде отиваме да направи една и съща идея. Той все пак ще има недостатък не е в състояние напълно да се справят когато самият корен е нула, или миналото влизането е нулев, но вместо да се занимават с родител показалеца, нека приложим същата логика водене на указатели към указатели. Ако тук ние държим възел ** тек, и ние не трябва да следим на вече но възел ** тек = дърво. И сега нашата линия, докато ще бъде, докато * тек не е равно на нула. Не е необходимо да следите вече на родителите. Не трябва да следим на ляво и дясно. И аз ще го наречем температура, защото ние сме вече използват темп. Добре. Така че, ако (стойност * Temp), & (* ТЕМП) -> дясно друго TEMP = & (* Temp) -> оставяли. И сега, в този момент, след това, докато контур, Само това, защото може би е по-лесно да се мисли за итеративно от рекурсивно но след това, докато контур, * Температура е показалеца искаме да променим. 

Преди имахме майка, и искахме да променим ляво или родител или родител, както, но ако искаме да се промени правото на родителя, * темп е правото на родителя, и можем да го промените директно. Така че тук, можем да направим * TEMP = newnode, и това е всичко. Така предизвестие, всичко, което сме направили в тази реда код. За да се запази следите на майка във всичко, което е допълнително усилие. Тук, ако ние просто следите на показалеца на показалеца, и дори ако искахме да се отървете от всички тези фигурни скоби, да изглеждат по-къси. Това сега е точно същото решение, , но по-малък брой редове код. След като започнете да признае това като валидно решение, това е причина за по-лесно, отколкото като, добре, защо имам този флаг в INT право? Какво означава това? О, това означава, че всеки път, когато отида право, аз трябва да го оправят, иначе, ако отида напуснах, аз трябва да го зададете на нула. Ето, аз не трябва да се причина за това, той е просто по-лесно да си помисля. Въпроси? [Student, неразбираем] >> Да. Добре, така че в последната част - Предполагам, че един бърз и лесен функция, което можем да направим, е, let's - заедно, предполагам, опитайте и напишете съдържа функция , който не се интересува дали е двоично дърво за търсене. Той съдържа функция трябва да се върне вярно ако навсякъде в този общ двоичен дърво е стойността търсим. Така че нека първо го направи рекурсивно и след това ще го направим итеративно. Ние действително можем просто да го направим заедно, защото това ще бъде много кратко. 

Каква е моята база случай ще бъде? [Student, неразбираем] Bowden] Така че, ако (дърво == NULL), тогава какво? [Student] връщане фалшиви. [Bowden] Иначе, добре, аз не се нуждаят от друго. Ако ми беше друг случай база. Студентски] Tree стойност? >> Да. Така че, ако (дърво> стойност == стойност. Забележете, ние сме назад възел * не възел **? Съдържа никога няма да се наложи да използвате възел **, тъй като ние не сме промяна указатели. Ние просто ги пресичат. Ако това се случи, тогава ще искате да се върнете вярно. Иначе искаме да преминават децата. Така че ние не може да се ориентира дали всичко от ляво е по-малко и всичко в дясно е по-голяма. И така, какво е нашето състояние ще бъде тук - или, какво ще правим? [Student, неразбираем] >> Да. Върни се съдържа (стойност, дървото-> ляво) или съдържа (стойност, дърво-> дясно). И това е всичко. И забележите, че някои от късо съединение оценка, където, ако се случи да се намери стойност в лявото дърво, ние никога не трябва да се търси в дясното дърво. Това е цялата функция. Сега нека го направим итеративно, , която ще бъде по-хубаво. Ще вземем обичайното началото на възел * тек = дърво. Докато (тек = NULL). Бързо ще видим проблем. Ако тек - тук, ако някога се измъкне от това, тогава сме се изчерпят неща да погледнете, така че връщане фалшиви. Ако (тек-> стойност == стойност), върнете вярно. Така че сега, ние сме на едно място - ние не знаем дали искаме да отидем наляво или надясно. Произволно, нека просто отиди наляво. Очевидно съм тичам в проблем, когато съм напълно изоставен всичко - Аз само ще провери лявата страна на дървото. Аз никога не ще провери всичко, което е право дете на каквото и да било. Как мога да поправя това? [Student] Трябва да следите на ляво и дясно в комин. [Bowden Да. Така че нека да го направи структура на списък, възел * N, а след това възел ** следващият? Мисля, че работи добре. Ние искаме да отидем в ляво, или let's - до тук. Структура = Списък, тя ще започне в тази структура списък. * Списък = NULL. Така че това ще бъде нашата свързан списък поддървета, че сме прескачат. Ние ще Traverse останало, но тъй като ние неизбежно трябва да се върне в правото, Ние ще продължим да дясната страна вътрешната структура на нашия списък. Тогава ще имаме new_list или структура, структура на списък *, new_list = изчистване (sizeof (списък)). Отивам да игнорирате грешка проверка, че, но трябва да се провери, за да видите, ако това е нищожна. New_list възел ще посочи - О, това е защо аз го исках тук. Това ще да сочи към втори списък структура. Това е просто начина, свързани списъци работа. Това е същото като INT свързан списък освен ние просто замяна на цяло число възел *. Това е точно същото. Така new_list стойността на нашия new_list възел, ще бъде тек-> дясно. Стойността на нашата new_list-> следващия ще бъде нашата първоначалния списък, и след това ние ще актуализираме списъка, за да сочи към new_list. 

Сега имаме нужда от някаква дърпа неща, като ние изминахме целия ляв поддърво. Сега ние трябва да дръпнете неща от него, като тек е нула, ние не искаме просто връщане фалшиви. Ние искаме да дръпнете извън нашия нов списък. Удобен начин за това - добре, всъщност, има няколко начина да направите това. Всеки, който има предложение? Ако аз трябва да направя това или как аз трябва да направя това? Ние имаме само няколко минути, но някакви предложения? Вместо по един начин, вместо на нашето състояние, а това, което сме в момента търси не е празен, Вместо това, ние ще продължим да отидете до нашия списък е празен. Така че, ако в нашия списък в крайна сметка е нула, тогава сме свършили неща, които трябва да се търси, да се търси и във. Но това означава, че първото нещо, което в нашия списък е просто ще бъде първият възел. Първото нещо, което ще бъде - ние вече не трябва да се види, че. Така списък-> N ще бъде нашето дърво. списък-> следващия ще бъде нула. И сега, докато списъкът не е равно на нула. Cur се ще да покажете нещо от нашия списък. Така тек на равно списък->. И тогава списък на равно списък-> или списък-> следващия. Така че, ако тек стойност е равна стойност. Сега можем да добавим нашето право показалеца и лявата ни показалеца толкова дълго, тъй като те не са нула. Надолу тук, предполагам, че е трябвало да направи, че на първо място. Ако (тек-> Добре! = NULL) тогава ние ще да вмъкнете този възел в нашия списък. Ако (тек-> ляво), това е малко допълнителна работа, но всичко е наред. Ако (тек-> ляво! = NULL), и отиваме да вмъкнете в ляво в свързан списък, и че трябва да бъде. Ние обхождане - толкова дълго, колкото ние имаме нещо в нашия списък, имаме друг възел да погледна. Така че ние гледаме на този възел, вървим напред нашия списък към следващия. Ако този възел е стойността търсим, можем да се върнем вярно. Else поставете двете ни лявото и дясното поддървета, толкова дълго, колкото те не са нула, в нашия списък така че ние неизбежно върху тях. Така че, ако те не са били нула, ако нашият корен показалеца посочи две неща, тогава най-напред извади нещо, така че в нашия списък в крайна сметка е нищожна. И тогава ние поставяме две неща обратно, така че сега нашия списък е с размер 2. След това започваш да отскача назад и просто щяхме да тегли, нека кажем, лявата показалеца на нашата коренът. И това просто ще запази случва, ние ще свършим лупинг над всичко. 

Забележете, че това е значително по-сложно в рекурсивния решение. И аз съм казвал няколко пъти че рекурсивно решение обикновено има много общо с повтарящ решение. Ето това е точно това, което рекурсивно разтвор се прави. Единствената промяна е, че вместо да имплицитно стека стека на програмата, като начин за следене на какви възли все още трябва да посетите, сега ще трябва да изрично да се използва свързан списък. И в двата случая се следи какво възел все още трябва да бъдат посетени. В рекурсивния случай това е просто по-лесно, тъй като комин се осъществява за вас, тъй като програмата стека. Забележете, че тази свързан списък, стек. Каквото и ние просто сложи на стека незабавно какво ще да потеглям стека, за да посети следващия. Ние сме извън времето, но някакви въпроси? [Student, неразбираем] [Bowden Да. Така че, ако ние имаме свързан списък, ток се ще да сочи към този човек, и сега ние просто развиване на нашата свързан списък да се съсредоточи върху този човек. Преминаващи над свързан списък, в този ред. И тогава аз предполагам, че трябва да се освободим свързан списък и такива неща веднъж, преди да се върне вярно или невярно, ние трябва да обхождане свързани нашия списък и винаги тук, предполагам, ако ние тек не е равно на, да го добавите, затова сега искаме да освободи тек, защото добре, не сме напълно да забравите за списъка? Да. Така че това е, което искаме да направим тук. Къде е показалеца? Cur тогава - ние искаме структура списък * 10 е равно на списъка до. Безплатно списък, списък = темп. И в случаите, когато се върнем вярно, ние се нуждаем, за да превъртите над останалата част от нашата обвързана списък освобождаването неща. Хубавото на рекурсивния решение освобождаването неща просто означава пръкват factorings край стека, което ще се случи за вас. Така че ние сме отишли ​​от нещо, което е като три линии е трудно да се мисли за код нещо, което е значително много по-трудно да-мисля, че за реда код. Има ли още въпроси? Добре. Ние сме добре. Чао! [CS50.TV]