Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Дерево

Автор: Самозванка 17.12.2008, 20:09

text    Parent_text    level LENTA                          1 BUDJ      LENTA            2 CIK        LENTA            2 OP         LENTA            2 DUMMY  LENTA            2 CIK1       CIK               3 CIK2       CIK               3 CIK3       CIK               3 OP1        OP                3 OP2        OP                3 CIK11    CIK1              4 CIK12    CIK1              4 CIK13    CIK1              4 Ну и так далее… Уровней вложенности может быть сколь угодно… Объясните как построить это дерево? Есть такой метод AddNode  В него мы передаем номер узла и text, а метод возвращает след. номер…. Ну и соответсвенно рисует сам узел… Грубо говоря передали 1, он вернул 2… Передавать Parent text в него нельзя… ну и выстраивает взаимосвязи между узлами, то есть если в него потом опять передать тот же номер, то он на тойже ветке строить будет, а если новый - то ниже перейдет) Я хотела делать цикл по этому табличке и потом по смене Parentteext пускать метод))) – это всё в одну папку хреначится тогда)

Автор: SoWa 17.12.2008, 21:30

Если я не ошибаюсь- каждый элемент поля text будет являться и предком, и потомком. Кроме первого элемента. Он не является потомком. То, что в поле Parent_text указывает на предка. Поэтому не вижу ничего сложного кроме реализации. Для твоего примера- поле Parent_text даже упорядочено. Поэтому делаем так: Код LENTA                          1 BUDJ      LENTA            2 CIK        LENTA            2 OP         LENTA            2 DUMMY  LENTA            2 CIK1       CIK               3 CIK2       CIK               3 CIK3       CIK               3 OP1        OP                3 OP2        OP                3 CIK11    CIK1              4 CIK12    CIK1              4 CIK13    CIK1              4 Ставим во главу дерева LENTA Далее ищем по полю Parent_text все поля, которые являются потомками Ленты. Выставляем их в дерево на второй уровень. Теперь начинаем просматривать каждый из этих 4 потомков, уже считая их предками. Ищем потомков для них- они имеют в поле Parent_text свое название, и при этом уровень вложености 3. Уровень вложенности более 3 не будем проверять, ибо иметь на 2 уровне потомка 4 и более уровня в принципе невозможно. Таким образом, мы выстроили еще одну горизонтальную линию дерева. И для нее повторяем операцию, лишь увеличив проверяемый уровень вложенности. А с вопросом реализации- это уже в раздел конкретного языка

Автор: Самозванка 17.12.2008, 21:55

SoWa, Это то я всё понимаю, спасибо, но тема в том... вот к примеру нашли мы все потомки Ленты... нам надо идти от каждого к след потомку.... Потому что метод стандартный AddNode работает так...  Первый раз для него передается "", для создания корневой папке... а потом он на выходе всегда получает key для следующего уровня...передаю туда Lenta  и ' ' - верхний уровень (на выходе 1), затем передаю след запись OP и 1(которую я при прошлом запуске метода получила) - получилось OP - вложенный раздел LENTA... То есть пусть я нашла все потомку Ленты и передала им key = 1, типа как след уровень... а теперь если нахожу для OP потомков, и передаю им key = 3, то они записываются в последнюю text потомков Ленты... вот как то так, а надо чтоб каждый в свой корень записался... нужна какая то хитроумная рекурсия видимо - не сообразить что то...

Автор: Romikgy 17.12.2008, 22:01

не сильно понятно с объяснением но я бы строил по уровнево  корневое потом все 1 уровня  потом все 2 уровня ... учитывая все вложености и т.д. можно еще рекурсией  построил 1 уровня элемент , есть ли у него 2 уровень есть строим 2 уровень есть ? да - строим 3 уровень .... , нет строим 2  уровень соселний если есть , нет 1 уровень соседний  и т.п.

Автор: Самозванка 17.12.2008, 22:03

Мы идем до 1 ого потомка Лента, далее сразу ищем потомка этого потомка, и так далее пока не найдем такого потомка, потом возвращаем к предыдущему потомку...и так далее.... блин как то так... но так как я это делаю по циклу, не понимаю как тут не запутаться. Помоги плиз структурировать мысль) Добавлено через 50 секунд Romikgy, да, именно так можно еще рекурсией  построил 1 уровня элемент , есть ли у него 2 уровень есть строим 2 уровень есть ? да - строим 3 уровень .... , нет строим 2  уровень соселний если есть , нет 1 уровень соседний  и т.п.

Автор: SoWa 17.12.2008, 22:16

Такс, кажется вкурил  Вся проблемма в возможностях твоей среды разработки. И значит, метод построчного построения неприемлим. Тогда надо строить поветочно. Итак. Есть предок. Главный батька такой. Ищем всех его потомков. Нашли. Круто! Не рвемся в бой и не добавляем всех сразу. Добавляем только одного. Ищем всех его потомков. Нашли. Круто! Не рвемся в бой и не добавляем всех сразу. Добавляем только одного. Ищем всех его потомков итд  Рекурсия, да, нужно, но я с ней не смогу помочь- я её не люблю и не умею ^_^ Судя по всему будет функция вида: Код Проверить элемент, строили мы для него дерево полностью(т.е. всех ли потомков мы уже воткнули в дерево, или нет) дальше или нет? (просто каждый элемент таблицы заносить в некий список "пройденных" элементов) Если строили: перейти к следующему элементу. Если не строили: найти всех потомков, не занесенных в дерево на данный момент. Обозначить связь с первым из них с помощью AddNode Вызвать функцию для него. Как-то так. Мб даже и понятно  Мне не очень, потому что, еще раз, не люблю рекурсию, но иногда надо.

Автор: Самозванка 17.12.2008, 22:18

SoWa, спасибо огромное, тебя люблю, а рекусрию видимо тоже теперь не люблю... фу..    Тему пока не закрываю, напишу точный алгоритм - отпишусь...

Автор: SoWa 17.12.2008, 22:24

Попробуй её почеркать на бумажке в виде квадратиков(кружочков, сердечек и пр.) и стрелочек  Станет понятнее, при каких условиях спускаться на уровень по дереву, а при каких подниматься.

Автор: Самозванка 18.12.2008, 12:57

Написала)) на ABAP... но думаю кому вдруг пригодится - поймут Код FORM get_level  using  lv_parent like FMHISV-parent_st                        ld_pfm_key type lvc_nkey.   data: lt_pfm_pr type FMHISV occurs 0 WITH HEADER LINE.   data: ln_pfm_key type lvc_nkey.   loop at gt_pfm_end where parent_st = lv_parent.     append gt_pfm_end to lt_pfm_pr.     clear gt_pfm_end.   endloop.     loop at lt_pfm_pr.       gs_pfm-fistl = lt_pfm_pr-fistl.       perform add_pfm_node using      gs_pfm                                   ld_pfm_key                          changing ln_pfm_key.       perform get_level using gs_pfm-fistl ln_pfm_key.       delete lt_pfm_pr.     endloop. ENDFORM.       И запускаем эту perform get_level  using space spaсе Я люблю рекурсию!

Автор: SoWa 18.12.2008, 13:02

Цитата(Самозванка @  18.12.2008,  12:57 ) на ABAP Застрелиться можно... Молодец

Автор: Фыва 21.12.2008, 00:58

Цитата(Самозванка @ 18.12.2008,  12:57) Я люблю рекурсию!   А рекурсия любит переполнение стэка   проверку на максимальный уровень вложенности поставьте хотя-бы.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)