Как изобразить двоичное дерево в текстовом процессоре

Обновлено: 07.07.2024

Разработчик нанимается небольшим городом населением в сто тысяч. Задача состоит в том, чтобы преобразовать бумажную телефонную книгу в цифровой вариант. У мэра города есть одно требование для проекта: цифровая 📖 телефонная книга должна иметь возможность 🔍 находить номера телефонов на ⚡ молниеносных скоростях.

Вариант A:

Один логический подход для поиска номеров т е лефонов начнётся с начала телефонной книги. Затем произойдёт проверка страницы на содержание желаемого номера телефона. Если номер на странице не найден, то страница пролистывается и попытка повторяется. Попытки будут продолжаться до тех пор, пока желаемый номер не будет найден.

Этот подход работает, но также требует посещения всех страниц от начала книги и до нужного номера телефона. В информатике это будет сопоставимо с размещением телефонных номеров в связанном списке и поиском от главы списка. Представьте себе, если желаемый номер телефона находится в середине телефонной книги города. Это означает, что для поиска нужного номера страницу пролистают пятьдесят тысяч раз, и никто на самом деле не делает это с реальной или цифровой телефонной книгой.

Вариант Б:

Что же делается обычно? Обычно мы открываем телефонную книгу где-то рядом с серединой и спрашиваем себя: «желаемый номер меньше или больше, чем номер телефона на этой странице?» Если желаемый номер меньше, несколько страниц пролистывается влево. Если желаемый номер больше, несколько страниц пролистывается вправо, а затем снова проверяется. На каждой итерации поиск становится значительно уже. В информатике этот метод был бы сопоставим с размещением телефонных номеров в двоичном дереве и поиском из корня дерева.

Обычно, при использовании двоичного дерева, из ста тысяч телефонных номеров можно найти желаемый примерно за шестнадцать шагов. Вот почему двоичное дерево обеспечивает управляемый подход к поиску значений.

Двоичное дерево представляет собой набор объектов, которые соединены с помощью левого и правого указателей. Каждое соединение, будь то слева или справа, основывается на двоичном сравнении.

Если в дереве нет узлов, входящий узел становится корнем дерева. В приведенном выше примере корнем является десятка. Теперь обратите внимание на узел слева от корня — пять. Пять — меньше десяти. Идём на один уровень ниже. Обратите внимание на узел справа от пяти — семь. Семь больше пяти, но также семь меньше десяти. Семь была размещена слева от десяти и справа от пяти. Это двоичное размещение создает очень специфическое подмножество. Давайте подробнее рассмотрим, что именно делает бинарное дерево.

Допустим, инженер искал значение восемь в дереве ниже.

Код инженера сначала бы сравнил желаемое значение — восемь с корневым значением — десять. Восемь меньше десяти, поэтому программа будет переходить влево. Другими словами, значение восьмерки никогда не будет в правом поддереве. Зная, что восемь никогда не будет в правом поддереве, инженер сможет исключить половину вероятностей.

На следующей итерации восемь будут сравниваться со значением пять, но так как восемь больше пяти, то в этот раз программа перейдёт вправо. Другими словами, теперь значение восьмерки никогда не будет в левом поддереве. После этого второго перехода инженер снова исключает половину дерева. Смотрите ниже.

На третьей итерации восемь сравнивается со значением — семь. Поскольку восемь больше семи, алгоритм снова перейдёт вправо, и еще раз половина оставшихся вероятностей исключается.

Теперь восьмёрка находится на уровне третьего листа. Значение — восемь сравнивается со значением узла и, наконец, находит эквивалентное значение. Теперь алгоритм достиг нужного узла.

Создайте двоичное дерево, используя это веб-приложение.

Теперь давайте построим двоичное дерево 🌲. Затем мы проверим это дерево и посчитаем, как ⌛ много времени нужно коду для того, чтобы найти необходимое значение в ста тысячах узлов дерева.

