[Powered by Google Translate] [Часть 7: более комфортным] [Rob Боуден] [Harvard University] [Это CS50] [CS50.TV] Хорошо. Так как я сказал в моей электронной почте, это будет двоичного дерева интенсивной разделе. Но есть не то, что многие вопросы. Итак, мы собираемся, чтобы попытаться вытянуть на каждый вопрос и перейти в болезненное подробно все лучшие способы ведения дел. Таким образом, в самом начале, мы проходим через образцов рисунков бинарные деревья и прочее. Так вот, "Помни, что бинарное дерево имеет узлы, аналогичные связанный список, только вместо одного указателя существует два: один для «ребенка» левый и один для правого "ребенок". Таким образом, бинарное дерево так же, как связанный список, кроме структура будет иметь два указателя. Там в троичной деревьев, которые будет иметь три указателя, Есть N-арной деревья, которые только есть общий указатель что вы тогда должны таНос быть достаточно большим, чтобы иметь Достаточно указатели на все возможные детей. Таким образом, бинарное дерево только, случается, имеют постоянное число два. Если вы хотите, вы можете дать связанный список как унарный дерева, Но я не думаю, что кто-то называет ее этим. "Ничья коробки-и-стрелки схема двоичного дерева узлов содержащие любимый номер Нейта, 7, где каждый ребенок указатель нулевой ". Так Ipad режиме. 

Это будет довольно просто. Мы просто будем иметь узел, я нарисую его как квадрат. И я нарисую значения здесь. Таким образом, значение будет идти сюда, , а затем здесь мы будем иметь левый указатель на левый и правый указатель справа. И это даже очень конвенции назвать его левым и правым, имена указателей. Оба этих собираетесь быть нулевым. Это будет просто нулевым, и это будет просто нулевым. Хорошо. Итак, вернемся сюда. "С связанного списка, мы только должны были хранить указатель на первый узел в списке, чтобы запомнить весь связанный список, или весь список. Кроме того, с деревьями, у нас есть только для хранения указателя в один узел, чтобы помнить все дерево. Этот узел Calle «корень» дерева. Построить на вашей схеме от до или привлечь новое такое, что у вас есть коробки-и-стрелки изображение бинарное дерево с значением 7, затем 3 в левой, Затем 9 на правую, а затем 6 на право 3 ". Давайте посмотрим, если я могу помнить все, что в моей голове. Таким образом, это будет наш корень здесь. У нас будет несколько указателей где-то, что-то, что мы называем корнем, , и это указывает на этого парня. Теперь, чтобы сделать новый узел, Что мы имеем, 3 слева? Таким образом, новый узел с 3 лет, и первоначально отмечает нулевой. Я просто положил N. Теперь мы хотим, чтобы это пойти налево 7. Таким образом, мы изменить это указатель теперь указывает на этого парня. И мы делаем то же самое. Мы хотим, чтобы в 9 здесь который изначально просто говорит нулевым. Мы собираемся изменить это указатель, точка до 9, и теперь мы хотим положить 6 на право 3. Так что это будет - сделать 6. И этот парень будет указывать там. Хорошо. Так что это все, что просит нас сделать. 

Теперь давайте пройдемся по терминологии. Мы уже говорили о том, как корень дерева является самый верхний узел в дереве. Одна из которых 7. Узлов в нижней части дерева называются листьями. Любой узел, который просто имеет нулевое своим детям листа. Таким образом, это возможно, если наши бинарное дерево находится всего в одном узле, , что дерево является листом, и это все. "" Высота "дерева является количество прыжков вы должны сделать чтобы получить от вершины до листа ". Мы войдем в во втором, разница между симметричными и несимметричными бинарные деревья, но сейчас, общая высота этого дерева Я бы сказал, это 3, хотя если посчитать количество прыжков Вы должны сделать для того, чтобы добраться до 9, то это действительно только высота 2. Сейчас это несбалансированное бинарное дерево, но мы говорили о сбалансированном, когда оно станет актуальным. Так что теперь мы можем говорить о узлов в дереве с точки зрения по отношению к другим узлам в дереве. Так что теперь у нас есть родители, дети, братья, сестры, предки, и потомки. Они довольно здравого смысла, что они означают. Если мы спросим, ​​- это родители. Так что родитель 3? [Студенты] 7. >> Да. Родитель просто будет то, что указывает на вас. Тогда что дети от 7? [Студенты] 3 и 9. >> Да. Обратите внимание, что "дети" буквально означает дети, так 6 не будет применяться, потому что это, как внук. Но тогда, если мы пойдем потомков, так что являются потомками 7? [Студенты] 3, 6 и 9. >> Да. Потомки корневого узла будет все в дереве, кроме, может быть корневым узлом себя, если вы не хотите, чтобы рассмотреть, что потомок. И, наконец, предки, так что это в противоположном направлении. Так что предки 6? [Студенты] 3 и 7. >> Да. 9 не включены. Это просто прямая спина линии в корень будет вашим предкам. 

"Мы говорим, что бинарное дерево" заказать ", если для каждого узла в дереве, все его потомки слева имеют меньшие значения и все те, на правом иметь больше значения. Например, дерево выше заказали, но это не единственный возможный упорядоченное расположение ". Прежде чем мы перейдем к этому, приказал бинарное дерево также известен как бинарное дерево поиска. Здесь мы, случается, назвав его заказал бинарное дерево, Но я никогда не слышал его называют приказал двоичного дерева прежде, и на тест мы гораздо больше шансов поставить двоичного дерева поиска. Они одно и то же, и очень важно, вы узнаете различие между бинарное дерево и дерево двоичного поиска. Бинарное дерево это просто дерево, которое указывает на две вещи. Каждый узел указывает на две вещи. Существует нет рассуждений о ценностях, которые он указывает. Так как здесь, так как это бинарное дерево поиска, Мы знаем, что если мы пойдем слева от 7, Затем все ценности, которые мы может достичь , идя слева от 7 должны быть меньше 7. Обратите внимание, что все значения меньше, чем 7, 3 и 6. Это все к левой 7. Если мы идем направо из 7, все должно быть больше, чем 7, поэтому 9 с правой стороны 7, так что мы хорошие. Это не так в случае двоичного дерева, для обычного бинарного дерева мы можем просто есть 3 в верхнем, 7 влево, 9 слева от 7; нет упорядоченности значений вообще. Теперь мы на самом деле не делают этого, потому что это скучно и ненужно, но "пытаются привлечь столько приказал деревьев, как вы можете думать о с помощью чисел 7, 3, 9 и 6. Сколько различных механизмов есть? Что такое высота каждого из них? " 

