Несложная задачка

← →
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]
> Т.е. строим дерево по уровням, а рыщем по тростнику ?Это хужее.

Почему хужее? Есть же скоростные алгоритмы поиска по списку.

> Существовало "ветвистое" дерево с одним корнем.
> Перед его уничтожением был предпринят рекурсивный обход
> от корня вверх и справа (или слева).

Я чуть не подавился. Предупреждать надо :)

← →
Sandman31 (2007-09-07 16:06) [10]

ParNode := UpToParent(CurNode, Block.Level - 1)

заменить на

for I := Block.Level downto LastLevel do
ParNode := ParNode.Parent

и по скорости будет оптимально.

> 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
сбор дерева по списку будет линейным

Несложная задачка Найти похожие ветки