Реализация
Алгоритм TreeSort
Древесная сортировка
Задача. Упорядочить заданный набор (возможно, с повторениями) некоторых элементов (чисел, слов, т.п.).
- Для сортируемого множества элементов построить дерево двоичного поиска:
- первый элемент занести в корень дерева;
- для всех остальных элементов: начать проверку с корня; двигаться влево или вправо (в зависимости от результата сравнения с текущей вершиной дерева) до тех пор, пока не встретится такой же элемент, либо пока не встретится nil. Во втором случае нужно создать новый лист в дереве, куда и будет записано значение нового элемента.
- Совершить синтаксический обход построенного дерева, печатая каждую встреченную вершину столько раз, сколько было ее вхождений в сортируемый набор.
Мы приведем реализацию первого шага алгоритма, сортирующего числа (для элементов другой природы потребуется изменить только процесс считывания):
new(root);read(f,root^.chislo);root^.kol:= 1;root^.left:= nil;root^.right:= nil;while not eof(f) do begin read(f,x); p:= root; while true do begin if x = p^.chislo then begin inc(p^.kol); break end; if x > p^.chislo then if p^.right <> nil then p:= p^.right else begin new(p^.right); p:= p^.right; p^.chislo:= x; p^.kol:= 1; p^.left:= nil; p^.right:= nil; break end (* x < p^.chislo *) else if p^.left <> nil then p:= p^.left else begin new(p^.left); p:= p^.left; p^.chislo:= x; p^.kol:= 1; p^.left:= nil; p^.right:= nil; break end end;end;