0 / 0 / 0
Регистрация: 22.05.2016
Сообщений: 4
|
||||||
1 | ||||||
Итератор дерева для обхода в ширину22.05.2016, 22:04. Показов 1262. Ответов 14
Задано дерево вида
0
|
22.05.2016, 22:04 | |
Ответы с готовыми решениями:
14
Печать на консоль бинарного дерева, обход в ширину Особый итератор словаря. Итератор возвращающий нужные комбинации Реализация обхода в ширину и глубину бинарного дерева Итератор для обхода по бинарному дереву |
Модератор
3051 / 2193 / 459
Регистрация: 26.03.2015
Сообщений: 8,469
|
|
22.05.2016, 22:34 | 2 |
Какое отношение к итератору имеет выделение памяти и "засовывание" в очередь?
0
|
0 / 0 / 0
Регистрация: 22.05.2016
Сообщений: 4
|
|
22.05.2016, 22:44 [ТС] | 3 |
Я имел в виду, что в итераторе будет храниться очередь узлов. Для дерева вида
1 2 3 4 5 6 7 когда итератор указывает на 1 и происходит операция ++ - в очередь заталкиваются 2 3, на следующем шаге из очереди достается 2 и заталкивается 4, 5. И так далее. Вопрос - существует ли возможность обойтись без очереди?
0
|
Модератор
3051 / 2193 / 459
Регистрация: 26.03.2015
Сообщений: 8,469
|
|
22.05.2016, 22:55 | 4 |
0
|
0 / 0 / 0
Регистрация: 22.05.2016
Сообщений: 4
|
|
22.05.2016, 22:57 [ТС] | 5 |
0
|
Модератор
3051 / 2193 / 459
Регистрация: 26.03.2015
Сообщений: 8,469
|
|
22.05.2016, 23:06 | 6 |
Навскидку.
Приоритеты (переходим к следующему пункту, если предыдущие возвращают пусто): 1. Следующий брат 2. Следующий "двоюродный" брат 3. Первый племянник (сын старшего брата) 4. Сын 5. Первый племянник (сын младшего брата) Я особо не продумывал. Мог ошибиться. Нужно тестировать.
0
|
0 / 0 / 0
Регистрация: 22.05.2016
Сообщений: 4
|
|
22.05.2016, 23:30 [ТС] | 7 |
ну тут понятно
Двоюродных может быть несколько, равно как и троюродные, четвероюродные итд тут вообще ничего не понял
0
|
Модератор
3051 / 2193 / 459
Регистрация: 26.03.2015
Сообщений: 8,469
|
|
23.05.2016, 00:11 | 8 |
Следующий один (или нет совсем).
Если следующего двоюродного нет, то следующий троюродный... и так далее. просто первый племянник (в широком смысле - первый сын первого сколь-угодно-родного брата)
0
|
90 / 87 / 11
Регистрация: 20.11.2008
Сообщений: 724
|
|
23.05.2016, 11:21 | 9 |
пусть есть функция, возвращающая следующего родного братаnextBrother(node)
пишем вспомогательные функции нахождение предка имеющего следующего родного брата Код
getBParent=function(node) local father=node local i=0 -- на сколько уровней поднялись repeat father=father.parent i=i+1 until (not father) or nextBrother(father) if not father then return -- нет такого else return father,i end end Код
getChild=function(node,i) repeat local n=node.sons.first -- node.sons[0] if not n then -- у node детей нет local b=nextBrother(node) if b then -- заменим его на следующего брата node=b else -- нет брата, обратимся к предкам local father,k=getBParent(node) if not father then -- у предков нет братьев return -- значит и нет подходящего ребёнка end node=father -- теперь будем искать ребёнка у этого предка i=i+k -- на этом уровне end else node=n i=i-1 end until i==0 or not node return node end НЕТ, ошибся, так не получится Код
next=function(node) local i=0 repeat if i==0 then local br=nextNode(node) if br then return br end else local ch=getChild(node,i) if ch then return ch end end local father,k=getBParent(node) if not father then return end i=i+k node=father until false end Добавлено через 11 минут так правильно функция возвращающая следующего по текущему уровню дерева будет такой Код
next=function(node) local i=0 repeat local br=nextNode(node) if br then if i==0 then return br else local ch=getChild(node,i) if ch then return ch end end end local father,k=getBParent(node) if not father then return end i=i+k node=father until false end опять правка Код
next=function(node) local i=0 repeat local br=nextNode(node) if br then if i==0 then return br else local ch=getChild(br,i) -- тут была ошибка if ch then return ch end end end local father,k=getBParent(node) if not father then return end i=i+k node=father until false end
0
|
Модератор
3051 / 2193 / 459
Регистрация: 26.03.2015
Сообщений: 8,469
|
|
23.05.2016, 12:06 | 10 |
Пара замечаний:
Для того, чтобы получить следующий узел, нам придётся пройти по дереву весь путь от текущего узла до следующего. В худшем случае этот путь может оказаться 2L, где L - высота дерева. А с учётом "холостых" пробегов к несуществующим более близким родственникам получается O(L2) в худшем случае. Для хранения детей лучше использовать не вектор, а связанный список. При использовании вектора получение следующего ребёнка стоит O(m), где m - "арность" дерева (сначала нужно перейти к родителю и найти текущий элемент в списке его детей).
0
|
90 / 87 / 11
Регистрация: 20.11.2008
Сообщений: 724
|
|
23.05.2016, 13:13 | 11 |
Shamil1, так ведь ТС хотел уменьшить использование памяти, поэтому я предложил вариант без массивов и рекурсии
И тогда я не понимаю, что вы имели ввиду, когда говорили
0
|
Модератор
3051 / 2193 / 459
Регистрация: 26.03.2015
Сообщений: 8,469
|
|
23.05.2016, 13:46 | 12 |
Именно это и имел ввиду - код, который тратит O(L2) на получение следующего узла.
Мои замечания относятся в первую очередь к моим сообщениям. (Хотя, насколько я понял, Ваш код делает примерно то же самое).
0
|
24.05.2016, 15:04 | 13 |
Evgenii_I, в общем случае деревья не могут иметь итератор в терминологии STL из-за неопределенности концепции "следующего" элемента дерева. В этом легко убедиться хотя бы раз пройдя по дереву и осознав, что это нелинейная операция в плане исполнения поскольку можно идти вниз как направо так и налево. Распространенный подход, если действительно нужен итератор такого вида, заключается в обходе всего дерева слева направо. В таком виде в роли begin() выступает крайний левый узел, а в роли end() -- специальный узел над корнем. Такое например реализовано для красно-черного дерева здесь: http://www.sgi.com/tech/stl/stl_tree.h
0
|
ProgJ
|
24.05.2016, 15:47
#14
|
0
|
HighPredator
|
24.05.2016, 15:51
Итератор дерева для обхода в ширину
#15
|
0
|
24.05.2016, 15:51 | |
Итератор для бинарного дерева Процедура обхода для дерева Процедура обхода для дерева Итератор для бинарного дерева поиска. Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |