Форум: "Прочее";
Текущий архив: 2007.10.07;
Скачать: [xml.tar.bz2];
ВнизНесложная задачка Найти похожие ветки
← →
Jeer © (2007-09-07 14:58) [0]Задачка не сложная и сочтем ее за пятничную:
Существовало "ветвистое" дерево с одним корнем.
Перед его уничтожением был предпринят рекурсивный обход от корня вверх и справа (или слева).
В результате было "посажен" тростник, т.е. линейный список блоков, представляющих описание узлов дерева
и в каждом блоке Block есть свойство Level, определяющее уровень блока, когда он находился в дереве.
Задача в том, чтобы по "тростнику" воссоздать дерево.
Собственно я ее решил, но мне не нравится мой алгоритм:
Сажаем корень:
CurNode := Add(nil)
В процессе прохода списка:
// обработка блока
- если Block.Level > LastLevel, то:
ParNode := CurNode;
- иначе
ParNode := UpToParent(CurNode, Block.Level - 1)
CurNode := AddChild(ParNode)
LastLevel := Block.Level
// конец обработки блока
// конец обработки списка
// подъем до parent
UpToParent(node: TNode, level: int): TNode;
begin
Result := node;
while Result.Level > level do Result := Result.Parent;
end;
Предложите более эффективные варианты построения дерева по списку без "ныряния" верх-вниз.
← →
Johnmen © (2007-09-07 15:02) [1]А вариантов, по-сути, только два.
Один ты описал. А второй - последовательно строим дерево от корня, находя подходящий для текущего положения узел из списка ("тростник").
← →
ferr © (2007-09-07 15:06) [2]Я мало что понимаю в Вашей терминологии, например первый раз слышу слово тростник..
Если есть дерево, то мы можем LCR обойти его, сохранить узлы в порядке обхода, пометить листья битиком. После чего при помощи стека можно легко воссоздать дерево. Чем Ваша задача отличается?
← →
Jeer © (2007-09-07 15:08) [3]Johnmen © (07.09.07 15:02) [1]
Т.е. строим дерево по уровням, а рыщем по тростнику ?
Это хужее.
← →
Jeer © (2007-09-07 15:11) [4]
> то мы можем LCR обойти его, сохранить узлы в порядке обхода,
> пометить листья битиком
Это и было сделано, в результате образовался "тростник" - линейный список из узлов дерева в порядке LCR-обхода.
Можешь считать меня первооткрывателем термина "тростник" - "линеаризированное" дерево. :))
← →
ferr © (2007-09-07 15:15) [5]Я опечатался, стеком легко когда RLC или LRC обход. =)
← →
Sandman31 (2007-09-07 15:37) [6]Можно хранить всех текущих "родителей" в массиве (в I элементе - родитель I уровня). Тогда вместо линейного подъема можно сразу переходить к родительскому узлу нужного уровня.
← →
iam (2007-09-07 15:38) [7]http://www.algolist.ncstu.ru/ds/walk.php
см обход в ширину
сгодится?;)
← →
Johnmen © (2007-09-07 15:59) [8]
> Jeer © (07.09.07 15:08) [3]
> Т.е. строим дерево по уровням, а рыщем по тростнику ?Это хужее.
Почему хужее? Есть же скоростные алгоритмы поиска по списку.
← →
homm © (2007-09-07 16:02) [9]> Существовало "ветвистое" дерево с одним корнем.
> Перед его уничтожением был предпринят рекурсивный обход
> от корня вверх и справа (или слева).
Я чуть не подавился. Предупреждать надо :)
← →
Sandman31 (2007-09-07 16:06) [10]ParNode := UpToParent(CurNode, Block.Level - 1)
заменить на
for I := Block.Level downto LastLevel do
ParNode := ParNode.Parent
и по скорости будет оптимально.
← →
Jeer © (2007-09-07 16:18) [11]
> homm © (07.09.07 16:02) [9]
> Я чуть не подавился. Предупреждать надо :)
Надо же было повеселить:))
>Johnmen © (07.09.07 15:02) [1]
>А вариантов, по-сути, только два.
Зависит от способа организации дерева.
Вот мне кажется, что в случае с прошитыми деревьями, я выиграю:)
Вместо рекурсии или стека - линейный обход.
> for I := Block.Level downto LastLevel do
> ParNode := ParNode.Parent
>
> и по скорости будет оптимально.
Это мелочи, хотя и согласен:)
← →
iam (2007-09-07 16:22) [12]ну можно линейный список иметь типа
1 2 4 8 16 32 64 128 ...(количество узлов на каждом последующем уровне)
если при обходе в ширину какого-то узла нету элемент в списке будет nil
сбор дерева по списку будет линейным
Страницы: 1 вся ветка
Форум: "Прочее";
Текущий архив: 2007.10.07;
Скачать: [xml.tar.bz2];
Память: 0.47 MB
Время: 0.063 c