Обход древовидной структуры | |
---|---|
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 |
Re: Обход древовидной структуры | |
---|---|
PaulWist Сообщений: 14621 Дата регистрации: 01.04.2004 |
Надо сохранять дерево в "правильном" виде (недавно "мучился").
------------------ Есть многое на свете, друг Горацио... Что и не снилось нашим мудрецам. (В.Шекспир Гамлет) |
Re: Обход древовидной структуры | |
---|---|
Extortioner Автор Сообщений: 854 Откуда: Новосибирск Дата регистрации: 06.10.2005 |
А в каком "Правильном"? Матрицу смежности рисовать что-ли?
|
Re: Обход древовидной структуры | |
---|---|
Igor Korolyov Сообщений: 34580 Дата регистрации: 28.05.2002 |
Нормальная структура, зря придираешься.
Касаемо задачи - вообще-то без разницы откуда начинается обход - с узла с parent_id=null или с любого другого. Вариантов обхода масса - от чистой рекурсии (вызов метода/процедуры для начального узла, а уже из самого этого метода идёт рекурсивный вызов для каждого непосредственного потомка) до предварительного наполнения "плоского" курсора или массива (т.е. цикл добавляющий на каждом шаге очередной уровень - используя данные предыдущего шага - пока идёт рост выходного массива). Рекурсия тут лучше тем, что позволит по простому сортировать каждый уровень (ибо обрабатываются за 1 шаг только узлы одного "родителя"). В больших СУБД есть специальные средства для разузлования - в т.ч. и хитрый order by позволяющий сортировать результат в рамках иерархии (не перемешивая разные ветки). ------------------ WBR, Igor |
© 2000-2024 Fox Club  |