Начнем со структуры узлов.

В структуре узлов имеется переменная с целым числом val, которое хранит значение с номером телефона. Далее структура определяет два указателя слева и справа для значений, которые меньше или больше, чем данный узел. Наконец, объявляется конструктор, который будет заниматься передачей значений к узлу. Обратите внимание, что конструктор также инициализирует левый (left) и правый (right) указатели нулями.

Теперь давайте представим макет для класса BinaryTree.

Приватная часть класса содержит: структуру узла, указатель узла на корень (root) и перегруженную функцию вывода.

Публичный раздел класса содержит: функции для добавления узлов, поиска узлов, вывода узлов и конструктора классов.

Обратите внимание, что функция публичного вывода не принимает параметры, в отличие от приватной функции вывода.

Класс BinaryTree (макет):

Теперь давайте сосредоточимся на функции добавления узла, используя итеративный подход.

Сначала код проверяет, есть ли root. Если его нет, то создаётся новый узел, который присваивается к root. В ином случае начинается проход по дереву с указателем узла walker.

Следующим шагом будет проверка: входящее значение меньше или больше значения walker? Если значение меньше, то что-то произойдет на левой ветке. Если значение больше, что-то произойдет на правой ветви.

Что именно происходит, если значение меньше? Сначала мы проверим, указывает ли walker left на другой узел или указывает на null. Если walker left указывает на другой узел, происходит обновление walker до значения walker left и процесс повторяется. В противном случае walker left указывает на null, а это означает, что алгоритм достиг конца дерева. Достижение конечной части дерева также означает, что пришло время добавить новый узел для walker left.

Такой же шаблон применяется к правой ветви, но теперь входящее значение должно быть больше, чем значение walker. Сначала мы проверяем указывает ли walker right на другой узел или указывает на null. Если walker right указывает на другой узел, происходит обновление walker для указывания на walker right и начинается новая итерация. В ином случае walker right указывает на null, а это значит, что алгоритм готов добавить новый узел в нижней части дерева, поэтому происходит установка нового узла вwalker right.

Вдобавок, каждый раз, когда новый узел присоединяется к дереву, мы будем устанавливать указатель узла walker в значение null, чтобы индицировать конец цикла while и в этом же ходу покинуть функцию добавления узла.

Отлично, перейдём к функции подсчёта количества узлов.

Эта функция считает сколько итераций алгоритм предпримет, чтобы найти любой желаемый узел в дереве.

Начните с объявления переменной count для подсчета каждой итерации. Затем установите значение для указателя узла walker = root. В то время как узел wlaker ищет дерево. Теперь проверьте, совпадают ли значение ходока (walker) и требуемое входное значение. Если совпадают, значит номер найден и пора вернуть значение счётчика. В ином случае пусть троичный оператор определит следующий ход walker’а и счетчик инкрементов.

Наконец, если ходок доходит до конца, то значение walker становится null. Это означает, что желаемый узел не находится в дереве, поэтому возвращаемое значение отрицательно.

Публичный метод вывода вызывает приватный метод вывода. Это делается для того, чтобы приватный метод вывода мог рекурсивно сканировать дерево. Этот метод известен как упорядоченный перебор.

public print function:

public print function

Наконец, конструктор для инициализации root значением null.

Теперь разместите сто тысяч узлов в двоичном древе и протестируйте возможности дерева.

Тестирование включает в себя следующее: добавьте в двоичное дерево сто тысяч случайных телефонных номеров, выберите для поиска случайный номер, выведите дерево, а затем найдите случайно выбранный номер.

Скопируйте код в текстовый редактор и сохраните как main.cpp
Скомпилируйте из командной строки, g++ main.cpp -std=c++11 -o bt.exe
Затем выполните код из командной строки ./bt.exe

После компиляции и выполняя исходного кода программа сгенерирует двоичное дерево 🎉 и выведет количество обходов, необходимых для поиска узла.

