Вывод изображения дерева на экран монитора

Чтобы получить наглядное представление о способе разметки дерева, нужно вывести его на экран в виде диаграммы. Можно обойтись для этого текстовым режимом, если принять следующее соглашение. В середине первой строки текста вывести метку корня дерева. В следующей строке — расположить метки левого и правого сыновей в серединах левой и правой половины строки и т. д. Если дерево — троичное, метку среднего сына можно разместить прямо под корнем, и т. д., уменьшая смещение сыновей относительно корня в два раза по отношению к предыдущему ряду. Удобно воспользоваться рекурсивной функцией обхода дерева, которая выдаёт метку узла в некоторой точке экрана (r, c), а для сыновей добавляет 1 к номеру ряда и смещения к номеру столбца. Смещение удобно вычислять сдвигом некоторой константы offset на номер ряда, который совпадает с глубиной узла.

Для выдачи метки в нужную точку экрана можно использовать функцию позиционирования курсора gotoxy(r, c) из библиотеки conio.h, предварительно очистив экран функцией clrscr(). Но поскольку эти функции есть не во всех оболочках, можно обойтись без них, использовав промежуточную буферную память в виде матрицы символов, как это сделано ниже в примере.

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

Функция-член для вывода изображения дерева на экран может выглядеть так:

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)); //правый сын

}

}

Затем матрица символов построчно выводится на экран.

2.4. Шаблоны классов для очереди и стека
и нерекурсивные алгоритмы обхода дерева

Шаблон для класса «стек»:

template <class Item> 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 Item> 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 put(Item item) { Q[ t++ ] = item; t %= N; }

Item get() { h %= N; return Q[ h++ ]; }

};

Нерекурсивный обход дерева способом «в глубину»:

int Tree:: DFS()

{ const int MaxS=20; // максимальный размер стека

int count = 0;

STACK <Node *> S(MaxS); //создание стека указателей на узлы

S.push(root); // QUEUE <- v

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.put(root); // QUEUE <- root поместить в очередь корень дерева

while (!Q.empty()) //пока очередь не пуста

{ Node * v = Q.get();// взять из очереди,

cout << v->d << '_'; count++; // выдать тег, счёт узлов

if (v->lft) Q.put(v->lft); // QUEUE <- (левый сын)

if (v->rgt) Q.put(v->rgt); // QUEUE <- (правый сын)

}

return count;

}

Пример программы для создания случайного дерева, выдачи его на экран и обхода двумя способами с подсчётом мощности дерева:

void main()

{ int n = 0;

Tree Tr('a', 'z', 8);

srand(time(NULL));

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’ << "=== Конец ===";

_getch();

}

Результат работы программы может выглядеть так:

2.4.1. Практикум по теме

1. Написать и отладить программу для работы с деревьями по предложенному преподавателем варианту индивидуального задания. Программа должна выводить на экран изображение дерева с разметкой его вершин, сделанной заданным способом, а под ним — последовательность меток вершин при обходе дерева и результат вычисления заданного параметра. Можно взять за основу учебный пример.

2. Сделать узел дерева и дерево в целом объектами соответствующих классов, а обходы дерева — методами для этого класса.

3. Объявить в классе «дерево» деструктор и все конструкторы, поддерживаемые по умолчанию. Сделать невозможным использование тех конструкторов, которые на самом деле не нужны. Сделать в тексте программы временные дополнения и убедиться, что это действительно так.

2.4.2. Варианты индивидуальных заданий к теме «Деревья»

№ вари- анта	Вид дерева	Разметка	Способ обхода	Что надо вычислить
	Двоичное	Обратная	В глубину	Высоту дерева
	Двоичное	Прямая	В ширину	Количество листьев
	Троичное	Обратная	Внутрен­ний	Количество вершин, имеющих хотя бы одного потомка
	Троичное	Прямая	В ширину	Общее количество вершин

Продолжение таблицы

