Помощь - Поиск - Пользователи - Календарь
Полная версия: Задача с деревом.
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
Timon
Добрый день.
Помогите, плиз. Дана вот такая задачка:

Текстовый файл содержит набор целых чисел. Прочитать его в память и сформировать бинарное дерево, содержащий номера элементов исходного массива, абсолютное значение которых является простым числом. Повторяющиеся значения в дерево не включать.
Порядок ввода исходных данных:
- имя файла с данными;
- файл с числами. Числа размещены в нескольких строках и отделены друг от друга пробелом или концом строки. Признаком окончания данных является конец файла.
Порядок вывода результатов:
- исходные данные;
- число элементов в дереве;
- элементы дерева в порядке убывания значений.

Сама программа, вроде бы не особо сложная, но как-то не получается не включать повторяющиеся значения. Помогите плиз.

И ещё, если не сложно, напишите вкрадце как вывести дерево в порядке убывания значений. Просто сдавать уже завтра и с отчётом, а надо ещё одну программу дописать.
Заранее спасибо.
volvo
Цитата(Timon @ 26.07.05 18:56)
Сама программа, вроде бы не особо сложная, но как-то не получается не включать повторяющиеся значения. Помогите плиз.
Это еще почему? Перед занесением в дерево проверяй элемент на дублирование... Что-то в этом роде:
Var
arr: array[1 .. 20] of integer; { для примера }

Function DuplicateElement(index: integer): Boolean;
...
Begin
DuplicateElement := False;
For i := 1 To Pred(index) Do
If arr[i] = arr[index] Then Begin
DuplicateElement := True; Exit
End;
End;

...
For i := 1 To n Do
If not DuplicateElement(i) Then AddToTree(root, i);

Может быть можно и еще проще... ;)

Цитата(Timon @ 26.07.05 18:56)
И ещё, если не сложно, напишите вкрадце как вывести дерево в порядке убывания значений.
В порядке убывания каких значений? Индексов, или именно значений?
Timon
За первое спасибо. Большое. Просто у меня, почему-то, выходил какой-то отстой.
Насчёт второго. Именно по величине именно значений. Индексы тут не ведутся.
volvo
Тогда еще проще: в процедуре
AddToTree(p: ptree; val: integer);
заноси в дерево индексы, но сортируй не по значению Val, а по значению arr[Val], то есть примерно так:
procedure AddToTree(var root:PTree; val: integer);
var elem:PTree;
begin
if (root=Nil) then begin
{ создать новый лист (elem) и записать в него значение Val }
root := elem; { присоединить новый лист вместо пустого дерева }
end

else begin
if (arr[Val] < arr[root^.info]) { <--- Вот основная идея !!! }
then AddToTree(root^.left, Val)
else AddToTree(root^.right, Val);
end;
end;

Ну, а теперь для того, чтобы распечатать элементы в порядке убывания, достаточно просто пройти по дереву в таком порядке: Правое поддерево -> Левое поддерево -> Корень... И все... rolleyes.gif
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.