2.11.3. Деревья

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

Единственный узел, в который не ведет ни одна дуга, называется корнем дерева.

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

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

Или в качестве корня дерева можно представить университет. Он делится на факультеты. Каждый факультет состоит из курсов, курсы из специальностей, специальности из групп, группы из студентов. Можно составить дерево для представления структуры университета.

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

Еще одно применение деревьев — это хранение и поиск информации.

Дерево по своей сути является рекурсивной структурой данных, поэтому дадим рекурсивное определение дерева.

Пустое дерево — это отсутствие элементов.

Дерево — это или пустое дерево или узел, связанный дугами с конечным числом деревьев. '

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

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

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

Пример. Описание узла дерева.

type

PNode =^TNode; {указатель на узел дерева} TNode = record { узел дерева }

Inf: string; (здесь хранится сама информация}

Left, Right: PNode;{указатели на узлы-потомки}

end;

В качестве хранимой информации выбрана строка символов, но ничто не мешает хранить данные любого типа.

Отдельная переменная типа PNode должна указывать на корень дерева подобно переменной, указывающей на голову списка.

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

• Посетить корень.

• Пройти левое поддерево.

• Пройти правое поддерево.

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

Назовем ключом признак, по которому ведется поиск информации.

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

Например, если нужно найти в библиотечном каталоге книгу определенного автора, то ключом будет являться фамилия автора, а сравнение будет осуществляться по алфавиту

Двоичное дерево упорядочено, если все ключи левого поддерева каждого узла меньше, чем ключ узла, а ключи правого поддерева — больше.

Поиск в упорядоченном дереве выполняют рекурсивным алгоритмом очень похожим на алгоритм двоичного поиска.

• В начале поиска взять все дерево в качестве текущего поддерева.

• Если текущее поддерево не пусто, то нужно сравнить искомый ключ с тем, что в корне поддерева:

  • если ключи совпадают, поиск завершен;

  • если ключ в корне больше искомого, в качестве текущего взять левое поддерево и повторить поиск;

  • если ключ в корне меньше искомого, в качестве текущего взять правое поддерево и повторить поиск.

• Если дерево пусто, поиск неудачен. Продолжительность поиска определяется длиной одной

ветви дерева. Если ветви примерно одинаковы (дерево сбалансировано), то время поиска в дереве с N узлами такое же, как время двоичного поиска в упорядоченном массиве из N элементов.

Алгоритм поиска легко переделать в алгоритм включения нового узла в упорядоченное дерево. Для этого достаточно слова «поиск неудачен» заменить словами «включаем новый узел в качестве правого (левого) поддерева».

При удалении узла из дерева возможны следующие случаи:

• удаляемый узел не имеет поддеревьев;

• удаляемый узел имеет лишь одно поддерево;

• удаляемый узел имеет оба поддерева.

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

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

program tree type

PNode =^TNode; {указатель на узел дерева}

TNode = record { узел дерева }

Inf: string; {здесь хранится сама информация}

Left, Right: PNode; {указатели на узлы-потомки}

end;

var

Head,Curr:PNode; s: string;

{добавление узла в упорядоченное дерево}

procedure Add_Node(var Head:PNode;Curr:PNode);

begin

if Head = nil then Head:=Curr

else

begin

if Head^.Inf > Curr.^Inf

then Add_Node(Head^.Left,Curr) {вставка узла в левое поддерево}

else Add_Node(Head^.Right,Curr); (вставка узла в правое поддерево}

end;

end;

{печать дерева}

procedure Print_Tree(Head:PNode); begin

if Head <> nil then begin

Print_Tree(Head^.Left); {печать левого поддерева} writeln(Head^.Inf); {печать текущего узла} Print_Tree(Head^.Right); {печать правого поддерева} end

end;

begin

Head:=nil; {корень дерева} readln(s);

while s<>" do

begin

New(Curr); {введение нового узла} Curr^Mnf:=s;

Curr^.Left:=nil;Curr^.Right:=nil;

Add_Node(Head,Curr); {добавление нового узла в дерево}

readln(s);

end;

Print_Tree(Head); writeln;

end.