[Powered by Google Translate] [Частина 7: більш комфортним]
[Rob Боуден] [Harvard University]
[Це CS50] [CS50.TV]
Добре. Так як я сказав у моїй електронній пошті,
це буде двійкового дерева інтенсивної розділі.
Але є не те, що багато питань.
Отже, ми збираємося, щоб спробувати витягнути на кожне питання
і перейти в хворобливе докладно все кращі способи ведення справ.
Таким чином, на самому початку, ми проходимо через зразків малюнків бінарні дерева та інше.
Так от, "Пам'ятай, що бінарне дерево має вузли, аналогічні зв'язаний список,
тільки замість одного покажчика існує два: один для «дитини» лівий
і один для правого "дитина".
Таким чином, бінарне дерево так само, як зв'язаний список,
крім структура матиме два покажчика.
Там в троичной дерев, які матиме три покажчика,
Є N-арной дерева, які тільки є загальний покажчик
що ви тоді повинні Танос бути достатньо великим, щоб мати
Досить покажчики на всі можливі дітей.
Таким чином, бінарне дерево тільки, трапляється, мають постійне число два.
Якщо ви хочете, ви можете дати зв'язаний список як унарний дерева,
Але я не думаю, що хтось називає її цим.
"Нічия коробки-і-стрілки схема двійкового дерева вузлів
містять улюблений номер Нейта, 7, де кожна дитина покажчик нульовий ".
Так Ipad режимі.
>> Це буде досить просто.
Ми просто будемо мати вузол, я намалюю його як квадрат.
І я намалюю значення тут.
Таким чином, значення буде йти сюди,
, А потім тут ми матимемо лівий покажчик на лівий і правий покажчик праворуч.
І це навіть дуже конвенції назвати його лівим і правим, імена покажчиків.
Обидва цих збираєтеся бути нульовим.
Це буде просто нульовим, і це буде просто нульовим.
Добре. Отже, повернемося сюди.
"З пов'язаного списку, ми тільки повинні були зберігати покажчик
на перший вузол у списку, щоб запам'ятати весь зв'язаний список, або весь список.
Крім того, з деревами, у нас є тільки для зберігання покажчика
в один вузол, щоб пам'ятати все дерево.
Цей вузол Calle «корінь» дерева.
Побудувати на вашій схемі від до або залучити нове
таке, що у вас є коробки-і-стрілки зображення бінарне дерево
з значенням 7, потім 3 в лівій,
Потім 9 на праву, а потім 6 на право 3 ".
Давайте подивимося, якщо я можу пам'ятати все, що в моїй голові.
Таким чином, це буде наш корінь тут.
У нас буде декілька покажчиків десь, щось, що ми називаємо коренем,
, І це вказує на цього хлопця.
Тепер, щоб зробити новий вузол,
Що ми маємо, 3 зліва?
Таким чином, новий вузол з 3 років, і спочатку відзначає нульовий.
Я просто поклав N.
Тепер ми хочемо, щоб це піти наліво 7.
Таким чином, ми змінити це покажчик тепер вказує на цього хлопця.
І ми робимо те ж саме. Ми хочемо, щоб в 9 тут
який спочатку просто говорить нульовим.
Ми збираємося змінити це покажчик, крапка до 9,
і тепер ми хочемо покласти 6 на право 3.
Так що це буде - зробити 6.
І цей хлопець буде вказувати там.
Добре. Так що це все, що просить нас зробити.
>> Тепер давайте пройдемося по термінології.
Ми вже говорили про те, як корінь дерева є самий верхній вузол в дереві.
Одна з яких 7. Вузлів у нижній частині дерева називаються листям.
Будь вузол, який просто має нульове своїм дітям аркуша.
Таким чином, це можливо, якщо наші бінарне дерево знаходиться всього в одному вузлі,
, Що дерево є листом, і це все.
"" Висота "дерева є кількість стрибків ви повинні зробити
щоб отримати від вершини до листа ".
Ми увійдемо в у другому, різниця
між симетричними і несиметричними бінарні дерева,
але зараз, загальна висота цього дерева
Я б сказав, це 3, хоча якщо порахувати кількість стрибків
Ви повинні зробити для того, щоб дістатися до 9, то це дійсно тільки висота 2.
Зараз це незбалансоване бінарне дерево,
але ми говорили про збалансоване, коли воно стане актуальним.
Так що тепер ми можемо говорити про вузлів в дереві з точки зору
по відношенню до інших вузлів в дереві.
Так що тепер у нас є батьки, діти, брати, сестри, предки, і нащадки.
Вони досить здорового глузду, що вони означають.
Якщо ми запитаємо, - це батьки.
Так що батько 3?
[Студенти] 7. >> Да. Батько просто буде те, що вказує на вас.
Тоді що діти від 7?
[Студенти] 3 і 9. >> Да.
Зверніть увагу, що "діти" буквально означає діти,
так 6 не буде застосовуватися, тому що це, як онук.
Але тоді, якщо ми підемо нащадків, так що є нащадками 7?
[Студенти] 3, 6 і 9. >> Да.
Нащадки кореневого вузла буде все в дереві,
крім, може бути кореневим вузлом себе, якщо ви не хочете, щоб розглянути, що нащадок.
І, нарешті, предки, так що це в протилежному напрямку.
Так що предки 6?
[Студенти] 3 і 7. >> Да. 9 не включені.
Це просто пряма спина лінії в корінь
буде вашим предкам.
>> "Ми говоримо, що бінарне дерево" замовити ", якщо для кожного вузла в дереві,
всі його нащадки зліва мають менші значення
і всі ті, на правому мати більше значення.
Наприклад, дерево вище замовили, але це не єдиний можливий впорядковане розташування ".
Перш ніж ми перейдемо до цього,
наказав бінарне дерево також відомий як бінарне дерево пошуку.
Тут ми, трапляється, назвавши його замовив бінарне дерево,
Але я ніколи не чув його називають наказав двійкового дерева перш,
і на тест ми набагато більше шансів поставити двійкового дерева пошуку.
Вони одне і те ж,
і дуже важливо, ви дізнаєтеся відмінність між бінарне дерево і дерево двійкового пошуку.
Бінарне дерево це просто дерево, яке вказує на дві речі.
Кожен вузол вказує на дві речі.
Існує немає міркувань про цінності, які він вказує.
Так як тут, так як це бінарне дерево пошуку,
Ми знаємо, що якщо ми підемо ліворуч від 7,
Потім всі цінності, які ми може досягти
, Йдучи зліва від 7 повинні бути менше 7.
Зверніть увагу, що всі значення менше, ніж 7, 3 і 6.
Це все до лівої 7.
Якщо ми йдемо направо з 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.
Це як і раніше дійсні бінарне дерево пошуку.
Що поганого, якщо я - подивимося, чи зможу я придумати домовленості.
Так, все в порядку. Так що ж не так з цим деревом?
Я припускаю, що я вже дав вам підказку, що щось не в порядку з цим.
Чому я роблю це?
Добре. Це виглядає розумним.
Якщо ми подивимося на кожен вузол, як і 7, то зліва від 7, 3.
Таким чином, ми маємо 3, річ праворуч від 3 являє собою 6.
І якщо ви подивитеся на 6, річ праворуч від 6, 9.
Так чому ж це не є допустимим бінарне дерево пошуку?
[Студенти] 9 і раніше в лівій частині 7. >> Да.
Це повинно бути вірно, що всі значення, які може досягти, перейшовши в ліву від 7 менше, ніж 7.
Якщо ми йдемо наліво з 7, ми отримуємо 3, і ми все ще можете отримати до 6,
Ми все ще можете отримати до 9, але, пройшовши менше 7,
ми не повинні бути в змозі дістатися до ряду, що це більше 7.
Так що це не є допустимим бінарне дерево пошуку.
>> Мій брат насправді було інтерв'ю питання
, Що в основному це, просто код щось для перевірки
Чи дерево бінарне дерево пошуку,
і тому перше, що він зробив, було просто перевірити,
якщо лівий і правий правильно, а потім повторювати там.
Але ви не можете просто зробити це, ви повинні стежити
той факт, що тепер, коли я пішов лівіше 7,
всі в цьому поддереве повинно бути менше 7.
Правильний алгоритм повинен стежити
за межі значень, що може впасти можливо дюйма
Ми не будемо пройти через всі з них.
Існує гарне ставлення рецидиву,
хоча ми ще не дійшли до тих, чи ми не отримаємо тих,
визначає, скільки там насправді.
Таким чином, існує 14 з них.
Ідея про те, як ви могли б зробити це математично, як,
Ви можете вибрати будь-якої однієї, щоб бути кореневий вузол,
а потім, якщо я вибираю бути від 7 до кореневого вузла,
тобто, скажімо, деякі цифри, які можуть піти моїм лівим вузлом,
і є деякі номери, які можуть бути моя права вузла,
але якщо я п загального числа, то сума, яка може піти наліво
плюс сума, яка може піти на право N - 1.
Таким чином, з решти чисел, вони повинні бути в змозі піти або вліво або вправо.
Здається, важко, що, якщо я поставлю 3 перших, то все має піти наліво,
але якщо я поставлю 7, то деякі речі можуть піти лівої і деякі речі можуть піти направо.
І '3 перший "я мав на увазі все може піти направо.
Це дійсно, ви просто повинні думати про це, як,
як багато може піти на наступному рівні дерева.
І він виходить на 14, або ви можете намалювати всі,
і тоді ви отримаєте 14.
>> Повертаючись сюди,
"Впорядковані бінарні дерева є здорово, тому що ми можемо шукати через них
У дуже схоже на пошуки більш впорядкований масив.
Щоб зробити це, ми починаємо з кореня і працювати наш шлях вниз по дереву
на листках, перевіряючи значення кожного вузла у відношенні цінностей, які ми шукаємо.
Якщо значення поточного вузла менше, ніж значення, яке ми шукаємо,
Ви йдете поруч з правим нащадком вузла.
В іншому випадку, ви йдете в лівому нащадка.
У якийсь момент, ви або знайти значення, яке ви шукаєте, або ви будете працювати в нуль,
із зазначенням значення не в дереві ".
У мене є для перемальовування дерева, що було раніше, то візьму другий.
Але ми хочемо, щоб шукати чи 6, 10, і 1 в дерево.
Так що ж це було, 7, 9, 3, 6. Добре.
Цифри, які ви хочете подивитися, ми хочемо, щоб подивитися 6.
Як це алгоритм роботи?
Ну, у нас є кілька кореневих покажчик на дерево.
І ми пішли б в корені і говорити, це значення дорівнює значенню ми шукаємо?
Таким чином, ми шукаємо 6, так що це не рівні.
Таким чином, ми продовжуємо, і тепер ми говоримо, ладно, так 6 менше 7.
Чи означає це, ми хочемо йти наліво, або ми хочемо, щоб піти в порядку?
[Студент] вліво. >> Да.
Це значно простіше, все, що вам потрібно зробити, це зробити один можливий вузол дерева
і тоді ви не - замість того, щоб думати головою,
Добре, якщо вона менше, я можу піти наліво або піти направо,
просто дивлячись на цю картину, це дуже ясно, що я повинен йти зліва
якщо цей вузол більше, ніж значення, що я шукав.
Таким чином, ви йдіть наліво, тепер я на 3.
Я хочу - 3 менше, ніж значення, я шукаю, що на 6.
Таким чином, ми йдемо направо, і тепер я в кінцевому підсумку на 6,
яка є значенням я шукаю, так що я повертаюся правда.
Таке значення, я буду дивитися на це 10.
Добре. Так що 10, зараз буде - відрізав, що - будемо слідувати кореня.
Тепер, 10 буде більше 7, тому я хочу, щоб дивитися направо.
Я збираюся приїхати сюди, 10 буде більше 9,
так що я збираюся хочете подивитися вправо.
Я прийшов сюди, але тут зараз я в нуль.
Що мені робити, якщо я вдарив нуль?
[Студент] Повернутися помилковим? >> Да. Я не знайшов 10.
1, буде майже ідентична випадку,
винятком того, що тільки збирається бути перевернута, замість того щоб шукати
вниз по правій стороні, я буду дивитися на ліву сторону.
>> Тепер я думаю, що ми насправді отримати код.
Ось де - відкрити CS50 прилад і прокладаєте свій шлях там,
але ви також можете просто зробити це в просторі.
Це, напевно, ідеальний зробити це в просторі,
тому що ми можемо працювати в космосі.
"Спочатку потрібно нове визначення типу для бінарного вузла дерева, що містить Int значення.
Використання шаблону ЬурейеЕ нижче,
створити нове визначення типу для вузла в бінарному дереві.
Якщо ви застрягли. . . "Бла, бла, бла. Гаразд.
Так давайте шаблонного тут,
ЬурейеЕ вузла структури і вузлів. Так, все в порядку.
Так що поле ми збираємося хочемо в нашій вузла?
[Студент] Int, а потім два покажчика?
>> Int значення, два покажчика? Як написати покажчики?
[Студент] Struct. >> Я повинна збільшити масштаб Так, так що структура вузла * пішов,
і структура вузла * прав.
І пам'ятайте обговорення в минулий раз,
що це не має сенсу, це не має сенсу,
це не має сенсу.
Вам потрібно все, для того, щоб визначити це рекурсивна структура.
Гаразд, так це те, що наше дерево буде виглядати.
Якщо б ми зробили трійкового дерева, то вузол може виглядати В1, В2, структура вузла * b3,
де Ь філії - насправді, я більше чув він залишив, середній, правий, але незалежно.
Ми дбаємо лише про бінарних, так вправо, вліво.
"Тепер оголосити глобальну змінну * вузол для кореня дерева".
Таким чином, ми не збираємося цього робити.
Для того, щоб зробити речі трохи більш складним і більш узагальнені,
у нас не буде глобальної змінної вузла.
Замість цього, в головному ми оголосимо всі наші вузол речі,
і це означає, що нижче, коли ми почнемо роботи
наші містить функцію і наші функції вставки,
замість того, щоб наші містить функцію тільки за допомогою цієї глобальної змінної вузла,
ми будемо мати його прийняти в якості аргументу дерево, яке ми хочемо, щоб обробити.
Наявність глобальних змінних повинен був зробити речі простіше.
Ми збираємося зробити все важче.
Тепер візьміть хвилину або близько того, щоб просто робити такого роду речі,
де всередині основного ви хочете створити це дерево, і це все, що ви хочете зробити.
Спробуйте побудувати це дерево в основною функцією.
>> Добре. Таким чином, ви не повинні навіть побудували дерево всю дорогу поки немає.
Але у кого щось я міг би підтягнути
щоб показати, як можна було б розпочати будівництво такого дерева?
[Студент] Хтось стукіт, намагаючись вибратися назовні.
[Боуден] Будь комфортно з їх побудови дерева?
[Студент] Звичайно. Це не зроблено. >> Це нормально. Ми можемо просто закінчити -
ой, ви можете зберегти його? Ура.
Таким чином, тут ми маємо - ой, я трохи обрізаються.
Чи можу я збільшив?
Збільшення, прокрутка з. >> У мене є питання. >> Да?
[Студент] При визначенні структури, такі речі, як ініціалізується небудь?
[Боуден] Немає >> Добре. Таким чином, ви повинні ініціалізувати -
[Боуден] Немає Коли ви визначаєте, чи при оголошенні структури,
він не ініціалізований за замовчуванням, це все одно, якщо ви оголосите Int.
Це рівно те ж саме. Це як кожен з її окремих полів
може мати значення сміття в ньому. >> А чи можна визначити - чи оголосити структуру
таким чином, що це робить їх ініціалізації?
[Боуден] Так. Таким чином, контекстне синтаксис ініціалізації
буде виглядати -
Там дві, як ми можемо це зробити. Я думаю, ми повинні скомпілювати його
щоб переконатися, що Clang робить теж саме.
Порядок аргументів, який входить в структуру,
ви покладете в порядок аргументів усередині цих фігурні дужки.
Тому якщо ви хочете, щоб підготувати його до 9 і залишили бути нульовою, а потім праву бути нульовим,
було б 9, NULL, NULL.
В якості альтернативи, і редактор не подобається цей синтаксис,
і він думає, що я хочу новий блок,
але альтернатива є щось подібне -
Тут, я покладу її на новий рядок.
Можна прямо сказати, не пам'ятаю точно синтаксис.
Таким чином, ви можете явно звернутися до них по імені, і говорю:
. С, або. Значення = 9. Ліва = NULL.
Я припускаю, це необхідність бути коми.
. Право = NULL, щоб таким чином ви не
насправді потрібно знати порядок структури,
і коли ви це читаєте, це набагато більш явну
про те, що цінність буття ініціалізується.
>> Це трапляється, одна з речей, які -
так, по більшій частині, C + + є розширенням C.
Ви можете взяти C код, перемістити його на C + +, і вона повинна зібрати.
Це одна з речей, які C + + не підтримує, так що люди, як правило не робити цього.
Я не знаю, якщо це єдина причина, люди, як правило не робити цього,
але справа, де я повинен його використовувати необхідні для роботи з C + + і тому я не міг використовувати це.
Інший приклад того, що не працює з C + + є
як Танос повертає "порожнеча *," технічно,
але ви могли б просто сказати, символ * х = Танос що завгодно,
і він автоматично буде приведений до символ *.
Це автоматичний литих не буває в C + +.
Це не буде компілюватися, і ви б явно потрібно сказати
символ *, Танос, що завгодно, щоб кинути його в символ *.
Є не так багато речей, які C і C + + не згодні з,
але ці два.
Таким чином, ми підемо з цим синтаксисом.
Але навіть якщо б ми не йшли з синтаксисом,
що таке - може бути поганого в цьому?
[Студент] Мені не потрібно разименовать це? >> Да.
Пам'ятайте, що стрілка має неявний разименованія,
і тому, коли ми просто маємо справу з структурою,
Ми хочемо використовувати. щоб дістатися до поля всередині структури.
І єдиний раз, коли ми використовуємо стрілки, коли ми хочемо зробити -
Ну, стрілки еквівалентно -
ось що це означало б, якби я використовував стрілку.
Всі стрілки засіб, разименовать, тепер я в структури, і я можу отримати полю.
Або отримати полю прямо або разименованія і отримати полю -
Я думаю, це має бути значення.
Але тут я маю справу тільки з структуру, а не покажчик на структуру,
і тому я не можу використовувати стрілки.
Але такого роду речі ми можемо зробити для всіх вузлів.
О, мій Бог.
Це 6, 7 і 3.
Тоді ми можемо створити філії в нашому дереві, ми можемо мати 7 -
Ми можемо мати, його ліва повинна вказувати на 3.
Так як же нам це зробити?
[Студенти, нерозбірливо] >> Да. Адреса node3,
і якщо у вас не було адреси, то він просто не буде компілюватися.
Але пам'ятайте, що ці покажчики на наступний вузлів.
Право повинно вказувати на 9,
і 3 слід вказати на право 6.
Я думаю, що це все в порядку. Будь-які коментарі або питання?
[Студент, нерозбірливо] корінь буде 7.
Ми можемо тільки сказати, вузол * PTR =
або корінь = & node7.
>> Для наших цілей, ми будемо мати справу зі вставкою,
так що ми збираємося хочете написати функцію, щоб вставити в цю бінарне дерево
і вставки неминуче будемо називати Танос, щоб створити новий вузол цього дерева.
Так що все буде заплутатися з тим, що деякі вузли
В даний час в стеку
та інші вузли збираються в кінцевому підсумку на купі коли ми вставляємо їх.
Це цілком справедливо, але єдина причина,
ми в змозі зробити це в стеку
Тому що це такий надуманий приклад, що ми знаємо
Дерево має бути побудовано як 7, 3, 6, 9.
Якщо ми цього не було, то ми не мали б Танос в першу чергу.
Як ми побачимо трохи пізніше, ми повинні malloc'ing.
Зараз це цілком розумно поставити в стек,
але давайте змінимо цю Танос реалізації.
Таким чином, кожен з них тепер буде щось подібне
вузол * node9 = Танос (SizeOf (вузла)).
І тепер ми збираємося потрібно зробити наш чек.
якщо (node9 == NULL) - я не хочу, -
повертає 1, а потім ми можемо зробити node9-> тому що тепер це покажчик,
Значення = 6, node9-> вліво = NULL,
node9-> Право = NULL,
і ми збираємося потрібно зробити, що для кожного з цих вузлів.
Таким чином, замість, скажімо всередині окремої функції.
Давайте назвемо це вузол * build_node,
і це дещо схоже на API, ми пропонуємо для кодування Хаффмана.
Ми даємо вам ініціалізатор функцій для дерева
деконструкторів і «функції» для тих, дерева і те ж саме для лісу.
>> Отже, ми збираємося мати функцію ініціалізації
просто побудувати вузол для нас.
І це буде виглядати досить багато саме так.
І я навіть збирався бути ледачим і не змінювати ім'я змінної,
хоча node9 не має ніякого сенсу.
О, я думаю node9 значення не повинно було бути 6.
Тепер ми можемо повернутися node9.
І тут ми повинні повернутися нульовий.
Усі згодні з цим Build-A-вузла функцію?
Так що тепер ми можемо просто подзвонити, що для створення будь-якого вузла із заданим значенням і нульових покажчиків.
Тепер ми можемо викликати те, що ми можемо зробити вузол * node9 = build_node (9).
І давайте робити. . .
6, 3, 7, 6, 3, 7.
І тепер ми хочемо створити такий же покажчики,
тільки тепер все це вже в термінах покажчиків
так більше не потрібні адреси.
Добре. Так що останнє, що я хочу зробити?
Там у виправлення помилок, що я не роблю.
Що побудувати вузол натомість?
[Студент, нерозбірливо] >> Да. Якщо Танос не вдалося, він буде повертати NULL.
Так що я збираюся ліниво поклав його сюди, а не робити умова для кожного.
Якщо (node9 == NULL, або - ще простіше,
це рівносильно тому, якщо тільки не node9.
Так що, якщо не node9, або не node6, або не node3, або не node7, повернути 1.
Може бути, ми повинні друкувати Танос не вдалося, або щось ще.
[Студент] Помилково дорівнює нулю, а?
[Боуден] Будь нульове значення є хибним.
Таким чином, нульові є нульове значення.
Нуль нуль. Помилкові є нульове значення.
Будь - в значній мірі тільки 2 нульові значення не мають законної нуля,
помилковими тільки хеш визначається як нуль.
Це відноситься і якщо ми заявляємо глобальної змінної.
Якби ми мали кореневий вузол * тут,
Потім - хороша річ про глобальних змінних є те, що вони завжди мають початкове значення.
Це не правда функцій, як всередині тут,
якщо у нас є, начебто, вузла або вузла * х.
Ми поняття не маємо, що x.value, x.whatever,
або ми можемо роздрукувати їх, і вони можуть бути довільними.
Це не правда глобальних змінних.
Так кореневого вузла або вузла х.
За замовчуванням, все, що глобальне, якщо явно не ініціалізований до деякого значення,
має нульове значення як значення.
Так от, вузол * корінь, ми явно не ініціалізувати його ні до чого,
таким чином, його значення за замовчуванням буде нульовим, яка є нульове значення покажчика.
За замовчуванням значення х буде означати, що x.value дорівнює нулю,
x.left є недійсним, і x.right є недійсним.
Таким чином, так як він є структурою, всі поля структури будуть дорівнюють нулю значень.
Ми не повинні використовувати що тут, однако.
[Студент] структури відрізняються від інших змінних, і інші змінні
сміття цінностей; ці нулі?
[Боуден] Інші значення теж. Таким чином, в х, х буде дорівнювати нулю.
Якщо це в глобальній області, вона має первинне значення. >> Добре.
[Боуден] Або початкове значення ви дали його або дорівнюють нулю.
Я думаю, що бере на себе все це.
>> Добре. Так що в наступний частини питання питає,
"Тепер ми хочемо написати функцію, називається містить
з прототипом BOOL містить цілочисельне значення ".
Ми не збираємося робити BOOL містить цілочисельне значення.
Наш прототип буде виглядати
BOOL містить (цілочисельне значення.
І тоді ми також збираємося передати його дерево
що вона повинна бути перевірка, щоб побачити, якщо вона має це значення.
Таким чином, вузол * дерево). Добре.
І тоді ми можемо назвати це чимось на зразок,
може бути, ми хочемо Printf або щось.
Містить 6, наш корінь.
Це повинно повернути один або правда,
в той час як містить 5 корінь повинен повернутися помилковим.
Так що беріть другу для реалізації цього.
Ви можете зробити це або ітераційно або рекурсивно.
Гарна річ про те, як ми встановили речей є те, що
вона піддається нашому рекурсивне рішення набагато простіше
ніж глобальна змінна шляху і зробили.
Тому що, якщо ми просто містить цілочисельне значення, то немає ніякого способу рекурсії вниз піддерев.
Ми повинні були б мати окрему допоміжну функцію, яка рекурсивно вниз піддерев для нас.
Але так як ми змінили його взяти дерево в якості аргументу,
які він повинен завжди були на першому місці,
Тепер ми можемо рекурсивно більш легко.
Таким чином, ітераційний або рекурсивний, ми підемо на обох,
але ми побачимо, що рекурсивні закінчує тим, що досить легко.
Добре. Хто-небудь є щось, що ми можемо працювати з?
>> [Студент] У мене є рішення ітеративним. >> Гаразд, ітераційні.
Гаразд, це добре виглядає.
Так що, хочете йти з нами через це?
[Студент] Звичайно. Тому я тимчасову змінну, щоб отримати перший вузол дерева.
А потім я просто петельні через час температура не дорівнює нулю,
так що поки все ще був у дерево, я думаю.
І якщо значення дорівнює значенню, температура вказує на,
Потім він повертає це значення.
В іншому випадку, він перевіряє, якщо він знаходиться на правій стороні або до лівої сторони.
Якщо ви коли-небудь ситуація, коли немає більше дерев,
Потім він повертається - він виходить з циклу і повертає брехня.
[Боуден] Добре. Так що здається хорошим.
Будь-який, є коментарі на що-небудь?
У мене немає коректності коментарів взагалі.
Єдине, що ми можемо зробити це за хлопець.
О, він збирається піти трохи задовгий.
Я полагоджу, що до. Добре.
>> Кожен повинен пам'ятати, як потрійний працює.
Там безумовно були тести в минулому
, Які дають вам функції з потрійною оператор,
і говорять, перевести це, робити те, що не використовується потрійний.
Так що це дуже поширений випадок, коли я думав використовувати потрійні,
де, якщо деякі умови встановити змінну на щось,
ще встановити, що ж змінну на щось інше.
Це те, що дуже часто може бути перетворена в такого роду речі
, Де встановлено, що змінна це - або, ну, це правда? Тоді це, інакше це.
[Студент] Перша якщо це правда, чи не так?
[Боуден] Так. Те, як я завжди читав це, темп одно значення більше, ніж тимчасовий значення,
то це, інакше це. Він задає питання.
Це більше? Тоді зробіть перший крок. Решта роблять друге.
Я майже завжди - товсту кишку, я просто - у мене в голові, я читав, як решта.
>> Хто-небудь є рекурсивне рішення?
Добре. Це той, який ми збираємося - це вже може бути більшим,
але ми збираємося зробити його ще краще.
Це в значній мірі точно такий же ідеєю.
Це просто, ну, ти хочеш пояснити?
[Студент] Звичайно. Таким чином, ми переконайтеся, що дерево не є нульовим першим,
тому що, якщо дерево є нульовим, тоді вона збирається повернутися помилковим, тому що ми не знайшли його.
І якщо є ще дерево, йдемо в - ми спочатку перевіряємо, якщо значення поточного вузла.
Повернутися вірно, якщо вона є, і якщо не ми рекурсивно ліворуч або праворуч.
Звучить так це необхідно? >> Угу. (Угоду)
Так зауважити, що це майже - конструктивно дуже схожі на ітераційному розв'язанні.
Це просто, що замість рекурсії, у нас був час циклу.
І справа тут базу, де дерев не однаково NULL
була умова, при якому ми вирвалися з циклу.
Вони дуже схожі. Але ми збираємося зробити ще один крок вперед.
Тепер ми робимо те ж саме і тут.
Зверніть увагу, ми повертаємося одне і те ж в обох цих рядків,
за винятком одного аргументу інший.
Так що ми збираємося зробити це в потрійному.
Я вдарив варіант щось, і він зробив символом. Добре.
Так що ми збираємося повернутися містить цьому.
Це стає бути кілька рядків, а, збільшеної в цьому є.
Як правило, в якості стилістичного річ, я не думаю, що багато людей
поставити пробіл після стрілки, але я думаю, якщо ви послідовні, це прекрасно.
Якщо значення менше, ніж значення дерева, ми хочемо, щоб рекурсивно по дереву зліва,
ще ми хочемо, щоб рекурсивно по дереву права.
Так що було кроком одним з рішень цієї виглядати менше.
Другий крок зробити цей вид менше -
ми можемо розділити це на кілька рядків.
Добре. Крок два роблячи його схожим менше тут,
так що повернене значення дорівнює дерево значення, чи містить завгодно.
>> Це важлива річ.
Я не впевнений, якщо б він сказав, що це в явному вигляді в класі,
але це називається коротке замикання оцінки.
Ідея тут полягає значення == дерева значення.
Якщо це правда, то це дійсно так, і ми хочемо »або« що з тим, що є тут.
Таким чином, навіть не думаючи про все, що знаходиться тут,
що всі вираз збирається повернутися?
[Студент] True? >> Так, тому що істинне нічого,
з'єднані через АБО - або істинний з'єднані через АБО з чим обов'язково вірно.
Тому, як тільки ми бачимо, повертається значення = Дерево значення,
ми тільки збираємося повернутися вірно.
Навіть не збираюся рекурсивно додатково містить по лінії.
Ми можемо прийняти це ще один крок вперед.
Повернутися дерево не дорівнює NULL і все це.
Він зробив це один рядок функції.
Це також приклад короткого замикання оцінки.
Але тепер це та ж сама ідея -
замість того, щоб - так, якщо дерево не дорівнює NULL - або, ну,
якщо дерево має рівні нулю, що є поганою випадок,
якщо дерево дорівнює нулю, то перша умова буде хибним.
Так помилкова операція AND з чим буде що?
[Студент] False. >> Да. Це інша половина короткого замикання оцінки,
де, якщо дерево не дорівнюють нулю, то ми не збираємося навіть піти -
або якщо дерево має рівні нулю, то ми не збираємося робити значення == дерева значення.
Ми просто збираємося, щоб негайно повернутися помилковим.
Що важливо, так як якщо це не коротке замикання оцінки,
потім, якщо дерево має рівні нулю, це друга умова буде вини сегмента,
тому що дерево-> значення разименованія NULL.
Так ось що. Можете зробити це - перейти рази старше.
Це дуже звична річ, також, не робить це один Відповідно до цього,
але це звичайна справа в умовах, може бути, не прямо тут,
але якщо (дерево! = NULL, і дерево-> значення == значення), робити що завгодно.
Це дуже поширене захворювання, де замість того,
розірвати її на дві IFS, де завгодно, це дерево нуль?
Гаразд, це не нульовий, так що тепер це дерево значення, рівного вартості? Зробіть це.
Замість цього стану, цього ніколи не буде сегментам вина
тому що він вирветься назовні, якщо це відбудеться, є недійсними.
Ну, я думаю, якщо ваше дерево зовсім невірний покажчик, він все ще може сегментам вина,
але вона не може сегментам вина, якщо дерево є недійсним.
Якби це був нульовим, це порушило б перш, ніж ви коли-небудь разименован покажчик на перше місце.
[Студент] Це званих ледачих оцінки?
>> [Боуден] Ледачі обчислення окрема річ.
Ледачі обчислення більш, як ви просите значення,
Ви запитаєте для обчислення значення, свого роду, але ви не повинні його негайно.
Так що, поки ви насправді потрібно, воно не обчислюється.
Це не зовсім те ж саме, але в Хаффман PSET,
він говорить, що ми "ліниво" писати.
Тому ми робимо це тому, що ми насправді буферизації запису -
Ми не хочемо, щоб написати окремі біти в той час,
або окремих байтів за раз, замість цього ми хочемо отримати шматок байт.
Потім, коли у нас є шматок байт, то ми будемо його виписувати.
Навіть якщо ви попросите його написати - і FWRITE і FREAD зробити таку ж річ.
Вони буфер вашого читання і запису.
Навіть якщо ви попросите його написати відразу, він, ймовірно, не буде.
І ви не можете бути впевнені, що речі будуть написані
до виклику hfclose або що це таке,
які потім каже, гаразд, я закриваю свій файл,
це означає, що мені краще написати все, що я ще не написана.
Це не потрібно писати все з
поки ви не закриваєте файл, а потім це необхідно.
Так що це саме те, що лінь - він чекає, поки це має статися.
Це - взяти 51 і ви будете входити в його більш докладно,
тому що OCaml і все в 51, все рекурсії.
Є ніяких ітераційного рішення, в основному.
Всі рекурсії і ледачі обчислення
буде важливим для багатьох обставин
де, якщо не ліниво оцінку, це буде означати -
Прикладом є потоків, які є нескінченно довго.
У теорії, ви можете думати про натуральних чисел у вигляді потоку 1-2-3-4-5-6-7,
Так ліниво оцінювати речі в порядку.
Якщо я кажу, я хочу десятого числа, то я можу оцінити до десятого числа.
Якщо я хочу в сотий номер, то я можу оцінити до сотого номера.
Без ледачих обчислень, то він буде намагатися оцінити всі номери відразу.
Ти оцінці нескінченно багато чисел, і це просто не можливо.
Таким чином, є багато випадків, коли ліниві обчислення
просто необхідно для отримання речей на роботу.
>> Тепер ми хочемо написати вставку, де вставка буде
Аналогічно зміни в його визначенні.
Так що зараз це BOOL вставки (цілочисельне значення).
Ми збираємося змінити це BOOL вставки (цілочисельне значення, вузол * дерево).
Ми дійсно збираємося змінити це знову в трохи, ми побачимо, чому.
І давайте перейдемо build_node, просто заради цього,
вставити вище, тому ми не повинні написати прототип функції.
Які це натяк, що ви збираєтеся використовувати build_node в вставки.
Добре. Зупиніться на хвилинку за це.
Я думаю, що я врятував редакції, якщо ви хочете, щоб витягнути з цього,
або, принаймні, я зробив зараз.
Я хотіла невелику перерву, щоб думати про логіку вставки,
якщо ви не можете думати про це.
В принципі, ви тільки коли-небудь вставки на листках.
Мовляв, якщо я вставляю 1, то я неминуче буде вставка 1 -
Я зміню в чорному - I'll бути вставка 1 над тут.
Або, якщо я вставляю 4, я хочу, щоб вставка 4 над тут.
Так що не має значення, що ви робите, ви будете вставки на аркуш.
Все, що вам потрібно зробити, це ітерації вниз по дереву, поки не дійдете до вузла
, Які повинні бути батьком вузла, батько нового вузла,
, А потім змінити її вліво або вправо, покажчик, в залежності від того,
це більше або менше поточного вузла.
Змінити цей покажчик, щоб вказати на новий вузол.
Таким чином, ітерації по дереву, зробити кінцевий пункт нового вузла.
Крім того, думаю про те, чому, який забороняє тип ситуації і колись,
де я побудував двійкового дерева, де це було правильно
якщо ви дивилися тільки на одному вузлі,
але 9 був зліва від 7, якщо ви повторних вниз до упору.
Так, що це неможливо в цій ситуації, так як -
думаю про встановлення 9 або щось; на самому першому вузлі,
Я збираюся дивитися 7, і я просто збираюся йти з правого боку.
Так що не має значення, що мені робити, якщо я вставка, перейшовши на лист,
і листя допомогою відповідного алгоритму,
це буде для мене неможливо вставити 9 до лівого з 7
тому що як тільки я потрапив 7 я піду направо.
Хто-небудь є щось почати?
[Студент] я роблю. >> Звичайно.
[Студент, нерозбірливо]
[Інший студент, нерозбірливо]
[Боуден] Це цінується. Добре. Хочете пояснити?
>> [Студент] Оскільки ми знаємо, що ми вставка
нові вузли в кінці дерева,
Я петлю по дереву итеративно
поки я не дістався до вузла, який вказав на нуль.
І тоді я вирішив поставити його або на правій, або з лівої сторони
використання цього права змінна, вона сказала мені, куди його покласти.
І тоді, по суті, я тільки що зробив, що в минулому -
цієї точки температура вузла на новий вузол, який він створює,
або на лівій стороні або на правій стороні, в залежності від того, що значення прав був.
Нарешті, я встановив нове значення вузла до вартості його тестування.
[Боуден] Отже, я бачу одне питання тут.
Це як 95% шляху.
Одне питання, який я бачу, ну, хто-небудь ще бачив проблеми?
Що таке обставина, при яких вони вирватися з петлі?
[Студент] Якщо температура є недійсним? >> Да. Отже, як ви вирватися з петлі, якщо температура є недійсним.
Але те, що я роблю тут?
Я разименованія температура, яка неминуче нульовий.
Таким чином, інші, що вам потрібно зробити, це не просто відстежувати, поки температура порожній,
Ви хочете, щоб стежити за батьків у всі часи.
Ми також хочемо батьківський вузол *, я думаю, ми можемо зберегти, що при нульових на перший погляд.
Це матиме дивну поведінку для кореня дерева,
але ми повернемося до цього.
Якщо значення більше, ніж будь-який інший, то Temp = Температура права.
Але перш ніж ми це зробимо, батько = темп.
Або батьки завжди будуть рівні температурі? Чи так це?
Якщо температура не є нульовим, то я буду рухатися вниз, незважаючи ні на що,
до вузла, для якого тимчасовий батьків.
Таким чином, батько це буде тимчасовий, а потім рухатися темп вниз.
Зараз температура є дійсним, але батько вказує на батька те, що є нульовим.
Так що тут, я не хочу, щоб встановити право дорівнює 1.
Так я переїхав в праву, так що якщо правий = 1,
і я думаю, ви також хочете робити -
якщо рухатися вліво, ви хочете встановити права дорівнюють 0.
Або ж, якщо ви коли-небудь рухатися вправо.
Таким чином, право = 0. Якщо право = 1,
Тепер ми хочемо, щоб батьки право newnode покажчик,
ще ми хочемо, щоб батьки лівої newnode покажчик.
Питань з цього приводу?
Добре. Отже, це те, як ми - ну, насправді, а не робити цього,
Ми майже очікував використовувати build_node.
І потім, якщо newnode дорівнює нулю, повернутися помилковим.
Ось і все. Тепер, це те, що ми очікували, що ви робите.
>> Це те, що співробітники рішень роблять.
Я не згоден з цим, як "правильний" спосіб йти про нього
Але це чудово, і вона буде працювати.
Єдине, що трохи дивно прямо зараз
якщо дерево починається як нульові, ми передаємо в нульове дерево.
Я думаю, це залежить від того, як визначати поведінку проходять в нульових дерева.
Я думаю, що якщо ви проходите в нульове дерево,
потім вставити значення в нульовий дерева
треба просто повернути дерево, де єдина цінність у тому, що один вузол.
У людей з цим згодні? Ви могли б, якщо б ви хотіли,
якщо ви проходите в нульове дерево
і ви хочете вставити значення в ній, повернутися помилковим.
Це до вас, щоб визначити, що.
Для цього перше, що я сказав, а потім -
добре, ви будете мати проблеми роблять це, тому що
було б легше, якби ми мали глобальний покажчик на річ,
але у нас немає, так що якщо дерево є нульовим, то ми нічого не можемо з цим зробити.
Ми можемо просто повернутися помилковим.
Так що я збираюся змінити вставки.
Ми технічно міг би просто змінити це прямо тут,
як це ітерації речі,
але я збираюся змінити вставки прийняти вузла ** дерево.
Двомісний покажчиків.
Що це значить?
Замість того, щоб мати справу з покажчиками на вузли,
що я збираюся бути маніпулювання це покажчик.
Я збираюся бути маніпулювання цей покажчик.
Я збираюся бути маніпуляцій покажчиками напряму.
Це має сенс, оскільки, думаю про вниз -
Ну, зараз це вказує на нуль.
Те, що я хочу зробити, це управляти цією покажчик, щоб вказати на не нульовий.
Я хочу, щоб вона вказувала на моєму новому вузлі.
Якби я просто стежити за покажчиками на мій покажчиків,
то мені не потрібно стежити за предка.
Я можу тільки стежити, щоб переконатися, що покажчик направлений до нуля,
і якщо покажчик вказує на нуль,
змінити його, щоб вказати на вузол я хочу.
І я можу змінити його, так як у мене є покажчик на покажчик.
Давайте подивимося це прямо зараз.
Ви дійсно можете зробити це рекурсивно досить легко.
Чи хочемо ми це зробити?
Так, ми робимо.
>> Давайте подивимося, що рекурсивно.
По-перше, те, що наш базовий сценарій буде?
Майже завжди наш базовий сценарій, але насправді, це ніби складно.
Насамперед, якщо (дерево == NULL)
Я думаю, ми просто збираємося, щоб повернутися помилковим.
Це відрізняється від вашого дерева бути нульовим.
Це покажчик на кореневий покажчик бути нульовим
Це означає, що ваш кореневої покажчик не існує.
Так що тут, якщо я роблю
вузол * - давайте просто повторно використовувати цей.
Node * корінь = NULL,
і тоді я буду називати вставки, роблячи щось подібне,
вставте 4 і в корені.
Так і кореня, якщо корінь вузол *
то і корінь буде вузлом. **
Це справедливо. У цьому випадку, дерево, тут,
Дерево не порожній - або вставки.
Тут. Дерево не є нульовим; * Дерево є недійсним, і це добре
тому що, якщо * Дерево є нульовим, то я можу керувати ним
в даний час вказують на те, що я хочу, щоб це вказують.
Але якщо дерево є порожнім, це означає, що я тільки що прийшов сюди і сказав, нульовий.
Це не має сенсу. Я нічого не можу зробити з цим.
Якщо дерево є порожнім, повернутися помилковим.
Так що я в принципі вже говорив, що наші реальні справи бази.
І що це буде?
[Студент, нерозбірливо]
[Боуден] Так. Так що, якщо (* дерево == NULL).
Це відноситься до випадку тут
де, якщо мій червоний покажчик вказує я зосереджений на,
так як я зосереджений на цей покажчик, зараз я зосереджений на цей покажчик.
Зараз я зосереджений на цей покажчик.
Так що, якщо мій червоний покажчик, який є моїм ** вузла,
це все - якщо *, моя червона стрілка, це ніколи не нульовий,
це означає, що я перебуваю в тому випадку, коли я зосереджений на покажчик, який вказує -
це покажчик, який належить аркуша.
Я хочу змінити цей покажчик, щоб вказати на моєму новому вузлі.
Приходьте сюди.
Мій newnode буде просто вузол * п = build_node (вартість)
Потім п, якщо п = NULL, повертає брехня.
Решту ми хочемо змінити те, що покажчик в даний момент вказує
в даний час вказують на нашому новому вузлі.
Ми можемо реально зробити це тут.
Замість того щоб сказати я, ми говоримо * = дерево, якщо дерево *.
Всі розуміють, що? Це, маючи справу з покажчиками на покажчики,
ми можемо змінити нульові покажчики вказують на те, що ми хочемо, щоб вони вказують.
Це наш базовий сценарій.
>> Тепер наші рецидиву, або наш рекурсії,
буде дуже схожий на всі інші рекурсії ми робили.
Ми збираємося хочете вставити значення,
і тепер я збираюся використовувати потрійні знову, але те, що наша умова буде?
Що це ми шукаємо вирішити, чи хочемо ми йти вліво або вправо?
Давайте робити це в окремих кроків.
Якщо (значення <) що?
[Студент] Значення дерево?
[Боуден] Тому пам'ятайте, що я в даний час -
[Студенти, нерозбірливо]
[Боуден] Так, так прямо тут, скажемо, що ця зелена стрілка
є прикладом того, що дерево в даний час, є покажчиком на цей покажчик.
Таким чином, це означає, що я покажчик на покажчик до 3.
Разименованія двічі звучало добре.
Що мені - як я можу це зробити?
[Студент] Dereference один раз, а потім зробити стрілки таким чином?
[Боуден] Таким чином, (* дерево) є разименованія один раз, -> значення
збирається дати мені значення вузла, що я побічно вказує.
Так що я теж можу писати ** tree.value, якщо ви віддаєте перевагу це.
Або працює.
Якщо це так, то я хочу звернути вставити зі значенням.
І те, що мій оновлений вузол ** буде?
Я хочу піти наліво, так ** tree.left буде ліворуч від мене.
І я хочу, покажчик на цю річ
так що якщо ліва закінчує тим, що нульовий покажчик,
Я можу змінити його, щоб вказати на моєму новому вузлі.
>> І в іншому випадку можуть бути дуже схожі.
Давайте реально зробити, що мій потрійний прямо зараз.
Вставте значення, якщо значення <(** дерево). Значення.
Потім ми хочемо оновити нашу ** вліво,
ще ми хочемо оновити нашу ** вправо.
[Студент] Чи означає це, що отримати покажчик на покажчик?
[Боуден] Пам'ятайте, що - ** tree.right є вузлом зірки.
[Студент, нерозбірливо] >> Да.
** Tree.right, як цей покажчик або щось.
Таким чином, приймаючи покажчик на те, що це дає мені те, що я хочу
покажчика на цього хлопця.
[Студент] Чи можемо ми піти знову, чому ми використовуємо два покажчика?
[Боуден] Так. Так що - ні, ви можете, і це рішення до
був спосіб зробити це, не роблячи двох покажчиків.
Ви повинні бути в змозі зрозуміти за допомогою двох покажчиків,
і це чисте рішення.
Крім того, зауважив, що те, що відбувається, якщо моє дерево -
Що станеться, якщо мій корінь був нульовим? Що станеться, якщо я зроблю це випадок прямо тут?
Таким чином, вузол * корінь = NULL, вставте 4 і в корені.
Те, що корінь буде після цього?
[Студент, нерозбірливо] >> Да.
Коренева значення буде 4.
Коренева лівого буде нульовим, корінь право буде нульовим.
У разі, коли ми не пройшли корінь за адресою,
ми не могли змінити корінь.
У разі, коли дерево - де корінь був нульовим,
ми просто повинні були повернутися помилковим. Там немає нічого, що ми могли зробити.
Ми не можемо вставити вузол в порожнє дерево.
Але тепер ми можемо, ми просто зробити порожнє дерево в одній вузла дерева.
Яка зазвичай очікуваним чином, що воно має працювати.
>> Крім того, це значно менше, ніж
Також стежити за батьками, і тому ви ітерації до упору.
Тепер у мене є мої батьки, і я просто мої батьки право покажчик на що завгодно.
Замість цього, якщо б ми робили це багато разів, це було б те ж ідею з циклу.
Але замість того, щоб мати справу з моїми батьками покажчик,
Замість мого поточного покажчика б річ
що я безпосередньо змінювати, щоб вказати на моєму новому вузлі.
Я не доводиться мати справу з того, що це вказує на лівому.
Я не доводиться мати справу з того, що це вказує на права.
Це просто, що цей покажчик, я збираюся встановити його, щоб вказати на моєму новому вузлі.
Всі розуміють, як це працює?
Якщо ні, то чому ми хочемо зробити це таким чином,
але принаймні, що це працює як рішення?
[Студент] Куди ми повертаємося правда?
[Боуден] Це, напевно, прямо тут.
Якщо ми правильно вставити його, повернути істинний.
В іншому випадку, тут ми збираємося хочете повернути все повертається вставки.
>> А що особливого в цій рекурсивної функції?
Це хвіст рекурсивної, так як поки ми складаємо з деякої оптимізації,
вона буде визнати, що і ви ніколи не отримаєте переповнення стека з цього,
навіть якщо наше дерево має висоту 10.000 чи 10 мільйонів.
[Студент, нерозбірливо]
[Боуден] Я думаю, що він це робить на Dash - або те, що рівень оптимізації
вимагається для хвостовій рекурсії щоб бути визнаним.
Я думаю, що він визнає - GCC і Clang
Також мають різні значення для їх рівня оптимізації.
Я хочу сказати, що це Дашо 2, переконатися, що він не визнає хвостовій рекурсії.
Але ми - ви можете побудувати, як наприклад Fibonocci або щось.
Це не легко перевірити за цим, тому що це важко побудувати
бінарне дерево, що такий великий.
Але так, я думаю, що це Дашо 2,
Якщо ви компілюєте з Дашо 2, він буде шукати хвостову рекурсію
і оптимізувати це.
Давайте повернемося до - вставити буквально останнім, що йому потрібно.
Давайте повернемося до вставці тут
де ми збираємося робити ту ж ідею.
Він все ще будете мати недолік не в змозі повністю впоратися
коли сам корінь є порожнім, або минуле вступу порожній,
але замість того щоб впоратися з одним з батьків покажчик,
Давайте застосувати ту ж логіку зберігання покажчиків на покажчики.
Якщо при цьому ми продовжуємо наш вузол ** текущ.,
і нам не потрібно стежити за право більше,
але вузлі ** = текущ. та дерева.
І тепер наша в той час як цикл буде час * струму не дорівнює нулю.
Не потрібно стежити за батьків більше.
Не потрібно стежити за ліву і праву.
І я буду називати його темп, тому що ми вже використовує темп.
Добре. Так що, якщо (значення> * температура),
то й (* температура) -> Право
ще Temp = & (* температура) -> пішов.
І зараз, в даний момент, після цього час циклу,
Я тільки роблю це тому, можливо, легше думати про що багаторазово рекурсивно,
але після цього час циклу,
* Тимчасовий покажчик ми хочемо змінити.
>> Перш, ніж ми мали батьків, і ми хотіли змінити чи лівої батьків або батька права,
Але якщо ми хочемо змінити батьківський прав,
Потім * тимчасовий батьки мають рацію, і ми можемо змінити його безпосередньо.
Так що тут, внизу, ми можемо зробити * Temp = newnode, ось і все.
Таким чином, повідомлення, все, що ми зробили в цьому було вивезти рядків коду.
Для того, щоб стежити за батьків у всьому, що додаткові зусилля.
При цьому, якщо ми просто стежити за покажчиком на покажчик,
і навіть якщо б ми хотіли, щоб позбутися від усіх цих фігурні дужки зараз,
зробити його коротшим.
Це тепер точно такий же розчин,
але менше рядків коду.
Як тільки ви починаєте визнаючи це як правильне рішення,
це також легше розмірковувати про що, як, в порядку,
чому я повинен цим прапором на Int вірно?
Що це значить? О, це означало, що
кожен раз, коли я йду рацію, мені потрібно, щоб встановити його,
ще, якщо я йду залишив мені потрібно встановити його до нуля.
Ось, у мене немає причин, щоб про це, це просто легше думати.
Питання?
[Студент, нерозбірливо] >> Да.
Отже, в останній біт -
Я думаю, одна швидкий і простий функції ми можемо зробити, це,
let's - разом, я думаю, спробувати і написати функцію, містить
який не дбає, чи є це бінарне дерево пошуку.
У ньому міститься функція повинна повертати істинним
якщо де-небудь в цьому загальному бінарне дерево є значення, яке ми шукаємо.
Так давайте робити це рекурсивно, і тоді ми будемо робити це повторно.
Ми можемо насправді просто робити це разом, тому що це буде дуже коротким.
>> Те, що мій базовий варіант буде?
[Студент, нерозбірливо]
[Боуден] Так що, якщо (дерево == NULL), то що?
[Студент] Повернутися помилковим.
[Боуден] інше, ну, мені не потрібно іншого.
Якщо був моїм другом випадку база.
[Студент] Дерева значення? >> Да.
Так що, якщо (дерево-> значення == значення.
Зверніть увагу, що ми повернулися до вузла *, а не вузла ** и?
Містить ніколи не потрібно буде використовувати вузол **
так як ми не змінюємо покажчиків.
Ми просто через них.
Якщо це відбудеться, то ми хочемо повернути істинний.
Решту ми хочемо, щоб перетнути дітей.
Тому ми не можемо міркувати про те, щоб все залишилося менше
і все, що правіше більше.
Так що ж наш стан буде тут - або, що ми будемо робити?
[Студент, нерозбірливо] >> Да.
Повернутися містить (значення, дерево-> ліворуч)
або містить (значення, дерево-> праворуч). І це все.
І зверніть увагу, є деяке коротке замикання оцінки,
де, якщо ми, трапляється, знайти значення в лівому дереві,
Ми ніколи не повинні дивитися на правому дереві.
Це ціла функція.
Тепер давайте робити це багато разів,
який буде менш приємно.
Ми візьмемо звичайну початку вузла * текущ. = Дерево.
У той час (поточн.! = NULL).
Швидко збираємося бачу проблеми.
Якщо текущ. - Тут, якщо ми коли-небудь вирватися з цього,
Потім ми запускаємо з речей, щоб дивитися на, так що повернутися помилковим.
Якщо (в даний> значення == значення), повернутися вірно.
Отже, тепер ми знаходимося на місці -
Ми не знаємо, чи хочемо ми, щоб піти наліво або направо.
Таким чином, довільно, давайте просто піти наліво.
Я, очевидно, зіткнулися з питанням, де я повністю відмовилася від усього -
Я тільки коли-небудь перевірити лівій стороні дерева.
Я ніколи не буду перевірити все, що право дитини на все.
Як я можу це виправити?
[Студент] Ви повинні стежити за лівий і правий в стеці.
[Боуден] Так. Так давайте зробимо це
Структура списку вузлів * N, а потім вузол ** далі?
Я думаю, що відмінно працює.
Ми хочемо йти по лівій або let's - тут.
Struct = список список, він почне
при цьому структура списку.
* Список = NULL. Так що це буде наш пов'язаного списку
піддерев, які ми пропустили.
Ми збираємося пройти залишилося,
але так як ми неминуче повинні повернутися до права,
Ми збираємося тримати в правій частині всередині нашої структури списку.
Тоді ми будемо мати new_list або структури,
Структура списку *, new_list = Танос (SizeOf (список)).
Я збираюся ігнорувати перевірки помилок, але ви повинні перевірити, якщо це нульовий.
New_list вузла це буде вказувати на -
Ах, ось чому я хотів його тут. Це буде вказувати на другий список структуру.
От тільки як зв'язані списки робіт.
Це те ж саме, як Int зв'язаний список
крім ми просто замінивши Int з вузлом *.
Це точно так само.
Так new_list, вартість наших new_list вузла,
буде струм> рацію.
Цінність нашого new_list-> наступний буде наш початковий список,
, А потім ми будемо оновлювати наш список, щоб вказати на new_list.
>> Тепер нам потрібно якийсь спосіб витягування речей,
як у нас пройшов увесь лівого піддерева.
Тепер нам потрібно витягнути речі з нього,
як струму є нульовим, ми не хочемо, щоб просто повернутися помилковим.
Ми хочемо зараз тягнути за межами на нашому новому списку.
Зручний спосіб зробити це - добре, насправді, є кілька способів зробити це.
Будь-який, є пропозиції?
Де я повинен це зробити, або, як я повинен це зробити?
У нас є тільки пара хвилин, але які-небудь пропозиції?
Замість того, щоб - в одну сторону, а наші умовою є час,
те, що ми в даний час дивимося на це не нульовий,
Замість цього ми збираємося продовжувати йти, поки наші Сам список є порожнім.
Таким чином, якщо наш список закінчує тим, що нульовий,
Потім ми запустили з речей, щоб шукати, шукати більш.
Але це означає, що в першу чергу в нашому списку тільки збирається стати першим вузлом.
Найперше, що буде - ми більше не повинні бачити, що.
Таким чином, список-> N буде наше дерево.
Список-> наступна буде нульовим.
І зараз, поки список не дорівнює нулю.
Cur збирається витягнути щось з нашого списку.
Так текущ. Буде рівним список-> л.
І тоді список буде рівним список-> п, або список-> далі.
Так що, якщо текущ. Значення дорівнює значенню.
Тепер ми можемо додати і наше право і наш покажчик лівого покажчика
тих пір, поки вони не нульові.
Тут, внизу, я думаю, ми повинні були це зробити в першу чергу.
Якщо (в даний> праві! = NULL)
Потім ми збираємося, щоб вставити цей вузол в наш список.
Якщо (в даний> ліворуч), це трохи додаткової роботи, але це нормально.
Якщо (в даний> зліва! = NULL),
і ми збираємося, щоб вставити ліворуч в нашу зв'язаний список,
і що повинно бути.
Ми ітерації - поки у нас є щось у нашому списку
у нас є ще один вузол на що подивитися.
Таким чином, ми дивимося на цей вузол,
ми просуваємо наш список в наступному.
Якщо вузол є значення, яке ми шукаємо, ми можемо повернутися вірно.
Решта вставити обидві наші ліві і праві піддерев,
тих пір, поки вони не нульовий, в нашому списку
так що ми неминуче йдуть за ними.
Так що, якщо вони не були нульові,
якщо наш кореневої покажчик вказував на дві речі:
Потім ми спочатку витягнув щось з нашого списку так закінчує тим, що нульовий.
І тоді ми ставимо дві речі назад, так що тепер наш список має розмір 2.
Потім ми збираємося циклу резервного копіювання і ми тільки збираємося тягти,
скажімо, лівий покажчик нашого кореневого вузла.
І це буде просто тримати відбувається, ми закінчимо цикл над усім.
>> Зверніть увагу, що це було значно складніше
У рекурсивне рішення.
І я вже говорив кілька разів
, Що рекурсивне рішення, як правило, має багато спільного з вирішенням ітеративним.
Ось це саме те, що рекурсивне рішення робить.
Єдина зміна полягає в тому, що замість неявно за допомогою стека, стек програми,
як ваш спосіб відслідковувати, які вузли ви все ще повинні відвідати,
Тепер ви повинні явно використовувати зв'язаний список.
В обох випадках ви відстеження того, що вузол ще потрібно відвідати.
У рекурсивному випадку це просто легше, тому що стек
реалізується для вас, як стек програми.
Зверніть увагу, що це зв'язаний список, це стек.
Все, що ми просто покласти в стек
відразу, що ми збираємося витягти з стека, щоб відвідати наступний.
Ми поза часом, але є питання?
[Студент, нерозбірливо]
[Боуден] Так. Так що, якщо у нас є зв'язаний список,
Струм буде вказувати на цього хлопця,
і тепер ми просто просування наших зв'язаний список, щоб зосередитися на цього хлопця.
Ми переміщення через зв'язаний список у цьому рядку.
І тоді я думаю, ми повинні звільнити наші зв'язаний список та інше
разів, перш ніж повернутися істинним або хибним, ми повинні
перебору наших зв'язаний список і завжди тут, я думаю,
якщо ми текущ. право не є рівним, додайте його, так що тепер ми хочемо, щоб звільнити
текущ. тому що, ну, хіба ми абсолютно забуваємо про список? Так.
Так ось що ми хочемо зробити тут.
Де покажчик?
Cur було потім - ми хочемо, щоб список структур * 10 дорівнює списку поруч.
Безкоштовні список, список = темп.
І в разі, коли ми повертаємося правда, нам потрібно ітерації
протягом решти наші зв'язаний список, звільняючи речі.
Гарна річ про рекурсивні рішення визволення речі
просто означає, з'являються factorings стека, які відбуватимуться для вас.
Таким чином, ми пішли від чогось, що походить на 3 лінії важко думати про код-
до того, що значно багато інших важко думати-о рядках коду.
Є ще питання?
Добре. Ми добре. Bye!
[CS50.TV]