C++ для начинающих Динамические деревья Обходы

Дерево, дерево, дерево… Что за деревья такие, как же понять. Я на такое вообще способен? Такие мысли могут появляться у начинающих программистов. Хорошо когда знаешь английский, а когда не знаешь, то программистам труднее. Я вот не знаю и мне приходится крупицами искать материалы. Но эти крупицы есть! Так с миру по нитке получаются статьи этого блога.

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

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

Вот например так: С++ Дерево

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

Код C++ Создание динамического дерева

В таком случае дерево будет разрастаться равномерно. На первом уровне один узел, на втором два, на третьем четыре, четвертом восемь и так далее. При этом информация не будет иметь каких-то признаков обработки. Мы инструктировали компилятор, чтобы он писал так, как мы пишем в тетрадках слева направо по чистым местам листов. Это проиллюстрировано рисунком выше.

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

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

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

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

Для того чтоб описать функции обхода деревьев, я покажу их кодом. Предполагается, что обход дерева — это функция отображения дерева, поэтому опишу внутри функции.

Нетрудно увидеть и понять разницу.

Есть еще обход в ширину, в котором узлы посещаются уровень за уровнем(N-й уровень дерева — множество узлов с высотой N). Каждый уровень обходится слева направо.
Для реализации используется структура queue — очередь с методами (поставить в очередь, взять из очереди, проверка очереди на пустоту)

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

Код С++ Создание бинарного дерева Обход в прямом порядке

============

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

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

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Поиск

 
     

Случайная книга в электронном формате

https://www.litres.ru/valeriy-laptev/c-ekspress-kurs/?lfrom=15589587
Яндекс.Метрика