1 00:00:00,000 --> 00:00:02,500 [Powered by Google Translate] [Частина 7] [менш комфортно] 2 00:00:02,500 --> 00:00:04,890 [Nate Хардісон] [Harvard University] 3 00:00:04,890 --> 00:00:07,000 [Це CS50.] [CS50.TV] 4 00:00:07,000 --> 00:00:09,080 >> Ласкаво просимо до розділу 7. 5 00:00:09,080 --> 00:00:11,330 Завдяки ураган Sandy, 6 00:00:11,330 --> 00:00:13,440 замість того нормального перерізу на цьому тижні, 7 00:00:13,440 --> 00:00:17,650 Ми робимо це прохідний, через розділ питань. 8 00:00:17,650 --> 00:00:22,830 Я збираюся бути наступні Поряд з проблемою Set 6 Специфікація, 9 00:00:22,830 --> 00:00:25,650 і переживає всі питання в 10 00:00:25,650 --> 00:00:27,770 Розділ розділу Питання. 11 00:00:27,770 --> 00:00:30,940 Якщо є які-небудь питання, 12 00:00:30,940 --> 00:00:32,960 будь ласка, напишіть їх на CS50 обговорити. 13 00:00:32,960 --> 00:00:35,480 >> Добре. Давайте почнемо. 14 00:00:35,480 --> 00:00:40,780 Прямо зараз я дивлюся на стор 3 Специфікація поставленого завдання. 15 00:00:40,780 --> 00:00:44,110 Ми йдемо до першого почати розмову про бінарних дерев 16 00:00:44,110 --> 00:00:47,850 З тих є багато, що мають відношення до проблеми набору на цьому тижні - 17 00:00:47,850 --> 00:00:49,950 Кодування Хаффмана дерева. 18 00:00:49,950 --> 00:00:55,000 Один з найперших структур даних ми говорили про на CS50 був масиву. 19 00:00:55,000 --> 00:01:00,170 Пам'ятайте, що масив являє собою послідовність елементів - 20 00:01:00,170 --> 00:01:04,019 Все ж типу - зберігаються поруч один з одним в пам'яті. 21 00:01:04,019 --> 00:01:14,420 Якщо у мене є масив цілих чисел, що я можу зробити за допомогою цієї коробки-числа-цілі стиль - 22 00:01:14,420 --> 00:01:20,290 Скажімо, у мене є 5 в першому полі, у мене 7 в другій, 23 00:01:20,290 --> 00:01:27,760 то у мене є 8, 10, та 20 в кінцевому полі. 24 00:01:27,760 --> 00:01:33,000 Пам'ятайте, що два дійсно хороших речей про це масиві 25 00:01:33,000 --> 00:01:38,800 в тому, що у нас є ця постійна часу доступ до будь-який конкретний елемент 26 00:01:38,800 --> 00:01:40,500  в масиві, якщо ми знаємо його індекс. 27 00:01:40,500 --> 00:01:44,670 Наприклад, якщо я хочу, щоб захопити третій елемент масиву - 28 00:01:44,670 --> 00:01:47,870 з індексом 2, використовуючи нашу з нуля системи - 29 00:01:47,870 --> 00:01:52,220 Я буквально тільки що потрібно зробити простий математичний розрахунок, 30 00:01:52,220 --> 00:01:56,170 стрибати на цю посаду в масиві, 31 00:01:56,170 --> 00:01:57,840 витягніть 8, який зберігається там, 32 00:01:57,840 --> 00:01:59,260 і я добре йти. 33 00:01:59,260 --> 00:02:03,350 >> Один з поганих речей про це масиву - про які ми говорили 34 00:02:03,350 --> 00:02:05,010 Коли ми обговорювали зв'язані списки - 35 00:02:05,010 --> 00:02:09,120 є те, що якщо я хочу, щоб вставити елемент у цьому масиві, 36 00:02:09,120 --> 00:02:11,090 Я збираюся зробити деяке переміщення навколо. 37 00:02:11,090 --> 00:02:12,940 Наприклад, цей масив прямо тут 38 00:02:12,940 --> 00:02:16,850 є в певному порядку - відсортовані в порядку зростання - 39 00:02:16,850 --> 00:02:19,440 5, потім 7, потім 8, потім 10, а потім 20 - 40 00:02:19,440 --> 00:02:23,100 але якщо я хочу, щоб вставити номер 9 у цьому масиві, 41 00:02:23,100 --> 00:02:27,460 Я хочу, щоб перенести деякі елементи для того, щоб звільнити місце. 42 00:02:27,460 --> 00:02:30,440 Ми можемо зробити це тут. 43 00:02:30,440 --> 00:02:35,650 Я збираюся повинні рухатися 5, 7, а потім 8; 44 00:02:35,650 --> 00:02:38,720 створити зазор, де я можу поставити 9, 45 00:02:38,720 --> 00:02:45,910 , А потім 10 і 20 може піти в праві 9. 46 00:02:45,910 --> 00:02:49,450 Це свого роду болю, тому що в гіршому випадку - 47 00:02:49,450 --> 00:02:54,350 коли ми того, щоб вставити або на початку, або в кінці 48 00:02:54,350 --> 00:02:56,040 масиву, в залежності від того, як ми зміщення - 49 00:02:56,040 --> 00:02:58,850 Ми могли б у кінцевому підсумку того, щоб зрушити всі елементи 50 00:02:58,850 --> 00:03:00,750 що ми в даний час зберігання в масиві. 51 00:03:00,750 --> 00:03:03,810 >> Отже, що був спосіб обійти це? 52 00:03:03,810 --> 00:03:09,260 Спосіб обійти це був піти у наш пов'язаного списку метод, де - 53 00:03:09,260 --> 00:03:19,820 замість зберігання елементів 5, 7, 8, 10 і 20 все поруч один з одним в пам'яті - 54 00:03:19,820 --> 00:03:25,630 Замість того, що ми робили, було зберігати їх виду, де б ми хотіли, щоб зберегти їх 55 00:03:25,630 --> 00:03:32,470 У цих зв'язаний список вузлів, які я малюю тут, начебто спеціальних. 56 00:03:32,470 --> 00:03:42,060 І тоді ми з'єднали їх разом, використовуючи ці наступні покажчики. 57 00:03:42,060 --> 00:03:44,370 Я можу їсти покажчик від 5 до 7, 58 00:03:44,370 --> 00:03:46,420 Покажчик від 7 до 8, 59 00:03:46,420 --> 00:03:47,770 Покажчик від 8 до 10, 60 00:03:47,770 --> 00:03:51,220 І, нарешті, покажчик від 10 до 20, 61 00:03:51,220 --> 00:03:54,880 , А потім нульовим покажчиком на 20 про те, що там нічого не залишилося. 62 00:03:54,880 --> 00:03:59,690 Компроміс, що ми маємо тут 63 00:03:59,690 --> 00:04:05,360 є те, що тепер, якщо ми хочемо, щоб вставити номер 9 в нашій відсортований список, 64 00:04:05,360 --> 00:04:08,270 все, що нам потрібно зробити, це створити новий вузол з 9, 65 00:04:08,270 --> 00:04:12,290 підключити його до точки в потрібне місце, 66 00:04:12,290 --> 00:04:20,630 , А потім повторно дроти від 8 до точки до 9. 67 00:04:20,630 --> 00:04:25,660 Це досить швидко, припускаючи, що ми точно знаємо, де ми хочемо, щоб вставити 9. 68 00:04:25,660 --> 00:04:32,610 Але компроміс в обмін на це, що ми тепер втратили постійне час доступу 69 00:04:32,610 --> 00:04:36,230 будь-який конкретний елемент в нашій структурі даних. 70 00:04:36,230 --> 00:04:40,950 Наприклад, якщо я хочу знайти четвертий елемент у цій пов'язаного списку, 71 00:04:40,950 --> 00:04:43,510 Я збираюся мати, щоб почати на самому початку списку 72 00:04:43,510 --> 00:04:48,930 і працює свій шлях через рахунки вузла-на-вузлі, поки не знайду четвертий. 73 00:04:48,930 --> 00:04:55,870 >> Для того щоб отримати більш широкий доступ продуктивність, ніж зв'язаний список - 74 00:04:55,870 --> 00:04:59,360 але і зберегти деякі з переваг, які у нас були 75 00:04:59,360 --> 00:05:01,800 В умовах введення часу від пов'язаного списку - 76 00:05:01,800 --> 00:05:05,750 бінарне дерево буде необхідно використовувати трохи більше пам'яті. 77 00:05:05,750 --> 00:05:11,460 Зокрема, замість того, щоб просто мати один покажчик в бінарному дереві вузлів - 78 00:05:11,460 --> 00:05:13,350 як зв'язаний список вузлів робить - 79 00:05:13,350 --> 00:05:16,950 Ми збираємося додати другий покажчик на двійковий вузла дерева. 80 00:05:16,950 --> 00:05:19,950 Замість того, щоб просто мати один покажчик на наступний елемент, 81 00:05:19,950 --> 00:05:24,420 ми будемо мати покажчик на лівий дитини та право дитини. 82 00:05:24,420 --> 00:05:26,560 >> Давайте намалюємо картинку, щоб подивитися, що насправді виглядає. 83 00:05:26,560 --> 00:05:31,350 Знову ж таки, я збираюся використовувати ці коробки і стріли. 84 00:05:31,350 --> 00:05:37,150 Бінарний вузол дерева буде почати з простою коробці. 85 00:05:37,150 --> 00:05:40,940 Це буде мати місце для значення, 86 00:05:40,940 --> 00:05:47,280 а потім він також буде мати простір для лівого дитини та право дитини. 87 00:05:47,280 --> 00:05:49,280 Я буду називати їх тут. 88 00:05:49,280 --> 00:05:57,560 Ми збираємося у ліва дитини, і тоді ми будемо мати право дитини. 89 00:05:57,560 --> 00:05:59,920 Є багато різних способів зробити це. 90 00:05:59,920 --> 00:06:02,050 Іноді для простору і зручності, 91 00:06:02,050 --> 00:06:06,460 Я насправді зробити це, як я роблю тут на дні 92 00:06:06,460 --> 00:06:10,910 де я збираюся мати значення у верхній частині, 93 00:06:10,910 --> 00:06:14,060 , А потім праву дитини на правій нижній, 94 00:06:14,060 --> 00:06:16,060 і лівої дитини на лівій нижній. 95 00:06:16,060 --> 00:06:20,250 Повертаючись до цієї вершини діаграми, 96 00:06:20,250 --> 00:06:22,560 у нас є значення на самому верху, 97 00:06:22,560 --> 00:06:25,560 Потім у нас є лівий покажчик дитини, і тоді ми маємо право дитині покажчик. 98 00:06:25,560 --> 00:06:30,110 >> У специфікації поставленого завдання, 99 00:06:30,110 --> 00:06:33,110 ми говоримо про розробку вузла, який має значення 7, 100 00:06:33,110 --> 00:06:39,750 , А потім ліву дитини покажчик, який є порожнім, і права дитини-покажчик, який є нульовим. 101 00:06:39,750 --> 00:06:46,040 Ми можемо або написати капіталу NULL в просторі для 102 00:06:46,040 --> 00:06:51,610 як лівої дитини та право дитини, або ми можемо зробити це коса риска 103 00:06:51,610 --> 00:06:53,750 в кожному з коробки, щоб вказати, що це нульовий. 104 00:06:53,750 --> 00:06:57,560 Я збираюся зробити це просто, тому що це простіше. 105 00:06:57,560 --> 00:07:03,700 Те, що ви бачите тут два способи побудови діаграм дуже простий вузол двійкового дерева 106 00:07:03,700 --> 00:07:07,960 де у нас є значення 7 і нульових покажчиків дитини. 107 00:07:07,960 --> 00:07:15,220 >> Друга частина нашої специфікації переговори про те, як зі зв'язаними списками - 108 00:07:15,220 --> 00:07:18,270 Пам'ятаєте, ми тільки повинні були триматися за перший елемент у списку 109 00:07:18,270 --> 00:07:20,270 пригадати весь список - 110 00:07:20,270 --> 00:07:26,140 і аналогічно, з бінарним деревом, ми тільки повинні тримати на одного покажчика на дереві 111 00:07:26,140 --> 00:07:31,120 З метою збереження контролю над усією структурою даних. 112 00:07:31,120 --> 00:07:36,150 Цей спеціальний елемент дерева називається кореневим вузлом дерева. 113 00:07:36,150 --> 00:07:43,360 Наприклад, якщо цей вузол - це вузол, що містить значення 7 114 00:07:43,360 --> 00:07:45,500 з нульовою лівої і правої дитині покажчики - 115 00:07:45,500 --> 00:07:47,360 були єдиною цінністю в нашому дереві, 116 00:07:47,360 --> 00:07:50,390 то це буде нашим кореневим вузлом. 117 00:07:50,390 --> 00:07:52,240 Це самий початок нашого дерева. 118 00:07:52,240 --> 00:07:58,530 Ми можемо побачити це трохи ясніше, як тільки ми почнемо додавати додаткові вузли до нашого дереву. 119 00:07:58,530 --> 00:08:01,510 Дозвольте мені підтягти нову сторінку. 120 00:08:01,510 --> 00:08:05,000 >> Тепер ми будемо малювати дерево, яке має 7 на корені, 121 00:08:05,000 --> 00:08:10,920 і 3 внутрішній стороні лівого дитини, і 9 в правому дитини. 122 00:08:10,920 --> 00:08:13,500 Знову ж таки, це досить просто. 123 00:08:13,500 --> 00:08:26,510 У нас є 7, намалювати вузол 3, вузол 9, 124 00:08:26,510 --> 00:08:32,150 і я збираюся встановити лівий покажчик дитини від 7 до вказують на вузол, що містить 3, 125 00:08:32,150 --> 00:08:37,850 і право дитини покажчик вузол, що містить від 7 до вузол, що містить 9. 126 00:08:37,850 --> 00:08:42,419 Тепер, так як 3 і 9 не мають дітей, 127 00:08:42,419 --> 00:08:48,500 ми збираємося встановити всі їх покажчики дитини, є недійсними. 128 00:08:48,500 --> 00:08:56,060 Тут корінь нашого дерева відповідає вузол, що містить номер 7. 129 00:08:56,060 --> 00:09:02,440 Ви можете бачити, що якщо всі ми маємо покажчик на кореневий вузол, 130 00:09:02,440 --> 00:09:07,330 ми можемо пройти через наше дерево і доступ як дочірні вузли - 131 00:09:07,330 --> 00:09:10,630 як 3 і 9. 132 00:09:10,630 --> 00:09:14,820 Не потрібно зберегти покажчики на кожному вузлі дерева. 133 00:09:14,820 --> 00:09:22,080 Добре. Тепер ми збираємося додати ще один вузол до цієї схеми. 134 00:09:22,080 --> 00:09:25,370 Ми збираємося додати вузол, що містить 6, 135 00:09:25,370 --> 00:09:34,140 і ми збираємося додати його в якості правого нащадка вузла, що містить 3. 136 00:09:34,140 --> 00:09:41,850 Щоб зробити це, я збираюся стерти цю нульового покажчика в 3-вузлі 137 00:09:41,850 --> 00:09:47,750 і підключити його до вказувала на вузол, що містить 6. Добре. 138 00:09:47,750 --> 00:09:53,800 >> На даний момент, давайте перейдемо трохи термінології. 139 00:09:53,800 --> 00:09:58,230 Для початку, причина того, що це називається бінарне дерево, зокрема, 140 00:09:58,230 --> 00:10:00,460 є те, що вона має два покажчика дитини. 141 00:10:00,460 --> 00:10:06,020 Є й інші види дерев, які мають більше покажчиків дитини. 142 00:10:06,020 --> 00:10:10,930 Зокрема, ви зробили "спробувати" в проблемі Set 5. 143 00:10:10,930 --> 00:10:19,310 Ви помітите, що в цій спробі, у вас було 27 різних покажчиків на різні діти - 144 00:10:19,310 --> 00:10:22,410 по одному для кожної з 26 букв англійського алфавіту, 145 00:10:22,410 --> 00:10:25,410 , А потім 27-й по апострофа - 146 00:10:25,410 --> 00:10:28,900 так, що схожий на тип дерева. 147 00:10:28,900 --> 00:10:34,070 Але тут, так як це двійковий, у нас є тільки два покажчика дитини. 148 00:10:34,070 --> 00:10:37,880 >> На додаток до цієї кореневий вузол, що ми говорили про те, 149 00:10:37,880 --> 00:10:41,470 Ми також кидали навколо цього терміна "дитина". 150 00:10:41,470 --> 00:10:44,470 Що це означає для одного вузла, щоб бути нащадком іншого вузла? 151 00:10:44,470 --> 00:10:54,060 Це буквально означає, що дитина вузол є нащадком іншого вузла 152 00:10:54,060 --> 00:10:58,760 якщо інший вузол має одну з його дочірніх покажчики встановлені, щоб вказати на цьому вузлі. 153 00:10:58,760 --> 00:11:01,230 Щоб поставити це в більш конкретних термінах, 154 00:11:01,230 --> 00:11:11,170 якщо 3, вказав на одну дитину покажчики 7, потім 3 є дочірнім 7. 155 00:11:11,170 --> 00:11:14,510 Якби ми могли зрозуміти, що діти до 7 років - 156 00:11:14,510 --> 00:11:18,510 Ну, ми бачимо, що 7 має покажчик на 3 та покажчик на 9, 157 00:11:18,510 --> 00:11:22,190 тому 9 і 3 дітей 7. 158 00:11:22,190 --> 00:11:26,650 Дев'ять дітей немає, тому що його покажчики дитини є недійсними, 159 00:11:26,650 --> 00:11:30,940 і 3 має тільки одну дитину, 6. 160 00:11:30,940 --> 00:11:37,430 Шість також не має дітей, тому що обидва його покажчики є недійсними, яку ми будемо малювати прямо зараз. 161 00:11:37,430 --> 00:11:45,010 >> Крім того, ми також говоримо про батьків конкретного вузла, 162 00:11:45,010 --> 00:11:51,100 і це, як і слід було очікувати, зворотний цієї дитини опису. 163 00:11:51,100 --> 00:11:58,620 Кожен вузол має тільки одного батька - замість двох, як ви могли б очікувати з людьми. 164 00:11:58,620 --> 00:12:03,390 Наприклад, батько 3, 7. 165 00:12:03,390 --> 00:12:10,800 Батько 9 також 7 і батьків 6, 3. Не так багато до нього. 166 00:12:10,800 --> 00:12:15,720 У нас також є умови, щоб говорити про бабусь і дідусів і внуків, 167 00:12:15,720 --> 00:12:18,210 і взагалі ми говоримо про предків 168 00:12:18,210 --> 00:12:20,960 і нащадків конкретного вузла. 169 00:12:20,960 --> 00:12:25,710 Предком вузла - або предків, швидше, вузол - 170 00:12:25,710 --> 00:12:32,730 Всі вузлів, які лежать на шляху від кореня до цього вузла. 171 00:12:32,730 --> 00:12:36,640 Наприклад, якщо я дивлюся на вузлі 6, 172 00:12:36,640 --> 00:12:46,430 Потім предки збираються бути як 3 і 7. 173 00:12:46,430 --> 00:12:55,310 Предки 9, наприклад, є - якщо я дивлюся на вузлі 9 - 174 00:12:55,310 --> 00:12:59,990 Потім предка з 9 знаходиться всього в 7. 175 00:12:59,990 --> 00:13:01,940 І нащадки в точності навпаки. 176 00:13:01,940 --> 00:13:05,430 Якщо я хочу подивитися на всі нащадки 7, 177 00:13:05,430 --> 00:13:11,020 Потім я повинен дивитися на всі вузли під ним. 178 00:13:11,020 --> 00:13:16,950 Отже, у мене є 3, 9 і 6, всі як нащадки 7. 179 00:13:16,950 --> 00:13:24,170 >> Останній термін, який ми будемо говорити про це поняття буття рідного брата. 180 00:13:24,170 --> 00:13:27,980 Брати і сестри - на кшталт наступних разом на цих сімейних умовах - 181 00:13:27,980 --> 00:13:33,150 вузли, які знаходяться на тому ж рівні в дереві. 182 00:13:33,150 --> 00:13:42,230 Так, 3 і 9 братів і сестер, тому що вони на тому ж рівні в дереві. 183 00:13:42,230 --> 00:13:46,190 Вони обидва мають одного батька, 7. 184 00:13:46,190 --> 00:13:51,400 6 не має братів і сестер, бо 9 не має дітей. 185 00:13:51,400 --> 00:13:55,540 І 7 не має братів і сестер, тому що це корінь нашого дерева, 186 00:13:55,540 --> 00:13:59,010 і є тільки коли-небудь 1 корінь. 187 00:13:59,010 --> 00:14:02,260 На 7 братів і сестер, щоб там мали б бути вище 7 вузлів. 188 00:14:02,260 --> 00:14:07,480 Там повинно було б бути батьком 7, в якому випадку 7 більше не буде коренем дерева. 189 00:14:07,480 --> 00:14:10,480 Потім, що нові батьки з 7 також буде мати дитину, 190 00:14:10,480 --> 00:14:16,480 і що дитина б тоді брат 7. 191 00:14:16,480 --> 00:14:21,040 >> Добре. Рухаємося далі. 192 00:14:21,040 --> 00:14:24,930 Коли ми почали нашу розмову про бінарних дерев, 193 00:14:24,930 --> 00:14:28,790 ми говорили про те, як ми збираємося використовувати їх для 194 00:14:28,790 --> 00:14:32,800 отримати перевагу над обох масивів і пов'язаних списків. 195 00:14:32,800 --> 00:14:37,220 І те, як ми збираємося зробити це з цим замовленням власності. 196 00:14:37,220 --> 00:14:41,080 Ми говоримо, що бінарне дерево упорядкований, у відповідності зі специфікацією, 197 00:14:41,080 --> 00:14:45,740 якщо для кожного вузла в дереві, всі його нащадки зліва - 198 00:14:45,740 --> 00:14:48,670 лівий дитині, і всіх нащадків лівої дитини - 199 00:14:48,670 --> 00:14:54,510 мають менші значення, а все вузли справа - 200 00:14:54,510 --> 00:14:57,770 права дитини і всіх нащадків права дитини - 201 00:14:57,770 --> 00:15:02,800 є вузли більше, ніж значення поточного вузла, що ми дивимося. 202 00:15:02,800 --> 00:15:07,850 Просто для простоти ми будемо вважати, що немає ніяких дублюючих вузлів у нашому дереві. 203 00:15:07,850 --> 00:15:11,180 Наприклад, в цьому дереві ми не збираємося мати справу з випадком 204 00:15:11,180 --> 00:15:13,680 де у нас є значення 7 в корені 205 00:15:13,680 --> 00:15:16,720  і у нас також є значення 7 в іншому місці в дерево. 206 00:15:16,720 --> 00:15:24,390 У цьому випадку, ви помітите, що це дерево дійсно замовлено. 207 00:15:24,390 --> 00:15:26,510 У нас є значення 7 на корені. 208 00:15:26,510 --> 00:15:29,720 Всі зліва від 7 - 209 00:15:29,720 --> 00:15:35,310 якщо я відміню всі ці маленькі знаки тут - 210 00:15:35,310 --> 00:15:40,450 все, що зліва від 7 - 3 і 6 - 211 00:15:40,450 --> 00:15:49,410 ці значення знаходяться менш ніж в 7, і все, що правіше - що саме це 9 - 212 00:15:49,410 --> 00:15:53,450 більше 7. 213 00:15:53,450 --> 00:15:58,650 >> Це не тільки впорядковане дерево, що містять ці значення, 214 00:15:58,650 --> 00:16:03,120 Але давайте намалювати кілька з них. 215 00:16:03,120 --> 00:16:05,030 Існує насправді ціла купа способів, якими ми можемо це зробити. 216 00:16:05,030 --> 00:16:09,380 Я збираюся використовувати скорочену тільки, щоб тримати речі простими, де - 217 00:16:09,380 --> 00:16:11,520 , А не розтягуючи цілому коробки-і-стрілки - 218 00:16:11,520 --> 00:16:14,220 Я просто хочу звернути номерів і додати стрілки, що з'єднують їх. 219 00:16:14,220 --> 00:16:22,920 Для початку, ми будемо просто писати свої оригінальні дерево ще раз, де у нас було 7, а потім 3, 220 00:16:22,920 --> 00:16:25,590 , А потім 3 зазначено назад в праві на 6, 221 00:16:25,590 --> 00:16:30,890 і 7 мали право дитини, яка була 9. 222 00:16:30,890 --> 00:16:33,860 Добре. Які ще один спосіб, що ми могли б написати це дерево? 223 00:16:33,860 --> 00:16:38,800 Замість того, щоб бути 3 лівий дитини 7, 224 00:16:38,800 --> 00:16:41,360 Ми також могли б бути 6 лівому дитини 7, 225 00:16:41,360 --> 00:16:44,470 , А потім 3 буде лівий дитини 6. 226 00:16:44,470 --> 00:16:48,520 Це буде виглядати наступним чином дерево прямо тут, де у мене 7, 227 00:16:48,520 --> 00:16:57,860 потім 6, потім 3, і 9 праворуч. 228 00:16:57,860 --> 00:17:01,490 Ми також не повинні мати 7, як наш кореневий вузол. 229 00:17:01,490 --> 00:17:03,860 Ми могли б також мати 6, як наш кореневий вузол. 230 00:17:03,860 --> 00:17:06,470 Що б виглядати? 231 00:17:06,470 --> 00:17:09,230 Якщо ми збираємося зберегти цю наказав власності, 232 00:17:09,230 --> 00:17:12,970 все, що лівіше з 6 повинен бути менше, ніж вона. 233 00:17:12,970 --> 00:17:16,540 Там тільки одна можливість, і ось 3. 234 00:17:16,540 --> 00:17:19,869 Але тоді, як право дитини з 6, у нас є дві можливості. 235 00:17:19,869 --> 00:17:25,380 По-перше, ми могли б 7, а потім 9, 236 00:17:25,380 --> 00:17:28,850 або ми можемо зробити це - як я збираюся зробити тут - 237 00:17:28,850 --> 00:17:34,790 де у нас є 9, права дитини 6, 238 00:17:34,790 --> 00:17:39,050 , А потім 7 в якості лівого дитиною з 9. 239 00:17:39,050 --> 00:17:44,240 >> Тепер, 7 і 6 не є єдино можливими значеннями кореня. 240 00:17:44,240 --> 00:17:50,200 Ми могли б також мати 3 бути докорінно. 241 00:17:50,200 --> 00:17:52,240 Що відбудеться, якщо 3 є в корені? 242 00:17:52,240 --> 00:17:54,390 Тут все стає трохи цікавіше. 243 00:17:54,390 --> 00:17:58,440 Три не має ніякого значення, які менше, ніж він, 244 00:17:58,440 --> 00:18:02,070 так що вся ліва сторона дерева просто буде нульовою. 245 00:18:02,070 --> 00:18:03,230 Там не буде нічого немає. 246 00:18:03,230 --> 00:18:07,220 Праворуч, ми могли б перерахувати речі в порядку зростання. 247 00:18:07,220 --> 00:18:15,530 Ми могли б 3, то 6, то 7, то 9. 248 00:18:15,530 --> 00:18:26,710 Або, ми могли б зробити 3, то 6, то 9, то 7. 249 00:18:26,710 --> 00:18:35,020 Або, ми могли б зробити 3, потім 7, потім 6, потім 9. 250 00:18:35,020 --> 00:18:40,950 Або, 3, 7 - насправді немає, ми не можемо зробити 7 більше. 251 00:18:40,950 --> 00:18:43,330 Це наша одне там. 252 00:18:43,330 --> 00:18:54,710 Ми можемо зробити 9, а потім з 9 ми можемо зробити 6, а потім 7. 253 00:18:54,710 --> 00:19:06,980 Або, що ми можемо зробити 3, то 9, то 7, а потім 6. 254 00:19:06,980 --> 00:19:12,490 >> Одна річ, щоб звернути вашу увагу на тут 255 00:19:12,490 --> 00:19:14,510 що ці дерева трохи дивний вигляд. 256 00:19:14,510 --> 00:19:17,840 Зокрема, якщо ми дивимося на 4 дерева на правій стороні - 257 00:19:17,840 --> 00:19:20,930 Я їх коло, тут - 258 00:19:20,930 --> 00:19:28,410 ці дерева виглядають майже так само, як зв'язаний список. 259 00:19:28,410 --> 00:19:32,670 Кожен вузол має тільки одну дитину, 260 00:19:32,670 --> 00:19:38,950 і тому ми не повинні все це деревовидна структура, яку ми бачимо, наприклад, 261 00:19:38,950 --> 00:19:44,720  У цьому одиноке дерево тут на нижній лівій. 262 00:19:44,720 --> 00:19:52,490 Ці дерева насправді називається виродженим, бінарні дерева, 263 00:19:52,490 --> 00:19:54,170 і ми поговоримо про це докладніше в майбутньому - 264 00:19:54,170 --> 00:19:56,730 Особливо якщо ви йдете на прийняття інших курсів з інформатики. 265 00:19:56,730 --> 00:19:59,670 Ці дерева є виродженими. 266 00:19:59,670 --> 00:20:03,780 Вони не дуже корисно, тому що, дійсно, ця структура піддається 267 00:20:03,780 --> 00:20:08,060  для пошуку рази схожий на зв'язаний список. 268 00:20:08,060 --> 00:20:13,050 Ми не отримуємо, щоб скористатися додаткової пам'яті - це додатковий покажчик - 269 00:20:13,050 --> 00:20:18,840 тому що наші структури поганих таким чином. 270 00:20:18,840 --> 00:20:24,700 Замість того, щоб іти далі і зробити з бінарних дерев, які мають 9 на корені, 271 00:20:24,700 --> 00:20:27,220 яка є останній випадок, що ми повинні, 272 00:20:27,220 --> 00:20:32,380 ми замість цього, на даний момент, поговоримо трохи про це іншим терміном 273 00:20:32,380 --> 00:20:36,150 , Які ми використовуємо, коли говоримо про дерева, які називають висотою. 274 00:20:36,150 --> 00:20:45,460 >> Висота дерева це відстань від кореня до найвіддаленіших вузлів, 275 00:20:45,460 --> 00:20:48,370 або, вірніше, кількість стрибків, що ви повинні зробити для того, щоб 276 00:20:48,370 --> 00:20:53,750 починається з кореня і потім в кінцевому підсумку на найвіддаленішому вузол в дереві. 277 00:20:53,750 --> 00:20:57,330 Якщо ми подивимося на деякі з цих дерев, які ми намалювали прямо тут, 278 00:20:57,330 --> 00:21:07,870 ми бачимо, що якщо ми візьмемо це дерево в лівому верхньому кутку, і ми починаємо на 3, 279 00:21:07,870 --> 00:21:14,510 Потім ми повинні зробити 1-хопу, щоб дістатися до 6, другого стрибка, щоб дістатися до 7, 280 00:21:14,510 --> 00:21:20,560 і третій хоп, щоб дістатися до 9. 281 00:21:20,560 --> 00:21:26,120 Таким чином, висота цього дерева 3. 282 00:21:26,120 --> 00:21:30,640 Ми можемо зробити те ж саме вправу для інших дерев, викладені з цієї зеленої, 283 00:21:30,640 --> 00:21:40,100 і ми бачимо, що висота всіх цих дерев також дійсно 3. 284 00:21:40,100 --> 00:21:45,230 Це частина того, що робить їх вироджені - 285 00:21:45,230 --> 00:21:53,750 що їх висота складає всього один менше, ніж кількість вузлів по всьому дереву. 286 00:21:53,750 --> 00:21:58,400 Якщо ми подивимося на цього іншого дерева, що це оточення з червоним, з іншого боку, 287 00:21:58,400 --> 00:22:03,920 ми бачимо, що найбільш віддалених вузлів листя 6 і 9 - 288 00:22:03,920 --> 00:22:06,940 листя опиняються ті вузли, які не мають дітей. 289 00:22:06,940 --> 00:22:11,760 Отже, для того, щоб отримати від кореневого вузла або 6 або 9, 290 00:22:11,760 --> 00:22:17,840 ми повинні зробити одне-хопа, щоб дістатися до 7, а потім другого стрибка, щоб дістатися до 9, 291 00:22:17,840 --> 00:22:21,240 і аналогічно, тільки другого стрибка з 7, щоб дістатися до 6. 292 00:22:21,240 --> 00:22:29,080 Таким чином, висота цього дерева тут тільки 2. 293 00:22:29,080 --> 00:22:35,330 Ви можете повернутися назад і зробити це для всіх інших дерев, які ми раніше обговорювали 294 00:22:35,330 --> 00:22:37,380 починаючи з 7 і 6, 295 00:22:37,480 --> 00:22:42,500 і ви побачите, що висота всіх цих дерев також 2. 296 00:22:42,500 --> 00:22:46,320 >> Тому ми говорили про наказав бінарні дерева 297 00:22:46,320 --> 00:22:50,250 і чому вони круті, тому що ви можете шукати через них в 298 00:22:50,250 --> 00:22:53,810 дуже схоже на пошуки більш впорядкований масив. 299 00:22:53,810 --> 00:22:58,720 Тут ми говоримо про те, що поліпшення час пошуку 300 00:22:58,720 --> 00:23:02,730 над простий зв'язаний список. 301 00:23:02,730 --> 00:23:05,010 З зв'язаний список - якщо ви хочете знайти конкретний елемент - 302 00:23:05,010 --> 00:23:07,470 Ви в кращому випадку збирається зробити якийсь лінійний пошук 303 00:23:07,470 --> 00:23:10,920 де ви починаєте на початку списку і хмелю один-на-один - 304 00:23:10,920 --> 00:23:12,620 одного вузла на один вузол - 305 00:23:12,620 --> 00:23:16,060 весь список, поки не знайдете те, що ви шукаєте. 306 00:23:16,060 --> 00:23:19,440 Беручи до уваги, якщо у вас є бінарне дерево, яке зберігається в цьому гарному форматі, 307 00:23:19,440 --> 00:23:23,300 Ви можете фактично отримати більше бінарний пошук триває 308 00:23:23,300 --> 00:23:25,160 де ви розділяй і володарюй 309 00:23:25,160 --> 00:23:29,490 і пошуку за допомогою відповідних половини дерев на кожному кроці. 310 00:23:29,490 --> 00:23:32,840 Давайте подивимося, як це працює. 311 00:23:32,840 --> 00:23:38,850 >> Якщо у нас є - знову ж таки, повертаючись до нашої початкової дерево - 312 00:23:38,850 --> 00:23:46,710 ми починаємо в 7, у нас є 3 зліва, 9 праворуч, 313 00:23:46,710 --> 00:23:51,740 і під 3 маємо 6. 314 00:23:51,740 --> 00:24:01,880 Якщо ми хочемо, щоб знайти номер 6 у цьому дереві, ми б почали в корені. 315 00:24:01,880 --> 00:24:08,910 Ми б порівняти значення ми шукаємо, скажімо, 6, 316 00:24:08,910 --> 00:24:12,320 зі значенням, що зберігається у вузлі, який ми в даний час дивимося, 7, 317 00:24:12,320 --> 00:24:21,200 виявите, що 6 є дійсно менше, ніж 7, так що ми б рухатися вліво. 318 00:24:21,200 --> 00:24:25,530 Якщо значення 6 було більше, ніж 7, ми б замість переміщується вправо. 319 00:24:25,530 --> 00:24:29,770 Оскільки ми знаємо, що - завдяки структурі нашої наказав бінарному дереві - 320 00:24:29,770 --> 00:24:33,910 всі значення менше 7 будуть зберігатися зліва від 7, 321 00:24:33,910 --> 00:24:40,520 немає необхідності навіть турбуватися, дивлячись через праву сторону дерева. 322 00:24:40,520 --> 00:24:43,780 Як тільки ми переходимо до лівої, і ми тепер на вузол, що містить 3, 323 00:24:43,780 --> 00:24:48,110 ми можемо зробити те ж порівняння ще раз, де ми порівнюємо 3 і 6. 324 00:24:48,110 --> 00:24:52,430 І ми бачимо, що в той час як 6 - цінність, яку ми шукаємо, - це більше, ніж 3, 325 00:24:52,430 --> 00:24:58,580 ми можемо перейти до правої сторони вузол, що містить 3. 326 00:24:58,580 --> 00:25:02,670 Там немає лівій стороні тут, так що ми могли б проігнорував. 327 00:25:02,670 --> 00:25:06,510 Але ми знаємо тільки, що, оскільки ми дивимося на саме дерево, 328 00:25:06,510 --> 00:25:08,660 і ми бачимо, що дерево не має дітей. 329 00:25:08,660 --> 00:25:13,640 >> Це також досить легко знайти 6 в цьому дереві, якщо ми робимо це самі, як люди, 330 00:25:13,640 --> 00:25:16,890 Але давайте стежити за цим процесом механічно, як комп'ютер буде робити 331 00:25:16,890 --> 00:25:18,620 щоб зрозуміти алгоритм. 332 00:25:18,620 --> 00:25:26,200 На даний момент, ми зараз дивимося на вузол, який містить 6, 333 00:25:26,200 --> 00:25:29,180 і ми шукаємо значення 6, 334 00:25:29,180 --> 00:25:31,740 так, дійсно, ми знайшли потрібний вузол. 335 00:25:31,740 --> 00:25:35,070 Ми виявили, що значення 6 в нашому дереві, і ми можемо припинити наші пошуки. 336 00:25:35,070 --> 00:25:37,330 На даний момент, в залежності від того, що відбувається, 337 00:25:37,330 --> 00:25:41,870 ми можемо сказати, так, ми знайшли значення 6, вона існує в нашому дереві. 338 00:25:41,870 --> 00:25:47,640 Або, якщо ми плануємо вставити вузол або зробити щось, що ми можемо зробити, що в цій точці. 339 00:25:47,640 --> 00:25:53,010 >> Давайте зробимо ще пару пошуку, щоб подивитися, як це працює. 340 00:25:53,010 --> 00:25:59,390 Давайте подивимося, що станеться, якщо ми повинні були спробувати і подивитися значення 10. 341 00:25:59,390 --> 00:26:02,970 Якби ми шукати значення 10, ми хотіли б почати з кореня. 342 00:26:02,970 --> 00:26:07,070 Ми бачимо, що 10 більше, ніж 7, тому ми будемо рухатися вправо. 343 00:26:07,070 --> 00:26:13,640 Ми хотіли потрапити на 9 і порівняйте 9 до 10 і бачимо, що 9 є дійсно менше, ніж 10. 344 00:26:13,640 --> 00:26:16,210 Отже, ще раз, ми будемо намагатися рухатися вправо. 345 00:26:16,210 --> 00:26:20,350 Але на даний момент, ми б помітили, що ми знаходимося на нульовий вузол. 346 00:26:20,350 --> 00:26:23,080 Там нічого немає. Там немає нічого, де 10 повинно бути. 347 00:26:23,080 --> 00:26:29,360 Це те, де ми можемо повідомити невдача - що там насправді немає 10 в дерево. 348 00:26:29,360 --> 00:26:35,420 І, нарешті, давайте пройдемо випадку, коли ми намагаємося знайти 1 в дерево. 349 00:26:35,420 --> 00:26:38,790 Це схоже на те, що відбувається, якщо ми подивимося на 10, тільки замість того, щоб йти направо, 350 00:26:38,790 --> 00:26:41,260 Ми збираємося піти наліво. 351 00:26:41,260 --> 00:26:46,170 Ми починаємо в 7 і бачимо, що 1 менше 7, тому ми рухаємося вліво. 352 00:26:46,170 --> 00:26:51,750 Ми добираємося до 3 і бачимо, що 1 менше, ніж 3, тому знову ми намагаємося рухатися вліво. 353 00:26:51,750 --> 00:26:59,080 На даний момент ми маємо нульовий вузол, так що знову ми можемо повідомити про невдачу. 354 00:26:59,080 --> 00:27:10,260 >> Якщо ви хочете дізнатися більше про бінарних дерев, 355 00:27:10,260 --> 00:27:14,420 Є ціла купа веселощів мало проблем, які ви можете зробити з ними. 356 00:27:14,420 --> 00:27:19,450 Я пропоную практикувати малюнок з цих діаграмах один-на-один 357 00:27:19,450 --> 00:27:21,910 і наступні через всі різні кроки, 358 00:27:21,910 --> 00:27:25,060 тому що це прийде в супер-зручна 359 00:27:25,060 --> 00:27:27,480 Не тільки тоді, коли ви робите проблема Huffman кодування набору 360 00:27:27,480 --> 00:27:29,390 але і в майбутніх курсів - 361 00:27:29,390 --> 00:27:32,220 просто навчитися малювати ці структури даних і думаю, через проблеми 362 00:27:32,220 --> 00:27:38,000 з ручкою і папером, або, в даному випадку, IPad і стилусом. 363 00:27:38,000 --> 00:27:41,000 >> На даний момент, однак, ми збираємося рухатися далі, щоб зробити деякі практики кодування 364 00:27:41,000 --> 00:27:44,870 а насправді грати з цими бінарні дерева і подивитися. 365 00:27:44,870 --> 00:27:52,150 Я збираюся повернутися до мого комп'ютера. 366 00:27:52,150 --> 00:27:58,480 Для цієї частини розрізу, замість використання CS50 або CS50 Run простору, 367 00:27:58,480 --> 00:28:01,500 Я збираюся використовувати прилад. 368 00:28:01,500 --> 00:28:04,950 >> Після поряд з специфікацією поставленого завдання, 369 00:28:04,950 --> 00:28:07,740 Я бачу, що я повинен відкрити прилад, 370 00:28:07,740 --> 00:28:11,020 йду в папку Dropbox, створити папку з ім'ям Розділ 7, 371 00:28:11,020 --> 00:28:15,730 , А потім створити файл з ім'ям binary_tree.c. 372 00:28:15,730 --> 00:28:22,050 Тут ми йдемо. У мене є прилад вже відкритий. 373 00:28:22,050 --> 00:28:25,910 Я збираюся тягнути до терміналу. 374 00:28:25,910 --> 00:28:38,250 Я збираюся піти в папку Dropbox, створіть каталог називається section7, 375 00:28:38,250 --> 00:28:42,230 і побачити його абсолютно порожнім. 376 00:28:42,230 --> 00:28:48,860 Тепер я збираюся відкрити binary_tree.c. 377 00:28:48,860 --> 00:28:51,750 Добре. Тут ми йдемо - порожній файл. 378 00:28:51,750 --> 00:28:54,330 >> Давайте повернемося до специфікації. 379 00:28:54,330 --> 00:28:59,850 Специфікація просить, щоб створити нове визначення типу 380 00:28:59,850 --> 00:29:03,080 для двійкового дерева вузлів містять Int значення - 381 00:29:03,080 --> 00:29:07,110 так само як і цінності, які ми звернули в нашій діаграм раніше. 382 00:29:07,110 --> 00:29:11,740 Ми збираємося використовувати цей шаблонний ЬурейеЕ, що ми зробили тут 383 00:29:11,740 --> 00:29:14,420 що ви повинні дізнатися із завдань 5 - 384 00:29:14,420 --> 00:29:19,190 якщо ви зробили хеш-таблиці шляхом завоювання правопису програми. 385 00:29:19,190 --> 00:29:22,540 Ви повинні також визнати, що в розділі минулого тижня 386 00:29:22,540 --> 00:29:23,890 де ми говорили про пов'язаних списків. 387 00:29:23,890 --> 00:29:27,870 У нас це ЬурейеЕ зі структури вузла, 388 00:29:27,870 --> 00:29:34,430 і ми дали цієї структури вузла ця назва структури вузла заздалегідь 389 00:29:34,430 --> 00:29:39,350 так що ми можемо посилатися на нього, так як ми хочемо мати покажчики структури вузла 390 00:29:39,350 --> 00:29:45,740 як частина нашої структури, але ми тоді оточили цю - 391 00:29:45,740 --> 00:29:47,700 або, скоріше, укладені цьому - в ЬурейеЕ 392 00:29:47,700 --> 00:29:54,600 так що, врешті коду, ми можемо звернутися до цієї структури, як тільки вузол, а структура вузла. 393 00:29:54,600 --> 00:30:03,120 >> Це буде дуже схожий на односвязного визначення списку, який ми бачили минулого тижня. 394 00:30:03,120 --> 00:30:20,070 Щоб зробити це, давайте почнемо з виписуючи шаблону. 395 00:30:20,070 --> 00:30:23,840 Ми знаємо, що ми повинні мати ціле значення, 396 00:30:23,840 --> 00:30:32,170 так що ми потрапили в цілочисельне значення, а потім замість того, щоб тільки один покажчик на наступний елемент - 397 00:30:32,170 --> 00:30:33,970 як ми зробили з односвязного списку - 398 00:30:33,970 --> 00:30:38,110 Ми збираємося мати лівий і правий покажчики дитини. 399 00:30:38,110 --> 00:30:42,880 Це досить проста теж - структура вузла * лівий дитини; 400 00:30:42,880 --> 00:30:51,190 і структура вузла * Право дитини;. Cool. 401 00:30:51,190 --> 00:30:54,740 Це виглядає як дуже хороший старт. 402 00:30:54,740 --> 00:30:58,530 Давайте повернемося до специфікації. 403 00:30:58,530 --> 00:31:05,030 >> Тепер нам потрібно оголосити глобальну змінну * вузол кореневого дерева. 404 00:31:05,030 --> 00:31:10,590 Ми збираємося зробити це глобальний так само, як ми зробили перший покажчик в нашому списку також зв'язана глобальним. 405 00:31:10,590 --> 00:31:12,690 Це було так, що у функціях, які ми пишемо 406 00:31:12,690 --> 00:31:16,180 ми не повинні тримати проходить навколо цього кореня - 407 00:31:16,180 --> 00:31:19,620 хоча ми побачимо, що, якщо ви хочете написати ці функції рекурсивно, 408 00:31:19,620 --> 00:31:22,830 що може бути краще навіть не передавати його в якості глобальної, в першу чергу 409 00:31:22,830 --> 00:31:28,090 і замість того, ініціалізувати його локально в основною функцією. 410 00:31:28,090 --> 00:31:31,960 Але, ми зробимо це в глобальному масштабі для початку. 411 00:31:31,960 --> 00:31:39,920 Знову ж таки, ми дамо пару просторів, і я збираюся оголосити кореневий вузол *. 412 00:31:39,920 --> 00:31:46,770 Просто щоб переконатися, що я не полишаю цієї неініціалізовані, я збираюся встановити його рівним нулю. 413 00:31:46,770 --> 00:31:52,210 Тепер, в основній функції - які ми будемо писати дуже швидко, прямо тут - 414 00:31:52,210 --> 00:32:00,450 Int основних (Int агдс, сопзЬ сЬаг * ARGV []) - 415 00:32:00,450 --> 00:32:10,640 і я збираюся розпочати декларування мій ARGV масиву як константний просто так, що я знаю, 416 00:32:10,640 --> 00:32:14,550 що ті аргументи аргументами, які я, ймовірно, не хочуть змінити. 417 00:32:14,550 --> 00:32:18,390 Якщо я хочу змінити їх, я, ймовірно, слід робити їх копії. 418 00:32:18,390 --> 00:32:21,740 Ви побачите це багато коду. 419 00:32:21,740 --> 00:32:25,440 Це добре в будь-якому випадку. Це прекрасно, щоб залишити все як - опустити сопзЬ, якщо ви хочете. 420 00:32:25,440 --> 00:32:28,630 Як правило, я поклав його в просто так, що я нагадую собі, 421 00:32:28,630 --> 00:32:33,650  що я, ймовірно, не хочете змінювати ці аргументи. 422 00:32:33,650 --> 00:32:39,240 >> Як завжди, я збираюся включити це повернення 0 лінію в кінці основного. 423 00:32:39,240 --> 00:32:45,730 Тут я ініціалізації мого кореневого вузла. 424 00:32:45,730 --> 00:32:48,900 Як вона стоїть зараз, у мене є покажчик, який встановлений в нуль, 425 00:32:48,900 --> 00:32:52,970 таким чином, це вказує на нічого. 426 00:32:52,970 --> 00:32:57,480 Для того щоб дійсно почати будівництво вузла, 427 00:32:57,480 --> 00:32:59,250 Я в першу чергу необхідно виділити пам'ять для нього. 428 00:32:59,250 --> 00:33:05,910 Я збираюся зробити це, зробивши пам'яті купи за допомогою Танос. 429 00:33:05,910 --> 00:33:10,660 Я збираюся встановити корінь, рівний результат Танос, 430 00:33:10,660 --> 00:33:19,550 і я збираюся використовувати SizeOf оператора для розрахунку розміру вузла. 431 00:33:19,550 --> 00:33:24,990 Причина, по якій я використовую SizeOf вузла, на відміну від, скажімо, 432 00:33:24,990 --> 00:33:37,020 робити щось подібне до цього - Танос (4 + 4 +4) або Танос 12 - 433 00:33:37,020 --> 00:33:40,820 тому що я хочу, щоб мій код, щоб бути сумісним наскільки це можливо. 434 00:33:40,820 --> 00:33:44,540 Я хочу бути в змозі прийняти це. С файлом, скомпілювати його на прилад, 435 00:33:44,540 --> 00:33:48,820 , А потім компілювати його на моєму 64-розрядний Mac - 436 00:33:48,820 --> 00:33:52,040 або на зовсім інший архітектурі - 437 00:33:52,040 --> 00:33:54,640 і я хочу це все буде працювати так само. 438 00:33:54,640 --> 00:33:59,510 >> Якщо я роблю припущення щодо розміру змінних - 439 00:33:59,510 --> 00:34:02,070 Розмір Int або розмір покажчика - 440 00:34:02,070 --> 00:34:06,070 Потім я також робить припущення про види архітектури 441 00:34:06,070 --> 00:34:10,440 , На якому мій код може успішно скомпілювати при запуску. 442 00:34:10,440 --> 00:34:15,030 Завжди використовуйте SizeOf, на відміну від ручного підсумовування структура полів. 443 00:34:15,030 --> 00:34:20,500 Інша причина в тому, що там може бути також оббивка, що компілятор поміщає в структуру. 444 00:34:20,500 --> 00:34:26,570 Навіть просто підсумовування окремих полів не те, що ви зазвичай хочуть робити, 445 00:34:26,570 --> 00:34:30,340 так, видаліть цей рядок. 446 00:34:30,340 --> 00:34:33,090 Тепер, щоб дійсно ініціалізації цього кореневого вузла, 447 00:34:33,090 --> 00:34:36,489 Я хочу, щоб підключити значення для кожного зі своїх різних областях. 448 00:34:36,489 --> 00:34:41,400 Наприклад, для значення Я знаю, я хочу, щоб ініціалізувати до 7, 449 00:34:41,400 --> 00:34:46,920 і тепер я збираюся встановити лівий дитина буде нульовим 450 00:34:46,920 --> 00:34:55,820 і право дитини бути нульовим. Відмінно! 451 00:34:55,820 --> 00:35:02,670 Ми зробили це частина спектра. 452 00:35:02,670 --> 00:35:07,390 >> Специфікація вниз в нижній частині сторінки 3 запитує мене на створення ще трьох вузлів - 453 00:35:07,390 --> 00:35:10,600 одна з яких 3, одна з яких 6, і один з 9 - 454 00:35:10,600 --> 00:35:14,210 , А потім підключити їх так, що виглядає точно так само, як наше дерево схема 455 00:35:14,210 --> 00:35:17,120 що мова йшла про раніше. 456 00:35:17,120 --> 00:35:20,450 Давайте зробимо це дуже швидко тут. 457 00:35:20,450 --> 00:35:26,270 Ви побачите дуже швидко, що я збираюся почати писати купу повторюваного коду. 458 00:35:26,270 --> 00:35:32,100 Я збираюся створити вузол *, і я збираюся називати це три. 459 00:35:32,100 --> 00:35:36,000 Я збираюся встановити його рівним Танос (SizeOf (вузла)). 460 00:35:36,000 --> 00:35:41,070 Я збираюся встановити три-> значення = 3. 461 00:35:41,070 --> 00:35:54,780 Три -> left_child = NULL; трьох -> правою _child = NULL; також. 462 00:35:54,780 --> 00:36:01,150 Це виглядає дуже схоже на ініціалізацію корінь, і це саме те, що 463 00:36:01,150 --> 00:36:05,760 Я збираюся потрібно зробити, якщо я почну ініціалізації 6 і 9, а також. 464 00:36:05,760 --> 00:36:20,720 Я зроблю це дуже швидко тут - на самом деле, я збираюся зробити невеликий копіювання і вставки, 465 00:36:20,720 --> 00:36:46,140 і переконатися, що я - все в порядку. 466 00:36:46,470 --> 00:37:09,900  Тепер, я отримав його скопіювати, і я можу піти далі і встановити рівним 6. 467 00:37:09,900 --> 00:37:14,670 Ви бачите, що це займає деякий час, і не супер-ефективним. 468 00:37:14,670 --> 00:37:22,610 У зовсім небагато, ми напишемо функцію, яка буде робити це за нас. 469 00:37:22,610 --> 00:37:32,890 Я хочу, щоб замінити цим з 9, замінити, що з 6. 470 00:37:32,890 --> 00:37:37,360 >> Тепер у нас є всі наші вузли створені і ініціалізований. 471 00:37:37,360 --> 00:37:41,200 У нас є наш корінь рівним 7, або містить значення 7, 472 00:37:41,200 --> 00:37:46,510 наш вузол, що містить 3, наш вузол, що містить 6, і наш вузол, що містить 9. 473 00:37:46,510 --> 00:37:50,390 На даний момент, все, що нам потрібно зробити, це дроти все вгору. 474 00:37:50,390 --> 00:37:53,020 Тому я ініціалізувалися всі покажчики до нуля, це просто так, що я переконатися, що 475 00:37:53,020 --> 00:37:56,260 Я не є якісь неініціалізувати покажчиків там випадково. 476 00:37:56,260 --> 00:38:02,290 А також, оскільки, на даний момент, у мене тільки є насправді з'єднання вузлів один з одним - 477 00:38:02,290 --> 00:38:04,750 з тими, що вони насправді пов'язаний з - я не повинен йти до кінця і зробити 478 00:38:04,750 --> 00:38:08,240 Переконайтеся, що всі нулі знаходяться там у відповідних місцях. 479 00:38:08,240 --> 00:38:15,630 >> Починаючи з коренем, я знаю, що ліва дитини кореня дорівнює 3. 480 00:38:15,630 --> 00:38:21,250 Я знаю, що права дитини кореня дорівнює 9. 481 00:38:21,250 --> 00:38:24,880 Після цього, тільки інша дитина, що я залишив для занепокоєння 482 00:38:24,880 --> 00:38:39,080 це право дитині 3, яка є 6. 483 00:38:39,080 --> 00:38:44,670 На даний момент, все це виглядає досить добре. 484 00:38:44,670 --> 00:38:54,210 Ми видалимо деякі з цих ліній. 485 00:38:54,210 --> 00:38:59,540 Тепер все виглядає досить добре. 486 00:38:59,540 --> 00:39:04,240 Давайте повернемося до нашої специфікації і подивитися, що ми повинні робити далі. 487 00:39:04,240 --> 00:39:07,610 >> На даний момент, ми повинні написати функцію, звану 'містить' 488 00:39:07,610 --> 00:39:14,150 з прототипом "BOOL містить (цілочисельне значення). 489 00:39:14,150 --> 00:39:17,060 І це містить функцію збирається повернути істинний 490 00:39:17,060 --> 00:39:21,200  якщо дерево на який вказує наша глобальна змінна кореневої 491 00:39:21,200 --> 00:39:26,950  містить значення передається в функцію і брехня в іншому випадку. 492 00:39:26,950 --> 00:39:29,000 Давайте підемо далі і що робити. 493 00:39:29,000 --> 00:39:35,380 Це буде так само, як пошук, що ми зробили вручну на IPad просто трохи назад. 494 00:39:35,380 --> 00:39:40,130 Давайте масштаб в трохи, і прокрутка вгору. 495 00:39:40,130 --> 00:39:43,130 Ми збираємося поставити цю функцію прямо над нашою основною функцією 496 00:39:43,130 --> 00:39:48,990 так що ми не повинні робити жодних прототипів. 497 00:39:48,990 --> 00:39:55,960 Таким чином, логічний містить (цілочисельне значення). 498 00:39:55,960 --> 00:40:00,330 Там ми йдемо. Там наш шаблонний декларації. 499 00:40:00,330 --> 00:40:02,900 Просто щоб переконатися, що це буде компілювати, 500 00:40:02,900 --> 00:40:06,820 Я збираюся йти вперед і просто встановити його рівним повернутися помилковим. 501 00:40:06,820 --> 00:40:09,980 Зараз ця функція просто не буде робити нічого, і завжди повідомляють, що 502 00:40:09,980 --> 00:40:14,010 значення, яке ми шукаємо не в дереві. 503 00:40:14,010 --> 00:40:16,280 >> У цей момент, ймовірно, це гарна ідея - 504 00:40:16,280 --> 00:40:19,600 так як ми написали цілу купу коду, і ми навіть не намагалися тестування ще - 505 00:40:19,600 --> 00:40:22,590 щоб переконатися, що все компілюється. 506 00:40:22,590 --> 00:40:27,460 Є кілька речей, які ми повинні зробити, щоб переконатися, що це буде насправді компіляції. 507 00:40:27,460 --> 00:40:33,530 По-перше, побачити, якщо ми використовуємо будь-які функції в будь бібліотеки, які ми ще не включені. 508 00:40:33,530 --> 00:40:37,940 Функції, які ми використовували досі, Танос, 509 00:40:37,940 --> 00:40:43,310 і ми також використовували цей тип - це нестандартний тип, званий "bool '- 510 00:40:43,310 --> 00:40:45,750 яка входить в стандартну BOOL заголовка файлу. 511 00:40:45,750 --> 00:40:53,250 Ми безумовно хочемо включати в себе стандартні bool.h для логічного типу, 512 00:40:53,250 --> 00:40:59,230 і ми також хочемо # включають в себе стандартні lib.h для стандартних бібліотек 513 00:40:59,230 --> 00:41:03,530 , Які включають Танос, і вільні, і все таке. 514 00:41:03,530 --> 00:41:08,660 Таким чином, масштаб, ми збираємося кинути палити. 515 00:41:08,660 --> 00:41:14,190 Давайте спробуємо і переконатися, що це насправді зробив компіляцію. 516 00:41:14,190 --> 00:41:18,150 Ми бачимо, що він робить, так що ми на правильному шляху. 517 00:41:18,150 --> 00:41:22,990 >> Давайте відкривати binary_tree.c знову. 518 00:41:22,990 --> 00:41:34,530 Він компілює. Давайте спустимося і переконатися, що ми вставляємо кілька дзвінків, щоб наша функція містить - 519 00:41:34,530 --> 00:41:40,130 просто щоб переконатися, що все добре. 520 00:41:40,130 --> 00:41:43,170 Наприклад, коли ми зробили деякі пошуку в нашому дереві раніше, 521 00:41:43,170 --> 00:41:48,500 Ми намагалися знайти значення 6, 10 і 1, і ми знали, що 6 було в дереві, 522 00:41:48,500 --> 00:41:52,220 10 був не в дереві, і 1 не був в дерево або. 523 00:41:52,220 --> 00:41:57,230 Давайте використовувати ці зразки дзвінки як спосіб з'ясувати, чи є чи ні 524 00:41:57,230 --> 00:41:59,880 наші містить функцію працює. 525 00:41:59,880 --> 00:42:05,210 Для того, щоб зробити це, я збираюся використовувати Е функція, 526 00:42:05,210 --> 00:42:10,280 і ми збираємося, щоб роздрукувати результат виклику містить. 527 00:42:10,280 --> 00:42:13,280 Я збираюся поставити в рядок "містить (% D) = тому що 528 00:42:13,280 --> 00:42:20,470  ми збираємося підключити значення, що ми збираємося шукати, 529 00:42:20,470 --> 00:42:27,130 і% = з \ п "і використовувати його в якості нашого формату рядка. 530 00:42:27,130 --> 00:42:30,720 Ми просто збираємося, щоб побачити - в буквальному сенсі роздрукувати на екрані - 531 00:42:30,720 --> 00:42:32,060 , Що виглядає як виклик функції. 532 00:42:32,060 --> 00:42:33,580 Це насправді не виклик функції. 533 00:42:33,580 --> 00:42:36,760  Це просто рядок призначена для виглядати як виклик функції. 534 00:42:36,760 --> 00:42:41,140 >> Тепер, ми збираємося підключити значення. 535 00:42:41,140 --> 00:42:43,580 Ми збираємося спробувати містить 6, 536 00:42:43,580 --> 00:42:48,340 і те, що ми збираємося зробити, так це використовувати, що потрійний оператор. 537 00:42:48,340 --> 00:42:56,340 Давайте подивимося, - містить 6 - так, тепер я містив 6 і якщо містить 6 правда, 538 00:42:56,340 --> 00:43:01,850 Рядок, що ми збираємося відправити у форматі характер% з 539 00:43:01,850 --> 00:43:04,850 буде рядок "істина". 540 00:43:04,850 --> 00:43:07,690 Давайте виділіть на трохи. 541 00:43:07,690 --> 00:43:16,210 В іншому випадку, ми хочемо послати рядок "помилковою", якщо містить 6 повертає брехня. 542 00:43:16,210 --> 00:43:19,730 Це трохи безглуздий з вигляду, але я думаю, я міг би також ілюструють 543 00:43:19,730 --> 00:43:23,780 що потрійний оператор виглядає так як ми не бачили його на деякий час. 544 00:43:23,780 --> 00:43:27,670 Це буде хороший, зручний спосіб з'ясувати, якщо наші містить функцію працює. 545 00:43:27,670 --> 00:43:30,040 Я буду прокручувати назад на ліву, 546 00:43:30,040 --> 00:43:39,900 і я збираюся скопіювати і вставити цей рядок кілька разів. 547 00:43:39,900 --> 00:43:44,910 Він змінив деякі з цих цінностей з усього, 548 00:43:44,910 --> 00:43:59,380 так що це буде 1, а це буде 10. 549 00:43:59,380 --> 00:44:02,480 >> На даний момент у нас є хороша функція містить. 550 00:44:02,480 --> 00:44:06,080 У нас є кілька тестів, і ми побачимо, якщо все це працює. 551 00:44:06,080 --> 00:44:08,120 На даний момент ми написали ще кілька коді. 552 00:44:08,120 --> 00:44:13,160 Час, щоб вийти, і переконайтеся, що все ще компілює. 553 00:44:13,160 --> 00:44:20,360 Вийти, і тепер давайте спробуємо робити бінарне дерево знову. 554 00:44:20,360 --> 00:44:22,260 Що ж, схоже, у нас є помилки, 555 00:44:22,260 --> 00:44:26,930 І у нас є ця явного оголошення бібліотечні функції Printf. 556 00:44:26,930 --> 00:44:39,350 Схоже, що ми повинні піти і # включити standardio.h. 557 00:44:39,350 --> 00:44:45,350 І з цим, все повинно компілюватися. Ми всі добре. 558 00:44:45,350 --> 00:44:50,420 Тепер спробуйте запустити бінарне дерево і подивитися, що відбувається. 559 00:44:50,420 --> 00:44:53,520 Ось і ми,. / Binary_tree, 560 00:44:53,520 --> 00:44:55,190 і ми бачимо, що, як ми й очікували - 561 00:44:55,190 --> 00:44:56,910 тому що ми не реалізували містить ще, 562 00:44:56,910 --> 00:44:59,800 або, скоріше, ми просто покласти у свою чергу помилковими - 563 00:44:59,800 --> 00:45:03,300 ми бачимо, що це просто повернення хибним для всіх з них, 564 00:45:03,300 --> 00:45:06,180 Так що всі робітники, по більшій частині досить добре. 565 00:45:06,180 --> 00:45:11,860 >> Давайте повернемося в справі здійснення і міститься в цій точці. 566 00:45:11,860 --> 00:45:17,490 Я хочу, щоб прокрутити вниз, збільшувати, і - 567 00:45:17,490 --> 00:45:22,330 Пам'ятайте, що алгоритм, який ми використовували в тому, що ми почали в кореневий вузол 568 00:45:22,330 --> 00:45:28,010 , А потім у кожному вузлі з якими ми стикаємося, ми робимо для порівняння, 569 00:45:28,010 --> 00:45:32,380 і на основі цього порівняння ми або рухатися вліво дитини або права дитини. 570 00:45:32,380 --> 00:45:39,670 Це буде виглядати дуже схоже на двійковий код пошуку, який ми писали раніше в строк. 571 00:45:39,670 --> 00:45:47,810 Коли ми починаємо, ми знаємо, що ми хочемо провести на поточний вузол 572 00:45:47,810 --> 00:45:54,050 що ми дивимося, і поточний вузол буде ініціалізований на кореневий вузол. 573 00:45:54,050 --> 00:45:56,260 І тепер, ми збираємося продовжувати йти по дереву, 574 00:45:56,260 --> 00:45:58,140 і пам'ятайте, що наші зупинки стані - 575 00:45:58,140 --> 00:46:01,870  Коли ми фактично працювали на прикладі вручну - 576 00:46:01,870 --> 00:46:03,960 був, коли ми зіткнулися з нульовою вузол, 577 00:46:03,960 --> 00:46:05,480 не тоді, коли ми дивилися на нульовий дитини, 578 00:46:05,480 --> 00:46:09,620 а коли ми дійсно переїхали в вузол в дереві 579 00:46:09,620 --> 00:46:12,640 і виявив, що ми знаходимося на нульовий вузол. 580 00:46:12,640 --> 00:46:20,720 Ми збираємося повторювати, поки струму не дорівнює нулю. 581 00:46:20,720 --> 00:46:22,920 І що ми будемо робити? 582 00:46:22,920 --> 00:46:31,610 Ми збираємося перевірити, якщо (поточн. -> значення == значення), 583 00:46:31,610 --> 00:46:35,160 Потім ми знаємо, що ми насправді знайшли вузол, який ми шукаємо. 584 00:46:35,160 --> 00:46:40,450 Так от, ми можемо повернутися вірно. 585 00:46:40,450 --> 00:46:49,830 В іншому випадку, ми хочемо бачити чи ні значення менше, ніж значення. 586 00:46:49,830 --> 00:46:53,850 Якщо значення поточного вузла менше, ніж значення, яке ми шукаємо, 587 00:46:53,850 --> 00:46:57,280 ми будемо рухатися вправо. 588 00:46:57,280 --> 00:47:10,600 Таким чином, текущ. = Текущ. -> Right_child, а в іншому випадку, ми будемо рухатися вліво. 589 00:47:10,600 --> 00:47:17,480 текущ. = текущ. -> left_child;. Досить просто. 590 00:47:17,480 --> 00:47:22,830 >> Ви, напевно, визнати цикл, який дуже схожий на цього від 591 00:47:22,830 --> 00:47:27,580 бінарний пошук на початку терміну, за винятком то ми маємо справу з низькою, середньою і високою. 592 00:47:27,580 --> 00:47:30,000 Тут ми просто повинні подивитися на поточне значення, 593 00:47:30,000 --> 00:47:31,930 так що це просто і красиво. 594 00:47:31,930 --> 00:47:34,960 Давайте переконатися, що цей код працює. 595 00:47:34,960 --> 00:47:42,780 По-перше, переконайтеся, що він компілює. Схоже, що він робить. 596 00:47:42,780 --> 00:47:47,920 Давайте спробуємо запустити його. 597 00:47:47,920 --> 00:47:50,160 І дійсно, він друкує все, що ми очікували. 598 00:47:50,160 --> 00:47:54,320 Він знаходить 6 в дереві, не знайти 10, тому що 10 не в дереві, 599 00:47:54,320 --> 00:47:57,740 і не знаходить 1, або тому, що 1 також не в дереві. 600 00:47:57,740 --> 00:48:01,420 Прикольних речей. 601 00:48:01,420 --> 00:48:04,470 >> Добре. Давайте повернемося до нашої специфікації і подивитися, що буде далі. 602 00:48:04,470 --> 00:48:07,990 Тепер він хоче додати ще кілька вузлів для нашого дерева. 603 00:48:07,990 --> 00:48:11,690 Вона хоче додати 5, 2 і 8, і переконатися, що наші містить код 604 00:48:11,690 --> 00:48:13,570 як і раніше працює, як очікувалося. 605 00:48:13,570 --> 00:48:14,900 Давайте робити це. 606 00:48:14,900 --> 00:48:19,430 На даний момент, а не робити те, що дратує копіювати і вставляти знову, 607 00:48:19,430 --> 00:48:23,770 давайте напишемо функцію, щоб фактично створити вузол. 608 00:48:23,770 --> 00:48:27,740 Якщо прокрутити весь шлях до головного, ми бачимо, що ми робили це 609 00:48:27,740 --> 00:48:31,210 дуже схожий код знову і знову, кожного разу, коли ми хочемо створити вузол. 610 00:48:31,210 --> 00:48:39,540 >> Давайте напишемо функцію, яка буде реально побудувати вузол для нас, і повернути його. 611 00:48:39,540 --> 00:48:41,960 Я буду називати його build_node. 612 00:48:41,960 --> 00:48:45,130 Я збираюся побудувати вузол з певним значенням. 613 00:48:45,130 --> 00:48:51,040 Збільшити тут. 614 00:48:51,040 --> 00:48:56,600 Перше, що я збираюся зробити, це насправді створити простір для вузла в купі. 615 00:48:56,600 --> 00:49:05,400 Таким чином, вузол * п = Танос (SizeOf (вузла)), п -> значення = значення; 616 00:49:05,400 --> 00:49:14,960 а потім тут, я просто хочу, щоб ініціалізувати всі поля, щоб бути відповідні значення. 617 00:49:14,960 --> 00:49:22,500 І в самому кінці, ми повернемо наш вузол. 618 00:49:22,500 --> 00:49:28,690 Добре. Єдине, що слід зазначити, що ця функція тут 619 00:49:28,690 --> 00:49:34,320 збирається повернути покажчик на область пам'яті, яка була купі. 620 00:49:34,320 --> 00:49:38,880 Що приємно про це є те, що цей вузол зараз - 621 00:49:38,880 --> 00:49:42,420 ми повинні оголосити його в купі, бо якщо ми оголосили його в стек 622 00:49:42,420 --> 00:49:45,050 ми не були б в змозі зробити це в цій функції, як це. 623 00:49:45,050 --> 00:49:47,690 Ця пам'ять буде вийти зі сфери 624 00:49:47,690 --> 00:49:51,590 і були б недійсними, якщо ми спробували отримати доступ до нього надалі. 625 00:49:51,590 --> 00:49:53,500 Оскільки ми оголошуємо купі пам'яті, 626 00:49:53,500 --> 00:49:55,830 ми будемо мати, щоб піклуватися про звільняючи його пізніше 627 00:49:55,830 --> 00:49:58,530 для нашої програми не витік будь-якої пам'яті. 628 00:49:58,530 --> 00:50:01,270 Ми понтіровавшего на що на все інше в коді 629 00:50:01,270 --> 00:50:02,880 тільки для простоти в той час, 630 00:50:02,880 --> 00:50:05,610 але якщо ви коли-небудь написати функцію, яка виглядає наступним чином 631 00:50:05,610 --> 00:50:10,370 де у вас є - деякі називають це Танос або перерозподілити всередині - 632 00:50:10,370 --> 00:50:14,330 Ви хочете, щоб переконатися, що ви поклали якийсь коментар тут, який говорить: 633 00:50:14,330 --> 00:50:29,970 агов, ви знаєте, повертає купі вузлів ініціалізується переданий в ціні. 634 00:50:29,970 --> 00:50:33,600 І тоді ви хочете, щоб переконатися, що ви поклали в якийсь увагу, що говорить 635 00:50:33,600 --> 00:50:41,720 Зухвалий повинен звільнити повернулася пам'ять. 636 00:50:41,720 --> 00:50:45,450 Таким чином, якщо хтось ніколи не йде, і використовує цю функцію, 637 00:50:45,450 --> 00:50:48,150 вони знають, що все, що вони повернуться з цієї функції 638 00:50:48,150 --> 00:50:50,870 в якийсь момент треба буде звільнений. 639 00:50:50,870 --> 00:50:53,940 >> Якщо припустити, що все добре, і тут добре, 640 00:50:53,940 --> 00:51:02,300 ми можемо спуститися в наш код і замінити всі ці рядки прямо тут 641 00:51:02,300 --> 00:51:05,410 із закликами до нашої функції вузла зборки. 642 00:51:05,410 --> 00:51:08,170 Давайте зробимо це дуже швидко. 643 00:51:08,170 --> 00:51:15,840 Одна частина, що ми не збираємося замінити ця частина тут 644 00:51:15,840 --> 00:51:18,520 на дно, де ми насправді з'єднувати вузли, щоб вказувати один на одного, 645 00:51:18,520 --> 00:51:21,030 тому що ми не можемо зробити в наших функцій. 646 00:51:21,030 --> 00:51:37,400 Але, давайте зробимо корінь = build_node (7); вузол * три = build_node (3); 647 00:51:37,400 --> 00:51:47,980 вузол * шість = build_node (6); вузол * Дев'ять = build_node (9),. 648 00:51:47,980 --> 00:51:52,590 І тепер, ми також хотіли б додати вузли - 649 00:51:52,590 --> 00:52:03,530 вузол * П'ять = build_node (5); вузол * = build_node вісім (8); 650 00:52:03,530 --> 00:52:09,760 і те, що було на інший вузол? Давайте подивимося тут. Ми хотіли б також додати 2 - 651 00:52:09,760 --> 00:52:20,280 * Два вузли = build_node (2);. 652 00:52:20,280 --> 00:52:26,850 Добре. На даний момент, ми знаємо, що у нас є 7, 3, 9, і 6 653 00:52:26,850 --> 00:52:30,320 Всі провідні відповідним чином, але як щодо 5, 8 і 2? 654 00:52:30,320 --> 00:52:33,550 Щоб зберегти все в належний порядок, 655 00:52:33,550 --> 00:52:39,230 Ми знаємо, що право дитині три є 6. 656 00:52:39,230 --> 00:52:40,890 Отже, якщо ми збираємося додати 5, 657 00:52:40,890 --> 00:52:46,670 5 також належить до правої сторони дерев, з яких 3 є коренем, 658 00:52:46,670 --> 00:52:50,440 5 належить так як ліва дитини 6. 659 00:52:50,440 --> 00:52:58,650 Ми можемо зробити це, сказавши, шість -> left_child = п'ять; 660 00:52:58,650 --> 00:53:10,790 , А потім 8 належить як ліва дитиною з 9, таким чином, дев'ять -> left_child = вісім; 661 00:53:10,790 --> 00:53:22,190 , А потім 2 є лівим дитиною 3, так що ми можемо зробити це тут - Тебе -> left_child = два,. 662 00:53:22,190 --> 00:53:27,730 Якщо ви не зовсім розумію разом з тим, я пропоную вам зробити це самостійно. 663 00:53:27,730 --> 00:53:35,660 >> Добре. Давайте збережемо це. Давайте виходити на вулицю і переконайтеся, що він збирає, 664 00:53:35,660 --> 00:53:40,760 і тоді ми можемо додати в нашу містить виклики. 665 00:53:40,760 --> 00:53:44,120 Схоже, все ще компілює. 666 00:53:44,120 --> 00:53:51,790 Давайте і додати в деяких містить виклики. 667 00:53:51,790 --> 00:53:59,640 Знову ж таки, я збираюся зробити трохи копіювання і вставки. 668 00:53:59,640 --> 00:54:15,860 Тепер давайте шукати 5, 8, і 2. Добре. 669 00:54:15,860 --> 00:54:28,330 Давайте переконався, що це все виглядає добре до цих пір. Відмінно! Зберегти і вийти. 670 00:54:28,330 --> 00:54:33,220 Тепер давайте зробимо, компіляції, а тепер давайте працювати. 671 00:54:33,220 --> 00:54:37,540 З результатів, схоже, все працює просто приємно і добре. 672 00:54:37,540 --> 00:54:41,780 Відмінно! Так що тепер у нас є наші містить функцію написано. 673 00:54:41,780 --> 00:54:46,160 Давайте рухатися далі і почати працювати на те, як вставити вузли в дерево 674 00:54:46,160 --> 00:54:50,000 , Оскільки, як ми робимо це зараз, все не дуже красиво. 675 00:54:50,000 --> 00:54:52,280 >> Якщо ми повернемося до специфікації, 676 00:54:52,280 --> 00:55:00,540 він просить, щоб ми написали функцію під назвою вставити - знову, повертаючись логічне 677 00:55:00,540 --> 00:55:04,400 для того чи ні, ми могли фактично вставки вузла в дерево - 678 00:55:04,400 --> 00:55:07,710 , А потім значення для вставки в дерево визначається як 679 00:55:07,710 --> 00:55:11,060 Єдиний аргумент, щоб наші функції вставки. 680 00:55:11,060 --> 00:55:18,180 Ми повернемося вірно, якщо ми могли б дійсно вставити вузол, що містить значення в дереві, 681 00:55:18,180 --> 00:55:20,930 Це означає, що ми, один, мав достатньо пам'яті, 682 00:55:20,930 --> 00:55:24,840 , А потім два, то цей вузол вже не існують в дереві, так - 683 00:55:24,840 --> 00:55:32,170 Пам'ятайте, що ми не будемо мати однакові значення в дереві, просто щоб зробити речі простими. 684 00:55:32,170 --> 00:55:35,590 Добре. Перейти до коду. 685 00:55:35,590 --> 00:55:44,240 Відкрийте його. Збільшити трохи, а потім прокрутити вниз. 686 00:55:44,240 --> 00:55:47,220 Скажімо функції вставки прямо над містить. 687 00:55:47,220 --> 00:55:56,360 Знову ж таки, це буде називатися BOOL вставки (цілочисельне значення). 688 00:55:56,360 --> 00:56:01,840 Дайте йому трохи більше простору, а потім, за замовчуванням, 689 00:56:01,840 --> 00:56:08,870 давайте замість помилкового в самому кінці. 690 00:56:08,870 --> 00:56:22,620 Тепер вниз, на дно, давайте йти вперед і замість того, щоб вручну створювати вузли 691 00:56:22,620 --> 00:56:27,900 В основній собі і проводка їх до вказувати один на одного, як ми робимо, 692 00:56:27,900 --> 00:56:30,600 ми покладаємося на наші функції вставки, щоб зробити це. 693 00:56:30,600 --> 00:56:35,510 Ми не будемо покладатися на наші функції вставки для зборки всього дерева з нуля, тільки все ж, 694 00:56:35,510 --> 00:56:39,970 а ми позбутися від цих ліній - МИ закоментуйте ці рядки - 695 00:56:39,970 --> 00:56:43,430 що будувати вузли 5, 8 і 2. 696 00:56:43,430 --> 00:56:55,740 А замість цього, ми вставимо дзвінки на наш функції вставки 697 00:56:55,740 --> 00:57:01,280 щоб переконатися, що це дійсно працює. 698 00:57:01,280 --> 00:57:05,840 Тут ми йдемо. 699 00:57:05,840 --> 00:57:09,300 >> Тепер ми закоментувати ці рядки. 700 00:57:09,300 --> 00:57:13,700 У нас є тільки 7, 3, 9 і 6 в нашій дерева в цій точці. 701 00:57:13,700 --> 00:57:18,870 Щоб переконатися в тому, що все це працює, 702 00:57:18,870 --> 00:57:25,050 ми можемо зменшити масштаб, щоб наші бінарне дерево, 703 00:57:25,050 --> 00:57:30,750 запустити його, і ми бачимо, що міститься в даний час говорить нам, що ми абсолютно праві - 704 00:57:30,750 --> 00:57:33,110 5, 8, і 2 вже не в дереві. 705 00:57:33,110 --> 00:57:37,960 Поверніться в коді, 706 00:57:37,960 --> 00:57:41,070 і як ми збираємося вставити? 707 00:57:41,070 --> 00:57:46,290 Пам'ятайте, що ми робили, коли ми були насправді вставка 5, 8, і 2 раніше. 708 00:57:46,290 --> 00:57:50,100 Ми грали в цю гру Plinko, де ми почали в корені, 709 00:57:50,100 --> 00:57:52,780 спустився по дереву один на один за іншим 710 00:57:52,780 --> 00:57:54,980 поки ми не знайшли відповідну щілину, 711 00:57:54,980 --> 00:57:57,570 і тоді ми підключені вузла у відповідному місці. 712 00:57:57,570 --> 00:57:59,480 Ми збираємося зробити те ж саме. 713 00:57:59,480 --> 00:58:04,070 Це, в основному, як написання коду, який ми використовували в містить функцію 714 00:58:04,070 --> 00:58:05,910 Щоб знайти місце, де вузол повинен бути, 715 00:58:05,910 --> 00:58:10,560 а потім ми тільки збираємося, щоб вставити вузол прямо там. 716 00:58:10,560 --> 00:58:17,000 Давайте почнемо це робити. 717 00:58:17,000 --> 00:58:24,200 >> Отже, ми маємо вузол * текущ. = Корінь; ми тільки збираємося слідувати код містить 718 00:58:24,200 --> 00:58:26,850 поки ми не знайдемо, що це не зовсім робота для нас. 719 00:58:26,850 --> 00:58:32,390 Ми збираємося пройти через дерево в той час як поточний елемент не є нульовим, 720 00:58:32,390 --> 00:58:45,280 і якщо ми виявимо, що значення струму, дорівнює значенню, що ми намагаємося вставити - 721 00:58:45,280 --> 00:58:49,600 Ну, це один з випадків, в яких ми не могли фактично вставки вузла 722 00:58:49,600 --> 00:58:52,730 в дерево, бо це означає, що у нас є повторювані значення. 723 00:58:52,730 --> 00:58:59,010 Тут ми насправді збираємося повернутися помилковим. 724 00:58:59,010 --> 00:59:08,440 Тепер, інакше, якщо значення струму складає менше значення, 725 00:59:08,440 --> 00:59:10,930 Тепер ми знаємо, що ми рухаємося вправо 726 00:59:10,930 --> 00:59:17,190  тому що значення належить в правій половині текущ. дерева. 727 00:59:17,190 --> 00:59:30,110 В іншому випадку, ми будемо рухатися вліво. 728 00:59:30,110 --> 00:59:37,980 Це в основному наші містить функцію прямо там. 729 00:59:37,980 --> 00:59:41,820 >> На даний момент, як тільки ми закінчили це в той час циклу, 730 00:59:41,820 --> 00:59:47,350 шему покажчик буде вказувати на нуль 731 00:59:47,350 --> 00:59:51,540 якщо функція вже не повернувся. 732 00:59:51,540 --> 00:59:58,710 Ми тому мають текущ. В тому місці, де ми хочемо, щоб вставити новий вузол. 733 00:59:58,710 --> 01:00:05,210 Те, що залишається зробити, це насправді побудувати новий вузол, 734 01:00:05,210 --> 01:00:08,480 що ми можемо зробити досить легко. 735 01:00:08,480 --> 01:00:14,930 Ми можемо використовувати наші супер-зручна збірка вузлів функції, 736 01:00:14,930 --> 01:00:17,210 і те, що ми не робили раніше - 737 01:00:17,210 --> 01:00:21,400 ми просто якась вважали само собою зрозумілим, але тепер ми будемо робити просто щоб переконатися - 738 01:00:21,400 --> 01:00:27,130 ми будемо перевірити, щоб переконатися, що значення повертається новий вузол був насправді 739 01:00:27,130 --> 01:00:33,410 не нульовий, тому що ми не хочемо, щоб почати доступ до цієї пам'яті, якщо воно є недійсним. 740 01:00:33,410 --> 01:00:39,910 Ми можемо перевірити, щоб переконатися, що новий вузол не дорівнює нулю. 741 01:00:39,910 --> 01:00:42,910 Або замість цього, ми можемо просто подивитися, якщо він насправді є порожнім, 742 01:00:42,910 --> 01:00:52,120 і якщо він дорівнює нулю, то ми можемо просто повернутися помилковим рано. 743 01:00:52,120 --> 01:00:59,090 >> На даний момент, ми повинні підключити новий вузол у свою відповідне місце в дереві. 744 01:00:59,090 --> 01:01:03,510 Якщо ми подивимося на основні і де ми були насправді проводки в значеннях раніше, 745 01:01:03,510 --> 01:01:08,470 ми бачимо, що те, як ми це робили, коли ми хотіли поставити 3 в дерево 746 01:01:08,470 --> 01:01:11,750 Ми були доступні лівому дитини кореня. 747 01:01:11,750 --> 01:01:14,920 Коли ми ставимо 9 в дерево, ми повинні були отримати доступ до право дитини на корені. 748 01:01:14,920 --> 01:01:21,030 Ми повинні були мати покажчик на батька для того, щоб покласти нове значення в дерево. 749 01:01:21,030 --> 01:01:24,430 Прокрутка назад вставити, що не збирається працювати тут цілком 750 01:01:24,430 --> 01:01:27,550 тому що у нас немає предка. 751 01:01:27,550 --> 01:01:31,650 Що ми хочемо бути в змозі робити це, на даний момент, 752 01:01:31,650 --> 01:01:37,080 перевірте значення батьків і подивитися - ну, чорт візьми, 753 01:01:37,080 --> 01:01:41,990 якщо значення батька менше, ніж поточне значення, 754 01:01:41,990 --> 01:01:54,440 Потім право дитини батько повинен бути новий вузол; 755 01:01:54,440 --> 01:02:07,280 В іншому випадку ліва дитини батько повинен бути новий вузол. 756 01:02:07,280 --> 01:02:10,290 Але ми не повинні цього батька покажчик зовсім ще. 757 01:02:10,290 --> 01:02:15,010 >> Для того, щоб отримати його, ми фактично доведеться відстежувати його, як ми йдемо по дереву 758 01:02:15,010 --> 01:02:18,440 і знайти відповідне місце в нашому циклі вище. 759 01:02:18,440 --> 01:02:26,840 Ми можемо зробити це за допомогою прокрутки назад до вершини нашої функції вставки 760 01:02:26,840 --> 01:02:32,350 і відстеження інший покажчик змінної батьків. 761 01:02:32,350 --> 01:02:39,340 Ми збираємося встановити його рівним нулю на початковому етапі, 762 01:02:39,340 --> 01:02:43,640 , А потім кожен раз, коли ми йдемо по дереву, 763 01:02:43,640 --> 01:02:51,540 Ми збираємося встановити батька, щоб відповідати поточним покажчиком. 764 01:02:51,540 --> 01:02:59,140 Встановити батьківський одно текущ .. 765 01:02:59,140 --> 01:03:02,260 Таким чином, кожен раз, коли ми пройти, 766 01:03:02,260 --> 01:03:05,550 Ми збираємося переконатися, що в якості поточного покажчика збільшується на одиницю 767 01:03:05,550 --> 01:03:12,640 батьківського покажчик слід за ним - просто на один рівень вище поточного покажчика в дереві. 768 01:03:12,640 --> 01:03:17,370 Це все виглядає досить добре. 769 01:03:17,370 --> 01:03:22,380 >> Я думаю, що одна річ, яку ми хочемо налаштувати це побудувати вузол повертається NULL. 770 01:03:22,380 --> 01:03:25,380 Для того, щоб побудувати вузол насправді успішно повертають NULL, 771 01:03:25,380 --> 01:03:31,060 ми повинні змінити цей код, 772 01:03:31,060 --> 01:03:37,270 тому що тут, ми ніколи не перевіряли, щоб переконатися, що Танос повернувся дійсний покажчик. 773 01:03:37,270 --> 01:03:53,390 Так що, якщо (п = NULL!), Потім - 774 01:03:53,390 --> 01:03:55,250 якщо Танос повернувся дійсний покажчик, то ми його ініціалізації; 775 01:03:55,250 --> 01:04:02,540 В іншому випадку ми будемо просто повернути, і що в кінцевому підсумку повертається NULL для нас. 776 01:04:02,540 --> 01:04:13,050 Тепер все виглядає досить добре. Давайте переконатися, що це насправді компілює. 777 01:04:13,050 --> 01:04:22,240 Зробити бінарне дерево, і ах, у нас є деякі речі тут відбувається. 778 01:04:22,240 --> 01:04:29,230 >> У нас є неявна декларація функції створення вузла. 779 01:04:29,230 --> 01:04:31,950 Знову ж таки, ці компілятори, ми збираємося почати з самого верху. 780 01:04:31,950 --> 01:04:36,380 Що це має означати, що я дзвоню побудувати вузол, перш ніж я насправді оголошена. 781 01:04:36,380 --> 01:04:37,730 Давайте повернемося до коду дуже швидко. 782 01:04:37,730 --> 01:04:43,510 Прокрутіть вниз, і, звичайно ж, моя вставка функція оголошена 783 01:04:43,510 --> 01:04:47,400 вище функції вузла зборки, 784 01:04:47,400 --> 01:04:50,070 Але я намагаюся використовувати побудувати вузол всередині вставки. 785 01:04:50,070 --> 01:05:06,610 Я збираюся піти і копію - а потім вставте функцію збирання вузлів шлях тут, на самому верху. 786 01:05:06,610 --> 01:05:11,750 Таким чином, ми сподіваємося, що буде працювати. Давайте дамо цьому ще один шанс. 787 01:05:11,750 --> 01:05:18,920 Тепер все компілюється. Все це добре. 788 01:05:18,920 --> 01:05:21,640 >> Але на даний момент, ми насправді не називали наші функції вставки. 789 01:05:21,640 --> 01:05:26,510 Ми просто знаємо, що він збирає, так що давайте підемо і покласти кілька дзвінків дюйма 790 01:05:26,510 --> 01:05:28,240 Давайте зробимо, що в наших основних функцій. 791 01:05:28,240 --> 01:05:32,390 Тут ми закоментовані 5, 8 і 2, 792 01:05:32,390 --> 01:05:36,680 і тоді ми не підключити їх сюди. 793 01:05:36,680 --> 01:05:41,640 Давайте зробимо декілька дзвінків, щоб вставити, 794 01:05:41,640 --> 01:05:46,440 і давайте також використовувати такі ж речі, які ми використовували 795 01:05:46,440 --> 01:05:52,810 Коли ми зробили ці Printf дзвінків, щоб переконатися, що все дійсно ставали вставлений правильно. 796 01:05:52,810 --> 01:06:00,550 Я збираюся копіювати і вставляти, 797 01:06:00,550 --> 01:06:12,450 і замість того, містить ми збираємося зробити вставку. 798 01:06:12,450 --> 01:06:30,140 І замість того, 6, 10 і 1, ми збираємося використовувати 5, 8 і 2. 799 01:06:30,140 --> 01:06:37,320 Це повинно, ми сподіваємося, вставити 5, 8, і 2 в дерево. 800 01:06:37,320 --> 01:06:44,050 Компіляція. Все це добре. Тепер ми будемо реально працювати наша програма. 801 01:06:44,050 --> 01:06:47,330 >> Всі повернулися помилковою. 802 01:06:47,330 --> 01:06:53,830 Так, 5, 8 і 2 не пішов, і це виглядає як Містить не знайшли їх або. 803 01:06:53,830 --> 01:06:58,890 Що відбувається? Давайте масштабу. 804 01:06:58,890 --> 01:07:02,160 Першою проблемою було те, що, здавалося вставки, щоб повернутися помилковим, 805 01:07:02,160 --> 01:07:08,750 і, схоже, це тому, що ми залишили в нашому поверненні помилковий виклик, 806 01:07:08,750 --> 01:07:14,590 і ми ніколи не повернулися правда. 807 01:07:14,590 --> 01:07:17,880 Ми можемо встановити, що. 808 01:07:17,880 --> 01:07:25,290 Друга проблема в тому, тепер, навіть якщо ми робимо - зберегти це, кинути це, 809 01:07:25,290 --> 01:07:34,530 запустити зробити знову, нехай він скомпілювати, а потім запустити його - 810 01:07:34,530 --> 01:07:37,670 ми бачимо, що щось ще сталося. 811 01:07:37,670 --> 01:07:42,980 5, 8, і 2 ще не знайшов у дереві. 812 01:07:42,980 --> 01:07:44,350 Отже, що відбувається? 813 01:07:44,350 --> 01:07:45,700 >> Давайте подивимося на це в коді. 814 01:07:45,700 --> 01:07:49,790 Давайте подивимося, чи зможемо ми зрозуміти це. 815 01:07:49,790 --> 01:07:57,940 Почнемо з батьками не бути нульовим. 816 01:07:57,940 --> 01:07:59,510 Ми встановлюємо покажчик поточної рівних в кореневій покажчик, 817 01:07:59,510 --> 01:08:04,280 і ми збираємося працювати наш шлях вниз по дереву. 818 01:08:04,280 --> 01:08:08,650 Якщо поточний вузол не є нульовим, то ми знаємо, що ми можемо рухатися вниз небагато. 819 01:08:08,650 --> 01:08:12,330 Ми встановлюємо наші батьки покажчик рівним поточному покажчику, 820 01:08:12,330 --> 01:08:15,420 перевірити значення - якщо значення збігаються, ми повернулися помилковою. 821 01:08:15,420 --> 01:08:17,540 Якщо значення менше ми переїхали в праву; 822 01:08:17,540 --> 01:08:20,399 В іншому випадку ми переїхали на лівий. 823 01:08:20,399 --> 01:08:24,220 Потім ми будуємо вузла. Я збільшити небагато. 824 01:08:24,220 --> 01:08:31,410 І ось, ми збираємося, щоб спробувати підключити до значень, те ж саме. 825 01:08:31,410 --> 01:08:37,250 Що відбувається? Давайте подивимося, якщо можливо Valgrind може дати нам підказку. 826 01:08:37,250 --> 01:08:43,910 >> Мені подобається використовувати Valgrind Valgrind тільки тому, що дуже швидко біжить 827 01:08:43,910 --> 01:08:46,729 і говорить вам, якщо є які-небудь помилки пам'яті. 828 01:08:46,729 --> 01:08:48,300 Коли ми запускаємо Valgrind на код, 829 01:08:48,300 --> 01:08:55,859 як ви можете бачити правий удар here--Valgrind./binary_tree--and входу. 830 01:08:55,859 --> 01:09:03,640 Ви бачите, що у нас не було ніяких помилок пам'яті, так що схоже, все в порядку досі. 831 01:09:03,640 --> 01:09:07,529 У нас є деякі витоку пам'яті, які ми знаємо, тому що ми не 832 01:09:07,529 --> 01:09:08,910 відбувається, щоб звільнити будь-якого з наших вузлів. 833 01:09:08,910 --> 01:09:13,050 Давайте спробуємо працює GDB, щоб подивитися, що відбувається насправді. 834 01:09:13,050 --> 01:09:20,010 Ми зробимо GDB. / Binary_tree. Він завантажився нормально. 835 01:09:20,010 --> 01:09:23,670 Давайте встановимо точку зупину на вставку. 836 01:09:23,670 --> 01:09:28,600 Давайте запустимо. 837 01:09:28,600 --> 01:09:31,200 Схоже, ми ніколи не називали вставки. 838 01:09:31,200 --> 01:09:39,410 Схоже, проблема була тільки що, коли я змінив тут, в головному - 839 01:09:39,410 --> 01:09:44,279 Всі ці Printf дзвінки з містить - 840 01:09:44,279 --> 01:09:56,430 Я ніколи насправді змінилося цих подзвонити вставки. 841 01:09:56,430 --> 01:10:01,660 Тепер давайте дати йому спробувати. Давайте компіляції. 842 01:10:01,660 --> 01:10:09,130 Все виглядає добре там. Тепер давайте спробуємо запустити його, подивитися, що відбувається. 843 01:10:09,130 --> 01:10:13,320 Добре! Все виглядає досить добре там. 844 01:10:13,320 --> 01:10:18,130 >> Остання річ, щоб думати про те, чи є якісь крайні випадки цієї вставки? 845 01:10:18,130 --> 01:10:23,170 І виходить, що, мовляв, одне ребро випадку це завжди цікаво думати про 846 01:10:23,170 --> 01:10:26,250 в тому, що станеться, якщо ваше дерево порожньо, і ви називаєте це вставка функції? 847 01:10:26,250 --> 01:10:30,330 Чи буде вона працювати? Що ж, давайте спробуємо. 848 01:10:30,330 --> 01:10:32,110 - Binary_tree с. - 849 01:10:32,110 --> 01:10:35,810 Те, як ми збираємося перевірити це, ми збираємося спуститися до нашої основної функції, 850 01:10:35,810 --> 01:10:41,690 і замість проводки цих вузлах ось так, 851 01:10:41,690 --> 01:10:56,730 ми тільки збираємося, щоб закоментувати всю річ, 852 01:10:56,730 --> 01:11:02,620 і замість проводки до вузли собі, 853 01:11:02,620 --> 01:11:09,400 ми дійсно можемо просто йти вперед і видалити все це. 854 01:11:09,400 --> 01:11:17,560 Ми збираємося зробити все виклик для вставки. 855 01:11:17,560 --> 01:11:49,020 Отже, давайте робити - замість 5, 8 і 2, ми збираємося, щоб вставити 7, 3 і 9. 856 01:11:49,020 --> 01:11:58,440 І тоді ми також хочемо, щоб вставити 6, а. 857 01:11:58,440 --> 01:12:05,190 Зберегти. Вийти. Зробити бінарне дерево. 858 01:12:05,190 --> 01:12:08,540 Це все компілюється. 859 01:12:08,540 --> 01:12:10,320 Ми можемо просто запустіть його як є і подивитися, що відбувається, 860 01:12:10,320 --> 01:12:12,770 але це також буде дуже важливо, щоб переконатися, що 861 01:12:12,770 --> 01:12:14,740 Ми не мають ніяких помилок пам'яті, 862 01:12:14,740 --> 01:12:16,840 так як це є одним з наших крайніх випадках, що ми знаємо про. 863 01:12:16,840 --> 01:12:20,150 >> Давайте переконався, що він добре працює під Valgrind, 864 01:12:20,150 --> 01:12:28,310 які ми будемо робити, просто видавши Valgrind. / binary_tree. 865 01:12:28,310 --> 01:12:31,110 Схоже, у нас дійсно одна помилка з одного контексту - 866 01:12:31,110 --> 01:12:33,790 у нас є ця помилка сегментації. 867 01:12:33,790 --> 01:12:36,690 Що трапилося? 868 01:12:36,690 --> 01:12:41,650 Valgrind насправді говорить нам, де він знаходиться. 869 01:12:41,650 --> 01:12:43,050 Зменшити небагато. 870 01:12:43,050 --> 01:12:46,040 Схоже, що відбувається в нашій функції вставки, 871 01:12:46,040 --> 01:12:53,420 де у нас є недійсним читання розміром 4 на вставку, рядок 60. 872 01:12:53,420 --> 01:13:03,590 Давайте повернемося і подивимося, що тут відбувається. 873 01:13:03,590 --> 01:13:05,350 Зменшити дуже швидко. 874 01:13:05,350 --> 01:13:14,230 Я хочу, щоб переконатися, що він не йде до краю екрану, щоб ми могли бачити всі. 875 01:13:14,230 --> 01:13:18,760 Потягніть, що в небагато. Добре. 876 01:13:18,760 --> 01:13:35,030 Прокрутіть вниз, і проблема прямо тут. 877 01:13:35,030 --> 01:13:40,120 Що станеться, якщо ми спускаємося і наш поточний вузол вже нульові, 878 01:13:40,120 --> 01:13:44,010 наш батьківський вузол є нульовим, тому, якщо ми дивимося на самому верху, прямо тут - 879 01:13:44,010 --> 01:13:47,340 Якщо цей час циклу ніколи не виконується 880 01:13:47,340 --> 01:13:52,330 тому що наше поточне значення дорівнює нулю - наш корінь нульовою так текущ. є недійсним - 881 01:13:52,330 --> 01:13:57,810 Потім наші батьки ніколи не буде встановлений в текущ. Або допустиме значення, 882 01:13:57,810 --> 01:14:00,580 Таким чином, батьки також буде нульовим. 883 01:14:00,580 --> 01:14:03,700 Ми повинні пам'ятати, щоб перевірити, що 884 01:14:03,700 --> 01:14:08,750 До того часу ми приступимо тут, і ми починаємо доступ до значення батьків. 885 01:14:08,750 --> 01:14:13,190 Отже, що відбувається? Ну, якщо батько є нуль - 886 01:14:13,190 --> 01:14:17,990 якщо (== NULL батька), - то ми знаємо, що 887 01:14:17,990 --> 01:14:19,530 не повинно бути нічого в дерево. 888 01:14:19,530 --> 01:14:22,030 Ми повинні намагатися вставити його в корені. 889 01:14:22,030 --> 01:14:32,570 Ми можемо зробити це, просто задавши корінь, рівний новий вузол. 890 01:14:32,570 --> 01:14:40,010 Тоді в цій точці ми насправді не хочуть, щоб пройти через ці інші речі. 891 01:14:40,010 --> 01:14:44,780 Замість цього, прямо тут, ми можемо зробити або інше-якщо-іншому, 892 01:14:44,780 --> 01:14:47,610 або ми могли б об'єднати всі тут в іншому, 893 01:14:47,610 --> 01:14:56,300 але тут ми будемо використовувати ще й зробити це таким чином. 894 01:14:56,300 --> 01:14:59,030 Тепер, ми збираємося перевірити, щоб переконатися, що наші батьки не нульовий 895 01:14:59,030 --> 01:15:02,160 до цього насправді намагається отримати доступ до його полях. 896 01:15:02,160 --> 01:15:05,330 Це допоможе нам уникнути помилки сегментації. 897 01:15:05,330 --> 01:15:14,740 Таким чином, ми кинути палити, зменшити масштаб, компілювати, запускати. 898 01:15:14,740 --> 01:15:18,130 >> Немає помилки, але у нас ще є купа витоків пам'яті 899 01:15:18,130 --> 01:15:20,650 тому що ми не звільнити будь-якого з наших вузлів. 900 01:15:20,650 --> 01:15:24,350 Але, якщо ми йдемо сюди, і ми дивимося на нашу роздруківку, 901 01:15:24,350 --> 01:15:30,880 ми бачимо, що, ну, схоже, що всі наші вставками поверталися правда, і це добре. 902 01:15:30,880 --> 01:15:33,050 Вставки все вірно, 903 01:15:33,050 --> 01:15:36,670 , А потім відповідні виклики містить, теж вірно. 904 01:15:36,670 --> 01:15:41,510 >> Гарна робота! Схоже, ми успішно написана вставки. 905 01:15:41,510 --> 01:15:47,430 Це все, що у нас є проблеми специфікації для набору на цьому тижні. 906 01:15:47,430 --> 01:15:51,720 Одна кумедна можливість подумати про те, як би ви насправді йдуть в 907 01:15:51,720 --> 01:15:55,340 і безкоштовно всі вузли в цьому дереві. 908 01:15:55,340 --> 01:15:58,830 Ми можемо зробити це різними способами, 909 01:15:58,830 --> 01:16:01,930 але я залишу це до вас, щоб експеримент, 910 01:16:01,930 --> 01:16:06,080 і як весело завданням, спробуйте і переконайтеся, що ви можете переконатися, 911 01:16:06,080 --> 01:16:09,490 що ця доповідь Valgrind не повертає помилки і витоку. 912 01:16:09,490 --> 01:16:12,880 >> Удачі на Хаффман цьому тижні поставленої задачі кодування, 913 01:16:12,880 --> 01:16:14,380 і ми будемо бачити вас на наступному тижні! 914 01:16:14,380 --> 01:16:17,290 [CS50.TV]