Скачать: CL | DM;

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

← →
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 смахивает.

---

← →
TUser ©   (2007-12-01 16:07) [4]

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

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) - искомый узел может быть только последним => можно проверять только последний дочерний узел из списка дочерних узлов.

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

---

Страницы: 1 вся ветка

Скачать: CL | DM;



Память: 0.46 MB
Время: 0.011 c