№ вари- анта	Вид дерева	Разметка	Способ обхода	Что надо вычислить
	Двоичное	Симмет­рич­ная	В ширину	Количество вершин, имеющих не более одного потомка
	Двоичное	Обратная	Внутрен­ний	Количество вершин на глубине больше 2
	Троичное	Ширинная	В глубину	Количество вершин, имеющих ровно одного потомка
	Троичное	Обратная	В ширину	Количество вершин, имеющих хотя бы одного потомка
	Двоичное	Прямая	Внутрен­ний	Количество вершин на уровне не больше 2
	Двоичное	Симмет­рич­ная	В глубину	Количество вершин, имеющих не более одного потомка
	Троичное	Прямая	В ширину	Высоту дерева
	Троичное	Обратная	Внутрен­ний	Количество правых листьев
	Двоичное	Симмет­рич­ная	В глубину	Количество вершин на глубине не более 2
	Двоичное	Симмет­рич­ная	В глубину	Количество потомков у каждой из вершин
	Троичное	Прямая	Внутрен­ний	Количество вершин, имеющих не более двух потомков
	Троичное	Обратная	Внутрен­ний	Высоту левого поддерева для корня
	Двоичное	Обратная	В глубину	Количество левых листьев
	Двоичное	Ширинная	Внутрен­ний	Количество вершин на самом нижнем уровне
	Троичное	Глубинная	Внутрен­ний	Количество вершин не на самом нижнем уровне
	Троичное	Обратная	В глубину	Количество вершин, имеющих не более трёх потомков
	Двоичное	Прямая	Внутрен­ний	Высоту правого поддерева для корня
	Двоичное	Обратная	Внутрен­ний	Количество листьев на самом нижнем уровне, имеющем листья
	Троичное	Симмет­рич­ная	В глубину	Количество средних листьев
	Троичное	Прямая	В ширину	Количество предков для каждой из вершин
	Двоичное	Обратная	Внутрен­ний	Количество вершин, имеющих не более двух потомков
	Троичное	Симмет­рич­ная	В глубину	Количество листьев не на самом нижнем уровне, имеющем листья
	Троичное	Прямая	В ширину	Высоту среднего поддерева для корня
	Двоичное	Обратная	Внутрен­ний	Количество предков для каждой из вершин

Окончание таблицы

№ вари- анта	Вид дерева	Разметка	Способ обхода	Что надо вычислить
	Двоичное	Обратная	В глубину	количество вершин на глубине не более 3
	Троичное	Симмет­рич­­ная	В ширину	количество вершин, имеющих не более двух потомков
	Двоичное	Симмет­рич­ная	В глубину	количество вершин на глубине не более 2
	Двоичное	Симмет­рич­ная	В ширину	количество потомков у каждой из вершин
	Троичное	Прямая	В ширину	высоту дерева
	Троичное	Обратная	Внутрен­ний	количество правых листьев
	Двоичное	Обратная	Прямой	количество левых листьев
	Двоичное	Симмет­рич­ная	В ширину	количество вершин на самом нижнем уровне
	Троичное	Глубинная	Внутрен­ний	количество вершин, имеющих не более двух потомков
	Троичное	Обратная	Внутрен­ний	высоту левого поддерева для корня
	Двоичное	Прямая	В ширину	высоту правого поддерева для корня
	Двоичное	Обратная	Внутрен­ний	количество листьев на самом нижнем уровне
	Троичное	Глубинная	Внутрен­ний	количество вершин на самом нижнем уровне
	Троичное	Обратная	В глубину	количество вершин, имеющих не более трёх потомков
	Двоичное	Обратная	Внутрен­ний	количество вершин, имеющих не менее одного потомка
	Троичное	Симмет­рич­ная	В глубину	количество листьев не на самом нижнем уровне
	Троичное	Симмет­рич­ная	В глубину	количество средних листьев
	Троичное	Прямая	В ширину	количество предков для каждой из вершин
	Двоичное	Обратная	В глубину	количество вершин на глубине не более 3
	Троичное	Симмет­рич­ная	В ширину	количество вершин, имеющих не менее двух потомков
	Троичное	Прямая	В ширину	высоту среднего поддерева для корня
	Двоичное	Обратная	В глубину	количество вершин на глубине не более 4

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

1. Чем отличаются алгоритмы для разных способов обхода деревьев?

2. Нужно ли сочетать ввод данных для построения дерева с клавиатуры с его обходом?