Мы сделаем пару, но основная идея в том, это ни в коей мере уникальное представление двоичного дерева, содержащего эти значения. Все, что нам нужно, это некоторое бинарное дерево, которое содержит 7, 3, 6 и 9. Другой возможный действительно был бы корень 3, идите налево, и это 6, идти налево, и это 7, идите налево, и это 9. Это вполне допустимо бинарное дерево поиска. Это не очень полезно, потому что это как связанный список и все эти указатели просто нулевой. Но это действительно дерева. Да? [Студент] Не значения должны быть больше на правой? Или это -? >> Эти Я хотел пойти другим путем. Там же - да, давайте перейдем это. 9, 7, 6, 3. Хороший улов. Он по-прежнему должен подчиняться, что поиск бинарное дерево, что должен делать. Таким образом, все, что левее должна быть меньше любого заданного узла. Мы могли бы просто двигаться, говорить, что это 6 и положил его здесь. Нет, мы не можем. Почему я делаю это? Давайте делать - вот 6, здесь 7, 6 очков 3. Это по-прежнему действительны бинарное дерево поиска. Что плохого, если я - посмотрим, смогу ли я придумать договоренности. Да, все в порядке. Так что же не так с этим деревом? Я предполагаю, что я уже дал вам подсказку, что что-то не в порядке с этим. Почему я делаю это? Хорошо. Это выглядит разумным. Если мы посмотрим на каждый узел, как и 7, то слева от 7, 3. Таким образом, мы имеем 3, вещь справа от 3 представляет собой 6. И если вы посмотрите на 6, вещь справа от 6, 9. Так почему же это не является допустимым бинарное дерево поиска? [Студенты] 9-прежнему в левой части 7. >> Да. Это должно быть верно, что все значения, которые может достичь, перейдя в левую от 7 меньше, чем 7. Если мы идем налево из 7, мы получаем 3, и мы все еще можете получить до 6, Мы все еще можете получить до 9, но, пройдя меньше 7, мы не должны быть в состоянии добраться до ряда, что это больше 7. Так что это не является допустимым бинарное дерево поиска. 

Мой брат на самом деле было интервью вопрос , что в основном это, просто код что-то для проверки ли дерево бинарное дерево поиска, и поэтому первое, что он сделал, было просто проверить, если левый и правый правильно, а затем повторять там. Но вы не можете просто сделать это, вы должны следить тот факт, что теперь, когда я ушел левее 7, все в этом поддереве должно быть меньше 7. Правильный алгоритм должен следить за пределы значений, что может упасть возможно дюйма Мы не будем пройти через все из них. Существует хорошее отношение рецидива, хотя мы еще не дошли до тех, или мы не получим тех, определяющая, сколько там на самом деле. Таким образом, существует 14 из них. Идея о том, как вы могли бы сделать это математически, как, Вы можете выбрать какой-либо одной, чтобы быть корневой узел, а затем, если я выбираю быть от 7 до корневого узла, то есть, скажем, некоторые цифры, которые могут пойти моим левым узлом, и есть некоторые номера, которые могут быть моя правая узла, но если я п общего числа, то сумма, которая может пойти налево плюс сумма, которая может пойти на право N - 1. Таким образом, из оставшихся чисел, они должны быть в состоянии пойти либо влево или вправо. Кажется, трудно, что, если я поставлю 3 первых, то все должно пойти налево, но если я поставлю 7, то некоторые вещи могут пойти левой и некоторые вещи могут пойти направо. И '3 первый "я имел в виду все может пойти направо. Это действительно, вы просто должны думать об этом, как, как многое может пойти на следующем уровне дерева. И он выходит на 14, или вы можете нарисовать все, и тогда вы получите 14. 

Возвращаясь сюда, "Упорядоченные бинарные деревья являются здорово, потому что мы можем искать через них В очень похоже на поиски более упорядоченный массив. Чтобы сделать это, мы начинаем с корня и работать наш путь вниз по дереву на листьях, проверяя значения каждого узла в отношении ценностей, которые мы ищем. Если значение текущего узла меньше, чем значение, которое мы ищем, Вы идете рядом с правым потомком узла. В противном случае, вы идете в левом потомка. В какой-то момент, вы либо найти значение, которое вы ищете, или вы будете работать в нуль, с указанием значения не в дереве ". У меня есть для перерисовки дерева, что было раньше, то возьму второй. Но мы хотим, чтобы искать ли 6, 10, и 1 в дерево. Так что же это было, 7, 9, 3, 6. Хорошо. Цифры, которые вы хотите посмотреть, мы хотим, чтобы посмотреть 6. Как это алгоритм работы? Ну, у нас есть несколько корневых указатель на дерево. И мы пошли бы в корне и говорить, это значение равно значению мы ищем? Таким образом, мы ищем 6, так что это не равны. Таким образом, мы продолжаем, и теперь мы говорим, ладно, так 6 меньше 7. Означает ли это, мы хотим идти налево, или мы хотим, чтобы пойти в порядке? [Студент] влево. >> Да. Это значительно проще, все, что вам нужно сделать, это сделать один возможный узел дерева и тогда вы не - вместо того, чтобы думать головой, Хорошо, если она меньше, я могу пойти налево или пойти направо, просто глядя на эту картину, это очень ясно, что я должен идти слева если этот узел больше, чем значение, что я искал. Таким образом, вы идите налево, теперь я на 3. Я хочу - 3 меньше, чем значение, я ищу, что на 6. Таким образом, мы идем направо, и теперь я в конечном итоге на 6, которая является значением я ищу, так что я возвращаюсь правда. Следующее значение, я буду смотреть на это 10. Хорошо. Так что 10, сейчас будет - отрезал, что - будем следовать корня. Теперь, 10 будет больше 7, поэтому я хочу, чтобы смотреть направо. Я собираюсь приехать сюда, 10 будет больше 9, так что я собираюсь хотите посмотреть вправо. Я пришел сюда, но здесь сейчас я в нуль. Что мне делать, если я ударил нуль? [Студент] Вернуться ложным? >> Да. Я не нашел 10. 1, будет почти идентична случае, исключением того, что только собирается быть перевернута, вместо того чтобы искать вниз по правой стороне, я буду смотреть на левую сторону. 

