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

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

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

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

Код C++ Создание динамического дерева ====================void Add (int x , Tree ** Node ) //В функцию принимается указатель на элемент данных и указатель на указатель на структуру, тип которой будет являться частью дерева ==================== В таком случае дерево будет разрастаться равномерно. На первом уровне один узел, на втором два, на третьем четыре, четвертом восемь и так далее. При этом информация не будет иметь каких-то признаков обработки. Мы инструктировали компилятор, чтобы он писал так, как мы пишем в тетрадках слева направо по чистым местам листов.

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

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

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

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

============================= /*ОБХОД В ПРЯМОМ ПОРЯДКЕ*/ void Show (Tree * Node )

/*СИММЕТРИЧНЫЙ ОБХОД*/ void Show (Tree * Node )

/*ОБРАТНЫЙ ОБХОД*/ void Show (Tree * Node ) ============================Нетрудно увидеть и понять разницу.

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

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

Код С++ Создание бинарного дерева Обход в прямом порядке ==============================#include //=====НАША СТРУКТУРА======== struct Tree ; //==============

/*ФУНКЦИЯ ДОБАВЛЕНИЯ ЗВЕНА В ДЕРЕВО*/ void Add (int x , Tree ** Node ) //В функцию принимается указатель на элемент данных и указатель на указатель на структуру

/*ОБХОД В ПРЯМОМ ПОРЯДКЕ*/ void Show (Tree * Node ) void main () ==================

Для закрепления приведу анимационные картинки прохода по дереву в трех вариантах. Намного лучше чем ничего и намного понятнее чем все воображать в голове. Как говорится: “Лучше один раз увидеть, чем сто раз услышать”