[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]