Теперь я думаю, что мы на самом деле получить код. Вот где - открыть CS50 прибор и прокладываете свой путь там, но вы также можете просто сделать это в пространстве. Это, наверное, идеальный сделать это в пространстве, потому что мы можем работать в космосе. "Сначала нужно новое определение типа для бинарного узла дерева, содержащего Int значения. Использование шаблона ЬурейеЕ ниже, создать новое определение типа для узла в бинарном дереве. Если вы застряли. . . "Бла, бла, бла. Ладно. Так давайте шаблонного здесь, ЬурейеЕ узла структуры и узлов. Да, все в порядке. Так что поле мы собираемся хотим в нашей узла? [Студент] Int, а затем два указателя? >> Int значения, два указателя? Как написать указатели? [Студент] Struct. >> Я должна увеличить масштаб Да, так что структура узла * ушел, и структура узла * прав. И помните обсуждение в прошлый раз, что это не имеет смысла, это не имеет смысла, это не имеет смысла. Вам нужно все, для того, чтобы определить это рекурсивная структура. Ладно, так это то, что наше дерево будет выглядеть. Если бы мы сделали троичного дерева, то узел может выглядеть В1, В2, структура узла * b3, где Ь филиала - на самом деле, я больше слышал он оставил, средний, правый, но независимо. Мы заботимся только о бинарных, так вправо, влево. "Теперь объявить глобальную переменную * узел для корня дерева". Таким образом, мы не собираемся этого делать. Для того, чтобы сделать вещи немного более сложным и более обобщенные, у нас не будет глобальной переменной узла. Вместо этого, в главном мы объявим все наши узел вещи, и это означает, что ниже, когда мы начнем работы наши содержит функцию и наши функции вставки, вместо того, чтобы наши содержит функцию только с помощью этой глобальной переменной узла, мы будем иметь его принять в качестве аргумента дерево, которое мы хотим, чтобы обработать. Наличие глобальных переменных должен был сделать вещи проще. Мы собираемся сделать все труднее. Теперь возьмите минуту или около того, чтобы просто делать такого рода вещи, где внутри основного вы хотите создать это дерево, и это все, что вы хотите сделать. Попробуйте построить это дерево в основной функцией. 

Хорошо. Таким образом, вы не должны даже построили дерево всю дорогу пока нет. Но у кого что-то я мог бы подтянуть чтобы показать, как можно было бы начать строительство такого дерева? [Студент] Кто-то стук, пытаясь выбраться наружу. [Боуден] Любой комфортно с их построения дерева? [Студент] Конечно. Это не сделано. >> Это нормально. Мы можем просто закончить - ой, вы можете сохранить его? Ура. Таким образом, здесь мы имеем - ой, я немного обрезаются. Могу ли я увеличил? Увеличение, прокрутка из. >> У меня есть вопрос. >> Да? [Студент] При определении структуры, такие вещи, как инициализируется что-нибудь? [Боуден] Нет >> Хорошо. Таким образом, вы должны инициализировать - [Боуден] Нет Когда вы определяете, или при объявлении структуры, он не инициализирован по умолчанию, это все равно, если вы объявите Int. Это ровно то же самое. Это как каждый из ее отдельных полей может иметь значение мусора в нем. >> А можно ли определить - или объявить структуру таким образом, что это делает их инициализации? [Боуден] Да. Таким образом, контекстное синтаксис инициализации будет выглядеть - Там две, как мы можем это сделать. Я думаю, мы должны скомпилировать его чтобы убедиться, что Clang делает тоже самое. Порядок аргументов, который входит в структуру, вы положите в порядок аргументов внутри этих фигурные скобки. Поэтому если вы хотите, чтобы подготовить его к 9 и оставили быть нулевой, а затем правую быть нулевым, было бы 9, NULL, NULL. В качестве альтернативы, и редактор не нравится этот синтаксис, и он думает, что я хочу новый блок, но альтернатива есть что-то вроде - Здесь, я положу ее на новую строку. Можно прямо сказать, не помню точно синтаксис. Таким образом, вы можете явно обратиться к ним по имени, и говорю: . С, или. Значение = 9. Левая = NULL. Я предполагаю, это необходимость быть запятые. . Право = NULL, чтобы таким образом вы не на самом деле нужно знать порядок структуры, и когда вы это читаете, это гораздо более явную о том, что ценность бытия инициализируется. 

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

Для наших целей, мы будем иметь дело со вставкой, так что мы собираемся хотите написать функцию, чтобы вставить в эту бинарное дерево и вставки неизбежно будем называть таНос, чтобы создать новый узел этого дерева. Так что все будет запутаться с тем, что некоторые узлы В настоящее время в стеке и другие узлы собираются в конечном итоге на куче когда мы вставляем их. Это совершенно справедливо, но единственная причина, мы в состоянии сделать это в стеке Потому что это такой надуманный пример, что мы знаем Дерево должно быть построено как 7, 3, 6, 9. Если мы этого не было, то мы не должны были бы таНос в первую очередь. Как мы увидим чуть позже, мы должны malloc'ing. Сейчас это вполне разумно поставить в стек, но давайте изменим эту таНос реализации. Таким образом, каждый из них теперь будет что-то вроде узел * node9 = таНос (SizeOf (узла)). И теперь мы собираемся нужно сделать наш чек. если (node9 == NULL) - я не хочу, - возвращает 1, а затем мы можем сделать node9-> потому что теперь это указатель, Значение = 6, node9-> влево = NULL, node9-> Право = NULL, и мы собираемся нужно сделать, что для каждого из этих узлов. Таким образом, вместо, скажем внутри отдельной функции. Давайте назовем это узел * build_node, и это несколько похоже на API, мы предлагаем для кодирования Хаффмана. Мы даем вам инициализатор функций для дерева деконструктор и «функции» для тех, деревья и то же самое для леса. 

