Совершенно удивительно порой в заданиях для студентов находить новые для себя вещи. К примеру, решение заданий на построение бинарного дерева, честно говоря, меня озадачило.
Бинарное дерево, в целом, - это структура зависимости данных, которую можно представить в виде череды модулей IF..ElSE. Хотя соглашусь с вами, данного описания явно не достаточно для четкого понимания термина. Для наглядности и простоты восприятия подобную структуру проще нарисовать, чем описать, поэтому я вам тут нарисовала схемку: Ромбы и исходящие из них вправо и влево линии означают условия, которые приводят на уровень ниже к другим условиям. Слово "Да" по сути означает "true" в модуле IF..ElSE или единицу в бинарном представлении. Таким образом, когда вам попадется задание типа: построить бинарное дерево из массива с 9 элементами, знайте, что от вас хотят добиться изображенной на рисунке структуры. В приведенном же мной примере задание выглядит довольно свободно. Фактически нужно самостоятельно выбрать условия для нашего бинарного дерева и затем написать программу на Delphi. Спешу заметить, что такие задачи мне не нравятся, т.к. преподаватель чаще всего имеет свое видение вопроса и, скорее всего, даже при верном ходе решения вам придется доказывать, почему вы выбрали именно этот путь. Но задание есть, поэтому приступим к его решению. Бинарное дерево массива, состоящего из 9 элементов, я решила строить исходя из их индексов. Мысленно разделив массив на 2 части, поставила на вершину структуры признак по индексу среднего элемента (i<4?). (Средний элемент у нас будет под индексом 4). Если индекс элемента меньше 4, то идем по правой ветке - true - 1, если больше, то по левой - false - 0. Следующий уровень разделения по признакам (i>2?) и (n<6?), ну и на третьем уровне оставшиеся числа проверим на (i=1?) и (i=8?). Приведенные мной условия, конечно же рассматриваются в соответствии с разделением по признаку первого уровня. Таким образом, мы условно зададим схему распределения элементов массива по признакам. Исходники Delphi:
assignFile(f,'C:\1.txt');
ReWrite(f); Writeln(f,'i-порядковый номер элемента в массиве [0..8]'); Writeln(f,'(i<4)?'); for i := 0 to Length(arr) - 1 do arr[i]:=i+1; s11:=' _1_'; s10:=' _0_'; s21R:=' __1R_'; s20R:=' __0R_'; s31R:=' ___1R_'; s30R:=' ___0R_'; s21L:=' __1L_'; s20L:=' __0L_'; s31L:=' ___1L_'; s30L:=' ___0L_'; for i := 0 to Length(arr) - 1 do if i<4 then begin s11:=s11+IntToStr(arr[i]); if i>2 then s21R:=s21R+IntToStr(arr[i]) else begin s20R:=s20R+IntToStr(arr[i]); if i=1 then s31R:=s31R+IntToStr(arr[i]) else s30R:=s30R+IntToStr(arr[i]) end end else begin s10:=s10+IntToStr(arr[i]); if i<6 then s21L:=s21L+IntToStr(arr[i]) else begin s20L:=s20L+IntToStr(arr[i]); if i=8 then s31L:=s31L+IntToStr(arr[i]) else s30L:=s30L+IntToStr(arr[i]) end; end; writeln(f,s11); writeln(f,' _(i>2)?_'); writeln(f,s21R); writeln(f,s20R); writeln(f,' __(i=1)?_'); writeln(f,s30R); writeln(f,s31R); writeln(f,''); writeln(f,s10); writeln(f,' _(i<6)?_'); writeln(f,s21L); writeln(f,s20L); writeln(f,' __(i=8)?_'); writeln(f,s31L); writeln(f,s30L); closefile(f)
Код немного громоздкий, но если вы присмотритесь повнимательнее, то основную часть кода составляет не столько формирование бинарного дерева из массива (массив я заполнила для наглядности числами от 1 до 9), сколько формирование файла с видом бинарного дерева. Отмечу сразу, что поскольку задание довольно вольное - вы в праве формировать такой файл так, как вашей душе угодно. Для наглядности я постаралась отобразить разветвления дерева по средствам явного упоминания условий и с помощью бинарных признаков 0 и 1 - ветви бинарного дерева. Таким образом, содержимое файла выглядит так:
i-порядковый номер элемента в массиве [0..8] (i<4)? _1_1234 _(i>2)?_ __1R_4 __0R_123 __(i=1)?_ ___0R_13 ___1R_2
Буковки L и R - условно обозначают левую и правую ветвь бинарного дерева относительно признака первого уровня. Ну что? Разобрались? Если какое-то задание все еще вызывает у вас затруднение, обратитесь за помощью ко мне (прошу в контакты).
