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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Все комментарии на сайте проверяются, поэтому ваш комментарий может появиться не сразу. Для вставки кода в комментарий используйте теги: [php]ВАШ_КОД[/php]

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

  • RaZzor говорит:

    Хмм.. Не могу понять, каким образом после добавления корня дерева, и создания левого и правого потомка происходит поуровневое заполнение. Как сказать программе, что сначала надо заполнить левой/правый узел от потомка а затем перейти на соседнего потомка…
    Из приведенного кода это не совсем ясно, хотя что-то подсказывает что дело в рекурсии.
    У меня это не получается реализовать.
    И что означают подобные записи Tree **Node(к чему сразу 2 указателя?) и Add(x,&MyTree) (можно как-то по-другому сказать, что x нужно записать в MyTree?)

    Автор сайта отвечает:
    Я не смогу ответить на ваши вопросы полностью и очень хорошо, но на часть ответить попробую
    1) Поуровневое заполнение происходит приблизительно так
    Вы ввели элемент, потом функция добавления начинает проверку этого элемента на какое-то определенное вами условие. В моем случае проверку (меньше ли веденный элемент чем текущий элемента из дерева) это строка 21. После проверки функция определяет в каком направлении двигать элемент. Таким образом получается своеобразный маршрут для каждого нового элемента.
    2) Да. Здесь нужно хорошо понимать рекурсию. Здесь Функция добавления является рекурсивной функцией. Элемент будет двигаться до тех пор, пока не залезет в пустую ячейку.
    3) Здесь приведен код получения Бинарного упорядоченного дерева, а на рисунках Простая нумерация НЕ такого дерева. Такая нумерация для того, чтоб было видно в каком порядке получается обход
    4) Tree **Node — Два указателя потому что надо передать указатель в функцию, да еще таким образом, чтобы все изменения чего-то функцией не отвалились после завершения работы функции
    5) Add(x,&MyTree) = x нужно записать в MyTree. Ссылка здесь только потому что параметр функции это указатель на указатель. Чтобы понимать 4 и 5 нужно хорошо разбираться в передачах параметров в функции.
    =======================
    вот то немногое, что я могу пояснить.
     
    Самый первый (верхний) Код C++ Создание динамического дерева 14 строк там
    Создает такое дерево, которое на рисунках

    Спасибо, стало немного яснее.
    Вот здесь есть еще дерево ci-plus-plus-snachala.ru/?p=89. И по нему у меня тоже вопрос, для чего в функции Print введена переменная u?

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

    Вот как-то так

    Т.е. что-то вроде представления уровня от корня на котором находится элемент?

    Автор сайта отвечает:
    да

  • артур говорит:

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

    Автор сайта отвечает:
    Да. Есть тут ошибка и похоже, что их тут много. Наверное придется все переписывать. Где ж вы раньше-то были, Артур?))
    Много народу их видело и все молчали, блин.
    ====================
    Будет время, займусь. Сейчас ближайшее время не могу все быстро и максимально грамотно исправить.
     
    Исправлено

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

Ваш e-mail не будет опубликован.

Поиск

 
     
Яндекс.Метрика

НАГРАДИ АВТОРА САЙТА
WEBMONEY
R375024497470
U251140483387
Z301246203264
E149319127674

Встречает в аду один черт другого и говорит: "Слушай, это ты того компьютерщика сюда притащил?" - "Да, а что?" - "Ты в другой раз толком объясняй, что такое ад - а то он, пока понял, что это не Doom, двести чертей перестрелял..."

Выражаю свою признательность

  • Максиму очень признателен за указание на мои ошибки и неточности.
  • Sergio ===> за оказание помощи в исправлении моих ошибок
  • Gen ===> за правильное стремление помочь другим новичкам и выявления моих ошибок