Сортировка двоичным деревом через список - Pascal ABC
Формулировка задачи:
Доброе время суток.
Надеюсь на вашу помощь , ибо уже 2ой час сижу и пытаюсь с помощью интернета и магических заклинаний сделать программу . Суть в построении двоичного дерева через список. То есть , делаем список в котором 4 пункта ( Сам введенный элемент , ссылка на родителя , ссылка на левого сына , ссылка на правого сына ) . Как оно строится ? 1ый элемент становится корнем дерева и каждый последующий элемент сравнивается с корнем и ставится слева ( если меньше корня) или справа (если больше корня) . Вообщем суть в том чтобы взять определенную введенную последовательность , выстроить двоичным деревом ( в данном случае списком ) и выдать отсортированную последовательность ( по принципу левый сын - родитель - правый сын ) . Сижу ломаю голову , интернет не помогает .
Вот что у меня получилось пока накрутить :
Решение задачи: «Сортировка двоичным деревом через список»
textual
Листинг программы
type derevo=^tderevo; tderevo=record roditel:derevo; info:integer; lsin:derevo; rsin:derevo; end; var P : Derevo; i : Integer; Procedure AddElem(inf:integer); {[I] Построение самого дерева[/I]} Var F,R : Derevo; begin New(R); R^.info:=inf; R^.roditel:=nil; R^.lsin:=nil; R^.rsin:=nil; If P=nil then P:=R else Begin F:=P; While ((F^.lsin<>nil) and (inf<=F^.info)) or ((F^.rsin<>nil) and (inf>F^.info)) do If inf<=F^.info then F:=F^.lsin else F:=F^.rsin; If inf<=F^.info then F^.lsin:=R else F^.rsin:=R; R^.roditel:=F; end; end; procedure Sort(F : Derevo); { [I]Вывод[/I]} Var R : Derevo; begin If F<>nil then Begin // Write('(',f^.info,')'); {----------for debuging--------------------} If F^.lsin<>nil then Sort(F^.lsin); Write(F^.info,' '); If F^.rsin<>nil then Sort(F^.rsin); Dispose(F); end; end; Begin P:=nil; // i:=1; // While i<>0 do { вводим элементы, конец последовательности 0 } // Begin // Readln(i); // If i<>0 then AddElem(i); // end; AddElem(4); AddElem(2); AddElem(6); AddElem(1); AddElem(3); AddElem(5); AddElem(7); Sort(P); Writeln; end.
Объяснение кода листинга программы
- В начале кода объявляются переменные и типы данных.
- Затем идет процедура AddElem, которая принимает информацию об элементе и добавляет его в дерево. Если дерево пустое, то создается новый элемент.
- После этого идет процедура Sort, которая сортирует дерево. Если дерево не пустое, то сначала сортируются левые поддеревья, а затем правые.
- В начале блока Begin идет объявление переменных для цикла, но этот цикл не запускается.
- Затем вызывается функция AddElem для добавления пяти элементов в дерево.
- После этого вызывается функция Sort для сортировки дерева.
- Конец программы.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д