В этой статье рассмотрим двоичное дерево, как оно строится и варианты обходов.

Двоичное дерево в первую очередь дерево. В программировании – структура данных, которая имеет корень и дочерние узлы, без циклических связей. Если рассмотреть отдельно любой узел с дочерними элементами, то получится тоже дерево. Узел называется внутренним, если имеет хотя бы одно поддерево. Cамые нижние элементы, которые не имеют дочерних элементов, называются листами или листовыми узлами.

Дерево обычно рисуется сверху вниз.

В узлах может храниться любая информация, от примитивных типов до объектов. В этой статье, мы рассмотрим реализацию, когда в узле также хранятся ссылки на дочерние элементы. Кроме такого подхода, возможен альтернативный подход для двоичного дерева — хранение в массиве.

Cube Dev , Удалённо , От 8000 $

Первая особенность двоичного дерева, что любой узел не может иметь более двух детей. Их называют просто — левый и правый потомок, или левое и правое поддерево.

Вторая особенность двоичного дерева, и основное правило его построения, заключается в том что левый потомок меньше текущего узла, а правый потомок больше. Отношение больше/меньше имеет смысл для сравниваемых объектов, например числа, строки, если в дереве содержатся сложные объекты, то для них берётся какая-нибудь процедура сравнения, и она будет отрабатывать при всех операциях работы с деревом.

Создание дерева, вставка

Рассмотрим существующее двоичное дерево. Корень содержит число 3, все узлы в левом поддереве меньше текущего, в правом — больше. Такие же правила действуют для любого рассматриваемого узла и его поддеревьев.

Попробуем вставить в это дерево элемент -1.

Из корня идем в левое поддерево, так как -1 меньше 3. Из узла со значением 1 также идём в левое поддерево. Но в этом узле левое поддерево отсутствует, вставляем в эту позицию элемент, создавая новый узел дерева.

Вставим в получившееся дерево элемент 3.5.

Проходим по дереву, сравнивая на каждом из этапов вставляемое значение с элементом в узле, пока не дойдем до узла, в котором следующий узел для сравнения отсутствует, в эту позицию и вставляем новый узел.

Если дерево не существует, то есть root равен null, то элемент вставляется в корень, после этого проводится вставка по описанному выше алгоритму.

Напишем класс для создания двоичного дерева:

На скриншоте ниже то, какую информацию хранит в себе binaryTree :

Обход

Рассмотрим несколько алгоритмов обхода/поиска элементов в двоичном дереве.

Мы можем спускаться по дереву, в каждом из узлов есть выбор куда можем пойти в первую очередь и какой из элементов обработать сначала: левое поддерево, корень или право поддерево. Такие варианты обхода называются обходы в глубину (depth first).

Какие возможны варианты обхода (слово поддерево опустим):

корень, левое, правое (preorder, прямой);
корень, правое, левое;
левое, корень, правое (inorder, симметричный, центрированный);
левое, правое, корень (postorder, обратный);
правое, корень, левое;
правое, левое, корень.

Также используется вариант для обхода деревьев по уровням. Уровень в дереве — его удалённость от корня. Сначала обходится корень, после этого узлы первого уровня и так далее. Называется обход в ширину, по уровням, breadth first, BFS — breadth first search или level order traversal.

Выбирается один из этих вариантов, и делается обход, в каждом из узлов применяя выбранную стратегию.

Обычно для обходов в глубину применяется рекурсия. Реализуем один из вариантов, например симметричный: левое поддерево, корень, правое поддерево.

При этом мы обработаем первым самый левый узел, где левое поддерево окажется пустым, но правое может присутствовать. То есть в каждом из узлов будем спускаться ниже и ниже, пока левое поддерево не окажется пустым.

Для реализации других вариантов обхода просто меняем порядок вызова функций в функции _inorderInternal . И нужно не забыть переименовать функцию, чтобы название соответствовало содержимому.

