3. ДЕРЕВЬЯ
Дерево в общем случае — это связный граф без циклов, абстрактная структура данных, представляющая собой множество вершин, или узлов, на которых определены попарные связи — ребра. Будем рассматривать частный случай — корневые упорядоченные деревья. У таких деревьев ребра становятся ориентированными, поскольку у любой последовательности попарно связанных вершин — пути, включающем корень, появляется направление от корня или к корню. Для некоторого узла v все вершины дерева на пути в корень, находящиеся ближе к корню, называется предками, а дальше от корня — потомками. Из пары узлов, связанных ребром, узел ближе к корню — отец, дальше от корня — сын. У каждого узла может быть несколько сыновей, которые называются братьями, или дочерними узлами, но только один отец. Корень — это единственный в дереве узел, у которого нет отца. Узлы, у которых нет сыновей, называются листьями.
Количество ребер на пути из корня в узел дерева называется глубиной узла, количество ребер на самом длинном пути в лист — высотой. Высота дерева — это высота его корня. Разность между высотой дерева и глубиной узла — это уровень узла.
Дерево упорядочено, если упорядочены сыновья любого его узла. Из корневых упорядоченных деревьев наиболее часто используются двоичные, или бинарные. Каждый узел двоичного дерева может иметь не более двух сыновей — левого и правого, причем единственный сын узла — обязательно левый или правый. Более сложный вариант — троичное дерево, где у каждого узла — не более трех сыновей: левый, средний, правый — в любой комбинации. Каждый из сыновей может рассматриваться как корень соответствующего поддерева, возможно, пустого.
Для представления дерева в памяти можно предложить естественный способ — разветвляющийся список. Узлы дерева — объекты, связи между которыми осуществляются через указатели. Для создания дерева достаточно объявить класс «узел дерева», членами которого должны быть указатели на узлы того же типа: «левый» и «правый» (у троичного дерева — «левый», «средний» и «правый»). В узле могут быть и другие данные-члены. Минимально необходимым является тег — метка или номер узла, с помощью которого можно различать узлы в процессе их обработки. Однако для работы с деревом в целом удобнее иметь особый класс «дерево», в котором собираются данные, относящиеся к дереву в целом, и функции-члены для работы с деревом. Чтобы эти функции имели доступ к данным узла, достаточно объявить класс «дерево» дружественным для класса «узел».
//Класс «узел дерева»
class Node { char d; //тег узла
Node * lft; // левый сын
// Node * mdl; — средний сын (если нужно)
Node * rgt; // правый сын
public:
Node() : lft(nullptr), rgt(nullptr) { } // конструктор узла
Node(const Node &) = delete;
Node & operator = (const Node &) = delete;
Node(){ delete lft; // деструктор узла (уничтожает все поддерево
delete rgt; } // в порядке, обратном его созданию)
friend class Tree; // дружественный класс «дерево»
} ;
// Класс «дерево в целом»
class Tree
{ Node * root; // указатель на корень дерева
char num, maxnum; // счетчик тегов и максимальный тег
int maxrow, offset; // максимальная глубина, смещение корня
char ** SCREEN; // буфер для выдачи на экран
void clrscr(); // очистка буфера
Node* MakeNode(int depth); // создание поддерева
void OutNodes(Node * v, int r, int c); // выдача поддерева
Tree (const Tree &) = delete; // конструктор копии
Tree (Tree &&) = delete; // копия с переносом (С++11)
Tree& operator = (const Tree &) const = delete; // присваивание
Tree& operator = (Tree &&) const = delete; // то же, с переносом
public:
Tree(char num, char maxnum, int maxrow);
Tree();
void MakeTree() // ввод — генерация дерева
{ root = MakeNode(0); }
bool exist() { return root != nullptr; } // проверка «дерево не пусто»
int DFS(); // обход дерева «в глубину»
int BFS(); // обход «в ширину»
void OutTree(); // выдача на экран
};
Кроме данных, в классе Tree объявлены скрытые функции-члены: вспомогательные функции, которые не входят в интерфейс и предназначены только для вызова из других функций-членов. Конструкторы копирования и перегрузки присваивания сделаны скрытыми умышленно: попытка создать в программе ситуацию, в которой эти функции могут быть вызваны, приведет к ошибке на этапе компиляции «нарушение защиты».
Конструктор дерева инициализирует параметры разметки и создает рабочую память — матрицу символов, необходимую для выдачи изображения дерева на экран.
Tree :: Tree(char nm, char mnm, int mxr):
num(nm), maxnum(mnm), maxrow(mxr), offset(40), root(nullptr),
SCREEN(new char * [maxrow])
{ for(int i = 0; i < maxrow; i++) SCREEN[ i ] = new char[ 80 ]; }
Деструктор дерева уничтожает матрицу символов и запускает деструктор узла для корня.
Tree ::
Tree( ) { for(int i = 0; i < maxrow; i++) delete [ ]SCREEN[ i ];
delete [ ]SCREEN; delete root; }
Обратите внимание на то, как создается и уничтожается матрица.
Чтобы обработать каким-либо образом множество узлов дерева, его нужно обойти. Каждый узел дерева является корнем поддерева, а его сыновья — тоже корнями поддеревьев. Поэтому алгоритм обхода, запускаясь для узла, должен обработать информацию в узле и запустить такой же алгоритм для каждого из непустых поддеревьев. Существует три способа сделать это, отличающиеся лишь порядком шагов:
1. Прямой обход:
— обработать узел;
— посетить (в прямом порядке) каждого сына.
2. Обратный обход:
— посетить (в обратном порядке) каждого сына;
— обработать узел.
3. Внутренний, или симметричный обход:
— посетить (во внутреннем порядке) левого сына;
— обработать узел;
— посетить во внутреннем порядке правого сына (остальных сыновей).
Минимальная обработка узла может состоять в присвоении соответствующему в нем полю номера в порядке посещения (разметка) или в выдаче номеров на экран, если они уже имеются, или в формировании последовательности из номеров посещенных узлов. Очевидно, что не существует иных способов отличить один порядок обхода узлов от другого.
При разметке дерева в прямом порядке номер любого узла — наименьший, а при обратном — наибольший в соответствующем поддереве, а диапазон использованных номеров равен мощности поддерева. При разметке внутренним способом номер узла больше любого номера в левом поддереве и меньше любого номера в правом.
3.2. Создание дерева
Для создания дерева в памяти тоже применяется алгоритм обхода. Первым шагом этого алгоритма является проверка необходимости создания узла.
Если ответ положительный, узел создается, и в нем заполняются информационные поля. В частности, может быть выполнен шаг разметки. Далее заполняются поля указателей на каждого сына: для получения значения указателя алгоритм запускается рекурсивно. Результат — указатель на вновь созданный узел или нуль, если узел не создан.
Проверка необходимости создания узла может быть выполнена тремя способами:
1. Запрос на ввод с клавиатуры. Приглашение к вводу может содержать какую-либо информацию о месте предполагаемого узла в дереве. Ожидаемый ответ — «да» или «нет» (1 или 0, Y или N, и т. п.). Вместо ответа «да» можно вводить информацию для размещения в узле, особый ввод, например пустой, может означать «нет».
2. Чтение очередного элемента заранее заготовленной последовательности из массива, линейного списка, файла или битов из машинного слова. Такая последовательность сама по себе тоже является способом размещения дерева в памяти, а алгоритм ввода просто преобразует ее в форму разветвляющегося списка.
3. Обращение к датчику случайных чисел с целью генерации дерева. Датчик должен быть управляемым. Простой датчик с равновероятной выдачей 0 или 1 будет создавать пустые или очень маломощные деревья — из 1, 2, 3 узлов, так как вероятность того, что узел будет создан, очень быстро падает с ростом его глубины: для корня она составляет всего 0.5, для сыновей — 0.25 и т. д. Нужен датчик, который обеспечивал бы вероятность создания корня близкую к 1 и уменьшал ее с ростом глубины узла.
Пример такого датчика:
Y = depth < rand() % 6 + 1,
где depth — глубина узла: для корня она 0, для произвольного узла — на 1 больше, чем у отца. Очевидно, что для корня Y всегда 1, а для узла на глубине больше 5 — всегда 0.
Функция-член для генерации случайного дерева может выглядеть следующим образом:
Node * Tree :: MakeNode(int depth)
{ Node * v = nullptr;
int Y = (depth < rand( )%6+1) && (num <= 'z');
//Вариант: cout << "Node (" << num << ',' << depth << ")1/0: "; cin >> Y;
if (Y) { // создание узла, если Y = 1
v = new Node;
v->d = num++; // разметка в прямом порядке (= «в глубину»)
v->lft = MakeNode(depth+1);
// v->d = num++; // вариант — во внутреннем
v->rgt = MakeNode(depth+1);
// v->d = num++; // вариант — в обратном
}
return v;
}
Эта функция запускается из встраиваемой функции-члена MakeTree(), результат ее работы присваивается полю root.
Вместо генерации случайного значения Y можно организовать ввод его с клавиатуры. Соответствующая альтернатива помещена в комментарий.
Функция создает дерево прямым обходом по той простой причине, что невозможно создать узел дерева, если не создан его отец. Но вот считать узел «пройденным» можно когда угодно. Поэтому для разметки узла в алгоритме можно использовать три точки (две из них закомментированы): до обхода поддеревьев, после левого поддерева и перед правым и по окончании обхода поддеревьев. Нужный вариант разметки можно обеспечить, включив инициализацию в соответствующей точке и выключив — в остальных.
Значение глубины узла depth, необходимое для датчика, известно при входе в функцию и может быть использовано в любом месте. А вот данные, зависящие от поддеревьев: высота узла, количество листьев, количество потомков и т. п., могут быть известны только тогда, когда оба поддерева уже обработаны, т. е. они доступны только при обратном обходе.
3.3. Вывод изображения дерева на экран монитора
Чтобы получить наглядное представление о способе разметки дерева, нужно вывести его на экран в виде диаграммы. Можно обойтись для этого текстовым режимом, если принять следующее соглашение. В середине первой строки текста вывести метку корня дерева. В следующей строке расположить метки левого и правого сыновей в серединах левой и правой половины строки и т. д. Если дерево троичное, метку среднего сына можно разместить прямо под корнем, и т. д., уменьшая смещение сыновей относительно корня в два раза по отношению к предыдущему ряду. Удобно воспользоваться рекурсивной функцией обхода дерева, которая выдает метку узла в некоторой точке экрана (r, c), а для сыновей добавляет 1 к номеру ряда и смещение к номеру столбца. Смещение удобно вычислять сдвигом некоторой константы offset на номер ряда, который совпадает с глубиной узла.
Для выдачи метки в нужную точку экрана можно использовать функцию позиционирования курсора gotoxy(r, c) из библиотеки conio.h, предварительно очистив экран функцией clrscr(). Но поскольку эти функции есть не во всех оболочках, можно обойтись без них, использовав промежуточную буферную память в виде матрицы символов, как это сделано далее в примере.
Для того чтобы понять разметку дерева, достаточно вывести узлы пяти-шести верхних уровней. Для улучшения читабельности картинки рекомендуется вместо числовых меток использовать буквы латинского алфавита.
Функция-член для вывода изображения дерева на экран может выглядеть таким образом:
void Tree :: OutTree( )
{ clrscr( );
OutNodes(root, 1, offset);
for (int i = 0; i < maxrow; i++)
{ SCREEN[ i ][ 79 ] = 0;
cout << ‘\n’ << SCREEN[ i ];
}
cout << ‘\n’;
}
Она запускает закрытую функцию-член clrscr( ), которая готовит матрицу символов, заполняя ее точками:
void Tree :: clrscr( )
{ for(int i = 0; i < maxrow; i++)
memset(SCREEN[i], '.', 80);
}
Далее выполняется закрытая функция OutNodes( ), расставляющая метки вершин дерева в матрице символов:
void Tree :: OutNodes(Node * v, int r, int c)
{ if (r && c && (c<80)) SCREEN[ r – 1 ][ c – 1 ] = v->d; // вывод метки
if (r < maxrow) {
if (v->lft) OutNodes(v->lft, r + 1, c – (offset >> r)); //левый сын
// if (v->mdl) OutNode(v->mdl, r + 1, c); – средний сын (если нужно)
if (v->rgt) OutNodes(v->rgt, r + 1, c + (offset >> r)); //правый сын
}
}
Затем матрица символов построчно выводится на экран.
3.4. Шаблоны классов для очереди и стека
и нерекурсивные алгоритмы обхода дерева
Шаблон для класса «стек»:
template class STACK
{ Item * S; int t;
public:
STACK(int maxt) : S(new Item[ maxt ]), t( 0 ) { }
int empty( ) const { return t == 0; }
void push(Item item) { S[t++] = item; }
Item pop( ) {return ( t ? S[ --t ] : 0 ); }
};
Шаблон для класса «очередь»:
template class QUEUE
{ Item * Q; int h, t, N;
public:
QUEUE(int maxQ): h(0), t(0), N(maxQ), Q(new Item[maxQ + 1]) { }
int empty( ) const { return (h % N) == t; }
void push(Item item) { Q[ t++ ] = item; t %= N; }
Item pop( ) { h %= N; return Q[ h++ ]; }
};
Нерекурсивный обход дерева способом «в глубину»:
int Tree :: DFS( )
{ const int MaxS = 20; // максимальный размер стека
int count = 0;
STACK S(MaxS); //создание стека указателей на узлы
S.push(root); // STACK <- root
while (!S.empty( )) // Пока стек не пуст…
{ Node * v = S.pop( ); // поднять узел из стека
cout << v->d << '_'; count++; // выдать тег, счет узлов
if (v->rgt) S.push(v->rgt); // STACK <- (правый сын)
if (v->lft) S.push(v->lft); // STACK <- (левый сын)
}
return count;
}
Замена стека очередью — нерекурсивный обход «в ширину»:
int Tree :: BFS( )
{ const int MaxQ = 20; //максимальный размер очереди
int count = 0;
QUEUE < Node * > Q(MaxQ); //создание очереди указателей на узлы
Q.push(root); // QUEUE <- root поместить в очередь корень дерева
while (!Q.empty( )) //пока очередь не пуста
{ Node * v = Q.pop( );// взять из очереди,
cout << v->d << '_'; count++; // выдать тег, счет узлов
if (v->lft) Q.push(v->lft); // QUEUE <- (левый сын)
if (v->rgt) Q.push(v->rgt); // QUEUE <- (правый сын)
}
return count;
}
Пример программы для создания случайного дерева, выдачи его на экран и обхода двумя способами с подсчетом мощности дерева:
int main( )
{ int n = 0;
Tree Tr('a', 'z', 8);
srand(time(nullptr));
setlocale(LC_ALL, "Russian");
Tr.MakeTree( );
if ( Tr.exist( ) ) {
Tr.OutTree( );
cout << ‘\n’ << "Обход в глубину: ";
n = Tr.DFS( );
cout << " Пройдено узлов = " << n;
cout << ‘\n’ << "Обход в ширину: ";
n = Tr.BFS( );
cout << " Пройдено узлов = " << n;
}
else cout << "Дерево пусто!";
cout << ‘\n’ << "=== Конец ==="; cin.get( );
}
Результат работы программы может выглядеть так:
3.5. Другие способы обхода дерева
Поскольку дерево — частный случай графа, способы хранения графа в памяти в принципе пригодны и для дерева (см. гл. 4). Деревом также можно объявить массив с произвольным содержимым, если принять соглашение: для любого i-того элемента массива-дерева его сыновьями будут элементы в позициях (i+1)*2–1 и (i+1)*2 (счет позиций от 0), а отцом — элемент в позиции ∟(i/2). Такое дерево (двоичное) однозначно определяется его мощностью n. Для троичного дерева в формулах нужно 2 заменить на 3.
Для дерева с такой формой представления возможен обход как простой перебор элементов массива циклом по позициям от 0 до n.
При применении произвольной перестановки индексов массива получается случайный обход. О генерации перестановок см. выше пп. 1.3.3 и 1.3.4.
3.6. Практикум по гл. 3
1. Написать и отладить программу для работы с деревьями по предложенному преподавателем варианту индивидуального задания (табл. П.2.2). Программа должна выводить на экран изображение дерева с разметкой его вершин, сделанной заданным способом, а под ним — последовательность меток вершин при обходе дерева и результат вычисления заданного параметра. Можно взять за основу учебный пример, убрав из него все лишнее.
2. Сделать узел дерева и дерево в целом объектами соответствующих классов, а обходы дерева — функциями-членами для класса «дерево».
3. Объявить в классе «дерево» деструктор и все конструкторы, поддерживаемые по умолчанию. Сделать невозможным использование тех конструкторов, которые на самом деле не нужны. Сделать в тексте программы временные дополнения и убедиться, что это действительно так.
3.8. Отчет по гл. 3
По темам гл. 3 должен быть оформлен сводный отчет:
1. Цель работы: исследование алгоритмов для работы с двоичным (троичным) деревом.
2. Задание на работу с деревьями.
3. Обоснование выбора способа представления деревьев в памяти ЭВМ. Здесь следует сделать ссылку на выводы в отчетах по разд. 1 и 2.
4. Результаты прогона программы с генерацией случайного дерева (скриншоты).
5. Последовательность битов, вводом которой можно построить дерево, полученное в результате генерации (например, дерево на рисунке выше может быть получено вводом последовательности «111011001001001110010 100100»).
6. Оценки временной сложности для каждой функции обхода дерева, использованной в программе: создание дерева, обработка, вывод.
7. Выводы о результатах испытания алгоритмов обхода деревьев.
8. Приложение: исходный текст программы для работы с деревьями.
Индивидуальные задания к гл. 3
табл. П.2.2
№ вар-та
|
Вид
дерева
|
Разметка
|
Способ обхода
|
Что надо вычислить
|
10
|
Двоичное
|
Симметричная
|
В глубину
|
Количество вершин, имеющих не более одного потомка
|
|
|
|
|
|
|
| |
Скачать 100.24 Kb.