Помогите решить задачу, пожалуйста!

← →
Lip (2007-12-01 00:47) [0]

Есть слова:
abc
abb
add
adc
bcd

Нужно построить дерево вида:
a-
|
-b-
| |
| -b
| |
| -c
|
-d-
| |
| -c
| -d
|
b-
|
-c-
|
-d

Должен соблюдаться алфавитный порядок.

Примерный алгоритм такой:
-вводим слова
-сортируем
-ну и самое сложное - выводим это дерево

Вот сижу мучаюсь пытаюсь реализовать вывод дерева. Что-то не получается, мозгов не хватает.
Решил что можно рекурсией реализовать это, но как написать пока не понял.
Не прошу писать за меня и т.д.
Помогите советов чтоль, как вот рекурсией это сделать если это вообще можно. Мне кажется рекурсией будет легче.
Заранее благодарен!

← →
Servelat (2007-12-01 02:14) [1]

Почему в конце твоего дерева-примера "c" на одном уровне с "d"? Вроде слов "bc" и "bd" небыло, а было лишь "bcd".

В предположении, что ты ошибся с примером, ход построения дерева мог бы быть таким:

for I := 0 to WordCount - 1 do begin CurrentTreeNode := Root; for J := 1 to Length(Words[I]) do begin if <буква Words[I][J] есть среди списка дочерних узлов CurrentTreeNode> then CurrentTreeNode := <тот самый дочерний узел, буква которого совпадает с CurrentTreeNode> else begin <добавить дочерний узел к CurrentTreeNode, присвоив ему букву Words[I][J]>; CurrentTreeNode := <только что добавленный дочерний узел>; end; end; end;

Words - массив отсортированных слов.
CurrentTreeNode - текущий узел
Root - корневой узел (от которого мы строим все дерево).

← →
Сергей М. © (2007-12-01 12:29) [2]

> Нужно построить дерево

Дерево обычно сажают, выращивают и строгают, а не "строят".

Определись для начала со значением фразы "посторить дерево" ..

← →
Efir (2007-12-01 13:03) [3]

Что-то на дерево для реализации алгоритма LZ смахивает.

Не надо сортировать слова. Тебе нужно префиксное дерево. Его строят так

for every word
PLACE = root of the tree
for L = first letter to last letter
if PLACE has no child for letter L then
add the child for PLACE
PLACE = a child of PLACE for letter L

← →
Servelat (2007-12-01 17:41) [5]

> [4]

Если не сортировать слова, то надо не "add the child for PLACE" делать, а скорее "insert the child for PLACE in appropriate position", иначе нарушится пожелание автора сабжа

> Должен соблюдаться алфавитный порядок.

Кстати, при предварительной алфавитной сортировке слов, упрощается проверка условия (PLACE has no child for letter L) - искомый узел может быть только последним => можно проверять только последний дочерний узел из списка дочерних узлов.

Впрочем, это все детали, реализаций множество (=.

Помогите решить задачу, пожалуйста! Найти похожие ветки