Рассмотрим inorder алгоритм обхода на примере дерева, созданного в предыдущем блоке кода.

Сначала мы спустимся в самое левое поддерево — узел -1. Зайдем в его левое поддерево, которого нет, первая конструкция выполнится, ничего не сделав внутри функции. Вызовется обработчик handlerFunction , на узле -1. После этого произойдёт попытка войти в правое поддерево, которого нет. Работа функции для узла -1 завершится.

В вызов для узла -1 мы пришли через вызов функции _inorderInternal для левого поддерева узла 1. Вызов для левого поддерева -1 завершился, вызовется обработчик для значения узла 1, после этого — для правого поддерева. Правого поддерева нет, функция для узла 1 заканчивает работу. Выходим в обработчик для корня дерева.

Для корня дерева левое поддерево полностью отработало, происходит переход ко второй строке процедуры обхода — вызов обработчика значения узла. После чего вызов функции для обработчика правого поддерева.

Аналогично продолжая рассуждения, и запоминая на какой строке для определенного узла мы вошли в рекурсивный вызов, можем пройти алгоритм «руками», лучше понимая его работу.

Для обходов в ширину используется дополнительный массив.

Поиск

Операция поиска — вернуть true или false, в зависимости от того, содержится элемент в дереве или нет. Может быть реализована на основе поиска в глубину или ширину, посмотрим на реализацию на основе алгоритма обхода в глубину.

Функция сравнения или получение ключа

До этого мы рассматривали простые данные, для которых определена операция сравнения между ключами. Не всегда возможно реализовать сравнение таким простым образом.

Можно сделать функцию, которая будет получать ключ из данных, которые хранятся в узле.

Можно передать в конструктор специальную функцию сравнения. Эту функцию можно сделать как обычно делают функции сравнения в программировании, возвращать 0, если ключи равны. Значение больше нуля, если первый переданный объект больше второго, и меньше нуля если меньше. Важно не перепутать когда что возвращается и правильно передать параметры. Например, текущий узел, уже существующий в дереве, первым параметром, а тот, с которым производится текущая операция — вторым.

Для реализации такой возможности потребуется во всех местах сравнения использовать эту функцию

Заключение

Мы познакомились с концепцией двоичных деревьев и операциями для создания такого типа дерева. Эти операции интуитивно понятны, в следующей статье рассмотрим процедуру удаления и скорость работы двоичного дерева.

Двоичное дерево — древовидная структура данных, в которой у родительских узлов не может быть больше двух детей.

Типы двоичных деревьев

Полное двоичное дерево

Полное двоичное дерево — особый тип бинарных деревьев, в котором у каждого узла либо 0 потомков, либо 2.

Совершенное двоичное дерево

Совершенное двоичное дерево — особый тип бинарного дерева, в котором у каждого внутреннего узла по два ребенка, а листовые вершины находятся на одном уровне.

Законченное двоичное дерево

Законченное двоичное дерево похоже на совершенное, но есть три большие отличия.

Все уровни должны быть заполнены.
Все листовые вершины склоняются влево.
У последней листовой вершины может не быть правого собрата. Это значит, что завершенное дерево необязательно полное.

Вырожденное двоичное дерево

Вырожденное двоичное дерево — дерево, в котором на каждый уровень приходится по одной вершине.

Скошенное вырожденное дерево

Скошенное вырожденное дерево — вырожденное дерево, в котором есть либо только левые, либо только правые узлы. Таким образом, есть два типа скошенных деревьев — скошенные влево вырожденные деревья и скошенные вправо вырожденные деревья.

Сбалансированное двоичное дерево

Сбалансированное двоичное дерево — тип бинарного дерева, в котором у каждой вершины количество вершин в левом и правом поддереве различаются либо на 0, либо на 1.

Представление двоичного дерева

Узел двоичного дерева можно представить структурой, содержащей данные и два указателя на другие структуры того же типа.

