Лабораторная работа №8

Двоичные деревья

Цель работы:

Изучить способы эффективного хранения и обработки информации на примере бинарных деревьев.

Общие сведения

Бинарное дерево - это иерархическая динамическая структура данных, состоящая из узлов и соединяющих их дуг. В каждый узел, кроме одного, ведет ровно одна дуга. Этот единственный узел называется корнем дерева.

С каждой вершиной дерева связывается конечное число отдельных деревьев, называемых поддеревьями. На рисунке изображено дерево, в узлах которого располагаются символы:

Вершина Y, находящаяся непосредственно ниже вершины X, называется непосредственным потомком X, а вершина X называется предком Y. Если вершина не имеет потомков, то она называется листом, если имеет, то называется внутренней вершиной. Например, вершины D, E являются непосредственными потомками вершины B; вершины H, I, J являются листьями. Очевидно, что для описания дерева требуются ссылки. Опишем бинарное дерево как структуру типа Record, содержащую как минимум два поля – указатели на левое и правое поддеревья, и поле данных, например типа Integer:

Type
  PTree = ^TTree;
  TTree = Record
     Data : Integer;
     Left, Right : PTree;
  end;
Корень дерева описывается ссылочной переменной:
Var
  Tree : PTree;

Основные операции над деревом

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

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

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

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

Примеры

Вставка элемента в дерево.

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

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

Procedure InsTree(var ANode : PTree; n : lnteger);
Begin
  if ANode = nil then
     Begin
       new(ANode);
       With ANode^ do
          Begin
            Left := nil;
            Right := nil;
            Data := n;
          end;
     end
  else if n< ANode^.Data then InsTree(ANode^.Left, n) else InsTree(ANode^.Right, n);
End;

Вывод элементов дерева.

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

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

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

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

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

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

• симметричный обход (слева направо);

• обратный обход (снизу вверх).

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

Procedure PrintTree(ANode : PTree);
Begin
  if ANode <> nil then
     Begin
       PrintTree(ANode^.Left);
       WriteLn(ANode^.Data);
       PrintTree(ANode^.Right)
     End;
End;
Основная программа осуществляет ввод чисел с клавиатуры. Используются: переменная Tree типа PTree – значение указателя на корень дерева; переменная Digit типа Integer для хранения очередного введенного числа.


Var
  Tree : PTree;
  Digit : Integer;
BEGIN                       {основная программа}
  Writeln(‘Окончание ввода – 0’);
  Tree := nil;
  Read(Digit);
  While Digit<>0 Do
     Begin
       InsTree(Tree,Digit);
       Write(‘Введите очередное число: ‘);
       ReadLn(Digit);
     End;
  PrintTree(Tree);
END.

Удаление из дерева.

Непосредственное удаление элемента из упорядоченного дерева реализуется достаточно просто, если эта вершина является конечной:

или из нее выходит только одно ребро:

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

Пусть задана следующая структура:

Type
  PTree = ^TTree;
  TTree = Record
     Data : Integer;
     Left, Right : PTree;
  end;
Var
  Tree : PTree;
Необходимо удалить из дерева Tree узел со значением поля Data=x.
В процедуре DeleteNode различаются три случая:
1. Узла со значение, равным х, нет.
2. Узел со значением х имеет не более одного потомка.
3. Узел со значением х имеет двух потомков.
Procedure DeleteNode(x : Integer; var ANode : PTree);
Var q : PTree;
Procedure Del(var R : PTree);
Begin
  if R^.Right <> nil then Del(R.^Right)
  else
     begin
       q^.Data := R^.Data;
       q := R;
       R := R^.Left;
       Dispose(q);
     end;
End; { Del }
Вegin  { DeleteTree }
  if ANode = nil then Writeln(‘Элемента с ключом ’,x,’ в дереве нет’)
  else
     if x < ANode^.Data then DeleteNode(x,ANode^.Left)
     else if  x > ANode^.Data then DeleteNode(x,ANode^.Right)
       else
          begin
            q := ANode;
            if q^.Right = nil then
              Begin
                 ANode := q^.Left;
                 Dispose(q);
              end
            else
              if q^.Left = nil then
                 begin
                   ANode := q^.Right;
                   Dispose(q);
                 end
              else Del(q^.Left);
          end;
End;

Вспомогательная процедура Del вызывается только в третьем случае. Она «спускается» вдоль самой правой ветви левого поддерева удаляемого узла q^ и затем заменяет данные (поле Data) в q^ соответствующими значениями самого правого узла R^ этого левого поддерева, после чего от R^ можно освободиться. На рисунке задано начальное дерево (а), из которого последовательно удаляются узлы со значениями 13, 15, 5, 10. Полученные деревья показаны на рис. b – e.

Контрольные вопросы

1. Что такое рекурсивный алгоритм?

2. Из каких частей строится определение рекурсивного алгоритма?

3. Что является обязательным в любом рекурсивном алгоритме?

4. Можно ли рекурсию заменить итерацией? Можно ли итерацию заменить рекурсией?

5. Каков принцип построения динамической структуры «дерево»?

6. Перечислите сходства и отличия динамических структур типа «линейный список», «стек», «дерево».

7. Перечислите структуры, которые можно представить в виде дерева, которые встречаются в повседневной жизни.

8. Закончите фразу: «Список – это дерево, в котором …».

Задачи

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

1. Написать рекурсивную числовую функцию, подсчитывающую сумму элементов дерева.

2. Написать функцию, которая находит наибольший элемент дерева.

3. Написать функцию, которая находит наименьший элемент дерева.

4. Напишите процедуру, которая удаляет из дерева все четные элементы.

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

6. Написать рекурсивную процедуру, которая печатает элементы из всех листьев дерева.

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

будет выведено так:

1 группа

1 курс

2 группа

ФМИ

3 группа

2 курс

4 группа

8. Написать рекурсивную функцию, которая определяет глубину заданного элемента на дереве и возвращает –1, если такого элемента нет.

9. Написать процедуру, которая печатает (по одному разу) все вершины дерева.

10. Написать процедуру, которая по заданному n считает число всех вершин глубины n в заданном дереве.

11. Написать процедуру, которая считает глубину дерева.

12. Отсортировать массив А путем включения его элементов в дерево и скопировать отсортированные данные обратно в А.

13. Задана последовательность слов. Определить частоту вхождения каждого из слов в последовательность.

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

Назад На главную

Учебник по языку Pascal Лабораторные работы по программированию Справочник

2011-04-13 14:43:05 Ибрагим

8. Закончите фразу: «Список – это дерево, в котором …». Или дуб, или пенёк, или ясень, или клён. Лиственное

2011-04-13 16:06:52 Алесандр

Пенёк это не дерево.

2011-12-01 02:03:38 Yaroslav

Вот кому нужно реализация бинарного дереа и обход его в ширину http://goldcoding.net/DoneProggrams/PreviewProgram/19

Оставить комментарий: