Найти поддерево двоичного поиска с максимальным количеством элементов - C (СИ)
Формулировка задачи:
Написать программу, которая формирует произвольно бинарное дерево,
выводит построенное дерево на экран и затем в сформированном дереве
находит поддерево двоичного поиска с максимальным количеством элементов.
Перед завершением работы программы освободить занимаемую динамическую память.
Для этого используйте поэлементарное удаление элементов динам. структуры данных.
Решение задачи: «Найти поддерево двоичного поиска с максимальным количеством элементов»
textual
Листинг программы
#include <stdio.h> #include <stdlib.h> #include <time.h> typedef struct tree_t { int value; struct tree_t* left; struct tree_t* right; } TTree; typedef struct stack_t { int value; struct stack_t* next; } TStack; //----------------------------------------------------------------------------- // Функция добавления элемента в дерево // В качестве аргумента принимает адрес указателя на дерево и // добавляемое значение void PushTree(TTree** tree, int value) { // Если указатель по заданном адресу есть if (*tree) { // Сравниваем значение узла с добавляемым элементом // Если значение больше, то вызываем функцию Push // передавая ей правое поддерево. Если же значение меньше, // то передаём левое поддерево. if ((*tree)->value < value) { PushTree(&(*tree)->right, value); } else if ((*tree)->value > value) { PushTree(&(*tree)->left, value); } } else { // Создаём новый узел *tree = malloc(sizeof(TTree)); (*tree)->value = value; (*tree)->left = (*tree)->right = NULL; } } //----------------------------------------------------------------------------- // Функция добавления элемента в стек void PushStack(TStack** stack, int value) { TStack* node = malloc(sizeof(TStack)); node->value = value; node->next = *stack; *stack = node; } //----------------------------------------------------------------------------- // Функция удаления/выдавливания элемента из стек void PopStack(TStack** stack) { TStack* node = *stack; *stack = node->next; free(node); } //----------------------------------------------------------------------------- // Функция клонирования/дублирования стека void CloneStack(TStack** dest, const TStack* src) { if (src) { CloneStack(dest, src->next); PushStack(dest, src->value); } } //----------------------------------------------------------------------------- // Рекурсивный вывод всех элементов дерева. // Обход осуществляется в прямом порядке. void PrintTree(const TTree* tree) { if (tree) { printf("%d ", tree->value); PrintTree(tree->left); PrintTree(tree->right); } } //----------------------------------------------------------------------------- // Функция вывода всех элементов стека void PrintStack(const TStack* stack) { if (stack) { printf("%d ", stack->value); PrintStack(stack->next); } } //----------------------------------------------------------------------------- // Рекурсивное удаление всех элементов дерева void ClearTree(TTree* tree) { if (tree) { ClearTree(tree->left); ClearTree(tree->right); free(tree); } } //----------------------------------------------------------------------------- // Функция удаления всех элементов из стека void ClearStack(TStack* stack) { if (stack) { ClearStack(stack->next); PopStack(&stack); } } //----------------------------------------------------------------------------- // Функция нахождения самой высокой ветви дерева // В качестве аргументов получает само дерево; // указатель на максимальное значение (значение по указателю обязательно // должно быть равно нулю); адрес указателя стека (значение указателя // обязательно должно быть равно NULL) int MaxLenBranch(TTree* tree, int* max, TStack** stack) { // Текущая высота static int len = 0; // Текущий "маршрут", т.е. список элементов текущей ветви static TStack* buff = NULL; if (tree) { // Увеличиваем высоту/длину на 1 len++; // Помещаем текущий узел в список элементов ветви PushStack(&buff, tree->value); // Идём по левой ветви MaxLenBranch(tree->left, max, stack); // Идём по правой ветви MaxLenBranch(tree->right, max, stack); // Если высота/длина текущей ветви оказалась выше/длинней предыдущей то if (*max < len) { //сохраняем текущую высоту/длину *max = len; // Очищаем ранее сохранённую ветвь/"маршрут" ClearStack(*stack); // Подготавливаем указатель для клонирования новой ветви/"маршрута" *stack = NULL; // Клонируем список элементов данной ветви CloneStack(stack, buff); } // Удаляем текущий узел из списка элементов ветви PopStack(&buff); // Уменьшаем высоту/длину на 1 len--; } return *max; } //----------------------------------------------------------------------------- int main() { TTree* tree = NULL; int i = 10; int max = 0; TStack* stack = NULL; srand(time(NULL)); // Заполняем дерево случайными элементами while (i--) { PushTree(&tree, rand() % 90 + 10); } // Выводи на экран поддерево PrintTree(tree); // Находим самую высокую/длинную ветвь MaxLenBranch(tree, &max, &stack); // Выводим высоту/длину ветви printf("\nmax = %d\n", max); // Выводи на экран саму ветвь PrintStack(stack); // Удаляем все элементы стека ClearStack(stack); // Удаляем все элементы дерева ClearTree(tree); return 0; }
Объяснение кода листинга программы
- Структура дерева:
- тип: TTree
- поля: value (значение), left (левое поддерево), right (правое поддерево)
- Структура стека:
- тип: TStack
- поля: value (значение), next (следующий элемент)
- Функция добавления элемента в дерево: PushTree
- аргументы: адрес указателя на дерево, значение
- действия:
- если указатель по заданном адресу есть
- сравнить значение узла с добавляемым элементом
- если значение больше, то вызвать функцию PushTree для правого поддерева
- если значение меньше, то вызвать функцию PushTree для левого поддерева
- возвращает: ничего
- Функция добавления элемента в стек: PushStack
- аргументы: адрес указателя на стек, значение
- действия:
- создать новый узел
- заполнить поля нового узла
- вставить новый узел в стек
- возвращает: ничего
- Функция удаления/выдавливания элемента из стека: PopStack
- аргументы: адрес указателя на стек
- действия:
- сохранить указатель на вершину стека
- удалить верхний элемент стека
- вернуть указатель на вершину стека
- Функция клонирования/дублирования стека: CloneStack
- аргументы: адрес указателя на целевой стек, адрес указателя на исходный стек
- действия:
- рекурсивно вызвать функцию CloneStack для клонирования следующего элемента исходного стека
- добавить скопированный элемент в целевой стек
- возвращает: ничего
- Рекурсивный вывод всех элементов дерева: PrintTree
- аргументы: адрес указателя на дерево
- действия:
- если дерево есть
- вывести значение дерева
- рекурсивно вызвать функцию PrintTree для левого поддерева
- рекурсивно вызвать функцию PrintTree для правого поддерева
- возвращает: ничего
- Функция вывода всех элементов стека: PrintStack
- аргументы: адрес указателя на стек
- действия:
- если стек не пустой
- вывести значение вершины стека
- рекурсивно вызвать функцию PrintStack для следующего элемента стека
- возвращает: ничего
- Рекурсивное удаление всех элементов дерева: ClearTree
- аргументы: адрес указателя на дерево
- действия:
- если дерево есть
- рекурсивно вызвать функцию ClearTree для левого поддерева
- рекурсивно вызвать функцию ClearTree для правого поддерева
- освободить память, выделенную под дерево
- возвращает: ничего
- Функция удаления всех элементов из стека: ClearStack
- аргументы: адрес указателя на стек
- действия:
- если стек не пустой
- удалить верхний элемент стека
- рекурсивно вызвать функцию ClearStack для следующего элемента стека
- возвращает: ничего
- Функция нахождения самой высокой ветви дерева: MaxLenBranch
- аргументы: адрес указателя на дерево, адрес указателя на максимальное значение, адрес указателя на стек
- действия:
- инициализировать переменные len (текущая высота) и buff (список элементов ветви)
- рекурсивно вызвать функцию MaxLenBranch для левого поддерева
- рекурсивно вызвать функцию MaxLenBranch для правого поддерева
- сравнить текущую высоту с максимальным значением
- если текущая высота больше максимального значения
- очистить ранее сохраненную ветвь и стек
- клонировать новую ветвь и поместить ее в стек
- вернуть максимальное значение
- возвращает: максимальное значение
- Основная функция:
- действия:
- заполнить дерево случайными элементами
- вывести поддерево на экран
- найти самую высокую ветвь и вывести ее на экран
- удалить все элементы стека и дерева
- возвращает: 0
- действия:
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д