Реализация дерева поиска список сыновей

Добрый день.
Нужно создать 2-а дерева поиска и хранить их "списком сыновей". В нужно вставить в А используя обратных обход. И вывести результат - А выводить прямым обходом, а В симметричным. Требуется реализовать начальное формирование деревьев А и В, путем добавления некоторой последовательности значений (узлов) в пустое дерево. После чего требуется реализовать заданную операцию над деревьями без использования каких-либо вспомогательных структур (списков, массивов и т.п.), работая только с узлами деревьев А и В. (Не знаю как можно отказаться от списков, если в них храниться структура дерева).

Что такое "список сыновей" я представляю, все как описано на 2-ой миниатюре, но как это реализовать на С++?

Миниатюры

   

1

Сообщение от Bonttpol Скорее всего, это дополнительные указатели в структуре node.

Bonttpol, - нет. У меня тоже вначале была такая мысль, - использовать ноды и их указатели на ноды, то есть каждый нод можно было left'ом связать со следующим в корневом списке, а right'ом со следующим в уровне. Это были бы ноды уже другой структуры и связь с деревом была бы утеряна. То есть такой список (списков) содержал бы ноды с копиями ключей и указателями на ноды (left, right), переустановленными для поддержания новой структуры. noode_root можно оставить указателем на начало. Это возможный вариант, но я думаю, дерево лучше не трогать. Список сыновей как структурированный набор указателей на дерево, гораздо интереснее (имхо). Во-первых, если данные это не целые числа (key), а объекты тяжелого (по размеру объекта) класса, то копирование таких структур не в радость. Во вторых, выбрав вектор, std::array или любую другую структуру произвольного доступа, Вы получаете логарифмическое время поиска. Кроме того, такая структура гарантирует последовательное размещение, то есть вероятность получить данные часть из которых размещена за пределами кэша данного ядра ничтожна.
Bonttpol, мне эта тема близка и Вы можете (когда будет время и силы) ознакомиться с моей статейкой в блоге:
https://www.cyberforum.ru/blog... g4772.html
Тут всё очень похоже, но (имхо), просто, лучше. Кроме всего оно уникально быстро работает на данных с большим количеством повторов. То есть, если есть задача, находить интервалы повторов (где количества объектов в повторах - тысячи и более), то можно локализовать такие участки, находя начало и конец, за практически, логарифмическое время.
ps
посмотрите мой пост выше, там всё сделано на списке списков

0

Bonttpol, хотелось бы посмотреть на готовый код, если вы всё-таки его осилили. Буду благодарен

0

Сообщение от БесподобeH Bonttpol, хотелось бы посмотреть на готовый код, если вы всё-таки его осилили. Буду благодарен

Тема не для "списывания". Это же не задача в кулинарном техникуме. Тут всё похоже на задачу профилированного под программирование факультета. И вопрос о списке сыновей сам по себе интересен.
БесподобeH, как вы думаете. Зачем нужно список сыновей?

0

вы все поняли????

0

Сообщение от shoker12397 вы все поняли????

Допускаю, что два года назад все всё поняли, кроме, возможно, товарища из поста #22.

1

Сообщение от lemegeton Допускаю, что два года назад все всё поняли, кроме, возможно, товарища из поста #22.

Одно из возможных применений такого списка, - сериализация. Когда разраба интересует мгновенное состояние дерева в какой-то момент времени, это нужно документировать каким-то образом. То есть, можно отразить дерево в линейную структуру. Мне не приходилось этого делать, но думаю, решение вполне очевидно. Хотя есть варианты)
Вот пример описания где пара сыновей представляет список (для бинарного дерева).
http://wwwcdl.bmstu.ru/iu7/book1/stage7.htm

1