Узнайте, как добавлять узлы в двоичное дерево поиска на C #
Меня зовут Алексис, я учусь на последнем курсе факультета информатики и математики. Я увлекаюсь алгоритмами и графиками, и сегодня я хочу написать код на примере бинарного дерева поиска.
Примечание: я не идеальный программист. Я знаю, что буду делать ошибки и упускать очевидные способы улучшить код, но пока я просто хочу показать вам простую, понятную модель того, как работает двоичное дерево поиска.
Бинарное дерево поиска - это тип графа, в котором у каждого узла может быть только два дочерних элемента, правый и левый. Левый узел всегда меньше своего родителя, а правый узел всегда больше своего родителя. Всегда есть один узел, с которого начинается дерево, и он называется «корневым» узлом. Это пример двоичного дерева поиска:
Существуют определенные алгоритмы добавления, удаления и поиска узлов в двоичном дереве поиска, но мы рассмотрим их позже.
Я использую Visual Studio для этого проекта. Итак, я начинаю с того, что нажимаю «создать новый проект» и выбираю «Консольное приложение (.NET Core)» в качестве типа проекта. Я назвал свой «BinarySearchTreeExample», но вы можете называть его как хотите! Затем нажмите "Создать" и "ПРЕСТО !!" У вас есть пустой проект Visual Studio, который выглядит примерно так:
Первое, что я собираюсь сделать, это щелкнуть правой кнопкой мыши проект справа (извините за ужасное выделение):
Наведите указатель мыши на «Добавить» и нажмите «Класс…». Я назвал свой класс «Узел», но вы можете называть его как хотите. У вас должен получиться новый файл, который выглядит примерно так:
Если вы вернетесь к изображению бинарного дерева поиска в начале этого фрагмента, вы заметите, что в каждом кружке или «узле» есть число. Мы собираемся называть этот номер нашим label. Итак, я создал публичное поле внутри класса Node, в котором хранятся наши label:
Вы также заметите, что у каждого Node есть ветвь слева и ветвь справа. Мы можем добавить эти ребра, создав две переменные, которые представляют эти узлы:
Потрясающий! А теперь сделаем конструктор. Конструктор - это то, что мы вызываем, когда хотим создать новый узел, который мы можем добавить к нашему графу.
Когда мы создаем новый узел, мы передаем значение, которое хотим ему присвоить, так что здесь в игру вступает заполнитель data. Вы также заметите, что я установил left и right на null, что по сути означает, что они «пусты». Мы сразу устанавливаем левый и правый дочерние узлы как null, потому что у узлов не может быть дочерних узлов до тех пор, пока они не будут добавлены в граф, а прямо сейчас они не являются частью графа. Они просто создаются.
Хорошо! У нас есть база для изготовления узлов. Вернемся к Program.cs и поработаем над инициализацией дерева.
Первое, что я сделал в Program.cs, - это удалил Console.WriteLine(“Hello World!”);, потому что он нам не понадобится для нашей программы.
Затем важно отметить, что нам не нужно иметь переменные для всех узлов в нашем графе, потому что, пока у нас есть способ добраться до корневого узла нашего дерева, связи между родителями и дочерними элементами должны иметь возможность добраться до каждого другого узла в дереве. Итак, я начал с создания переменной для хранения корневого узла в нашем дереве:
Не беспокойтесь о зеленой волнистой линии под root, она исчезнет через секунду.
Следующее, что нам нужно сделать с нашим деревом, - это добавить новые узлы. Итак, я вернулся к Node.cs, чтобы добавить функцию, которая позволила бы мне добавлять новые узлы в дерево.
Чтобы связать наш узел с деревом, нам нужно видеть дерево. Итак, нам нужно передать ссылку на корневой узел:
Первое, что я хочу сделать, это убедиться, что корень не пуст, потому что, если мы попытаемся сравнить значение нашего нового узла со значением корневого узла, но корневой узел пуст, мы получим ошибку. . Это проверяет очень простой оператор if. Я добавил Console.WriteLine(), чтобы, если моя программа выйдет из строя, я смогу понять, почему, просто посмотрев в консоль:
Забавный прием Visual Studio: если вы наберете буквы «CW» и дважды нажмете вкладку, синтаксис заполнится за вас, и вам просто нужно будет заполнить часть между круглыми скобками!
Следующее, что я хочу проверить, - это повторяющиеся значения. Деревья двоичного поиска становятся намного сложнее, если вы разрешаете дублирование значений, поэтому для целей этой программы мы не собираемся этого допускать.
Теперь нам нужно знать алгоритм добавления узлов к дереву. Допустим, у меня есть это дерево:
И я хочу добавить к нему Node 23. Мы начнем с верхнего узла и решим, принадлежит ли он левому или правому от него.
Поскольку 23 меньше 63, он принадлежит левой стороне.
На этом этапе мы можем игнорировать определенные части дерева. Мы знаем, что никогда не коснемся 63 или 82, потому что нет стрелок, указывающих на них с того места, где мы находимся. Единственный вариант - пойти туда, куда указывают стрелки, то есть вниз. Итак, мы можем игнорировать эти два узла и притвориться, что у нас есть новое дерево.
Новое дерево будет выглядеть примерно так:
Теперь мы можем сравнить 23 с 30.
Так как 23 меньше 30, идем налево.
Теперь мы можем повторить процесс игнорирования недоступных узлов.
Новое дерево - это всего лишь один узел:
Теперь мы должны решить, принадлежит ли оно левой или правой части 17. Поскольку 23 больше 17, оно принадлежит правой. Итак, перемещаем его туда, но сравнивать не с чем. Итак, вместо сравнения мы становимся узлом справа от 17.
Теперь дерево выглядит примерно так:
Чтобы реализовать это в нашем коде, мы переходим к нашей функции AddNode. На этом этапе кода у нас уже будет новый узел, расположенный наверху нашего графа. Наш первый шаг - решить, нужно ли новому узлу двигаться влево или вправо. Мы решаем это, сравнивая его с узлом, возле которого сидим. Итак, мы можем начать с добавления оболочки этих операторов if / else.
Следующий шаг - убедиться, что там есть узел, с которым можно его сравнить. Итак, давайте добавим это в:
Если сравнивать не с чем, значит, мы знаем, что это место на этом месте! Итак, добавим эту часть:
Ключевое слово this - это способ C # ссылаться на текущий объект, на который мы смотрим. Итак, в приведенном выше примере узел 23 был бы достигнут с помощью ключевого слова this.
Теперь это сложная часть. Если нам есть с чем сравнить новый узел, нам нужно повторить весь этот процесс, но мы не можем просто записать его снова, потому что мы не знаем, сколько раз нам нужно будет повторить этот процесс. Так что мы можем сделать….
Что ж, мы знаем, что если нам есть что сравнивать, мы можем игнорировать остальную часть дерева, которое мы уже прошли. Это похоже на новый корневой узел. Итак, что, если мы просто вызовем эту функцию еще раз и передадим новый корневой узел? Это называется рекурсией! Итак, добавим эту часть:
Давайте проверим это, вернувшись к Program.cs и добавив способ вызова!
Я знаю, что мне нужно добавить числа к этому дереву случайным образом, поэтому я собираюсь инициализировать новую случайную переменную. В C # это можно сделать так:
Я собираюсь написать for цикл. Цикл for по сути приказывает компьютеру повторять что-то определенное количество раз. Сейчас я хочу проделать это пять раз, поэтому мой цикл for выглядит так:
Забавный прием Visual Studio: если вы наберете "for" и дважды нажмете вкладку, он заполнит все за вас, и вам просто нужно изменить количество раз, которое вы хотите, чтобы это повторялось
Отсюда я могу добавлять новые узлы. Первое, что должно произойти, - это создать случайное число, которое я хочу добавить к дереву.
Я просто назвал свою переменную x и попросил ее выбрать случайное число от 0 до 100.
Следующее, что мы хотим сделать, - это создать узел, значение которого имеет "x":
Затем мы можем добавить n к графику, используя написанную нами функцию.
Однако у нас есть проблема. Обратите внимание, как root установлен в null, и мы передаем его в нашу функцию? Это проблема, потому что в нашей функции AddNode мы сказали, что если root равно null, ничего не делать. Этот код пять раз просто ничего не сделает! Итак, нам нужно добавить способ проверки, является ли root null, и если это так, то мы просто устанавливаем root на первый узел, который мы создаем. Это выглядит так:
Теперь наш код должен работать! Давайте попробуем, нажав эту кнопку воспроизведения:
Это результат, который я получил. Ваш будет другим, потому что мы использовали случайные числа:
Это означает, что мы пытались добавить к нашему дереву 40, 32, 43, 21 и 81. Чтение этого вывода не очень легко визуализирует график, но мы можем нарисовать его, чтобы увидеть, работает ли он!
Мы начали с пустого графа, а затем попытались добавить 40, которое устанавливается в корень дерева:
Затем мы пытаемся добавить 32, что меньше 40, поэтому оно идет влево:
Хороший! Вторая строка нашего вывода была правильной, мы добавили 32 слева от 40. Затем мы попытаемся добавить 43. 43 больше 40, поэтому оно идет вправо:
Это означает, что наша третья строка вывода была правильной! Далее идет 21, что меньше 40, поэтому мы идем налево. 21 меньше 32, поэтому мы идем и слева от него:
Наконец, мы пытаемся добавить 81. 81 больше 40, поэтому мы идем вправо. 81 также больше 43, поэтому мы добавим себя справа от 43:
Это означает, что последняя строка вывода была правильной! Идеально!
В следующий раз мы увидим, как удалять элементы из двоичного дерева поиска.
Спасибо за чтение!!