3. Можно ли считать применённые вами алгоритмы обхода дерева эффективными?

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

Отчёт по теме

По теме должен быть оформлен сводный отчёт следующего содержания:

1. Задание на работу с деревьями.

2. Обоснование выбора способа представления деревьев в памяти ЭВМ.

3. Тестовый пример: изображение дерева и порядок его ввода с клавиатуры.

4. Результаты прогона программы с генерацией случайного дерева (скриншоты).

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

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

7. Список использованной литературы (при ссылке на конспект лекций — указать дату лекции).

8. Приложение: исходный текст программы для работы с деревьями (на машинном носителе).

ГРАФЫ

Граф — это пара множеств G = <V, E>, где V — произвольное множество, а E = {{u, v}: u, v ∈ V, u ≠ v} — множество пар из элементов множества V. Если пара {u, v} представляет собой множество мощностью 2, граф называется неориентированным, а если это последовательность <u, v> — ориентированным. Будем обозначать мощность множества вершин |V| = n, а мощность множества рёбер |E| = m. Очевидно, что справедливо ограничение m = O (n²).

Вершины {u, v}, образующие ребро, называются смежными, а само ребро — инцидентным по отношению к образующим его вершинам, а вершины, в свою очередь, инцидентны ребру. Количество рёбер, инцидентных вершине, называется её степенью. Вершина, не входящая ни в одно ребро, имеет степень 0 и называется изолированной. В ориентированном графе различают также количество рёбер, входящих в вершину — полустепень захода — и количество выходящих рёбер — полустепень выхода.

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

Если любая пара вершин графа связана путём, граф называется связным. Если для любой пары вершин находятся, по крайней мере, два пути, множества вершин которых не пересекаются, граф — двусвязный.

В ориентированном графе (орграфе) путь между некоторыми вершинами может быть только в одну сторону. Если же любая пара вершин орграфа связана путями в обе стороны, такой граф называется сильно связным.

Граф с пустым множеством вершин называется пустым, а граф, в котором имеются все возможные рёбра — полным графом или кликой.

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

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

Графы G = <V, E> и G' = <V', E'> называются изоморфными, если существует биекция f: E→E' такая, что для любой пары вершин {u, v} ∈ E ⬄ {f(u), f(v)} ∈ E'.

На свойстве изоморфизма строятся все возможные способы хранения графа в памяти. Перечислим наиболее употребительные из них.

1. Вершины хранятся в массиве, каждый элемент которого — множество рёбер в форме вектора битов. Единичные биты соответствуют рёбрам, инцидентным данной вершине. Альтернатива — массив рёбер, каждое из которых задано вектором инцидентных вершин, которых может быть ровно две. Это — матрица инциденций размером m × n. Это расточительный способ, потому что матрица большей частью состоит из нулей. Но он достаточно компактен и удобен для некоторых задач, например, для отыскания вершинного или рёберного покрытия. Способ является естественным для неориентированного графа. Для орграфа нужно различать начала и концы рёбер, например, так: «–1» — ребро выходит из вершины, «+1» — ребро входит, «2» — и входит, и выходит (петля).

2. Вершины хранятся в массиве, каждый элемент которого — множество смежных вершин в форме вектора битов. Это матрица смежности размерами n × n, она может содержать 0 и 1 в любой пропорции. Так, полному графу соответствует единичная матрица. Способ удобен для орграфов. Неориентированные графы хранятся как дважды ориентированные, т. е. их матрица смежности всегда симметрична; она может храниться только верхним треугольником.

3. Вершины хранятся в массиве, каждый элемент которого — множество смежных вершин в форме списка. Каждый элемент списка содержит поле с номером смежной вершины — индексом массива вершин. Это — списки смежности. Они удобны, если количество рёбер в графе не очень велико, и требуют памяти порядка O(n + m).

4. Массив рёбер, каждое из которых задано парой номеров инцидентных вершин, — массив пар. Требует 2 × m ячеек памяти.

5. Разветвляющийся список из вершин, в котором рёбра реализованы посредством указателей. Этот способ применяется главным образом для ациклических орграфов (деревьев), а в общем случае малопригоден без каких-либо дополнений.