:: Игры Разума
Обход древовидной структуры
Extortioner
Автор

Сообщений: 854
Откуда: Новосибирск
Дата регистрации: 06.10.2005
Добрый день, не могу задачку решить - вроде бы крутится решение поблизости, а ухватиться не могу.
Суть такая есть табличка (tbl_structure) содержащая древовидную структуру вида Газета\рубрика\подрубрика\итд
id_st - идентификатор структуры
parent_id - ид. родителя (для газеты он null)
st_name - название структуры
n_order - порядок сортировки среди потомков одного узла

И есть табличка объявлений очень упрощённо можно представить её так (tbl_ann_txt)
id_st - ид. структуры к которой принадлежит объявление
text_ann - сам текст объявления
Все остальные поля в данном контексте (номер газеты, тип объявления итп несущественны)

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

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



Исправлено 1 раз(а). Последнее : Extortioner, 11.01.11 20:18
Ratings: 0 negative/0 positive
Re: Обход древовидной структуры
PaulWist

Сообщений: 14601
Дата регистрации: 01.04.2004
Надо сохранять дерево в "правильном" виде (недавно "мучился").


------------------
Есть многое на свете, друг Горацио...
Что и не снилось нашим мудрецам.
(В.Шекспир Гамлет)
Ratings: 0 negative/0 positive
Re: Обход древовидной структуры
Extortioner
Автор

Сообщений: 854
Откуда: Новосибирск
Дата регистрации: 06.10.2005
А в каком "Правильном"? Матрицу смежности рисовать что-ли?
Ratings: 0 negative/0 positive
Re: Обход древовидной структуры
Igor Korolyov

Сообщений: 34580
Дата регистрации: 28.05.2002
Нормальная структура, зря придираешься.
Касаемо задачи - вообще-то без разницы откуда начинается обход - с узла с parent_id=null или с любого другого.
Вариантов обхода масса - от чистой рекурсии (вызов метода/процедуры для начального узла, а уже из самого этого метода идёт рекурсивный вызов для каждого непосредственного потомка) до предварительного наполнения "плоского" курсора или массива (т.е. цикл добавляющий на каждом шаге очередной уровень - используя данные предыдущего шага - пока идёт рост выходного массива). Рекурсия тут лучше тем, что позволит по простому сортировать каждый уровень (ибо обрабатываются за 1 шаг только узлы одного "родителя"). В больших СУБД есть специальные средства для разузлования - в т.ч. и хитрый order by позволяющий сортировать результат в рамках иерархии (не перемешивая разные ветки).


------------------
WBR, Igor
Ratings: 0 negative/0 positive


Извините, только зарегистрированные пользователи могут оставлять сообщения в этом форуме.

On-line: 2 (Гостей: 2)

© 2000-2024 Fox Club 
Яндекс.Метрика