Узнайте, как распечатать двоичную древовидную диаграмму.

1. введение

В этом уроке мы изучим некоторые методы печати двоичных деревьев в Java.

2. Древовидные диаграммы

Несмотря на ограничения рисования только символами на консоли, существует множество различных форм диаграмм для представления древовидных структур. Выбор одного из них в основном зависит от размера и баланса дерева.

Давайте рассмотрим некоторые из возможных типов диаграмм, которые мы можем распечатать:

Но мы объясним практический вариант, который также легче реализовать. Принимая во внимание направление, в котором растет дерево, мы можем назвать его горизонтальным деревом :

Поскольку горизонтальное дерево всегда течет в том же направлении , что и текст , у нас есть некоторые преимущества в выборе горизонтальной диаграммы по сравнению с другими:

Мы также можем визуализировать большие и несбалансированные деревья
Длина значений узлов не влияет на структуру отображения
Это гораздо проще реализовать

Поэтому мы перейдем к горизонтальной диаграмме и реализуем простой класс принтера двоичного дерева в следующих разделах.

3. Модель бинарного дерева

Прежде всего, мы должны смоделировать базовое двоичное дерево, которое мы можем сделать всего с помощью нескольких строк кода.

Давайте определим простую Модель бинарного дерева класс:

4. Данные Выборочных Испытаний

Прежде чем мы начнем внедрять принтер с двоичным деревом, нам необходимо создать некоторые примеры данных для постепенного тестирования нашей визуализации:

5. Принтер двоичного дерева

Конечно, нам нужен отдельный класс, чтобы сохранить нашу Модель бинарного дерева чистой ради Принципа единой ответственности .

Теперь мы могли бы использовать шаблон посетителя, чтобы дерево обрабатывало иерархию, а наш принтер просто обрабатывал печать. Но для этого урока мы будем держать их вместе, чтобы все было просто.

Таким образом, мы определяем класс с именем Binary Tree Printer и начинаем его реализацию.

5.1. Обход Предварительного заказа

Учитывая нашу горизонтальную диаграмму, чтобы правильно ее распечатать, мы можем начать с простого использования предварительного заказа обхода.

Следовательно, для выполнения обхода предварительного заказа нам необходимо реализовать рекурсивный метод, который сначала посещает корневой узел, затем левое поддерево и, наконец, правое поддерево.

Давайте определим метод обхода нашего дерева:

Далее, давайте определим наш метод печати:

Таким образом, мы можем просто распечатать наше тестовое дерево:

Результатом будет список узлов дерева в пройденном порядке:

5.2. Добавление ребер Дерева

Давайте обновим наш метод traversePreOrder , добавим два параметра в качестве заполнения и указателя и будем использовать символы соответственно:

Кроме того, мы также обновляем print метод:

Итак, давайте снова протестируем наш Принтер двоичного дерева :

Таким образом, со всеми дополнениями и указателями наша диаграмма сложилась красиво.

Тем не менее, у нас все еще есть несколько дополнительных строк, от которых нужно избавиться:

Когда мы смотрим на диаграмму, все еще есть символы в трех неправильных местах:

Столбец дополнительных строк под корневым узлом
Дополнительные строки под правым поддеревом
Дополнительные строки под левым поддеревом, у которого нет правого родного брата

5.3. Различные реализации для корневых и дочерних узлов

Давайте настроим traversePreOrder только для корневого узла:

Затем мы создадим еще один метод для дочерних узлов в виде traverseNodes. A кроме того, мы добавим новый параметр имеет правильный брат для правильной реализации предыдущих строк:

Кроме того, нам нужно небольшое изменение в нашем методе print :

Наконец, наша диаграмма сформировалась в красивую форму с чистым выводом:

6. Заключение

В этой статье мы узнали простой и практичный способ распечатать двоичное дерево в Java .

Все примеры этой статьи и дополнительные тестовые примеры доступны на GitHub .

Читайте также: