Лабораторная работа № 3
Структуры данных типа дерево
Цель работы: Ознакомится с представлением данных в виде деревьев. Изучить основные алгоритмы обхода деревьев.
Краткие теоретические сведения
Элементы могут образовывать и более сложную структуру, чем линейный список. Часто данные, подлежащие обработке, образуют иерархическую структуру, подобную изображенной на рис. 1, которую необходимо отобразить в памяти компьютера и, соответственно, описать в структурах данных.
Каждый элемент такой структуры может содержать ссылки на элементы более низкого уровня иерархии, а может быть, и на объект, находящийся на более высоком уровне иерархии.
Рис. 1. Структура дерева
Если абстрагироваться от конкретного содержания объектов, то получится математический объект, называемый деревом (точнее, корневым деревом).
Корневым деревом называется множество элементов, в котором выделен один элемент, называемый корнем дерева, а все остальные элементы разбиты на несколько непересекающихся подмножеств, называемых поддеревьями исходного дерева, каждое из которых, в свою очередь, есть дерево.
При представлении в памяти компьютера элементы дерева (узлы) связывают между собой таким образом, чтобы каждый узел (который согласно определению обязательно является корнем некоторого дерева или поддерева) был связан с корнями своих поддеревьев.
Наиболее распространенными способами представления дерева являются следующие три (или их комбинации).
При первом способе каждый узел (кроме корня) содержит указатель на породивший его узел, т. е. на элемент, находящийся на более высоком уровне иерархии. Для корня дерева соответствующий указатель будет пустым. При таком способе представления, имея информацию о местоположении некоторого узла, можно, прослеживая указатели, подниматься на более высокие уровни иерархии.
struct node {
int key;
node *parent;
}
К сожалению, этот способ представления непригоден, если требуется не только «подниматься вверх» по дереву, но и «спускаться вниз», и нет возможности независимо получать информацию о местоположении узлов дерева. Тем не менее, такое представление дерева иногда используется в алгоритмах, где прохождение узлов всегда осуществляется в восходящем порядке. Преимуществом такого способа представления дерева является то, что в нем используется минимальное количество памяти, причем практически вся она эффективно используется для представления связей.
Второй способ представления применяют, если каждый узел дерева имеет не более двух (в более общем случае ― не более А) поддеревьев. Тогда можно включить в представление узла указатели на корни поддеревьев. В этом случае дерево называют двоичным (бинарным), а два поддерева каждого узла называют соответственно левым и правым поддеревьями этого узла.
Разумеется, узел может иметь только одно ― левое или правое ― поддерево (эти две ситуации в бинарных деревьях обычно считаются различными) или может вообще не иметь поддеревьев (и в этом случае узел называется концевым узлом или листом дерева).
При этом способе представления достаточно иметь ссылку на корень дерева, чтобы получить доступ к любому узлу дерева, спускаясь по указателям, однако память при таком способе представления используется не столь эффективно.
Описание структуры бинарного дерева, содержащего целые числа в узлах, может выглядеть так:
sruct node {
int key;
node *parent;
node *left;
node *right;
}
Каждый узел, содержит дополнительно две ссылки на корни левого и правого поддерева (left и right соответственно).
Если бинарное дерево имеет N узлов, то при таком способе представления всегда остаются пустыми более половины указателей. Тем не менее, такое представление является настолько удобным, что потерями памяти обычно пренебрегают.
Третий способ представления состоит в том, что в каждом элементе содержатся два указателя, причем один из них служит для представления списка поддеревьев, а второй для связывания элементов в этот список. Формально описание структуры для этого представления может быть тем же самым, что и для случая бинарного дерева, но смысл содержащихся в этом описании указателей меняется.
При третьем способе представления деревьев часто используется генеалогическая терминология: узлы, содержащиеся в поддеревьях каждого узла, называются его потомками, а корни этих поддеревьев, расположенные на одном уровнеиерархии, называют братьями. Эту терминологию можно отразить в описании структуры, и тогда поля left и right будут называться son и brother соответственно.
struct node {
int key;
node *parent;
node *son;
node *brother;
}
Иногда используются и более экзотические способы представления деревьев. Например, в некоторых случаях связи между узлами дерева можно вообще не представлять с помощью указателей, а «вычислять», если узлы дерева образуют регулярную структуру, не меняющуюся или меняющуюся очень мало в процессе работы с деревом.
Рассмотрим пример. Пусть узлы бинарного дерева пронумерованы, начиная с корня и далее вниз по иерархическим уровням.
При этом узлы расположены настолько плотно, что предком узла с номером i всегда является узел с номером i/2. В этом случае узлы дерева можно расположить в массиве, причем местоположение каждого узла будет задано его индексом в массиве, а максимальное число узлов указывается сразу же при создании дерева. Это дерево обладает еще одним свойством: каждый узел дерева содержит целое число, меньшее, чем значения, хранящиеся в поддеревьях этого узла. Таким образом, минимальное число всегда находится в корне дерева. Такое дерево иногда называют «пирамидой».
Высотой бинарного дерева назовем максимальное число узлов, которое может встретиться на пути из корня дерева в некоторый другой узел, при условии, то этот путь проходит только по связанным между собой узлам и никогда не проходит дважды через один и тот же узел.
Будем для удобства считать, что пустой указатель представляет вырожденное пустое» дерево, высота которого равна нулю. В этом случае высота бинарного дерева может быть выражена следующей формулой:
Тогда определение функции height, реализующим вычисление высоты дерева, может выгледеть так:
int height(node *root){
int hl = 0;
int hr = 0;
if (root->left!= NULL)
hl = height(root->left);
if (root->right!= NULL)
hr = height(root->right);
return ((hl > hr)? hl: hr) + 1; }
Обход деревьев
Рис. 2. Пример бинарного дерева
Рассмотрим двоичное дерево, содержащее в узлах символы, например, такое, как на рис. 2. Говорят, что дерево проходится сверху вниз, если каждый узел всегда проходится раньше, чем поддеревья этого узла. Для изображенного дерева следующие порядки прохождения узлов будут порядками обхода «сверху вниз»:
A B C D E F G H I
A B D H G C E F I
A C B F I E D G H
В этом случае также говорят, что дерево обходится в нисходящем порядке. Аналогично, при обходе снизу вверх (восходящий порядок обхода) узел проходится после того, как пройдены его поддеревья, например:
I H G F E D C B A
I F E C G H D B A
Очевидно, что для каждого обхода «сверху вниз» обход тех же узлов в противоположном порядке будет обходом «снизу вверх».
Порядок обхода бинарного дерева называется инфиксным, если каждый узел проходится после того, как пройдены все узлы одного поддерева, и до того, как пройдены узлы другого поддерева. Обычно используют либо левосторонний инфиксный обход, при котором сначала обходится левое поддерево, потом корневой узел, потом правое поддерево, либо правосторонний инфиксный обход, при котором наоборот, сначала обходится правое поддерево, затем корень, и, наконец, левое поддерево.
Вот как, например, располагаются узлы дерева в порядке левостороннего инфиксного обхода:
G D H B A E C I F
Для нисходящих и восходящих обходов обычно также определяются некоторые «стандартные» порядки обхода, например, при нисходящем левостороннем обходе порядок прохождения узлов определен следующим образом: непосредственно после обхода каждого узла проходятся узлы его поддеревьев в порядке слева направо (для бинарного дерева ― сначала левого поддерева, затем правого). Для дерева, приведенного на Рис. 16, узлы в порядке нисходящего левостороннего обхода располагаются следующим образом:
A B D G H C E F I
Еще два термина, часто использующихся для определения порядка обхода узлов, ― «обход в глубину» (depth first) и «обход в ширину» (breadth first).
Обход является обходом «в ширину», если узлы, расположенные ближе к корню дерева, обходятся раньше, чем узлы, отстоящие дальше от корня. При этом расстояние от узла до корня измеряется количеством ребер на кратчайшем пути из этого узла до корня. Так, например, в дереве на рис. 2.7 узлы D, Е и /'находятся на одном и том же расстоянии от корня ― 2, а узел В располагается ближе к корню, т. к. расстояние от него до корня равно 1. Обычно полагают, что корень находится на расстоянии 0от себя, так что при обходе «в ширину» он всегда обходится первым.
Обход является обходом «в глубину», если в любом поддереве исходного дерева узлы обходятся «подряд», т. е. если обход некоторого поддерева начат, то он продолжается до тех пор, пока все поддерево не будет обойдено. Например, нисходящий обход «в глубину» может быть представлен такой последовательностью узлов того же дерева:
A B D G H C E F I
Если в этой последовательности узлов расставить скобки для обозначения поддеревьев, то можно увидеть, что действительно, каждое поддерево занимает свой «участок» в этой последовательности, не пересекающийся с участками, занятыми другими поддеревьями:
(A (B (D (G) (H))) (C (E (F (I))))
Обходы «в глубину» особенно удобно реализовывать в виде рекурсивных процедур, поскольку такая процедура, получив в качестве аргумента некоторое поддерево для обхода, будет обходить его до тех пор, пока все узлы этого поддерева не будут пройдены. Напротив, реализовать обход «в ширину» с помощью рекурсивной процедуры практически невозможно, во всяком случае, такая реализация обхода будет неестественной и неэффективной.
Для примера приведем один способ обхода дерева ― левосторонний:
void left_walk(node *n){
if(n == NULL) return;
left_walk(n->left);
cout<< n->key;
left_walk(n->right);
}
Обходы «в глубину» особенно удобно реализовывать в виде рекурсивных процедур, поскольку такая процедура, получив в качестве аргумента некоторое поддерево для обхода, будет обходить его до тех пор, пока все узлы этого поддерева не будут пройдены. Напротив, реализовать обход «в ширину» с помощью рекурсивной процедуры практически невозможно, во всяком случае, такая реализация обхода будет неестественной и неэффективной.
Начнем с обхода в глубину. Будем использовать следующий алгоритм. Для того чтобы обойти некоторое поддерево, сначала пройдем корень этого поддерева, затем спустимся в его левое поддерево, а правое поддерево запомним в стеке. Если левое поддерево пусто, то можно сразу спускаться в правое поддерево вместо того, чтобы запоминать его в стеке. Если оба поддерева пусты, то очередное поддерево надо извлечь из стека.
void deep_walk(node *root){
stack = create_stack();
stack_push(stack, root)
// Пока в стеке есть узлы
while((node *n = stack_pop(stack))!= NULL){
do{
//Выводим текущую вершину
cout<< n->key;
if (n->left!= NULL){
// Помещаем в стек левое поддерево
if(n->right!= NULL)
stack_push(stack, n->right);
n = n->left;
} else
N = n->right;
} while(n!=NULL)
}
}
Данный фрагмент напечатает строку:
ABDGHCEFI
Рассмотрим процедуру для нисходящего обхода «в ширину», использующий очередь для хранения вершин в порядке обхода.
Очередь идеально походит для организации обхода «в ширину». Действительно, по мере продвижения от корня дерева вниз в очередь будут попадать все более удаленные от корня вершины дерева. При этом, чем раньше вершина попала в дерево, тем раньше она будет обработана ― это основной принцип хранения информации в структуре очереди. Рассмотрим опять дерево, приведенное на рис. 16.
void deep_walk(node *root){
queue = create_queue();
enqueue(queue, root);
while((node *n = dequeue(queue))!= NULL){
//Ставим в очередь поддеревья этого узла
if (n->left!= NULL) enqueue(queue, n->left);
if (n->right!= NULL) enqueue(queue, n->right);
cout<< n->key;
}
}
До сих пор мы все время говорили только о бинарных деревьях. В некоторой степени это оправдано, поскольку d деревьях общего вида узлы могут содержать два указателя точно так же, как и в бинарных деревьях. Соответственно, все те способы обхода, которые применимы к бинарным деревьям, могут быть применены и к деревьям общего вида. Тем не менее, смысл, вкладываемый нами в эти обходы, может меняться, поскольку логическая структура дерева может не совпадать с его физической структурой.
Поясним сказанное на примере. Пусть имеется дерево, логическая структура которого показана на рис. 3.
Рис. 3. Пример дерева общего вида для обхода
В памяти связи между узлами будут выглядеть несколько по-другому: каждый узел будет содержать указатели на первого непосредственного потомка («старшего сына») и на соседний узел, находящийся на том же уровне иерархии («брата»), так что физическая структура связей между теми же узлами будет выглядеть так, как на рис. 4 (логические связи, отсутствующие в физической структуре дерева, показаны пунктиром).
Рис. 4. Представление дерева общего вида с помощью бинарного
Если теперь рассмотреть какой-либо из порядков обхода узлов для исходного дерева, скажем, левосторонний обход «в ширину», то для второго дерева тот же порядок обхода уже не будет обходом «в ширину». Для исходного дерева узлы в порядке левостороннего обхода «в ширину» будут располагаться так:
А, В, С, D, Е, F, G, H, I, К,
но для второго дерева узлы в порядке обхода «в ширину» будут расположены уже по-другому:
А, B, C, Е, D, F, G, H, I, К.
Конечно, нетрудно написать функцию, которая будет представлять обход «в ширину» узлов исходного дерева, получая в качестве аргумента его физическое представление, однако, реализация этой функции будет, разумеется, отличаться от реализации обхода «в ширину» для бинарного дерева. Тем не менее, для некоторых порядков обхода функции будут одинаковы в обоих случаях. Например, нисходящий левосторонний обход «в глубину» для обоих деревьев будет одним и тем же:
А, В, С, E, F, H, I, К, D, G.
Иногда очень важным оказывается вопрос о количестве дополнительной памяти, требующейся для организации обхода дерева. Так, например, в системах, реализующих язык программирования LISP, практически вся память, участвующая в работе программы, организована в виде деревьев, которые иногда требуется обходить в условиях недостатка памяти (например, для организации «уборки мусора»). Во всех приводимых ранее алгоритмах для выполнения обхода явно или неявно использовалась некоторая достаточно сложно организованная структура памяти ― стек или очередь. Такая структура нужна для того, чтобы в процессе обхода помнить, какие элементы дерева еще не пройдены.
Конечно, можно каждый раз искать очередной непройденный элемент, исходя из того, какой узел дерева обходится в настоящий момент, но такой поиск очередного элемента «от корня» приводит к резкому замедлению скорости работы алгоритма. Компромиссом являются варианты, в которых в той или иной степени используются элементы памяти самого дерева. При этом обычно приходится отводить некоторую дополнительную память непосредственно в узлах дерева, так что какие-то потери памяти все равно остаются, однако их можно свести к минимуму: часто достаточно всего одного дополнительного бита памяти в каждом узле дерева для того, чтобы организовать обход дерева без использования дополнительных структур.
Иногда такой дополнительный бит памяти можно получить «даром», если при хранении информации в дереве имеется некоторая избыточность. Например, если информация, хранимая в узле дерева, содержит неотрицательное целое число, то часто можно использовать знаковый разряд этого числа для хранения нужной информации. Можно также задействовать неиспользуемые пустые указатели на несуществующие поддеревья и узлы для хранения дополнительной информации.
Рассмотрим два способа обхода деревьев на основе внутренней информации узлов дерева для организации обхода. В первом способе основная идея состоит в том, чтобы задействовать пустые указатели в исходном дереве для организации перехода от «потомков» к «предкам». Во втором способе указатели трансформируются уже в процессе обхода: при движении по дереву «вниз» пройденные указатели заменяются указателями «наверх», к корню дерева; при движении по ним обратно происходит восстановление направленности указателей. В обоих случаях требуется наличие дополнительного бита, который будет представлен в программах дополнительным полем типа bool в структуре узла дерева.
Сначала рассмотрим обход «сверху вниз» для дерева произвольной структуры (вообще говоря, не бинарного), представленного так, как показано на рис. 18.
Будем считать, что в узлах, представляющих самого младшего «брата», содержится ссылка на «родительский» узел. Для этого можно использовать свободную ссылку на «брата», а чтобы различить эти два способа применения
ссылки, введем дополнительный признак в каждый узел. Получившееся представление дерева изображено на рис. 5. На нем «младшие братья» выделены штриховкой, а ссылки на родительские узлы представлены стрелками иного вида, чем основные ссылки.
Рис. 5. Представление дерева с "обратными" ссылками
В этой процедуре переход к следующему элементу в порядке обхода осуществляется предельно просто: если у узла имеется «сын», то происходит переход к этому «сыну»; если имеется «брат», то выполняется переход к «брату», наконец, если нет и «брата», то происходит поиск «брата» у ближайшего предка. Обратите внимание, что поиск следующего узла осуществляется не в тот момент, когда этот узел становится действительно нужен, а «заранее», т. е. в тот момент, когда запрашивается предыдущий узел. Это дает возможность легко определить конец итерации.
walk_tree(node *root){
node *current = root;
while (current!= NULL){
cout<<current->key; //Выдача результата
// теперь ищем следующий элемент
if (current->son!= NULL)
current = current->son;
// Далее youngest признак того, что указатель
// ссылается на отца. Изначально все FALSE
while (current!= NULL && current->youngest) {
current = current->brother; // переход вверх
}
if (current!= NULL)
current = current->brother;
}
}
Если дерево, построено правильно, то его узлы будут пройдены в следующем порядке:
А, В, С, Е, F, H, I, К, D, G,
что для этого дерева является естественным порядком обхода «сверху вниз».
Недостатком такого способа обхода является то, что необходимо аккуратно поддерживать правильную структуру ссылок в дереве. Если, например, некоторый узел удаляется, то необходимо проверить, не содержит ли удаляемый узел ссылку вверх по дереву на предка (то есть не является ли он «самым младшим братом»). Если это действительно так, то необходимо найти его ближайшего «старшего брата» (разумеется, с использованием той же самой ссылки вверх по дереву), и модифицировать представление этого «брата». Аналогично, необходимо аккуратно следить за корректностью представления и при добавлении узлов.
Второй способ обхода с использованием внутренней структуры дерева, свободен от этого недостатка. Нет необходимости как-то по-особому обрабатывать или представлять узлы дерева при этом способе обхода. Все, что необходимо иметь, ― это свободный бит информации для использования его уже во время обхода.
Недостаток этого способа обхода в другом: структура дерева динамически меняется во время его обхода.
На рис. 6 представлен промежуточный этап при обходе бинарного дерева, изображенного на рис. 16. При работе алгоритма используются следующие указатели:
processed ― указатель на последнюю обработанную вершину, содержащую указатель «вверх» по дереву;
current ― указатель на первую вершину еще не обработанной части дерева.
При движении вниз по дереву (от корня к листьям) некоторые указатели в дереве используются для того, чтобы запомнить обратный путь. При движении обратно значения указателей восстанавливаются. Дополнительный бит информации служитдля того, чтобы запомнить, какой из двух указателей ― левый или правый ― используется для временного сохранения ссылки на родительский узел.
Рис. 6. Обход дерева с использованием внутренних указателей
На рис. 6 изображена ситуация, когда в двух узлах дерева - А и С - поля, в которых в нормальном состоянии записаны указатели на правое поддерево, используются для хранения ссылок на родительский узел.
public class Tree {
* Определение узла включает дополнительный бит flag
s t a t i c class Node {
public Object item; // содержимое узла
public boolean flag = false; // флажок для обхода
public Node left = null; // указатель на левое поддерево
public Node right = null; // указатель на правое поддерево
/ / Конструктор узла
public Node(Object item) {
this, item = item;
}
Node root = null; // корень дерева
void traverseWithlnversion (Visitor visitor) {
node processed = null; // указатель вверх по дереву
node current = root; // указатель на текущую вершину
bool down = true; // направление движения
// Цикл обхода узлов закончится,
// когда при движении вверх
// окажется, что уже все узлы пройдены
while (down || processed!= NULL) {
if (down) {
if (current == null) {
// Меняем направление движения
down = false;
} else {
// Спускаемся вниз по дереву на один шаг
node *W = current->left;
current->left = processed;
processed = current;
current = w;
}
} else {
if (processed.flag) {
// Восстанавливаем указатель и
//продвигаемся вверх по дереву
Processed->flag = false;
node *w = processed->right;
processed->right = current;
current = processed;
processed = w;
} else {
// Посещаем вершину при переходе
// из левого поддерева в правое
printf(“%c”,processed->key);
// Переходим к обработке правого поддерева
node *W = processed->right;
processed->flag = true;
processed->right = processed->left;
processed->left = current;
current = w;
// Снова двигаемся вниз
down = true;
}
}
}