Итак, мы собираемся иметь функцию инициализации просто построить узел для нас. И это будет выглядеть довольно много именно так. И я даже собирался быть ленивым и не изменять имя переменной, хотя node9 не имеет никакого смысла. О, я думаю node9 значение не должно было быть 6. Теперь мы можем вернуться node9. И здесь мы должны вернуться нулевой. Все согласны с этим Build-A-узла функцию? Так что теперь мы можем просто позвонить, что для создания любого узла с заданным значением и нулевых указателей. Теперь мы можем вызвать том, что мы можем сделать узел * node9 = build_node (9). И давайте делать. . . 6, 3, 7, 6, 3, 7. И теперь мы хотим создать такой же указатели, только теперь все это уже в терминах указателей так больше не нужны адреса. Хорошо. Так что последнее, что я хочу сделать? Там в исправление ошибок, что я не делаю. Что построить узел взамен? [Студент, неразборчиво] >> Да. Если таНос не удалось, он будет возвращать NULL. Так что я собираюсь лениво положил его сюда, а не делать условие для каждого. Если (node9 == NULL, или - еще проще, это равносильно тому, если только не node9. Так что, если не node9, или не node6, или не node3, или не node7, вернуть 1. Может быть, мы должны печатать таНос не удалось, или что-то еще. [Студент] Ложно равна нулю, а? [Боуден] Любое нулевое значение является ложным. Таким образом, нулевые является нулевое значение. Ноль ноль. Ложные является нулевое значение. Любой - в значительной степени только 2 нулевые значения не имеют законной нуля, ложными только хэш определяется как нуль. Это относится и если мы заявляем глобальной переменной. Если бы мы имели корневой узел * здесь, Затем - хорошая вещь о глобальных переменных является то, что они всегда имеют начальное значение. Это не правда функций, как внутри здесь, если у нас есть, вроде бы, узла или узла * х. Мы понятия не имеем, что x.value, x.whatever, или мы можем распечатать их, и они могут быть произвольными. Это не правда глобальных переменных. Так корневого узла или узла х. По умолчанию, все, что глобальное, если явно не инициализированы до некоторого значения, имеет нулевое значение в качестве значения. Так вот, узел * корень, мы явно не инициализировать его ни к чему, таким образом, его значение по умолчанию будет нулевым, которая является нулевое значение указателя. По умолчанию значение х будет означать, что x.value равна нулю, x.left является недействительным, и x.right является недействительным. Таким образом, так как он является структурой, все поля структуры будут равны нулю значений. Мы не должны использовать что здесь, однако. [Студент] структуры отличаются от других переменных, и другие переменные мусор ценностей; эти нули? [Боуден] Другие значения тоже. Таким образом, в х, х будет равна нулю. Если это в глобальной области, она имеет первоначальное значение. >> Хорошо. [Боуден] Либо начальное значение вы дали его или равны нулю. Я думаю, что берет на себя все это. 

Хорошо. Так что в следующий части вопроса спрашивает, "Теперь мы хотим написать функцию, называется содержит с прототипом BOOL содержит целочисленное значение ". Мы не собираемся делать BOOL содержит целочисленное значение. Наш прототип будет выглядеть BOOL содержит (целочисленное значение. И тогда мы также собираемся передать его дерево что она должна быть проверка, чтобы увидеть, если она имеет это значение. Таким образом, узел * дерево). Хорошо. И тогда мы можем назвать это чем-то вроде, может быть, мы хотим Printf или что-то. Содержит 6, наш корень. Это должно вернуть один или правда, в то время как содержит 5 корень должен вернуться ложным. Так что берите вторую для реализации этого. Вы можете сделать это либо итерационно или рекурсивно. Хорошая вещь о том, как мы установили вещей является то, что она поддается нашему рекурсивное решение гораздо проще чем глобальная переменная пути и сделали. Потому что, если мы просто содержит целочисленное значение, то нет никакого способа рекурсии вниз поддеревьев. Мы должны были бы иметь отдельную вспомогательную функцию, которая рекурсивно вниз поддеревья для нас. Но так как мы изменили его взять дерево в качестве аргумента, которые он должен всегда были на первом месте, Теперь мы можем рекурсивно более легко. Таким образом, итерационный или рекурсивный, мы пойдем на обоих, но мы увидим, что рекурсивные заканчивает тем, что довольно легко. Хорошо. Кто-нибудь есть что-то, что мы можем работать с? 

[Студент] У меня есть решение итеративным. >> Ладно, итерационные. Ладно, это хорошо выглядит. Так что, хотите идти с нами через это? [Студент] Конечно. Поэтому я временную переменную, чтобы получить первый узел дерева. А потом я просто петельные через время температура не равна нулю, так что пока все еще был в дерево, я думаю. И если значение равно значению, температура указывает на, Затем он возвращает это значение. В противном случае, он проверяет, если он находится на правой стороне или к левой стороне. Если вы когда-нибудь ситуация, когда нет больше деревьев, Затем он возвращается - он выходит из цикла и возвращает ложь. [Боуден] Хорошо. Так что кажется хорошим. Любой, есть какие-либо комментарии на что-нибудь? У меня нет корректности комментариев вообще. Единственное, что мы можем сделать это за парень. О, он собирается пойти немного длинноват. Я починю, что до. Хорошо. 

Каждый должен помнить, как тройной работает. Там определенно были тесты в прошлом , которые дают вам функции с тройной оператор, и говорят, перевести это, делать то, что не используется тройной. Так что это очень распространенный случай, когда я думал использовать тройные, где, если некоторые условия установить переменную на что-то, еще установить, что же переменную на что-то другое. Это то, что очень часто может быть преобразована в такого рода вещи , где установлено, что переменная это - или, ну, это правда? Тогда это, иначе это. [Студент] Первая если это правда, не так ли? [Боуден] Да. То, как я всегда читал это, темп равно значение большее, чем временный значение, то это, иначе это. Он задает вопрос. Это больше? Тогда сделайте первый шаг. Остальное делают второе. Я почти всегда - толстую кишку, я просто - у меня в голове, я читал, как остальные. 

Кто-нибудь есть рекурсивное решение? Хорошо. Это тот, который мы собираемся - это уже может быть большим, но мы собираемся сделать его еще лучше. Это в значительной степени точно такой же идеей. Это просто, ну, ты хочешь объяснить? [Студент] Конечно. Таким образом, мы убедитесь, что дерево не является нулевым первым, потому что, если дерево является нулевым, тогда она собирается вернуться ложным, потому что мы не нашли его. И если есть еще дерево, идем в - мы сначала проверяем, если значение текущего узла. Вернуться верно, если она есть, и если не мы рекурсивно слева или справа. Звучит ли это необходимо? >> Угу. (Соглашение) Так заметить, что это почти - конструктивно очень похожие на итерационном решении. Это просто, что вместо рекурсии, у нас было время цикла. И дело здесь базу, где деревьев не равно NULL было условие, при котором мы вырвались из цикла. Они очень похожи. Но мы собираемся сделать еще один шаг вперед. Теперь мы делаем то же самое и здесь. Обратите внимание, мы возвращаемся одно и то же в обоих этих строк, за исключением одного аргумента другой. Так что мы собираемся сделать это в тройном. Я ударил вариант что-то, и он сделал символом. Хорошо. Так что мы собираемся вернуться содержит этом. Это становится быть несколько строк, а, увеличенной в этом есть. Как правило, в качестве стилистического вещь, я не думаю, что многие люди поставить пробел после стрелки, но я думаю, если вы последовательны, это прекрасно. Если значение меньше, чем значение дерева, мы хотим, чтобы рекурсивно по дереву слева, еще мы хотим, чтобы рекурсивно по дереву права. Так что было шагом одним из решений этой выглядеть меньше. Второй шаг сделать этот вид меньше - мы можем разделить это на несколько строк. Хорошо. Шаг два делая его похожим меньше здесь, так что возвращаемое значение равно дерево значение, или содержит угодно. 

Это важная вещь. Я не уверен, если бы он сказал, что это в явном виде в классе, но это называется короткое замыкание оценки. Идея здесь состоит значение == дерева значение. Если это правда, то это действительно так, и мы хотим »или« что с тем, что есть здесь. Таким образом, даже не думая обо всем, что находится здесь, что все выражение собирается вернуться? [Студент] True? >> Да, потому что истинное ничего, соединены через ИЛИ - или истинный соединены через ИЛИ с чем обязательно верно. Поэтому, как только мы видим, возвращается значение = Дерево значение, мы только собираемся вернуться верно. Даже не собираюсь рекурсивно дополнительно содержит по линии. Мы можем принять это еще один шаг вперед. Вернуться дерево не равна NULL и все это. Он сделал это одна строка функции. Это также пример короткого замыкания оценки. Но теперь это та же самая идея - вместо того, чтобы - так, если дерево не равно NULL - или, ну, если дерево имеет равные нулю, что является плохой случай, если дерево равна нулю, то первое условие будет ложным. Так ложная операция AND с чем будет что? [Студент] False. >> Да. Это другая половина короткого замыкания оценки, где, если дерево не равны нулю, то мы не собираемся даже пойти - или если дерево имеет равные нулю, то мы не собираемся делать значение == дерева значение. Мы просто собираемся, чтобы немедленно вернуться ложным. Что важно, так как если это не короткое замыкание оценки, затем, если дерево имеет равные нулю, это второе условие будет вине сегмента, потому что дерево-> значение разыменования NULL. Так вот что. Можете сделать это - перейти раза старше. Это очень обычная вещь, также, не делает это один соответствии с этим, но это обычное дело в условиях, может быть, не прямо здесь, но если (дерево! = NULL, и дерево-> значение == значение), делать что угодно. Это очень распространенное заболевание, где вместо того, разорвать ее на две IFS, где угодно, это дерево нуль? Ладно, это не нулевой, так что теперь это дерево значения, равного стоимости? Сделайте это. Вместо этого состояния, этого никогда не будет сегментам вина потому что он вырвется наружу, если это произойдет, являются недействительными. Ну, я думаю, если ваше дерево совершенно неверный указатель, он все еще может сегментам вина, но она не может сегментам вина, если дерево является недействительным. Если бы это был нулевым, это нарушило бы прежде, чем вы когда-либо разыменован указатель на первое место. [Студент] Это называемых ленивых оценки? 

[Боуден] Ленивые вычисления отдельная вещь. Ленивые вычисления более, как вы просите значение, Вы спросите для вычисления значения, своего рода, но вы не должны его немедленно. Так что, пока вы на самом деле нужно, оно не вычисляется. Это не совсем то же самое, но в Хаффман PSET, он говорит, что мы "лениво" писать. Поэтому мы делаем это потому, что мы на самом деле буферизации записи - Мы не хотим, чтобы написать отдельные биты в то время, или отдельных байтов за раз, вместо этого мы хотим получить кусок байт. Затем, когда у нас есть кусок байт, то мы будем его выписывать. Даже если вы попросите его написать - и FWRITE и FREAD сделать такую ​​же вещь. Они буфер вашего чтения и записи. Даже если вы попросите его написать сразу, он, вероятно, не будет. И вы не можете быть уверены, что вещи будут написаны до вызова hfclose или что это такое, которые потом говорит, ладно, я закрываю свой файл, это означает, что мне лучше написать все, что я еще не написана. Это не нужно писать все из пока вы не закрываете файл, а затем это необходимо. Так что это именно то, что лень - он ждет, пока это должно произойти. Это - взять 51 и вы будете входить в его более подробно, потому что OCaml и все в 51, все рекурсии. Есть никаких итерационного решения, в основном. Все рекурсии и ленивые вычисления будет важным для многих обстоятельств где, если не лениво оценку, это будет означать - Примером является потоков, которые являются бесконечно долго. В теории, вы можете думать о натуральных чисел в виде потока 1-2-3-4-5-6-7, Так лениво оценивать вещи в порядке. Если я говорю, я хочу десятого числа, то я могу оценить до десятого числа. Если я хочу в сотый номер, то я могу оценить до сотого номера. Без ленивых вычислений, то он будет пытаться оценить все номера сразу. Ты оценке бесконечно много чисел, и это просто не возможно. Таким образом, есть много случаев, когда ленивые вычисления просто необходимо для получения вещей на работу. 

Теперь мы хотим написать вставку, где вставка будет Аналогично изменения в его определении. Так что сейчас это BOOL вставки (целочисленное значение). Мы собираемся изменить это BOOL вставки (целочисленное значение, узел * дерево). Мы действительно собираемся изменить это снова в немного, мы увидим, почему. И давайте перейдем build_node, просто ради этого, вставить выше, поэтому мы не должны написать прототип функции. Какие это намек, что вы собираетесь использовать build_node в вставки. Хорошо. Остановитесь на минутку за это. Я думаю, что я спас редакции, если вы хотите, чтобы вытащить из этого, или, по крайней мере, я сделал сейчас. Я хотела небольшой перерыв, чтобы думать о логике вставки, если вы не можете думать об этом. В принципе, вы только когда-либо вставки на листьях. Мол, если я вставляю 1, то я неизбежно будет вставка 1 - Я изменю в черном - I'll быть вставка 1 над здесь. Или, если я вставляю 4, я хочу, чтобы вставка 4 над здесь. Так что не имеет значения, что вы делаете, вы будете вставки на лист. Все, что вам нужно сделать, это итерации вниз по дереву, пока не дойдете до узла , которые должны быть родителем узла, родитель нового узла, , а затем изменить ее влево или вправо, указатель, в зависимости от того, это больше или меньше текущего узла. Изменить этот указатель, чтобы указать на новый узел. Таким образом, итерации по дереву, сделать конечный пункт нового узла. Кроме того, думаю о том, почему, который запрещает тип ситуации и прежде, где я построил двоичного дерева, где это было правильно если вы смотрели только на одном узле, но 9 был слева от 7, если вы повторных вниз до упора. Так, что это невозможно в этой ситуации, так как - думаю об установке 9 или что-то; на самом первом узле, Я собираюсь смотреть 7, и я просто собираюсь идти с правой стороны. Так что не имеет значения, что мне делать, если я вставка, перейдя на лист, и листья помощью соответствующего алгоритма, это будет для меня невозможно вставить 9 до левого из 7 потому что как только я попал 7 я пойду направо. Кто-нибудь есть что-то начать? [Студент] я делаю. >> Конечно. [Студент, неразборчиво] [Другой студент, неразборчиво] [Боуден] Это ценится. Хорошо. Хотите объяснить? 

[Студент] Поскольку мы знаем, что мы вставка новые узлы в конце дерева, Я петлю по дереву итеративно пока я не добрался до узла, который указал на нуль. И тогда я решил поставить его либо на правой, либо с левой стороны использование этого права переменная, она сказала мне, куда его положить. И тогда, по сути, я только что сделал, что в прошлом - этой точки температура узла на новый узел, который он создает, либо на левой стороне или на правой стороне, в зависимости от того, что значение прав был. Наконец, я установил новое значение узла к стоимости его тестирование. [Боуден] Итак, я вижу один вопрос здесь. Это как 95% пути. Один вопрос, который я вижу, ну, кто-нибудь еще видел проблемы? Что такое обстоятельство, при которых они вырваться из петли? [Студент] Если температура является недействительным? >> Да. Итак, как вы вырваться из петли, если температура является недействительным. Но то, что я делаю здесь? Я разыменования температура, которая неизбежно нулевой. Таким образом, другие, что вам нужно сделать, это не просто отслеживать, пока температура пустой, Вы хотите, чтобы следить за родителей во все времена. Мы также хотим родительский узел *, я думаю, мы можем сохранить, что при нулевых на первый взгляд. Это будет иметь странное поведение для корня дерева, но мы вернемся к этому. Если значение больше, чем любой другой, то Temp = Температура права. Но прежде чем мы это сделаем, родитель = темп. Или родители всегда будут равны температуре? Так ли это? Если температура не является нулевым, то я буду двигаться вниз, несмотря ни на что, к узлу, для которого временный родителей. Таким образом, родитель это будет временный, а потом двигаться темп вниз. Сейчас температура является действительным, но родитель указывает на родителя то, что является нулевым. Так что здесь, я не хочу, чтобы установить право равна 1. Так я переехал в правую, так что если правый = 1, и я думаю, вы также хотите делать - если двигаться влево, вы хотите установить права равны 0. Или же, если вы когда-нибудь двигаться вправо. Таким образом, право = 0. Если право = 1, Теперь мы хотим, чтобы родители право newnode указатель, еще мы хотим, чтобы родители левой newnode указатель. Вопросов по этому поводу? Хорошо. Итак, это то, как мы - ну, на самом деле, а не делать этого, Мы почти ожидал использовать build_node. И потом, если newnode равна нулю, вернуться ложным. Вот и все. Теперь, это то, что мы ожидали, что вы делаете. 

Это то, что сотрудники решений делают. Я не согласен с этим, как "правильный" способ идти о нем Но это прекрасно, и она будет работать. Единственное, что немного странно прямо сейчас если дерево начинается как нулевые, мы передаем в нулевое дерево. Я думаю, это зависит от того, как определять поведение проходящих в нулевых дерева. Я думаю, что если вы проходите в нулевое дерево, затем вставить значение в нулевой дерева надо просто вернуть дерево, где единственная ценность в том, что один узел. У людей с этим согласны? Вы могли бы, если бы вы хотели, если вы проходите в нулевое дерево и вы хотите вставить значение в ней, вернуться ложным. Это до вас, чтобы определить, что. Для этого первое, что я сказал, а потом - хорошо, вы будете иметь проблемы делают это, потому что было бы легче, если бы мы имели глобальный указатель на вещь, но у нас нет, так что если дерево является нулевым, то мы ничего не можем с этим поделать. Мы можем просто вернуться ложным. Так что я собираюсь изменить вставки. Мы технически мог бы просто изменить это прямо здесь, как это итерации вещи, но я собираюсь изменить вставки принять узла ** дерево. Двухместный указателей. Что это значит? Вместо того, чтобы иметь дело с указателями на узлы, что я собираюсь быть манипулирования это указатель. Я собираюсь быть манипулирования этот указатель. Я собираюсь быть манипуляций указателями напрямую. Это имеет смысл, так как, думаю о вниз - Ну, сейчас это указывает на нуль. То, что я хочу сделать, это управлять этой указатель, чтобы указать на не нулевой. Я хочу, чтобы она указывала на моем новом узле. Если бы я просто следить за указателями на мой указателей, то мне не нужно следить за предка. Я могу только следить, чтобы убедиться, что указатель направлен к нулю, и если указатель указывает на нуль, изменить его, чтобы указать на узел я хочу. И я могу изменить его, так как у меня есть указатель на указатель. Давайте посмотрим это прямо сейчас. Вы действительно можете сделать это рекурсивно довольно легко. Хотим ли мы это сделать? Да, мы делаем. 

Давайте посмотрим, что рекурсивно. Во-первых, то, что наш базовый сценарий будет? Почти всегда наш базовый сценарий, но на самом деле, это вроде сложно. Перво-наперво, если (дерево == NULL) Я думаю, мы просто собираемся, чтобы вернуться ложным. Это отличается от вашего дерева быть нулевым. Это указатель на корневой указатель быть нулевым Это означает, что ваш корневой указатель не существует. Так что здесь, если я делаю узел * - давайте просто повторно использовать этот. Node * корень = NULL, и тогда я буду называть вставки, делая что-то вроде, вставьте 4 и в корне. Так и корня, если корень узел * то и корень будет узлом. ** Это справедливо. В этом случае, дерево, здесь, Дерево не пустой - или вставки. Здесь. Дерево не является нулевым; * Дерево является недействительным, и это хорошо потому что, если * Дерево является нулевым, то я могу управлять им в настоящее время указывают на то, что я хочу, чтобы это указывают. Но если дерево является пустым, это означает, что я только что пришел сюда и сказал, нулевой. Это не имеет смысла. Я ничего не могу сделать с этим. Если дерево является пустым, вернуться ложным. Так что я в принципе уже говорил, что наши реальные дела базы. И что это будет? [Студент, неразборчиво] [Боуден] Да. Так что, если (* дерево == NULL). Это относится к случаю здесь где, если мой красный указатель является указателем я сосредоточен на, так как я сосредоточен на этот указатель, сейчас я сосредоточен на этот указатель. Сейчас я сосредоточен на этот указатель. Так что, если мой красный указатель, который является моим ** узла, это все - если *, моя красная стрелка, это никогда не нулевой, это означает, что я нахожусь в том случае, когда я сосредоточен на указатель, который указывает - это указатель, который принадлежит листа. Я хочу изменить этот указатель, чтобы указать на моем новом узле. Приходите сюда. Мой newnode будет просто узел * п = build_node (стоимость) Затем п, если п = NULL, возвращает ложь. Остальное мы хотим изменить то, что указатель в данный момент указывает в настоящее время указывают на нашем новом узле. Мы можем реально сделать это здесь. Вместо того чтобы сказать я, мы говорим * = дерево, если дерево *. Все понимают, что? Это, имея дело с указателями на указатели, мы можем изменить нулевые указатели указывают на то, что мы хотим, чтобы они указывают. Это наш базовый сценарий. 

Теперь наши рецидива, или наш рекурсии, будет очень похож на все другие рекурсии мы делали. Мы собираемся хотите вставить значение, и теперь я собираюсь использовать тройные снова, но то, что наше условие будет? Что это мы ищем решить, хотим ли мы идти влево или вправо? Давайте делать это в отдельных шагов. Если (значение <) что? [Студент] Значение дерево? [Боуден] Поэтому помните, что я в настоящее время - [Студенты, неразборчиво] [Боуден] Да, так прямо здесь, скажем, что эта зеленая стрелка является примером того, что дерево в настоящее время, является указателем на этот указатель. Таким образом, это означает, что я указатель на указатель до 3. Разыменования дважды звучало хорошо. Что мне - как я могу это сделать? [Студент] Dereference один раз, а затем сделать стрелки таким образом? [Боуден] Таким образом, (* дерево) является разыменования один раз, -> значение собирается дать мне значение узла, что я косвенно указывает. Так что я тоже могу писать ** tree.value, если вы предпочитаете это. Либо работает. Если это так, то я хочу обратить вставить со значением. И то, что мой обновленный узел ** будет? Я хочу пойти налево, так ** tree.left будет слева от меня. И я хочу, указатель на эту вещь так что если левая заканчивает тем, что нулевой указатель, Я могу изменить его, чтобы указать на моем новом узле. 

И в другом случае могут быть очень похожи. Давайте реально сделать, что мой тройной прямо сейчас. Вставьте значение, если значение <(** дерево). Значение. Затем мы хотим обновить нашу ** влево, еще мы хотим обновить нашу ** вправо. [Студент] ли это, что получить указатель на указатель? [Боуден] Помните, что - ** tree.right является узлом звезды. [Студент, неразборчиво] >> Да. ** Tree.right, как этот указатель или что-то. Таким образом, принимая указатель на том, что это дает мне то, что я хочу указателя на этого парня. [Студент] Можем ли мы пойти снова, почему мы используем два указателя? [Боуден] Да. Так что - нет, вы можете, и это решение до был способ сделать это, не делая двух указателей. Вы должны быть в состоянии понять с помощью двух указателей, и это чистое решение. Кроме того, заметил, что то, что происходит, если мое дерево - Что произойдет, если мой корень был нулевым? Что произойдет, если я сделаю это случай прямо здесь? Таким образом, узел * корень = NULL, вставьте 4 и в корне. То, что корень будет после этого? [Студент, неразборчиво] >> Да. Корневая значение будет 4. Корневая левого будет нулевым, корень право будет нулевым. В случае, когда мы не прошли корень по адресу, мы не могли изменить корень. В случае, когда дерево - где корень был нулевым, мы просто должны были вернуться ложным. Там нет ничего, что мы могли сделать. Мы не можем вставить узел в пустое дерево. Но теперь мы можем, мы просто сделать пустое дерево в одной узла дерева. Которая обычно ожидаемым образом, что оно должно работать. 

Кроме того, это значительно меньше, чем Также следить за родителями, и поэтому вы итерации до упора. Теперь у меня есть мои родители, и я просто мои родители право указатель на что угодно. Вместо этого, если бы мы делали это многократно, это было бы то же идею с цикла. Но вместо того, чтобы иметь дело с моими родителями указатель, Вместо моего текущего указателя бы вещь что я напрямую изменять, чтобы указать на моем новом узле. Я не приходится иметь дело с того, что это указывает на левом. Я не приходится иметь дело с того, что это указывает на права. Это просто, что этот указатель, я собираюсь установить его, чтобы указать на моем новом узле. Все понимают, как это работает? Если нет, то почему мы хотим сделать это таким образом, но по крайней мере, что это работает как решение? [Студент] Куда мы возвращаемся правда? [Боуден] Это, наверное, прямо здесь. Если мы правильно вставить его, вернуть истинный. В противном случае, здесь мы собираемся хотите вернуть все возвращается вставки. 

А что особенного в этой рекурсивной функции? Это хвост рекурсивной, так как пока мы составляем с некоторой оптимизации, она будет признать, что и вы никогда не получите переполнение стека из этого, даже если наше дерево имеет высоту 10.000 или 10 миллионов. [Студент, неразборчиво] [Боуден] Я думаю, что он это делает на Dash - или то, что уровень оптимизации требуется для хвостовой рекурсии чтобы быть признанным. Я думаю, что он признает - GCC и Clang Также имеют разные значения для их уровня оптимизации. Я хочу сказать, что это Дашо 2, убедиться, что он не признает хвостовой рекурсии. Но мы - вы можете построить, как например Fibonocci или что-то. Это не легко проверить с этим, потому что это трудно построить бинарное дерево, что такой большой. Но да, я думаю, что это Дашо 2, Если вы компилируете с Дашо 2, он будет искать хвостовую рекурсию и оптимизировать это. Давайте вернемся к - вставить буквально последним, что ему нужно. Давайте вернемся к вставке здесь где мы собираемся делать ту же идею. Он все еще будете иметь недостаток не в состоянии полностью справиться когда сам корень является пустым, или прошлое вступления пустой, но вместо того чтобы справиться с одним из родителей указатель, Давайте применить ту же логику хранения указателей на указатели. Если при этом мы продолжаем наш узел ** текущ., и нам не нужно следить за право больше, но узле ** = текущ. и дерева. И теперь наша в то время как цикл будет время * тока не равна нулю. Не нужно следить за родителей больше. Не нужно следить за левую и правую. И я буду называть его темп, потому что мы уже использует темп. Хорошо. Так что, если (значение> * температура), то и (* температура) -> Право еще Temp = & (* температура) -> ушел. И сейчас, в данный момент, после этого время цикла, Я только делаю это потому, может быть, легче думать о чем многократно рекурсивно, но после этого время цикла, * Временный указатель мы хотим изменить. 

Прежде, чем мы имели родителей, и мы хотели изменить или левой родителей или родителя права, Но если мы хотим изменить родительский прав, Затем * временный родители правы, и мы можем изменить его непосредственно. Так что здесь, внизу, мы можем сделать * Temp = newnode, вот и все. Таким образом, уведомление, все, что мы сделали в этом было вывезти строк кода. Для того, чтобы следить за родителей во всем, что дополнительные усилия. При этом, если мы просто следить за указателем на указатель, и даже если бы мы хотели, чтобы избавиться от всех этих фигурные скобки сейчас, сделать его короче. Это теперь точно такой же раствор, но меньше строк кода. Как только вы начинаете признавая это как правильное решение, это также легче рассуждать о чем, как, в порядке, почему я должен этим флагом на Int верно? Что это значит? О, это означало, что каждый раз, когда я иду правы, мне нужно, чтобы установить его, еще, если я иду оставил мне нужно установить его к нулю. Вот, у меня нет причин, чтобы об этом, это просто легче думать. Вопросы? [Студент, неразборчиво] >> Да. Итак, в последний бит - Я думаю, одна быстрый и простой функции мы можем сделать, это, let's - вместе, я думаю, попробовать и написать функцию, содержит который не заботится, является ли это бинарное дерево поиска. В нем содержится функция должна возвращать истинным если где-нибудь в этом общем бинарное дерево является значение, которое мы ищем. Так давайте делать это рекурсивно, и тогда мы будем делать это повторно. Мы можем на самом деле просто делать это вместе, потому что это будет очень коротким. 

То, что мой базовый вариант будет? [Студент, неразборчиво] [Боуден] Так что, если (дерево == NULL), то что? [Студент] Вернуться ложным. [Боуден] остальное, ну, мне не нужно другого. Если был моим другом случае база. [Студент] Дерева значение? >> Да. Так что, если (дерево-> значение == значение. Обратите внимание, что мы вернулись к узлу *, а не узла ** ы? Содержит никогда не нужно будет использовать узел ** так как мы не изменяем указателей. Мы просто через них. Если это произойдет, то мы хотим вернуть истинный. Остальное мы хотим, чтобы пересечь детей. Поэтому мы не можем рассуждать о том, чтобы все осталось менее и все, что правее больше. Так что же наше состояние будет здесь - или, что мы будем делать? [Студент, неразборчиво] >> Да. Вернуться содержит (значение, дерево-> слева) или содержит (значение, дерево-> справа). И это все. И обратите внимание, есть некоторое короткое замыкание оценки, где, если мы, случается, найти значение в левом дереве, Мы никогда не должны смотреть на правом дереве. Это целая функция. Теперь давайте делать это многократно, который будет менее приятно. Мы возьмем обычную начала узла * текущ. = дерево. В то время (текущ.! = NULL). Быстро собираемся вижу проблемы. Если текущ. - здесь, если мы когда-нибудь вырваться из этого, Затем мы запускаем из вещей, чтобы смотреть на, так что вернуться ложным. Если (в настоящее> значение == значение), вернуться верно. Итак, теперь мы находимся на месте - Мы не знаем, хотим ли мы, чтобы пойти налево или направо. Таким образом, произвольно, давайте просто пойти налево. Я, очевидно, столкнулись с вопросом, где я полностью отказалась от всего - Я только когда-либо проверить левой стороне дерева. Я никогда не буду проверить все, что право ребенка на все. Как я могу это исправить? [Студент] Вы должны следить за левый и правый в стеке. [Боуден] Да. Так давайте сделаем это Структура списка узлов * N, а затем узел ** дальше? Я думаю, что отлично работает. Мы хотим идти по левой или let's - здесь. Struct = список список, он начнет при этом структура списка. * Список = NULL. Так что это будет наш связанного списка поддеревьев, которые мы пропустили. Мы собираемся пройти осталось, но так как мы неизбежно должны вернуться к праву, Мы собираемся держать в правой части внутри нашей структуры списка. Тогда мы будем иметь new_list или структуры, Структура списка *, new_list = таНос (SizeOf (список)). Я собираюсь игнорировать проверки ошибок, но вы должны проверить, если это нулевой. New_list узла это будет указывать на - Ах, вот почему я хотел его здесь. Это будет указывать на второй список структуру. Вот только как связанные списки работ. Это то же самое, как Int связанный список кроме мы просто заменив Int с узлом *. Это точно так же. Так new_list, стоимость наших new_list узла, будет ток> правы. Ценность нашего new_list-> следующий будет наш первоначальный список, , а затем мы будем обновлять наш список, чтобы указать на new_list. 

Теперь нам нужно какой-то способ вытягивания вещей, как у нас прошел весь левого поддерева. Теперь нам нужно вытащить вещи из него, как тока является нулевым, мы не хотим, чтобы просто вернуться ложным. Мы хотим сейчас тянуть за пределами на нашем новом списке. Удобный способ сделать это - хорошо, на самом деле, есть несколько способов сделать это. Любой, есть предложения? Где я должен это сделать, или, как я должен это сделать? У нас есть только пара минут, но какие-либо предложения? Вместо того, чтобы - в одну сторону, а наши условием является время, то, что мы в настоящее время смотрим на это не нулевой, Вместо этого мы собираемся продолжать идти, пока наши Сам список является пустым. Таким образом, если наш список заканчивает тем, что нулевой, Затем мы запустили из вещей, чтобы искать, искать более. Но это означает, что в первую очередь в нашем списке только собирается стать первым узлом. Самое первое, что будет - мы больше не должны видеть, что. Таким образом, список-> N будет наше дерево. Список-> следующая будет нулевым. И сейчас, пока список не равна нулю. Cur собирается вытащить что-то из нашего списка. Так текущ. будет равным список-> л. И тогда список будет равным список-> п, или список-> дальше. Так что, если текущ. значение равно значению. Теперь мы можем добавить и наше право и наш указатель левого указателя тех пор, пока они не нулевые. Здесь, внизу, я думаю, мы должны были это сделать в первую очередь. Если (в настоящее> правы! = NULL) Затем мы собираемся, чтобы вставить этот узел в наш список. Если (в настоящее> слева), это немного дополнительной работы, но это нормально. Если (в настоящее> слева! = NULL), и мы собираемся, чтобы вставить слева в нашу связанный список, и что должно быть. Мы итерации - пока у нас есть что-то в нашем списке у нас есть еще один узел на что посмотреть. Таким образом, мы смотрим на этот узел, мы продвигаем наш список в следующем. Если узел является значение, которое мы ищем, мы можем вернуться верно. Остальное вставить обе наши левые и правые поддеревья, тех пор, пока они не нулевой, в нашем списке так что мы неизбежно идут за ними. Так что, если они не были нулевые, если наш корневой указатель указывал на две вещи: Затем мы сначала вытащил что-то из нашего списка так заканчивает тем, что нулевой. И тогда мы ставим две вещи обратно, так что теперь наш список имеет размер 2. Затем мы собираемся цикла резервного копирования и мы только собираемся тянуть, скажем, левый указатель нашего корневого узла. И это будет просто держать происходит, мы закончим цикл над всем. 

Обратите внимание, что это было значительно сложнее В рекурсивное решение. И я уже говорил несколько раз , что рекурсивное решение, как правило, имеет много общего с решением итеративным. Вот это именно то, что рекурсивное решение делает. Единственное изменение состоит в том, что вместо неявно с помощью стека, стек программы, как ваш способ отслеживать, какие узлы вы все еще должны посетить, Теперь вы должны явно использовать связанный список. В обоих случаях вы отслеживания того, что узел еще нужно посетить. В рекурсивном случае это просто легче, потому что стек реализуется для вас, как стек программы. Обратите внимание, что это связанный список, это стек. Все, что мы просто положить в стек сразу, что мы собираемся вытащить из стека, чтобы посетить следующий. Мы вне времени, но есть вопросы? [Студент, неразборчиво] [Боуден] Да. Так что, если у нас есть связанный список, Ток будет указывать на этого парня, и теперь мы просто продвижение наших связанный список, чтобы сосредоточиться на этого парня. Мы перемещения через связанный список в этой строке. И тогда я думаю, мы должны освободить наши связанный список и прочее раз, прежде чем вернуться истинным или ложным, мы должны перебора наших связанный список и всегда здесь, я думаю, если мы текущ. право не является равным, добавьте его, так что теперь мы хотим, чтобы освободить текущ. потому что, ну, разве мы совершенно забываем о списке? Да. Так вот что мы хотим сделать здесь. Где указатель? Cur было потом - мы хотим, чтобы список структур * 10 равна списке рядом. Бесплатные список, список = темп. И в случае, когда мы возвращаемся правда, нам нужно итерации в течение оставшейся части наши связанный список, освобождая вещи. Хорошая вещь о рекурсивные решения освобождение вещи просто означает, появляются factorings стека, которые будут происходить для вас. Таким образом, мы ушли от чего-то, что походит на 3 линии трудно думать о код- к тому, что значительно многие другие трудно думать-о строках кода. Есть еще вопросы? Хорошо. Мы хорошо. Bye! [CS50.TV]