[Powered by Google Translate] [Частина 7] [менш комфортно]
[Nate Хардісон] [Harvard University]
[Це CS50.] [CS50.TV]
>> Ласкаво просимо до розділу 7.
Завдяки ураган Sandy,
замість того нормального перерізу на цьому тижні,
Ми робимо це прохідний, через розділ питань.
Я збираюся бути наступні Поряд з проблемою Set 6 Специфікація,
і переживає всі питання в
Розділ розділу Питання.
Якщо є які-небудь питання,
будь ласка, напишіть їх на CS50 обговорити.
>> Добре. Давайте почнемо.
Прямо зараз я дивлюся на стор 3 Специфікація поставленого завдання.
Ми йдемо до першого почати розмову про бінарних дерев
З тих є багато, що мають відношення до проблеми набору на цьому тижні -
Кодування Хаффмана дерева.
Один з найперших структур даних ми говорили про на CS50 був масиву.
Пам'ятайте, що масив являє собою послідовність елементів -
Все ж типу - зберігаються поруч один з одним в пам'яті.
Якщо у мене є масив цілих чисел, що я можу зробити за допомогою цієї коробки-числа-цілі стиль -
Скажімо, у мене є 5 в першому полі, у мене 7 в другій,
то у мене є 8, 10, та 20 в кінцевому полі.
Пам'ятайте, що два дійсно хороших речей про це масиві
в тому, що у нас є ця постійна часу доступ до будь-який конкретний елемент
в масиві, якщо ми знаємо його індекс.
Наприклад, якщо я хочу, щоб захопити третій елемент масиву -
з індексом 2, використовуючи нашу з нуля системи -
Я буквально тільки що потрібно зробити простий математичний розрахунок,
стрибати на цю посаду в масиві,
витягніть 8, який зберігається там,
і я добре йти.
>> Один з поганих речей про це масиву - про які ми говорили
Коли ми обговорювали зв'язані списки -
є те, що якщо я хочу, щоб вставити елемент у цьому масиві,
Я збираюся зробити деяке переміщення навколо.
Наприклад, цей масив прямо тут
є в певному порядку - відсортовані в порядку зростання -
5, потім 7, потім 8, потім 10, а потім 20 -
але якщо я хочу, щоб вставити номер 9 у цьому масиві,
Я хочу, щоб перенести деякі елементи для того, щоб звільнити місце.
Ми можемо зробити це тут.
Я збираюся повинні рухатися 5, 7, а потім 8;
створити зазор, де я можу поставити 9,
, А потім 10 і 20 може піти в праві 9.
Це свого роду болю, тому що в гіршому випадку -
коли ми того, щоб вставити або на початку, або в кінці
масиву, в залежності від того, як ми зміщення -
Ми могли б у кінцевому підсумку того, щоб зрушити всі елементи
що ми в даний час зберігання в масиві.
>> Отже, що був спосіб обійти це?
Спосіб обійти це був піти у наш пов'язаного списку метод, де -
замість зберігання елементів 5, 7, 8, 10 і 20 все поруч один з одним в пам'яті -
Замість того, що ми робили, було зберігати їх виду, де б ми хотіли, щоб зберегти їх
У цих зв'язаний список вузлів, які я малюю тут, начебто спеціальних.
І тоді ми з'єднали їх разом, використовуючи ці наступні покажчики.
Я можу їсти покажчик від 5 до 7,
Покажчик від 7 до 8,
Покажчик від 8 до 10,
І, нарешті, покажчик від 10 до 20,
, А потім нульовим покажчиком на 20 про те, що там нічого не залишилося.
Компроміс, що ми маємо тут
є те, що тепер, якщо ми хочемо, щоб вставити номер 9 в нашій відсортований список,
все, що нам потрібно зробити, це створити новий вузол з 9,
підключити його до точки в потрібне місце,
, А потім повторно дроти від 8 до точки до 9.
Це досить швидко, припускаючи, що ми точно знаємо, де ми хочемо, щоб вставити 9.
Але компроміс в обмін на це, що ми тепер втратили постійне час доступу
будь-який конкретний елемент в нашій структурі даних.
Наприклад, якщо я хочу знайти четвертий елемент у цій пов'язаного списку,
Я збираюся мати, щоб почати на самому початку списку
і працює свій шлях через рахунки вузла-на-вузлі, поки не знайду четвертий.
>> Для того щоб отримати більш широкий доступ продуктивність, ніж зв'язаний список -
але і зберегти деякі з переваг, які у нас були
В умовах введення часу від пов'язаного списку -
бінарне дерево буде необхідно використовувати трохи більше пам'яті.
Зокрема, замість того, щоб просто мати один покажчик в бінарному дереві вузлів -
як зв'язаний список вузлів робить -
Ми збираємося додати другий покажчик на двійковий вузла дерева.
Замість того, щоб просто мати один покажчик на наступний елемент,
ми будемо мати покажчик на лівий дитини та право дитини.
>> Давайте намалюємо картинку, щоб подивитися, що насправді виглядає.
Знову ж таки, я збираюся використовувати ці коробки і стріли.
Бінарний вузол дерева буде почати з простою коробці.
Це буде мати місце для значення,
а потім він також буде мати простір для лівого дитини та право дитини.
Я буду називати їх тут.
Ми збираємося у ліва дитини, і тоді ми будемо мати право дитини.
Є багато різних способів зробити це.
Іноді для простору і зручності,
Я насправді зробити це, як я роблю тут на дні
де я збираюся мати значення у верхній частині,
, А потім праву дитини на правій нижній,
і лівої дитини на лівій нижній.
Повертаючись до цієї вершини діаграми,
у нас є значення на самому верху,
Потім у нас є лівий покажчик дитини, і тоді ми маємо право дитині покажчик.
>> У специфікації поставленого завдання,
ми говоримо про розробку вузла, який має значення 7,
, А потім ліву дитини покажчик, який є порожнім, і права дитини-покажчик, який є нульовим.
Ми можемо або написати капіталу NULL в просторі для
як лівої дитини та право дитини, або ми можемо зробити це коса риска
в кожному з коробки, щоб вказати, що це нульовий.
Я збираюся зробити це просто, тому що це простіше.
Те, що ви бачите тут два способи побудови діаграм дуже простий вузол двійкового дерева
де у нас є значення 7 і нульових покажчиків дитини.
>> Друга частина нашої специфікації переговори про те, як зі зв'язаними списками -
Пам'ятаєте, ми тільки повинні були триматися за перший елемент у списку
пригадати весь список -
і аналогічно, з бінарним деревом, ми тільки повинні тримати на одного покажчика на дереві
З метою збереження контролю над усією структурою даних.
Цей спеціальний елемент дерева називається кореневим вузлом дерева.
Наприклад, якщо цей вузол - це вузол, що містить значення 7
з нульовою лівої і правої дитині покажчики -
були єдиною цінністю в нашому дереві,
то це буде нашим кореневим вузлом.
Це самий початок нашого дерева.
Ми можемо побачити це трохи ясніше, як тільки ми почнемо додавати додаткові вузли до нашого дереву.
Дозвольте мені підтягти нову сторінку.
>> Тепер ми будемо малювати дерево, яке має 7 на корені,
і 3 внутрішній стороні лівого дитини, і 9 в правому дитини.
Знову ж таки, це досить просто.
У нас є 7, намалювати вузол 3, вузол 9,
і я збираюся встановити лівий покажчик дитини від 7 до вказують на вузол, що містить 3,
і право дитини покажчик вузол, що містить від 7 до вузол, що містить 9.
Тепер, так як 3 і 9 не мають дітей,
ми збираємося встановити всі їх покажчики дитини, є недійсними.
Тут корінь нашого дерева відповідає вузол, що містить номер 7.
Ви можете бачити, що якщо всі ми маємо покажчик на кореневий вузол,
ми можемо пройти через наше дерево і доступ як дочірні вузли -
як 3 і 9.
Не потрібно зберегти покажчики на кожному вузлі дерева.
Добре. Тепер ми збираємося додати ще один вузол до цієї схеми.
Ми збираємося додати вузол, що містить 6,
і ми збираємося додати його в якості правого нащадка вузла, що містить 3.
Щоб зробити це, я збираюся стерти цю нульового покажчика в 3-вузлі
і підключити його до вказувала на вузол, що містить 6. Добре.
>> На даний момент, давайте перейдемо трохи термінології.
Для початку, причина того, що це називається бінарне дерево, зокрема,
є те, що вона має два покажчика дитини.
Є й інші види дерев, які мають більше покажчиків дитини.
Зокрема, ви зробили "спробувати" в проблемі Set 5.
Ви помітите, що в цій спробі, у вас було 27 різних покажчиків на різні діти -
по одному для кожної з 26 букв англійського алфавіту,
, А потім 27-й по апострофа -
так, що схожий на тип дерева.
Але тут, так як це двійковий, у нас є тільки два покажчика дитини.
>> На додаток до цієї кореневий вузол, що ми говорили про те,
Ми також кидали навколо цього терміна "дитина".
Що це означає для одного вузла, щоб бути нащадком іншого вузла?
Це буквально означає, що дитина вузол є нащадком іншого вузла
якщо інший вузол має одну з його дочірніх покажчики встановлені, щоб вказати на цьому вузлі.
Щоб поставити це в більш конкретних термінах,
якщо 3, вказав на одну дитину покажчики 7, потім 3 є дочірнім 7.
Якби ми могли зрозуміти, що діти до 7 років -
Ну, ми бачимо, що 7 має покажчик на 3 та покажчик на 9,
тому 9 і 3 дітей 7.
Дев'ять дітей немає, тому що його покажчики дитини є недійсними,
і 3 має тільки одну дитину, 6.
Шість також не має дітей, тому що обидва його покажчики є недійсними, яку ми будемо малювати прямо зараз.
>> Крім того, ми також говоримо про батьків конкретного вузла,
і це, як і слід було очікувати, зворотний цієї дитини опису.
Кожен вузол має тільки одного батька - замість двох, як ви могли б очікувати з людьми.
Наприклад, батько 3, 7.
Батько 9 також 7 і батьків 6, 3. Не так багато до нього.
У нас також є умови, щоб говорити про бабусь і дідусів і внуків,
і взагалі ми говоримо про предків
і нащадків конкретного вузла.
Предком вузла - або предків, швидше, вузол -
Всі вузлів, які лежать на шляху від кореня до цього вузла.
Наприклад, якщо я дивлюся на вузлі 6,
Потім предки збираються бути як 3 і 7.
Предки 9, наприклад, є - якщо я дивлюся на вузлі 9 -
Потім предка з 9 знаходиться всього в 7.
І нащадки в точності навпаки.
Якщо я хочу подивитися на всі нащадки 7,
Потім я повинен дивитися на всі вузли під ним.
Отже, у мене є 3, 9 і 6, всі як нащадки 7.
>> Останній термін, який ми будемо говорити про це поняття буття рідного брата.
Брати і сестри - на кшталт наступних разом на цих сімейних умовах -
вузли, які знаходяться на тому ж рівні в дереві.
Так, 3 і 9 братів і сестер, тому що вони на тому ж рівні в дереві.
Вони обидва мають одного батька, 7.
6 не має братів і сестер, бо 9 не має дітей.
І 7 не має братів і сестер, тому що це корінь нашого дерева,
і є тільки коли-небудь 1 корінь.
На 7 братів і сестер, щоб там мали б бути вище 7 вузлів.
Там повинно було б бути батьком 7, в якому випадку 7 більше не буде коренем дерева.
Потім, що нові батьки з 7 також буде мати дитину,
і що дитина б тоді брат 7.
>> Добре. Рухаємося далі.
Коли ми почали нашу розмову про бінарних дерев,
ми говорили про те, як ми збираємося використовувати їх для
отримати перевагу над обох масивів і пов'язаних списків.
І те, як ми збираємося зробити це з цим замовленням власності.
Ми говоримо, що бінарне дерево упорядкований, у відповідності зі специфікацією,
якщо для кожного вузла в дереві, всі його нащадки зліва -
лівий дитині, і всіх нащадків лівої дитини -
мають менші значення, а все вузли справа -
права дитини і всіх нащадків права дитини -
є вузли більше, ніж значення поточного вузла, що ми дивимося.
Просто для простоти ми будемо вважати, що немає ніяких дублюючих вузлів у нашому дереві.
Наприклад, в цьому дереві ми не збираємося мати справу з випадком
де у нас є значення 7 в корені
і у нас також є значення 7 в іншому місці в дерево.
У цьому випадку, ви помітите, що це дерево дійсно замовлено.
У нас є значення 7 на корені.
Всі зліва від 7 -
якщо я відміню всі ці маленькі знаки тут -
все, що зліва від 7 - 3 і 6 -
ці значення знаходяться менш ніж в 7, і все, що правіше - що саме це 9 -
більше 7.
>> Це не тільки впорядковане дерево, що містять ці значення,
Але давайте намалювати кілька з них.
Існує насправді ціла купа способів, якими ми можемо це зробити.
Я збираюся використовувати скорочену тільки, щоб тримати речі простими, де -
, А не розтягуючи цілому коробки-і-стрілки -
Я просто хочу звернути номерів і додати стрілки, що з'єднують їх.
Для початку, ми будемо просто писати свої оригінальні дерево ще раз, де у нас було 7, а потім 3,
, А потім 3 зазначено назад в праві на 6,
і 7 мали право дитини, яка була 9.
Добре. Які ще один спосіб, що ми могли б написати це дерево?
Замість того, щоб бути 3 лівий дитини 7,
Ми також могли б бути 6 лівому дитини 7,
, А потім 3 буде лівий дитини 6.
Це буде виглядати наступним чином дерево прямо тут, де у мене 7,
потім 6, потім 3, і 9 праворуч.
Ми також не повинні мати 7, як наш кореневий вузол.
Ми могли б також мати 6, як наш кореневий вузол.
Що б виглядати?
Якщо ми збираємося зберегти цю наказав власності,
все, що лівіше з 6 повинен бути менше, ніж вона.
Там тільки одна можливість, і ось 3.
Але тоді, як право дитини з 6, у нас є дві можливості.
По-перше, ми могли б 7, а потім 9,
або ми можемо зробити це - як я збираюся зробити тут -
де у нас є 9, права дитини 6,
, А потім 7 в якості лівого дитиною з 9.
>> Тепер, 7 і 6 не є єдино можливими значеннями кореня.
Ми могли б також мати 3 бути докорінно.
Що відбудеться, якщо 3 є в корені?
Тут все стає трохи цікавіше.
Три не має ніякого значення, які менше, ніж він,
так що вся ліва сторона дерева просто буде нульовою.
Там не буде нічого немає.
Праворуч, ми могли б перерахувати речі в порядку зростання.
Ми могли б 3, то 6, то 7, то 9.
Або, ми могли б зробити 3, то 6, то 9, то 7.
Або, ми могли б зробити 3, потім 7, потім 6, потім 9.
Або, 3, 7 - насправді немає, ми не можемо зробити 7 більше.
Це наша одне там.
Ми можемо зробити 9, а потім з 9 ми можемо зробити 6, а потім 7.
Або, що ми можемо зробити 3, то 9, то 7, а потім 6.
>> Одна річ, щоб звернути вашу увагу на тут
що ці дерева трохи дивний вигляд.
Зокрема, якщо ми дивимося на 4 дерева на правій стороні -
Я їх коло, тут -
ці дерева виглядають майже так само, як зв'язаний список.
Кожен вузол має тільки одну дитину,
і тому ми не повинні все це деревовидна структура, яку ми бачимо, наприклад,
У цьому одиноке дерево тут на нижній лівій.
Ці дерева насправді називається виродженим, бінарні дерева,
і ми поговоримо про це докладніше в майбутньому -
Особливо якщо ви йдете на прийняття інших курсів з інформатики.
Ці дерева є виродженими.
Вони не дуже корисно, тому що, дійсно, ця структура піддається
для пошуку рази схожий на зв'язаний список.
Ми не отримуємо, щоб скористатися додаткової пам'яті - це додатковий покажчик -
тому що наші структури поганих таким чином.
Замість того, щоб іти далі і зробити з бінарних дерев, які мають 9 на корені,
яка є останній випадок, що ми повинні,
ми замість цього, на даний момент, поговоримо трохи про це іншим терміном
, Які ми використовуємо, коли говоримо про дерева, які називають висотою.
>> Висота дерева це відстань від кореня до найвіддаленіших вузлів,
або, вірніше, кількість стрибків, що ви повинні зробити для того, щоб
починається з кореня і потім в кінцевому підсумку на найвіддаленішому вузол в дереві.
Якщо ми подивимося на деякі з цих дерев, які ми намалювали прямо тут,
ми бачимо, що якщо ми візьмемо це дерево в лівому верхньому кутку, і ми починаємо на 3,
Потім ми повинні зробити 1-хопу, щоб дістатися до 6, другого стрибка, щоб дістатися до 7,
і третій хоп, щоб дістатися до 9.
Таким чином, висота цього дерева 3.
Ми можемо зробити те ж саме вправу для інших дерев, викладені з цієї зеленої,
і ми бачимо, що висота всіх цих дерев також дійсно 3.
Це частина того, що робить їх вироджені -
що їх висота складає всього один менше, ніж кількість вузлів по всьому дереву.
Якщо ми подивимося на цього іншого дерева, що це оточення з червоним, з іншого боку,
ми бачимо, що найбільш віддалених вузлів листя 6 і 9 -
листя опиняються ті вузли, які не мають дітей.
Отже, для того, щоб отримати від кореневого вузла або 6 або 9,
ми повинні зробити одне-хопа, щоб дістатися до 7, а потім другого стрибка, щоб дістатися до 9,
і аналогічно, тільки другого стрибка з 7, щоб дістатися до 6.
Таким чином, висота цього дерева тут тільки 2.
Ви можете повернутися назад і зробити це для всіх інших дерев, які ми раніше обговорювали
починаючи з 7 і 6,
і ви побачите, що висота всіх цих дерев також 2.
>> Тому ми говорили про наказав бінарні дерева
і чому вони круті, тому що ви можете шукати через них в
дуже схоже на пошуки більш впорядкований масив.
Тут ми говоримо про те, що поліпшення час пошуку
над простий зв'язаний список.
З зв'язаний список - якщо ви хочете знайти конкретний елемент -
Ви в кращому випадку збирається зробити якийсь лінійний пошук
де ви починаєте на початку списку і хмелю один-на-один -
одного вузла на один вузол -
весь список, поки не знайдете те, що ви шукаєте.
Беручи до уваги, якщо у вас є бінарне дерево, яке зберігається в цьому гарному форматі,
Ви можете фактично отримати більше бінарний пошук триває
де ви розділяй і володарюй
і пошуку за допомогою відповідних половини дерев на кожному кроці.
Давайте подивимося, як це працює.
>> Якщо у нас є - знову ж таки, повертаючись до нашої початкової дерево -
ми починаємо в 7, у нас є 3 зліва, 9 праворуч,
і під 3 маємо 6.
Якщо ми хочемо, щоб знайти номер 6 у цьому дереві, ми б почали в корені.
Ми б порівняти значення ми шукаємо, скажімо, 6,
зі значенням, що зберігається у вузлі, який ми в даний час дивимося, 7,
виявите, що 6 є дійсно менше, ніж 7, так що ми б рухатися вліво.
Якщо значення 6 було більше, ніж 7, ми б замість переміщується вправо.
Оскільки ми знаємо, що - завдяки структурі нашої наказав бінарному дереві -
всі значення менше 7 будуть зберігатися зліва від 7,
немає необхідності навіть турбуватися, дивлячись через праву сторону дерева.
Як тільки ми переходимо до лівої, і ми тепер на вузол, що містить 3,
ми можемо зробити те ж порівняння ще раз, де ми порівнюємо 3 і 6.
І ми бачимо, що в той час як 6 - цінність, яку ми шукаємо, - це більше, ніж 3,
ми можемо перейти до правої сторони вузол, що містить 3.
Там немає лівій стороні тут, так що ми могли б проігнорував.
Але ми знаємо тільки, що, оскільки ми дивимося на саме дерево,
і ми бачимо, що дерево не має дітей.
>> Це також досить легко знайти 6 в цьому дереві, якщо ми робимо це самі, як люди,
Але давайте стежити за цим процесом механічно, як комп'ютер буде робити
щоб зрозуміти алгоритм.
На даний момент, ми зараз дивимося на вузол, який містить 6,
і ми шукаємо значення 6,
так, дійсно, ми знайшли потрібний вузол.
Ми виявили, що значення 6 в нашому дереві, і ми можемо припинити наші пошуки.
На даний момент, в залежності від того, що відбувається,
ми можемо сказати, так, ми знайшли значення 6, вона існує в нашому дереві.
Або, якщо ми плануємо вставити вузол або зробити щось, що ми можемо зробити, що в цій точці.
>> Давайте зробимо ще пару пошуку, щоб подивитися, як це працює.
Давайте подивимося, що станеться, якщо ми повинні були спробувати і подивитися значення 10.
Якби ми шукати значення 10, ми хотіли б почати з кореня.
Ми бачимо, що 10 більше, ніж 7, тому ми будемо рухатися вправо.
Ми хотіли потрапити на 9 і порівняйте 9 до 10 і бачимо, що 9 є дійсно менше, ніж 10.
Отже, ще раз, ми будемо намагатися рухатися вправо.
Але на даний момент, ми б помітили, що ми знаходимося на нульовий вузол.
Там нічого немає. Там немає нічого, де 10 повинно бути.
Це те, де ми можемо повідомити невдача - що там насправді немає 10 в дерево.
І, нарешті, давайте пройдемо випадку, коли ми намагаємося знайти 1 в дерево.
Це схоже на те, що відбувається, якщо ми подивимося на 10, тільки замість того, щоб йти направо,
Ми збираємося піти наліво.
Ми починаємо в 7 і бачимо, що 1 менше 7, тому ми рухаємося вліво.
Ми добираємося до 3 і бачимо, що 1 менше, ніж 3, тому знову ми намагаємося рухатися вліво.
На даний момент ми маємо нульовий вузол, так що знову ми можемо повідомити про невдачу.
>> Якщо ви хочете дізнатися більше про бінарних дерев,
Є ціла купа веселощів мало проблем, які ви можете зробити з ними.
Я пропоную практикувати малюнок з цих діаграмах один-на-один
і наступні через всі різні кроки,
тому що це прийде в супер-зручна
Не тільки тоді, коли ви робите проблема Huffman кодування набору
але і в майбутніх курсів -
просто навчитися малювати ці структури даних і думаю, через проблеми
з ручкою і папером, або, в даному випадку, IPad і стилусом.
>> На даний момент, однак, ми збираємося рухатися далі, щоб зробити деякі практики кодування
а насправді грати з цими бінарні дерева і подивитися.
Я збираюся повернутися до мого комп'ютера.
Для цієї частини розрізу, замість використання CS50 або CS50 Run простору,
Я збираюся використовувати прилад.
>> Після поряд з специфікацією поставленого завдання,
Я бачу, що я повинен відкрити прилад,
йду в папку Dropbox, створити папку з ім'ям Розділ 7,
, А потім створити файл з ім'ям binary_tree.c.
Тут ми йдемо. У мене є прилад вже відкритий.
Я збираюся тягнути до терміналу.
Я збираюся піти в папку Dropbox, створіть каталог називається section7,
і побачити його абсолютно порожнім.
Тепер я збираюся відкрити binary_tree.c.
Добре. Тут ми йдемо - порожній файл.
>> Давайте повернемося до специфікації.
Специфікація просить, щоб створити нове визначення типу
для двійкового дерева вузлів містять Int значення -
так само як і цінності, які ми звернули в нашій діаграм раніше.
Ми збираємося використовувати цей шаблонний ЬурейеЕ, що ми зробили тут
що ви повинні дізнатися із завдань 5 -
якщо ви зробили хеш-таблиці шляхом завоювання правопису програми.
Ви повинні також визнати, що в розділі минулого тижня
де ми говорили про пов'язаних списків.
У нас це ЬурейеЕ зі структури вузла,
і ми дали цієї структури вузла ця назва структури вузла заздалегідь
так що ми можемо посилатися на нього, так як ми хочемо мати покажчики структури вузла
як частина нашої структури, але ми тоді оточили цю -
або, скоріше, укладені цьому - в ЬурейеЕ
так що, врешті коду, ми можемо звернутися до цієї структури, як тільки вузол, а структура вузла.
>> Це буде дуже схожий на односвязного визначення списку, який ми бачили минулого тижня.
Щоб зробити це, давайте почнемо з виписуючи шаблону.
Ми знаємо, що ми повинні мати ціле значення,
так що ми потрапили в цілочисельне значення, а потім замість того, щоб тільки один покажчик на наступний елемент -
як ми зробили з односвязного списку -
Ми збираємося мати лівий і правий покажчики дитини.
Це досить проста теж - структура вузла * лівий дитини;
і структура вузла * Право дитини;. Cool.
Це виглядає як дуже хороший старт.
Давайте повернемося до специфікації.
>> Тепер нам потрібно оголосити глобальну змінну * вузол кореневого дерева.
Ми збираємося зробити це глобальний так само, як ми зробили перший покажчик в нашому списку також зв'язана глобальним.
Це було так, що у функціях, які ми пишемо
ми не повинні тримати проходить навколо цього кореня -
хоча ми побачимо, що, якщо ви хочете написати ці функції рекурсивно,
що може бути краще навіть не передавати його в якості глобальної, в першу чергу
і замість того, ініціалізувати його локально в основною функцією.
Але, ми зробимо це в глобальному масштабі для початку.
Знову ж таки, ми дамо пару просторів, і я збираюся оголосити кореневий вузол *.
Просто щоб переконатися, що я не полишаю цієї неініціалізовані, я збираюся встановити його рівним нулю.
Тепер, в основній функції - які ми будемо писати дуже швидко, прямо тут -
Int основних (Int агдс, сопзЬ сЬаг * ARGV []) -
і я збираюся розпочати декларування мій ARGV масиву як константний просто так, що я знаю,
що ті аргументи аргументами, які я, ймовірно, не хочуть змінити.
Якщо я хочу змінити їх, я, ймовірно, слід робити їх копії.
Ви побачите це багато коду.
Це добре в будь-якому випадку. Це прекрасно, щоб залишити все як - опустити сопзЬ, якщо ви хочете.
Як правило, я поклав його в просто так, що я нагадую собі,
що я, ймовірно, не хочете змінювати ці аргументи.
>> Як завжди, я збираюся включити це повернення 0 лінію в кінці основного.
Тут я ініціалізації мого кореневого вузла.
Як вона стоїть зараз, у мене є покажчик, який встановлений в нуль,
таким чином, це вказує на нічого.
Для того щоб дійсно почати будівництво вузла,
Я в першу чергу необхідно виділити пам'ять для нього.
Я збираюся зробити це, зробивши пам'яті купи за допомогою Танос.
Я збираюся встановити корінь, рівний результат Танос,
і я збираюся використовувати SizeOf оператора для розрахунку розміру вузла.
Причина, по якій я використовую SizeOf вузла, на відміну від, скажімо,
робити щось подібне до цього - Танос (4 + 4 +4) або Танос 12 -
тому що я хочу, щоб мій код, щоб бути сумісним наскільки це можливо.
Я хочу бути в змозі прийняти це. С файлом, скомпілювати його на прилад,
, А потім компілювати його на моєму 64-розрядний Mac -
або на зовсім інший архітектурі -
і я хочу це все буде працювати так само.
>> Якщо я роблю припущення щодо розміру змінних -
Розмір Int або розмір покажчика -
Потім я також робить припущення про види архітектури
, На якому мій код може успішно скомпілювати при запуску.
Завжди використовуйте SizeOf, на відміну від ручного підсумовування структура полів.
Інша причина в тому, що там може бути також оббивка, що компілятор поміщає в структуру.
Навіть просто підсумовування окремих полів не те, що ви зазвичай хочуть робити,
так, видаліть цей рядок.
Тепер, щоб дійсно ініціалізації цього кореневого вузла,
Я хочу, щоб підключити значення для кожного зі своїх різних областях.
Наприклад, для значення Я знаю, я хочу, щоб ініціалізувати до 7,
і тепер я збираюся встановити лівий дитина буде нульовим
і право дитини бути нульовим. Відмінно!
Ми зробили це частина спектра.
>> Специфікація вниз в нижній частині сторінки 3 запитує мене на створення ще трьох вузлів -
одна з яких 3, одна з яких 6, і один з 9 -
, А потім підключити їх так, що виглядає точно так само, як наше дерево схема
що мова йшла про раніше.
Давайте зробимо це дуже швидко тут.
Ви побачите дуже швидко, що я збираюся почати писати купу повторюваного коду.
Я збираюся створити вузол *, і я збираюся називати це три.
Я збираюся встановити його рівним Танос (SizeOf (вузла)).
Я збираюся встановити три-> значення = 3.
Три -> left_child = NULL; трьох -> правою _child = NULL; також.
Це виглядає дуже схоже на ініціалізацію корінь, і це саме те, що
Я збираюся потрібно зробити, якщо я почну ініціалізації 6 і 9, а також.
Я зроблю це дуже швидко тут - на самом деле, я збираюся зробити невеликий копіювання і вставки,
і переконатися, що я - все в порядку.
Тепер, я отримав його скопіювати, і я можу піти далі і встановити рівним 6.
Ви бачите, що це займає деякий час, і не супер-ефективним.
У зовсім небагато, ми напишемо функцію, яка буде робити це за нас.
Я хочу, щоб замінити цим з 9, замінити, що з 6.
>> Тепер у нас є всі наші вузли створені і ініціалізований.
У нас є наш корінь рівним 7, або містить значення 7,
наш вузол, що містить 3, наш вузол, що містить 6, і наш вузол, що містить 9.
На даний момент, все, що нам потрібно зробити, це дроти все вгору.
Тому я ініціалізувалися всі покажчики до нуля, це просто так, що я переконатися, що
Я не є якісь неініціалізувати покажчиків там випадково.
А також, оскільки, на даний момент, у мене тільки є насправді з'єднання вузлів один з одним -
з тими, що вони насправді пов'язаний з - я не повинен йти до кінця і зробити
Переконайтеся, що всі нулі знаходяться там у відповідних місцях.
>> Починаючи з коренем, я знаю, що ліва дитини кореня дорівнює 3.
Я знаю, що права дитини кореня дорівнює 9.
Після цього, тільки інша дитина, що я залишив для занепокоєння
це право дитині 3, яка є 6.
На даний момент, все це виглядає досить добре.
Ми видалимо деякі з цих ліній.
Тепер все виглядає досить добре.
Давайте повернемося до нашої специфікації і подивитися, що ми повинні робити далі.
>> На даний момент, ми повинні написати функцію, звану 'містить'
з прототипом "BOOL містить (цілочисельне значення).
І це містить функцію збирається повернути істинний
якщо дерево на який вказує наша глобальна змінна кореневої
містить значення передається в функцію і брехня в іншому випадку.
Давайте підемо далі і що робити.
Це буде так само, як пошук, що ми зробили вручну на IPad просто трохи назад.
Давайте масштаб в трохи, і прокрутка вгору.
Ми збираємося поставити цю функцію прямо над нашою основною функцією
так що ми не повинні робити жодних прототипів.
Таким чином, логічний містить (цілочисельне значення).
Там ми йдемо. Там наш шаблонний декларації.
Просто щоб переконатися, що це буде компілювати,
Я збираюся йти вперед і просто встановити його рівним повернутися помилковим.
Зараз ця функція просто не буде робити нічого, і завжди повідомляють, що
значення, яке ми шукаємо не в дереві.
>> У цей момент, ймовірно, це гарна ідея -
так як ми написали цілу купу коду, і ми навіть не намагалися тестування ще -
щоб переконатися, що все компілюється.
Є кілька речей, які ми повинні зробити, щоб переконатися, що це буде насправді компіляції.
По-перше, побачити, якщо ми використовуємо будь-які функції в будь бібліотеки, які ми ще не включені.
Функції, які ми використовували досі, Танос,
і ми також використовували цей тип - це нестандартний тип, званий "bool '-
яка входить в стандартну BOOL заголовка файлу.
Ми безумовно хочемо включати в себе стандартні bool.h для логічного типу,
і ми також хочемо # включають в себе стандартні lib.h для стандартних бібліотек
, Які включають Танос, і вільні, і все таке.
Таким чином, масштаб, ми збираємося кинути палити.
Давайте спробуємо і переконатися, що це насправді зробив компіляцію.
Ми бачимо, що він робить, так що ми на правильному шляху.
>> Давайте відкривати binary_tree.c знову.
Він компілює. Давайте спустимося і переконатися, що ми вставляємо кілька дзвінків, щоб наша функція містить -
просто щоб переконатися, що все добре.
Наприклад, коли ми зробили деякі пошуку в нашому дереві раніше,
Ми намагалися знайти значення 6, 10 і 1, і ми знали, що 6 було в дереві,
10 був не в дереві, і 1 не був в дерево або.
Давайте використовувати ці зразки дзвінки як спосіб з'ясувати, чи є чи ні
наші містить функцію працює.
Для того, щоб зробити це, я збираюся використовувати Е функція,
і ми збираємося, щоб роздрукувати результат виклику містить.
Я збираюся поставити в рядок "містить (% D) = тому що
ми збираємося підключити значення, що ми збираємося шукати,
і% = з \ п "і використовувати його в якості нашого формату рядка.
Ми просто збираємося, щоб побачити - в буквальному сенсі роздрукувати на екрані -
, Що виглядає як виклик функції.
Це насправді не виклик функції.
Це просто рядок призначена для виглядати як виклик функції.
>> Тепер, ми збираємося підключити значення.
Ми збираємося спробувати містить 6,
і те, що ми збираємося зробити, так це використовувати, що потрійний оператор.
Давайте подивимося, - містить 6 - так, тепер я містив 6 і якщо містить 6 правда,
Рядок, що ми збираємося відправити у форматі характер% з
буде рядок "істина".
Давайте виділіть на трохи.
В іншому випадку, ми хочемо послати рядок "помилковою", якщо містить 6 повертає брехня.
Це трохи безглуздий з вигляду, але я думаю, я міг би також ілюструють
що потрійний оператор виглядає так як ми не бачили його на деякий час.
Це буде хороший, зручний спосіб з'ясувати, якщо наші містить функцію працює.
Я буду прокручувати назад на ліву,
і я збираюся скопіювати і вставити цей рядок кілька разів.
Він змінив деякі з цих цінностей з усього,
так що це буде 1, а це буде 10.
>> На даний момент у нас є хороша функція містить.
У нас є кілька тестів, і ми побачимо, якщо все це працює.
На даний момент ми написали ще кілька коді.
Час, щоб вийти, і переконайтеся, що все ще компілює.
Вийти, і тепер давайте спробуємо робити бінарне дерево знову.
Що ж, схоже, у нас є помилки,
І у нас є ця явного оголошення бібліотечні функції Printf.
Схоже, що ми повинні піти і # включити standardio.h.
І з цим, все повинно компілюватися. Ми всі добре.
Тепер спробуйте запустити бінарне дерево і подивитися, що відбувається.
Ось і ми,. / Binary_tree,
і ми бачимо, що, як ми й очікували -
тому що ми не реалізували містить ще,
або, скоріше, ми просто покласти у свою чергу помилковими -
ми бачимо, що це просто повернення хибним для всіх з них,
Так що всі робітники, по більшій частині досить добре.
>> Давайте повернемося в справі здійснення і міститься в цій точці.
Я хочу, щоб прокрутити вниз, збільшувати, і -
Пам'ятайте, що алгоритм, який ми використовували в тому, що ми почали в кореневий вузол
, А потім у кожному вузлі з якими ми стикаємося, ми робимо для порівняння,
і на основі цього порівняння ми або рухатися вліво дитини або права дитини.
Це буде виглядати дуже схоже на двійковий код пошуку, який ми писали раніше в строк.
Коли ми починаємо, ми знаємо, що ми хочемо провести на поточний вузол
що ми дивимося, і поточний вузол буде ініціалізований на кореневий вузол.
І тепер, ми збираємося продовжувати йти по дереву,
і пам'ятайте, що наші зупинки стані -
Коли ми фактично працювали на прикладі вручну -
був, коли ми зіткнулися з нульовою вузол,
не тоді, коли ми дивилися на нульовий дитини,
а коли ми дійсно переїхали в вузол в дереві
і виявив, що ми знаходимося на нульовий вузол.
Ми збираємося повторювати, поки струму не дорівнює нулю.
І що ми будемо робити?
Ми збираємося перевірити, якщо (поточн. -> значення == значення),
Потім ми знаємо, що ми насправді знайшли вузол, який ми шукаємо.
Так от, ми можемо повернутися вірно.
В іншому випадку, ми хочемо бачити чи ні значення менше, ніж значення.
Якщо значення поточного вузла менше, ніж значення, яке ми шукаємо,
ми будемо рухатися вправо.
Таким чином, текущ. = Текущ. -> Right_child, а в іншому випадку, ми будемо рухатися вліво.
текущ. = текущ. -> left_child;. Досить просто.
>> Ви, напевно, визнати цикл, який дуже схожий на цього від
бінарний пошук на початку терміну, за винятком то ми маємо справу з низькою, середньою і високою.
Тут ми просто повинні подивитися на поточне значення,
так що це просто і красиво.
Давайте переконатися, що цей код працює.
По-перше, переконайтеся, що він компілює. Схоже, що він робить.
Давайте спробуємо запустити його.
І дійсно, він друкує все, що ми очікували.
Він знаходить 6 в дереві, не знайти 10, тому що 10 не в дереві,
і не знаходить 1, або тому, що 1 також не в дереві.
Прикольних речей.
>> Добре. Давайте повернемося до нашої специфікації і подивитися, що буде далі.
Тепер він хоче додати ще кілька вузлів для нашого дерева.
Вона хоче додати 5, 2 і 8, і переконатися, що наші містить код
як і раніше працює, як очікувалося.
Давайте робити це.
На даний момент, а не робити те, що дратує копіювати і вставляти знову,
давайте напишемо функцію, щоб фактично створити вузол.
Якщо прокрутити весь шлях до головного, ми бачимо, що ми робили це
дуже схожий код знову і знову, кожного разу, коли ми хочемо створити вузол.
>> Давайте напишемо функцію, яка буде реально побудувати вузол для нас, і повернути його.
Я буду називати його build_node.
Я збираюся побудувати вузол з певним значенням.
Збільшити тут.
Перше, що я збираюся зробити, це насправді створити простір для вузла в купі.
Таким чином, вузол * п = Танос (SizeOf (вузла)), п -> значення = значення;
а потім тут, я просто хочу, щоб ініціалізувати всі поля, щоб бути відповідні значення.
І в самому кінці, ми повернемо наш вузол.
Добре. Єдине, що слід зазначити, що ця функція тут
збирається повернути покажчик на область пам'яті, яка була купі.
Що приємно про це є те, що цей вузол зараз -
ми повинні оголосити його в купі, бо якщо ми оголосили його в стек
ми не були б в змозі зробити це в цій функції, як це.
Ця пам'ять буде вийти зі сфери
і були б недійсними, якщо ми спробували отримати доступ до нього надалі.
Оскільки ми оголошуємо купі пам'яті,
ми будемо мати, щоб піклуватися про звільняючи його пізніше
для нашої програми не витік будь-якої пам'яті.
Ми понтіровавшего на що на все інше в коді
тільки для простоти в той час,
але якщо ви коли-небудь написати функцію, яка виглядає наступним чином
де у вас є - деякі називають це Танос або перерозподілити всередині -
Ви хочете, щоб переконатися, що ви поклали якийсь коментар тут, який говорить:
агов, ви знаєте, повертає купі вузлів ініціалізується переданий в ціні.
І тоді ви хочете, щоб переконатися, що ви поклали в якийсь увагу, що говорить
Зухвалий повинен звільнити повернулася пам'ять.
Таким чином, якщо хтось ніколи не йде, і використовує цю функцію,
вони знають, що все, що вони повернуться з цієї функції
в якийсь момент треба буде звільнений.
>> Якщо припустити, що все добре, і тут добре,
ми можемо спуститися в наш код і замінити всі ці рядки прямо тут
із закликами до нашої функції вузла зборки.
Давайте зробимо це дуже швидко.
Одна частина, що ми не збираємося замінити ця частина тут
на дно, де ми насправді з'єднувати вузли, щоб вказувати один на одного,
тому що ми не можемо зробити в наших функцій.
Але, давайте зробимо корінь = build_node (7); вузол * три = build_node (3);
вузол * шість = build_node (6); вузол * Дев'ять = build_node (9),.
І тепер, ми також хотіли б додати вузли -
вузол * П'ять = build_node (5); вузол * = build_node вісім (8);
і те, що було на інший вузол? Давайте подивимося тут. Ми хотіли б також додати 2 -
* Два вузли = build_node (2);.
Добре. На даний момент, ми знаємо, що у нас є 7, 3, 9, і 6
Всі провідні відповідним чином, але як щодо 5, 8 і 2?
Щоб зберегти все в належний порядок,
Ми знаємо, що право дитині три є 6.
Отже, якщо ми збираємося додати 5,
5 також належить до правої сторони дерев, з яких 3 є коренем,
5 належить так як ліва дитини 6.
Ми можемо зробити це, сказавши, шість -> left_child = п'ять;
, А потім 8 належить як ліва дитиною з 9, таким чином, дев'ять -> left_child = вісім;
, А потім 2 є лівим дитиною 3, так що ми можемо зробити це тут - Тебе -> left_child = два,.
Якщо ви не зовсім розумію разом з тим, я пропоную вам зробити це самостійно.
>> Добре. Давайте збережемо це. Давайте виходити на вулицю і переконайтеся, що він збирає,
і тоді ми можемо додати в нашу містить виклики.
Схоже, все ще компілює.
Давайте і додати в деяких містить виклики.
Знову ж таки, я збираюся зробити трохи копіювання і вставки.
Тепер давайте шукати 5, 8, і 2. Добре.
Давайте переконався, що це все виглядає добре до цих пір. Відмінно! Зберегти і вийти.
Тепер давайте зробимо, компіляції, а тепер давайте працювати.
З результатів, схоже, все працює просто приємно і добре.
Відмінно! Так що тепер у нас є наші містить функцію написано.
Давайте рухатися далі і почати працювати на те, як вставити вузли в дерево
, Оскільки, як ми робимо це зараз, все не дуже красиво.
>> Якщо ми повернемося до специфікації,
він просить, щоб ми написали функцію під назвою вставити - знову, повертаючись логічне
для того чи ні, ми могли фактично вставки вузла в дерево -
, А потім значення для вставки в дерево визначається як
Єдиний аргумент, щоб наші функції вставки.
Ми повернемося вірно, якщо ми могли б дійсно вставити вузол, що містить значення в дереві,
Це означає, що ми, один, мав достатньо пам'яті,
, А потім два, то цей вузол вже не існують в дереві, так -
Пам'ятайте, що ми не будемо мати однакові значення в дереві, просто щоб зробити речі простими.
Добре. Перейти до коду.
Відкрийте його. Збільшити трохи, а потім прокрутити вниз.
Скажімо функції вставки прямо над містить.
Знову ж таки, це буде називатися BOOL вставки (цілочисельне значення).
Дайте йому трохи більше простору, а потім, за замовчуванням,
давайте замість помилкового в самому кінці.
Тепер вниз, на дно, давайте йти вперед і замість того, щоб вручну створювати вузли
В основній собі і проводка їх до вказувати один на одного, як ми робимо,
ми покладаємося на наші функції вставки, щоб зробити це.
Ми не будемо покладатися на наші функції вставки для зборки всього дерева з нуля, тільки все ж,
а ми позбутися від цих ліній - МИ закоментуйте ці рядки -
що будувати вузли 5, 8 і 2.
А замість цього, ми вставимо дзвінки на наш функції вставки
щоб переконатися, що це дійсно працює.
Тут ми йдемо.
>> Тепер ми закоментувати ці рядки.
У нас є тільки 7, 3, 9 і 6 в нашій дерева в цій точці.
Щоб переконатися в тому, що все це працює,
ми можемо зменшити масштаб, щоб наші бінарне дерево,
запустити його, і ми бачимо, що міститься в даний час говорить нам, що ми абсолютно праві -
5, 8, і 2 вже не в дереві.
Поверніться в коді,
і як ми збираємося вставити?
Пам'ятайте, що ми робили, коли ми були насправді вставка 5, 8, і 2 раніше.
Ми грали в цю гру Plinko, де ми почали в корені,
спустився по дереву один на один за іншим
поки ми не знайшли відповідну щілину,
і тоді ми підключені вузла у відповідному місці.
Ми збираємося зробити те ж саме.
Це, в основному, як написання коду, який ми використовували в містить функцію
Щоб знайти місце, де вузол повинен бути,
а потім ми тільки збираємося, щоб вставити вузол прямо там.
Давайте почнемо це робити.
>> Отже, ми маємо вузол * текущ. = Корінь; ми тільки збираємося слідувати код містить
поки ми не знайдемо, що це не зовсім робота для нас.
Ми збираємося пройти через дерево в той час як поточний елемент не є нульовим,
і якщо ми виявимо, що значення струму, дорівнює значенню, що ми намагаємося вставити -
Ну, це один з випадків, в яких ми не могли фактично вставки вузла
в дерево, бо це означає, що у нас є повторювані значення.
Тут ми насправді збираємося повернутися помилковим.
Тепер, інакше, якщо значення струму складає менше значення,
Тепер ми знаємо, що ми рухаємося вправо
тому що значення належить в правій половині текущ. дерева.
В іншому випадку, ми будемо рухатися вліво.
Це в основному наші містить функцію прямо там.
>> На даний момент, як тільки ми закінчили це в той час циклу,
шему покажчик буде вказувати на нуль
якщо функція вже не повернувся.
Ми тому мають текущ. В тому місці, де ми хочемо, щоб вставити новий вузол.
Те, що залишається зробити, це насправді побудувати новий вузол,
що ми можемо зробити досить легко.
Ми можемо використовувати наші супер-зручна збірка вузлів функції,
і те, що ми не робили раніше -
ми просто якась вважали само собою зрозумілим, але тепер ми будемо робити просто щоб переконатися -
ми будемо перевірити, щоб переконатися, що значення повертається новий вузол був насправді
не нульовий, тому що ми не хочемо, щоб почати доступ до цієї пам'яті, якщо воно є недійсним.
Ми можемо перевірити, щоб переконатися, що новий вузол не дорівнює нулю.
Або замість цього, ми можемо просто подивитися, якщо він насправді є порожнім,
і якщо він дорівнює нулю, то ми можемо просто повернутися помилковим рано.
>> На даний момент, ми повинні підключити новий вузол у свою відповідне місце в дереві.
Якщо ми подивимося на основні і де ми були насправді проводки в значеннях раніше,
ми бачимо, що те, як ми це робили, коли ми хотіли поставити 3 в дерево
Ми були доступні лівому дитини кореня.
Коли ми ставимо 9 в дерево, ми повинні були отримати доступ до право дитини на корені.
Ми повинні були мати покажчик на батька для того, щоб покласти нове значення в дерево.
Прокрутка назад вставити, що не збирається працювати тут цілком
тому що у нас немає предка.
Що ми хочемо бути в змозі робити це, на даний момент,
перевірте значення батьків і подивитися - ну, чорт візьми,
якщо значення батька менше, ніж поточне значення,
Потім право дитини батько повинен бути новий вузол;
В іншому випадку ліва дитини батько повинен бути новий вузол.
Але ми не повинні цього батька покажчик зовсім ще.
>> Для того, щоб отримати його, ми фактично доведеться відстежувати його, як ми йдемо по дереву
і знайти відповідне місце в нашому циклі вище.
Ми можемо зробити це за допомогою прокрутки назад до вершини нашої функції вставки
і відстеження інший покажчик змінної батьків.
Ми збираємося встановити його рівним нулю на початковому етапі,
, А потім кожен раз, коли ми йдемо по дереву,
Ми збираємося встановити батька, щоб відповідати поточним покажчиком.
Встановити батьківський одно текущ ..
Таким чином, кожен раз, коли ми пройти,
Ми збираємося переконатися, що в якості поточного покажчика збільшується на одиницю
батьківського покажчик слід за ним - просто на один рівень вище поточного покажчика в дереві.
Це все виглядає досить добре.
>> Я думаю, що одна річ, яку ми хочемо налаштувати це побудувати вузол повертається NULL.
Для того, щоб побудувати вузол насправді успішно повертають NULL,
ми повинні змінити цей код,
тому що тут, ми ніколи не перевіряли, щоб переконатися, що Танос повернувся дійсний покажчик.
Так що, якщо (п = NULL!), Потім -
якщо Танос повернувся дійсний покажчик, то ми його ініціалізації;
В іншому випадку ми будемо просто повернути, і що в кінцевому підсумку повертається NULL для нас.
Тепер все виглядає досить добре. Давайте переконатися, що це насправді компілює.
Зробити бінарне дерево, і ах, у нас є деякі речі тут відбувається.
>> У нас є неявна декларація функції створення вузла.
Знову ж таки, ці компілятори, ми збираємося почати з самого верху.
Що це має означати, що я дзвоню побудувати вузол, перш ніж я насправді оголошена.
Давайте повернемося до коду дуже швидко.
Прокрутіть вниз, і, звичайно ж, моя вставка функція оголошена
вище функції вузла зборки,
Але я намагаюся використовувати побудувати вузол всередині вставки.
Я збираюся піти і копію - а потім вставте функцію збирання вузлів шлях тут, на самому верху.
Таким чином, ми сподіваємося, що буде працювати. Давайте дамо цьому ще один шанс.
Тепер все компілюється. Все це добре.
>> Але на даний момент, ми насправді не називали наші функції вставки.
Ми просто знаємо, що він збирає, так що давайте підемо і покласти кілька дзвінків дюйма
Давайте зробимо, що в наших основних функцій.
Тут ми закоментовані 5, 8 і 2,
і тоді ми не підключити їх сюди.
Давайте зробимо декілька дзвінків, щоб вставити,
і давайте також використовувати такі ж речі, які ми використовували
Коли ми зробили ці Printf дзвінків, щоб переконатися, що все дійсно ставали вставлений правильно.
Я збираюся копіювати і вставляти,
і замість того, містить ми збираємося зробити вставку.
І замість того, 6, 10 і 1, ми збираємося використовувати 5, 8 і 2.
Це повинно, ми сподіваємося, вставити 5, 8, і 2 в дерево.
Компіляція. Все це добре. Тепер ми будемо реально працювати наша програма.
>> Всі повернулися помилковою.
Так, 5, 8 і 2 не пішов, і це виглядає як Містить не знайшли їх або.
Що відбувається? Давайте масштабу.
Першою проблемою було те, що, здавалося вставки, щоб повернутися помилковим,
і, схоже, це тому, що ми залишили в нашому поверненні помилковий виклик,
і ми ніколи не повернулися правда.
Ми можемо встановити, що.
Друга проблема в тому, тепер, навіть якщо ми робимо - зберегти це, кинути це,
запустити зробити знову, нехай він скомпілювати, а потім запустити його -
ми бачимо, що щось ще сталося.
5, 8, і 2 ще не знайшов у дереві.
Отже, що відбувається?
>> Давайте подивимося на це в коді.
Давайте подивимося, чи зможемо ми зрозуміти це.
Почнемо з батьками не бути нульовим.
Ми встановлюємо покажчик поточної рівних в кореневій покажчик,
і ми збираємося працювати наш шлях вниз по дереву.
Якщо поточний вузол не є нульовим, то ми знаємо, що ми можемо рухатися вниз небагато.
Ми встановлюємо наші батьки покажчик рівним поточному покажчику,
перевірити значення - якщо значення збігаються, ми повернулися помилковою.
Якщо значення менше ми переїхали в праву;
В іншому випадку ми переїхали на лівий.
Потім ми будуємо вузла. Я збільшити небагато.
І ось, ми збираємося, щоб спробувати підключити до значень, те ж саме.
Що відбувається? Давайте подивимося, якщо можливо Valgrind може дати нам підказку.
>> Мені подобається використовувати Valgrind Valgrind тільки тому, що дуже швидко біжить
і говорить вам, якщо є які-небудь помилки пам'яті.
Коли ми запускаємо Valgrind на код,
як ви можете бачити правий удар here--Valgrind./binary_tree--and входу.
Ви бачите, що у нас не було ніяких помилок пам'яті, так що схоже, все в порядку досі.
У нас є деякі витоку пам'яті, які ми знаємо, тому що ми не
відбувається, щоб звільнити будь-якого з наших вузлів.
Давайте спробуємо працює GDB, щоб подивитися, що відбувається насправді.
Ми зробимо GDB. / Binary_tree. Він завантажився нормально.
Давайте встановимо точку зупину на вставку.
Давайте запустимо.
Схоже, ми ніколи не називали вставки.
Схоже, проблема була тільки що, коли я змінив тут, в головному -
Всі ці Printf дзвінки з містить -
Я ніколи насправді змінилося цих подзвонити вставки.
Тепер давайте дати йому спробувати. Давайте компіляції.
Все виглядає добре там. Тепер давайте спробуємо запустити його, подивитися, що відбувається.
Добре! Все виглядає досить добре там.
>> Остання річ, щоб думати про те, чи є якісь крайні випадки цієї вставки?
І виходить, що, мовляв, одне ребро випадку це завжди цікаво думати про
в тому, що станеться, якщо ваше дерево порожньо, і ви називаєте це вставка функції?
Чи буде вона працювати? Що ж, давайте спробуємо.
- Binary_tree с. -
Те, як ми збираємося перевірити це, ми збираємося спуститися до нашої основної функції,
і замість проводки цих вузлах ось так,
ми тільки збираємося, щоб закоментувати всю річ,
і замість проводки до вузли собі,
ми дійсно можемо просто йти вперед і видалити все це.
Ми збираємося зробити все виклик для вставки.
Отже, давайте робити - замість 5, 8 і 2, ми збираємося, щоб вставити 7, 3 і 9.
І тоді ми також хочемо, щоб вставити 6, а.
Зберегти. Вийти. Зробити бінарне дерево.
Це все компілюється.
Ми можемо просто запустіть його як є і подивитися, що відбувається,
але це також буде дуже важливо, щоб переконатися, що
Ми не мають ніяких помилок пам'яті,
так як це є одним з наших крайніх випадках, що ми знаємо про.
>> Давайте переконався, що він добре працює під Valgrind,
які ми будемо робити, просто видавши Valgrind. / binary_tree.
Схоже, у нас дійсно одна помилка з одного контексту -
у нас є ця помилка сегментації.
Що трапилося?
Valgrind насправді говорить нам, де він знаходиться.
Зменшити небагато.
Схоже, що відбувається в нашій функції вставки,
де у нас є недійсним читання розміром 4 на вставку, рядок 60.
Давайте повернемося і подивимося, що тут відбувається.
Зменшити дуже швидко.
Я хочу, щоб переконатися, що він не йде до краю екрану, щоб ми могли бачити всі.
Потягніть, що в небагато. Добре.
Прокрутіть вниз, і проблема прямо тут.
Що станеться, якщо ми спускаємося і наш поточний вузол вже нульові,
наш батьківський вузол є нульовим, тому, якщо ми дивимося на самому верху, прямо тут -
Якщо цей час циклу ніколи не виконується
тому що наше поточне значення дорівнює нулю - наш корінь нульовою так текущ. є недійсним -
Потім наші батьки ніколи не буде встановлений в текущ. Або допустиме значення,
Таким чином, батьки також буде нульовим.
Ми повинні пам'ятати, щоб перевірити, що
До того часу ми приступимо тут, і ми починаємо доступ до значення батьків.
Отже, що відбувається? Ну, якщо батько є нуль -
якщо (== NULL батька), - то ми знаємо, що
не повинно бути нічого в дерево.
Ми повинні намагатися вставити його в корені.
Ми можемо зробити це, просто задавши корінь, рівний новий вузол.
Тоді в цій точці ми насправді не хочуть, щоб пройти через ці інші речі.
Замість цього, прямо тут, ми можемо зробити або інше-якщо-іншому,
або ми могли б об'єднати всі тут в іншому,
але тут ми будемо використовувати ще й зробити це таким чином.
Тепер, ми збираємося перевірити, щоб переконатися, що наші батьки не нульовий
до цього насправді намагається отримати доступ до його полях.
Це допоможе нам уникнути помилки сегментації.
Таким чином, ми кинути палити, зменшити масштаб, компілювати, запускати.
>> Немає помилки, але у нас ще є купа витоків пам'яті
тому що ми не звільнити будь-якого з наших вузлів.
Але, якщо ми йдемо сюди, і ми дивимося на нашу роздруківку,
ми бачимо, що, ну, схоже, що всі наші вставками поверталися правда, і це добре.
Вставки все вірно,
, А потім відповідні виклики містить, теж вірно.
>> Гарна робота! Схоже, ми успішно написана вставки.
Це все, що у нас є проблеми специфікації для набору на цьому тижні.
Одна кумедна можливість подумати про те, як би ви насправді йдуть в
і безкоштовно всі вузли в цьому дереві.
Ми можемо зробити це різними способами,
але я залишу це до вас, щоб експеримент,
і як весело завданням, спробуйте і переконайтеся, що ви можете переконатися,
що ця доповідь Valgrind не повертає помилки і витоку.
>> Удачі на Хаффман цьому тижні поставленої задачі кодування,
і ми будемо бачити вас на наступному тижні!
[CS50.TV]