Деревья


	1 занятие Основные понятия. 2 занятие Представление деревьев. Основные операции над деревом. 3 занятие Самостоятельное решение задач. 4 занятие Идеально сбалансированное дерево.

О проекте


	— Сертификат — Рецензии и отзывы

Преподавателям


	— Пояснительная записка — Учебно-тематический план — Программа курса — Содержание курса — Требования к уровню подготовки обучающихся

Тема: Представление деревьев. Основные операции над деревом.

Дерево – это сложная динамическая структура данных, применяющаяся для эффективного хранения информации.

Очевидно, что для описания требуются ссылки. Опишем, как переменные с фиксированной структурой – сами вершины, тогда степень дерева будет определять число ссылочных компонент, указывающих на вершины поддеревьев. В бинарном дереве их два: левое и правое.

Type
  TreeLink = ^Tree;
  Tree = Record
       Data : <тип данных>;
       Left, Right : TreeLink;
  End;

Корень дерева опишем в разделе описания переменных:

Var
  kd : TreeLink;

К основным операциям над деревьями относятся:

занесение элемента в дерево;

обход дерева;

удаление элемента из дерева.

Рассмотрим вставку и обход дерева на примере следующей задачи.

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

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

Procedure InsTree(n : integer; Var t : TreeLink);
Begin
  if t=nil
    then
      begin
        new(t);
        with t^ do
          begin
            Left := nil;
            Right := nil;
            Data := n;
          end;
      end;
    else
      if n<=t^.data 
        then
          InsTree(n, t^.Left)
        else
          InsTree(n, t^.Right)
End;

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

вывод числа, хранящегося в узле;

обход левого поддерева;

обход правого поддерева.

Порядок выполнения этих действий определяет способ обхода дерева. Способы вывода:

прямой вывод (сверху вниз);

обратный вывод (слева направо);

концевой вывод (снизу вверх).

Процедура обратного вывода дерева имеет следующий вид:

Procedure PrintTree(t : TreeLink);
Begin
  if t<>Nil
    then
      begin
        PrintTree(t^.Left);
        Write(t^.Data:3);
        PrintTree(t^.Right);
      end;
End;

Задание. Написать процедуры прямого и концевого вывода значений элементов дерева.

Основная программа осуществляет ввод чисел с клавиатуры. Используются: переменная nd типа TreeLink – значение указателя на корень дерева; переменная Digit типа integer для хранения очередного введенного числа.

Begin
writeln('Вводите вершины дерева. Окончание ввода – 0');
  kd := nil;
  read(Digit);
  while Digit <> 0 do
    begin
      InsTree(Digit, kd);
      writeln(' Введите очередное число ');
      read(Digit);
    end;
  PrintTree(kd);
End.

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

Вернуться назад

Проект «Pascaler» — лучший на ХI Всероссийской конференции молодых исследователей с международным участием «Шаг в будущее», Россия, Москва, 12 – 16 апреля 2004г.