Содержание
Краткая постановка задания
Необходимо написать модуль, содержащий решения $16$ задач для работы с бинарными деревьями, и программу, демонстрирующую работу этого модуля. Программа должна быть выполнена либо в качестве консольного приложения (тогда обязателен командно-текстовый интерфейс), либо иметь графический интерфейс пользователя.
При необходимости можно использовать вспомогательные функции. В разработанном модуле не должны применяться интерфейсные функции (исключение возможно только для функций вывода дерева).
Комментарий от разработчиков программы
Мы частично разработали решение данной задачи для всех студентов, изучающих данную тему. Программа реализована в среде MS Visual Studio на языке программирования C++ (консольный проект).
В коде учтены все пожелания и требования к данной задаче, выдвигаемые составителями. Соблюдены названия переменных, порядок выполнения операторов и пр.нюансы.
Закодированы следующие операции над бинарным деревом поиска:
№ | Смысл операции | Название функции в коде |
1 | Создание бинарного дерева поиска. Формируется бинарное дерево поиска, состоящее из $n$ элементов ($n$ вводится с клавиатуры). | void MakeBinaryTree(bintree** proot, const int pn) |
2 | Добавление узла в бинарное дерево поиска. Пользователь вводит число, необходимо добавить его в дерево, руководствуясь принципами построения бинарного дерева поиска. | void Insert(bintree** proot, const int pinf) |
3 | Вывод бинарного дерева. Элементы дерева необходимо вывести в порядке возрастания ключей узлов. Реализован симметричный обход дерева (ЛКП). Способ вывода простой, а не «красивый». | void LKP(bintree* proot) |
4 | Поиск образца в бинарном дереве. | bool SearchNodeByKey(bintree* proot, const int pkey) |
5 | Подсчет количества узлов дерева. Использовать для решения подзадачи рекурсивный алгоритм. | int GetCountNodes(bintree* proot) |
6 | Подсчет числа листьев дерева. Использовать для решения подзадачи рекурсивный алгоритм. | int GetCountLeaves(bintree* proot) |
7 | Генерация случайного целого числа на заданном отрезке. | int irand(const int pa, const int pb) |
8 | Ввод с клавиатуры значения ключа добавляемого узла. | int InputIntValue(void) |
9 | Создание узла бинарного дерева поиска с заданным ключом. | bintree* CreateNode(const int pinf) |
10 | Проверка добавляемого узла на дубликатность. | bool IsUniqueValueInsert(bintree* proot, const int pinf) |
11 | Вывод бинарного дерева. Реализован прямой обход дерева (КЛП). | void KLP(bintree* proot) |
12 | Вывод бинарного дерева. Реализован обратный обход дерева (ЛПК). | void LPK(bintree* proot) |
13 | Удаление всех узлов из бинарного дерева (полная очистка дерева). | void RemoveBinaryTree(bintree** proot) |
14 | Главная функция программы (точка входа). | int main(void) |
Операции, имеющие желтоватый фон, — вспомогательные операции, которые так или иначе были использованы при кодировании основных операций обработки бинарного дерева поиска.
Стоимость доработки программы
№ | Операция | Консольный формат | Визуальный формат |
1. | Создание бинарного дерева поиска из $n$ элементов. | Бесплатно (см.реализацию ниже) | $250$ рублей |
2. | Добавление узла в бинарное дерево поиска. | Бесплатно (см.реализацию ниже) | $250$ рублей |
3. | Вывод бинарного дерева в порядке возрастания ключей его элементов («красивый» формат). | $400$ рублей | $700$ рублей |
4. | Поиск образца в бинарном дереве поиска. | Бесплатно (см.реализацию ниже) | $250$ рублей |
5. | Подсчет количества узлов дерева. | Бесплатно (см.реализацию ниже) | $150$ рублей |
6. | Подсчет числа листьев дерева. | Бесплатно (см.реализацию ниже) | $150$ рублей |
7. | Расчет степени вершины, используя рекурсивный обход. | $100$ рублей | $250$ рублей |
8. | Расчет уровня вершины. | $100$ рублей | $250$ рублей |
9. | Расчет высоты дерева. | $100$ рублей | $250$ рублей |
10. | Поиск образца в бинарном дереве (любом дереве). | $100$ рублей | $250$ рублей |
11. | Удаление узла дерева с поддеревом. | $100$ рублей | $250$ рублей |
12. | Удаление всего дерева (с использованием п.11). | $100$ рублей | $250$ рублей |
13. | Удаление узла с перестройкой дерева. | $250$ рублей | $600$ рублей |
14. | Обход дерева в глубину (не рекурсивный). Требуется использовать стек, реализованный в предыдущей лабораторной работе. | $200$ рублей, если стек уже закодирован. $700$ рублей, если стек не закодирован и его нужно кодировать. | $500$ рублей, если стек уже закодирован. $1\ 200$ рублей, если стек не закодирован и его нужно кодировать. |
15. | Обход дерева в ширину (не рекурсивный). Требуется использовать очередь, реализованную в предыдущей лабораторной работе. | $200$ рублей, если очередь уже закодирована. $700$ рублей, если очередь не закодирована и ее нужно кодировать. | $500$ рублей, если очередь уже закодирована. $1\ 200$ рублей, если очередь не закодирована и ее нужно кодировать. |
16. | Балансировка дерева. | $500$ рублей | $900$ рублей |
Данная работа предполагает написание программы на языке C++. При заказе нужных вам операций над бинарным деревом поиска вы получите качественно написанную и хорошо прокомментированную программу.
➡ Дополнительно заказав алгоритм решения задачи (мы крайне рекомендуем это сделать), получите аккуратно оформленный отчет-алгоритм, поясняющий все тонкости решения поставленной задачи.
Структура проекта
В результате частичного кодирования данной задачи получился проект, состоящий из $3$ файлов:
- tree.h — пользовательские описания (типы данных и прототипы функций).
- tree.cpp — модуль для работы с бинарным деревом поиска.
- source.cpp — программа, демонстрирующая работу модуля tree.cpp.
Реализация задачи на языке С++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | #ifndef _TREE_H_ #define _TREE_H_ //-------------------------------------------------------------------------- // структура "Узел бинарного дерева поиска" //-------------------------------------------------------------------------- struct bintree { int inf; // ключевое значение узла дерева bintree* left; // указатель на левое поддерево bintree* right; // указатель на правое поддерево }; //-------------------------------------------------------------------------- void RemoveBinaryTree(bintree** proot); // создание узла бинарного дерева поиска с заданным ключом bintree* CreateNode(const int pinf); // проверка на дубликатность узла при добавлении bool IsUniqueValueInsert(bintree* proot, const int pinf); void Insert(bintree** proot, const int pinf); // добавление узла в бинарное дерево поиска // генерация случайного числа на заданном отрезке int irand(const int pa, const int pb); // построение бинарного дерева поиска, состоящего из n узлов void MakeBinaryTree(bintree** proot, const int pn); void LKP(bintree* proot); // симметричных обход дерева void KLP(bintree* proot); // прямой обход дерева void LPK(bintree* proot); // обратный обход дерева // поиска образца в дереве (поиск по ключу узла) bool SearchNodeByKey(bintree* proot, const int pkey); int GetCountNodes(bintree* proot); // подсчет узлов дерева int GetCountLeaves(bintree* proot); // подсчет узлов-листьев дерева void RemoveBinaryTree(bintree** proot); // удаление всех узлов из дерева #endif |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 | #include <iostream> #include <iomanip> #include "tree.h" using namespace std; //-------------------------------------------------------------------------- // удаление всех узлов дерева (очистка дерева) //-------------------------------------------------------------------------- void RemoveBinaryTree(bintree** proot) { if(*proot != NULL) { RemoveBinaryTree(&((*proot)->left)); RemoveBinaryTree(&((*proot)->right)); // текущий удаляемый узел гарантировано является листом delete *proot; *proot = NULL; } } //-------------------------------------------------------------------------- // создание узла бинарного дерева поиска с заданным ключом //-------------------------------------------------------------------------- bintree* CreateNode(const int pinf) { bintree* node = new bintree; node->inf = pinf; node->left = node->right = NULL; return node; } //-------------------------------------------------------------------------- // проверка на дубликат ключа узла дерева // false - добавляемый узел уже присутствует в дереве // true - добавляемый узел отсутствует в дереве //-------------------------------------------------------------------------- bool IsUniqueValueInsert(bintree* proot, const int pinf) { // "прошли" все дерево, не встретив дубликатного значения if(proot == NULL) return true; // встали на узел, имеющий такой же ключ (встретили дубликат) if(pinf == proot->inf) return false; // продвигаемся по дереву if(pinf < proot->inf) return IsUniqueValueInsert(proot->left, pinf); else return IsUniqueValueInsert(proot->right, pinf); } //-------------------------------------------------------------------------- // добавление узла в бинарное дерево поиска //-------------------------------------------------------------------------- void Insert(bintree** proot, const int pinf) { if(*proot == NULL) *proot = CreateNode(pinf); else if(pinf < (*proot)->inf) Insert(&((*proot)->left), pinf); else Insert(&((*proot)->right), pinf); } //-------------------------------------------------------------------------- // генерация случайного целого числа на заданном отрезке //-------------------------------------------------------------------------- int irand(const int pa, const int pb) { return (rand() % (pb - pa + 1) + pa); } //-------------------------------------------------------------------------- // создание бинарного дерева поиска, состоящего из n узлов //-------------------------------------------------------------------------- void MakeBinaryTree(bintree** proot, const int pn) { // если дерево было сформировано раньше, то сначала нужно // удалить все узлы "старого" дерева, а потом создавать новое if(*proot != NULL) RemoveBinaryTree(proot); for(int i = 1; i <= pn; i++) { int key = irand(-100, 100); // пытаемся добавлять узел до тех пор, пока не будет сгенерирован уникальный ключ while(IsUniqueValueInsert(*proot, key) == false) key = irand(-100, 100); // гарантировано добавляем в дерево узел с уникальным ключом Insert(proot, key); } } //-------------------------------------------------------------------------- // вывод ключей узлов дерева по возрастанию (симметричный обход) //-------------------------------------------------------------------------- void LKP(bintree* proot) { if(proot != NULL) { LKP(proot->left); cout << setw(8) << proot->inf; LKP(proot->right); } } //-------------------------------------------------------------------------- // прямой порядок обхода (корень-влево-вправо) //-------------------------------------------------------------------------- void KLP(bintree* proot) { if(proot != NULL) { cout << setw(8) << proot->inf; KLP(proot->left); KLP(proot->right); } } //-------------------------------------------------------------------------- // обратный порядок обхода (влево-вправо-корень) //-------------------------------------------------------------------------- void LPK(bintree* proot) { if(proot != NULL) { LPK(proot->left); LPK(proot->right); cout << setw(8) << proot->inf; } } //-------------------------------------------------------------------------- // поиска образца в дереве по заданному ключу узла //-------------------------------------------------------------------------- bool SearchNodeByKey(bintree* proot, const int pkey) { if(proot == NULL) return false; if(proot->inf == pkey) return true; if(pkey < proot->inf) return (SearchNodeByKey(proot->left, pkey)); else return (SearchNodeByKey(proot->right, pkey)); } //-------------------------------------------------------------------------- // подсчет количество узлов дерева (рекурсивный обход) //-------------------------------------------------------------------------- int GetCountNodes(bintree* proot) { if(proot == NULL) return 0; else return GetCountNodes(proot->left) + GetCountNodes(proot->right) + 1; } //-------------------------------------------------------------------------- // подсчет количество узлов-листьев дерева (рекурсивный обход) //-------------------------------------------------------------------------- int GetCountLeaves(bintree* proot) { if(proot == NULL) return 0; if((proot->left == NULL) && (proot->right == NULL)) return 1; else return (GetCountLeaves(proot->left) + GetCountLeaves(proot->right)); } //-------------------------------------------------------------------------- |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 | #include <iostream> // для ввода, вывода (cin, cout), а также NULL #include <time.h> // для использования функции (time) #include <iomanip> // для форматированного вывода (setw) #include <Windows.h> // для заголовка программы #include "tree.h" // заголовочный файл с описание операций над деревом using namespace std; //-------------------------------------------------------------------------- // главное меню программы //-------------------------------------------------------------------------- int Menu(void) { int select; do { system("CLS"); cout << "Аббревиатура \'ДДП\' расшифровывается как \'Двоичное Дерево Поиска\'." << endl << endl; cout << "1 - СОЗДАНИЕ ДДП из n элементов" << endl; cout << "2 - ДОБАВЛЕНИЕ УЗЛА В ДДП" << endl; cout << "3 - СИММЕТРИЧНЫЙ ОБХОД ДДП (влево-корень-вправо)" << endl; cout << "4 - ПОИСК ОБРАЗЦА В ДДП" << endl; cout << "5 - ПОДЧСЕТ КОЛИЧЕСТВА УЗЛОВ ДДП" << endl; cout << "6 - ПОДСЧЕТ КОЛИЧЕСТВА УЗЛОВ-ЛИСТЬЕВ ДДП" << endl; cout << "7 - ВЫХОД" << endl; cout << "Выбор: "; cin >> select; } while((select < 1) || (select > 7)); return select; } //-------------------------------------------------------------------------- // ввод с клавиатуры значения ключа добавляемого узла //-------------------------------------------------------------------------- int InputIntValue(void) { int value; cout << endl << "Введите значение ключа добавляемого узла (целое число): "; cin >> value; return value; } //-------------------------------------------------------------------------- // главная функция программы (точка входа) //-------------------------------------------------------------------------- int main(void) { bintree* root = NULL; // указатель на корень дерева setlocale(LC_ALL, "rus"); // руссификация диалогов программы // настройка заголовка консольного окна static const TCHAR* title = TEXT("Практикум на ЭВМ. Структуры данных и алгоритмы. С++. Лабораторная работа №3 (бинарное дерево поиска)"); SetConsoleTitle(title); // чтобы генератор каждый раз возвращал различные числа srand((unsigned)time(0)); int select; do { select = Menu(); switch(select) { case 1: // создание ДДП, состоящего из n узлов { int n; cout << endl << "Введите количество узлов, добавляемых в дерево (> 0): "; cin >> n; MakeBinaryTree(&root, n); cout << "Бинарное дерево поиска, состоящее из " << n << " узлов, успешно сформировано."; break; } case 2: // добавление нового узла в ДДП { int key = InputIntValue(); if(IsUniqueValueInsert(root, key) == false) cout << "Узел с ключом \'" << key << "\' уже присутствует в дереве. Добавление дубликата невозможно!"; else { Insert(&root, key); cout << "Новый узел с ключевым значением \'" << key << "\' успешно добавлен в бинарное дерево поиска."; } break; } case 3: // симметричный обход дерева (влево-корень-вправо) { if(root == NULL) cout << endl << "Бинарное дерево поиска не содержит ни одного узла. Печать невозожна."; else { cout << endl << "Узлы дерева имеют значения: "; LKP(root); } break; } case 4: // поиск образца в бинарном дереве поиска { if(root == NULL) cout << endl << "Бинарное дерево поиска не содержит ни одного узла. Поиск образца невозможен."; else { int sample; cout << endl << "Введите значение образца для поиска (целое число): "; cin >> sample; if(SearchNodeByKey(root, sample) == true) cout << "Узел с заданным ключом присутствует в дереве."; else cout << "Узел с заданным ключом отсутсвует в дереве."; } break; } case 5: { cout << endl << "Двоичное дерево поиска содержит узлов: " << GetCountNodes(root) << " шт."; break; } case 6: { cout << endl << "Двоичное дерево поиска содержит узлов-листьев: " << GetCountLeaves(root) << " шт."; break; } } if(select != 7) { fflush(stdin); cin.get(); } } while(select != 7); // перед выходом из программы следует подчистить память из-под узлов бинарного дерева поиска if(root != NULL) RemoveBinaryTree(&root); return 0; // завершение работы программы и передача управления в ОС } //-------------------------------------------------------------------------- |
Результаты работы программы
№ | Смысл операции и результат |
1 | Попытка получить общее количество узлов в дереве (изначально дерево пустое). |
2 | Добавление узла в дерево с ключом, равным $27$. |
3 | Добавляем последовательно узлы со значениями: $11$, $45$, $33$, $-5$, $21$. После этого печатаем узлы дерева на экран. |
4 | Попытка получить общее количество листьев в дереве. |
5 | Создаем дерево, состоящее из $8$ узлов. |
6 | Печатаем узлы дерева на экран. |
7 | Завершаем работу с программой. |
Варианты индивидуальных заданий их стоимость реализации
Задание для всех вариантов звучит так (или, возможно, немного изменено, так как могут быть разные издания учебного пособия):
За индивидуальную задачу при работе по БРС можно получить до 5 баллов. Для ее решения рекомендуется использовать подготовленный ранее программный модуль.
💡 ВАЖНО!
- Задания обладают не одинаковой сложностью. Есть достаточно нетривиальные операции, требующие кодирования дополнительных функций.
- Стоимость каждой операции обозначена в таблице ниже в самой правкой колонке «Стоимость».
№ | Формулировка | Стоимость |
1. | Определите, есть ли в данном бинарном дереве два одинаковых элемента (дерево не является бинарным деревом поиска). | $350$ рублей |
2. | Выведите номера уровней данного бинарного дерева, на которых имеются листья. | $300$ рублей |
3. | Выведите номера вершин, у которых количество потомков в леввом поддереве не равно количеству потомков в правом поддереве. | $300$ рублей |
4. | Выведите номера вершин, для которых высота левого поддерева не равна высоте правого поддерева. | $250$ рублей |
5. | Выведите номера вершин, у которых количество потомков в левом поддереве отличается от количества потомков в правом поддереве на $1$. | Бесплатно |
6. | Найдите высоту дерева $H$ и удалите из него (с перейстройкой) все вершины на уровне $\frac{H}{2}$. | $500$ рублей |
7. | Найдите минимальный путь между двумя произвольными листьями. | $250$ рублей |
8. | Найдите минимальный путь между двумя произвольными вершинами дерева. | $250$ рублей |
9. | Найдите высоту дерева $H$ и удалите в нем все вершины (с перейстройкой) на глубине $\frac{H}{2}$, у которых высота левого поддерева равна высоте правого поддерева. | $500$ рублей |
10. | Найдите путь максимальной длины и отразите дерево зеркально относительно этого пути. | $400$ рублей |
11. | Найдите путь максимальной длины между двумя произвольными вершинами с разным числом потомков. | $350$ рублей |
12. | Найдите путь максимальной длины между двумя произвольными вершинами разной высоты. | $300$ рублей |
13. | Найдите пути минимальной длины между корнем и листьями. | $300$ рублей |
14. | Определите, являются ли два дерева зеркальным отражением друг друга. | $450$ рублей |
15. | Найдите среднюю по значению вершину в дереве (вершину, у которой значение ближе всего по модулю к среднему арифметическому значений всех вершин). | $300$ рублей |
16. | Найдите вершины, у которых высоты поддеревьев равны, а количество потомков в правом и левом поддеревьях не равны. | $250$ рублей |
17. | Найдите вершины, у которых высоты поддеревьев равны, а количество потомков в правом и левом поддеревьях не равны. | $250$ рублей |
18. | Удалите все вершины, для которых количество потомков в левом поддереве отличается от количества вершин в правом поддереве на $2$ и более. | $250$ рублей |
19. | Удалите все вершины, у которых высота левого поддерева отличается от высоты правого поддерева на $2$. | $250$ рублей |
20. | Выясните, является ли дерево симметричным. | $300$ рублей |
21. | Вычислите количество вершин, для которых высота левого поддерева равна высоте правого поддерева. | $250$ рублей |
22. | Вычислите количество вершин, у которых равны или высоты поддеревьев, или количество потомков в правом и левом поддеревьях. | $250$ рублей |
Лабораторная работа $№3$ предполагает написание программы на языке C++. При заказе работы своего варианта вы получите качественно написанную и хорошо прокомментированную программу.
➡ Дополнительно заказав алгоритм решения вашей задачи (мы крайне рекомендуем это сделать), получите аккуратно оформленный отчет-алгоритм, поясняющий все тонкости решения поставленной задачи.
Образец выполнения (вариант №5)
Условие задания
Выведите номера вершин, у которых количество потомков в левом поддереве отличается от количества потомков в правом поддереве на $1$.
Алгоритм решения задачи
Прежде чем переходить непосредственно к кодированию данного задания, нужно провести его алгоритмизацию. Данный этап является обязательным и ни один профессиональный программист не опускает его в своей работе.
Предположим, что мы получили бинарное дерево поиска следующей конфигурации:
Данное дерево состоит из $12$ узлов, образующих $4$ уровня, кстати, является почти сбалансированным (для решения данной задачи это не важно).
Очевидно, что придется просмотреть все узлы данного дерева. Для этого можно воспользоваться любым из вариантов обхода дерева (прямой, обратный, симметричный). Выбираем симметричный порядок обхода, чтобы при печати номеров вершин они шли по возрастанию.
Далее нужно вспомнить, что в нашем распоряжении (в разработанном ранее модуле для работы с двоичным деревом поиска) есть замечательная функция, подсчитывающая количество узлов в заданном дереве/поддереве:
1 2 3 4 5 6 7 8 9 10 11 | //-------------------------------------------------------------------------- // подсчет количества узлов дерева (рекурсивный обход) //-------------------------------------------------------------------------- int GetCountNodes(bintree* proot) { if(proot == NULL) return 0; else return GetCountNodes(proot->left) + GetCountNodes(proot->right) + 1; } //-------------------------------------------------------------------------- |
➡ Благодаря данной функции мы достаточно просто решим поставленную задачу! Начинаем последовательно сканировать в симметричном порядке все вершины дерева и для каждого узла подсчитывать количество потомков из левого и правого поддерева. Затем сравниваем модуль разности этих количеств на $1$, т к нам не важно, в каком из поддеревьев будет больше потомков на одного, главное, чтобы отличие было строго на один потомок.
Для приведенного дерева оранжевые узлы удовлетворяют этому условию:
Значение вершины | Количество потомков в левом поддереве | Количество потомков в правом поддереве | Разность | Условие |
-7 | 0 | 1 | 1 | |
14 | 0 | 0 | 0 | |
25 | 2 | 2 | 0 | |
36 | 0 | 1 | 1 | |
39 | 0 | 0 | 0 | |
50 | 5 | 6 | 1 | |
61 | 0 | 1 | 1 | |
62 | 0 | 0 | 0 | |
77 | 2 | 3 | 1 | |
94 | 0 | 0 | 0 | |
100 | 1 | 0 | 1 | |
123 | 2 | 0 | 2 |
Реализация задачи на языке С++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 | #include <iostream> // для ввода, вывода (cin, cout) #include <Windows.h> #include "tree.h" // подключаем заголовочный файл с описаниями модуля работы с ДДП using namespace std; // стандартное пространство имен //------------------------------------------------------------------------------- // получаем все вершины дерева, у которых количество потомков в левом поддереве // отличается от количества потомков в правом поддереве на 1 //------------------------------------------------------------------------------- void PrintNodesDifferent_one(bintree* proot) { static const int DIFFERENT = 1; // отличие кол-ва потомков должно быть на 1 if(proot != NULL) { PrintNodesDifferent_one(proot->left); // продвигаемся в левое поддерево // вычисляем количество потомков из левого поддерева int countNodesInLeftSubtree = GetCountNodes(proot->left); // вычисляем количество потомков из правого поддерева int countNodesInRightSubtree = GetCountNodes(proot->right); // выводим на экран значение вершины, удовлетворяющее условию if(abs(countNodesInLeftSubtree - countNodesInRightSubtree) == DIFFERENT) cout << "\t" << proot->inf; PrintNodesDifferent_one(proot->right); // продвигаемся в правое поддерево } } //------------------------------------------------------------------------------- // главная функция программы (точка входа) //------------------------------------------------------------------------------- int main(void) { setlocale(LC_ALL, "rus"); // руссификация диалогов программы // настройка заголовка консольного окна static const TCHAR* title = TEXT("Практикум на ЭВМ. Структуры данных и алгоритмы. С++. Лабораторная работа №3 (бинарное дерево поиска)"); SetConsoleTitle(title); bintree* root = NULL; int count; cout << "Введите количество узлов создаваемого бинарного дерева поиска (> 0): "; cin >> count; for(int i = 1; i <= count; i++) { int key; cout << "\t- введите значение ключа добавляемого узла: "; cin >> key; Insert(&root, key); } cout << endl << "Значения вершин, у которых количество потомков в левом поддереве отличается от " << endl; cout << "\tколичества потомков в правом поддереве на 1: "; // получаем все вершины, удовлетворяющие заданному условию PrintNodesDifferent_one(root); RemoveBinaryTree(&root); // удаляем все узлы из бинарного дерева поиска // задержка программы, чтобы можно было просмотреть результат работы программы cout << endl << endl << "Для завершения работы программы нажмите клавишу ENTER..."; fflush(stdin); cin.get(); return 0; // завершение работы программы и передача управления в ОС } //------------------------------------------------------------------------------- |
Результаты работы программы
➡ Для реализации индивидуального задания $№5$ мы воспользовались лишь одной готовой функцией (GetCountNodes — подсчет количества потомков), обход дерева пришлось кодировать с нуля, т к в модуле нет на $100\%$ подходящей функции обхода бинарного дерева поиска. Также программа, приведенная в задании $№5$, предназначена только для нахождения нужных вершин двоичного дерева поиска.
Добавить комментарий