Бинарное дерево

Лабораторная работа 5

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

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

B – потомок A, A – предок B, I - лист.

Бинарное дерево можно описать как структуру типа Record, содержащую как минимум два поля – указатели на левое и правое поддеревья, и поле данных:

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

Var kd: TreeLink; {корень дерева}

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

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

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

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

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

Решение:

1. Процедура вставки элемента в дерево.

При вставке в дерево вершина вставляется либо как поддерево уже существующей вершины или как единственная вершина дерева. Поэтому и левая и правая связи новой вершины должны быть 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;

2. Процедура вывода значений элементов двоичного дерева на экран.

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

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

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

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

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

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

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

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

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

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

3. Основная программа.

Осуществляется ввод чисел с клавиатуры. Используются:

переменная 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.

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

1. Дайте определение динамической структуры «дерево», «двоичное дерево».

2. Сколько элементов может содержать дерево?

3. Можно ли одновременно работать с несколькими деревьями?

Упражнения

1. Создать программой числовое двоичное дерево. Написать программу:

1) проверки наличия заданного числа в сформированном дереве;

2) подсчета суммы элементов дерева;

3) нахождения наибольшего элемента непустого дерева.

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

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

4. Создать программой символьное двоичное дерево. Написать программу:

1) получения строки, сформированной на базе этих символов;

2) проверки, имеются ли в непустом дереве хотя бы два одинаковых символа;

3) получения строки, сформированной на базе символов, встречающихся в каждой строке дерева.

5. Создать двоичное дерево записей. Проверить выбранное поле записей на равенство.

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

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

8. Написать программу, которая находит в непустом дереве длины (число ветвей) путей от корня до всех вершин, используя очередь или стек.

9. Написать программу, которая подсчитывает число вершин на каждом уровне непустого дерева (корень считать вершиной 0-го уровня).

10. Написать программу, которая определяет максимальную глубину непустого дерева Т, т.е. число ветвей в самом длинном из путей от корня дерева до листьев.

11. Написать программу, которая строит Т1 – копию заданного дерева Т.

12. Написать программу, которая строит Т – дерево, изображенное на рисунке (n – заданное натуральное число):

13. Формулу вида

<формула>::=<терминал>|(<формула><знак><формула>)
<знак>::=+|-|*
<терминал>::=0|1|2|3|4|5|6|7|8|9

можно представить в виде двоичного дерева с элементами типа char по следующим правилам: формула из одного терминала (цифры) представляется деревом из одной вершины с этим терминалом, а формула вида (f1sf2) – деревом, в котором корень – это знак s, а левое и правое поддеревья – это соответствующие представления формул f1 и f2.
Опишите рекурсивную функцию или процедуру, которая:

а) вычисляет числовое значение дерева-формулы Т;
б) по формуле из текстового файла f строит соответствующее дерево-формулу Т;
в) печатает дерево-формулу Т в виде соответствующей формулы;
г) проверяет, является ли двоичное дерево Т деревом-формулой.

14. Во внешнем текстовом файле записана (без ошибок) некоторая программа на языке Паскаль. Известно, что в этой программе каждый идентификатор (служебное слово или имя) содержит не более 9 латинских букв и(ли) цифр. Напечатать в алфавитном порядке все различные идентификаторы этой программы, указав для каждого из них число его вхождений в текст программы. При этом иметь в виду, что одноименные прописные и строчные буквы в идентификаторах отождествляются; внутри литерных значений, строк-констант и комментариев последовательности из букв и цифр не являются идентификаторами; в записи вещественных чисел может встретиться буква Е или е.

15. Написать программу подсчета количества листов заданного бинарного дерева.

Литература

1. Деревья: основные понятия и определения. Бинарное дерево. – [Электронный ресурс]. – Режим доступа http://www.structur.h1.ru/derevo.htm

Дата добавления: 2015-11-16