Ильницкий В.Г.

Костанайский государственный университет им. А Байтурсынова

В статье говорится об одном из методов отображения бинарного дерева на экране компьютера при изучении программирования.

Ключевые слова: Список, дерево, граф, указатель, динамическая память.

При создании программ и программного обеспечения часто используются такие структуры данных, как графы, деревья, списки. При изучении этих структур данных материал будет усваиваться намного лучше, если его представить более наглядно. Предлагается простая процедура, которая позволит отображать небольшое бинарное дерево на экране компьютера.

Для начала для построения дерева необходимо объявить нестандартные типы данных указатель на текущую вершину дерева и тип, описывающий элемент дерева.

type  ukaz = ^tree;

  tree = record  inf: integer;   R,L: ukaz  end; 

Дерево будет построено в динамической памяти компьютера. Для ввода данных с клавиатуры и построения по ним бинарного дерева поиска предлагается следующая процедура:

procedure poisk (var t: ukaz; x: integer);

begin     if    t = nil  then begin  New(t);   t^.Inf:=x;   t^.R:=nil; t^.L:=nil  end

                                else   if   x<t^.inf   then poisk(t^.L,x)  else poisk(t^.R,x)

end;

Данная рекурсивная процедура проверяет, указывает ли текущая вершина на нулевую ссылку и если да, создает новый элемент. В противном случае процедура осуществляет рекурсивный поиск по левому или правому поддереву в зависимости от условия. Для отображения на экране дерева предлагается осуществить обход всех элементов дерева и вывод на экран значения узла в заданную точку. Координаты точки рассчитываются аналогично алгоритма метода половинного деления, где а и в отрезок для отображения дерева.

procedure Ris (t: ukaz; a, b, y: integer);

begin     if    t=nil then exit ;

  gotoxy((a+b) div 2, y);  write(t^.inf);

  Ris(t^.L, a,  (a+b) div 2,  y+20);

 Ris(t^.R,  (a+b) div 2, b,  y+20);

end;

Такая простая процедура позволит постоянно отображать бинарное дерево на экране компьютера, что позволит наглядно демонстрировать различные операции с бинарными деревьями, такими как, удаление элементов бинарного дерева, балансировка бинарного дерева, добавление новых элементов. Это в свою очередь приведет к более глубокому пониманию и осмыслению данной темы при ее изучении.

Литература:

1 М.С.Долинский, Решение сложных и олимпиадных задач по программированию / ЗАО Издательский дом «Питер», 2006. 366 с.

2 М.С.Долинский, Алгоритмизация и программирование на Tyrbo Pascal: от простых, до олимпиадных задач / СПб: Питер, 2004.240 с.

3 В.А.Емеличев, Лекции по теории графов / М.: Наука, 1990. 384 с.