Найти поддерево двоичного поиска с максимальным количеством элементов - 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;
}

Объяснение кода листинга программы

  1. Структура дерева:
    • тип: TTree
    • поля: value (значение), left (левое поддерево), right (правое поддерево)
  2. Структура стека:
    • тип: TStack
    • поля: value (значение), next (следующий элемент)
  3. Функция добавления элемента в дерево: PushTree
    • аргументы: адрес указателя на дерево, значение
    • действия:
      • если указатель по заданном адресу есть
      • сравнить значение узла с добавляемым элементом
      • если значение больше, то вызвать функцию PushTree для правого поддерева
      • если значение меньше, то вызвать функцию PushTree для левого поддерева
    • возвращает: ничего
  4. Функция добавления элемента в стек: PushStack
    • аргументы: адрес указателя на стек, значение
    • действия:
      • создать новый узел
      • заполнить поля нового узла
      • вставить новый узел в стек
    • возвращает: ничего
  5. Функция удаления/выдавливания элемента из стека: PopStack
    • аргументы: адрес указателя на стек
    • действия:
      • сохранить указатель на вершину стека
      • удалить верхний элемент стека
      • вернуть указатель на вершину стека
  6. Функция клонирования/дублирования стека: CloneStack
    • аргументы: адрес указателя на целевой стек, адрес указателя на исходный стек
    • действия:
      • рекурсивно вызвать функцию CloneStack для клонирования следующего элемента исходного стека
      • добавить скопированный элемент в целевой стек
    • возвращает: ничего
  7. Рекурсивный вывод всех элементов дерева: PrintTree
    • аргументы: адрес указателя на дерево
    • действия:
      • если дерево есть
      • вывести значение дерева
      • рекурсивно вызвать функцию PrintTree для левого поддерева
      • рекурсивно вызвать функцию PrintTree для правого поддерева
    • возвращает: ничего
  8. Функция вывода всех элементов стека: PrintStack
    • аргументы: адрес указателя на стек
    • действия:
      • если стек не пустой
      • вывести значение вершины стека
      • рекурсивно вызвать функцию PrintStack для следующего элемента стека
    • возвращает: ничего
  9. Рекурсивное удаление всех элементов дерева: ClearTree
    • аргументы: адрес указателя на дерево
    • действия:
      • если дерево есть
      • рекурсивно вызвать функцию ClearTree для левого поддерева
      • рекурсивно вызвать функцию ClearTree для правого поддерева
      • освободить память, выделенную под дерево
    • возвращает: ничего
  10. Функция удаления всех элементов из стека: ClearStack
    • аргументы: адрес указателя на стек
    • действия:
      • если стек не пустой
      • удалить верхний элемент стека
      • рекурсивно вызвать функцию ClearStack для следующего элемента стека
    • возвращает: ничего
  11. Функция нахождения самой высокой ветви дерева: MaxLenBranch
    • аргументы: адрес указателя на дерево, адрес указателя на максимальное значение, адрес указателя на стек
    • действия:
      • инициализировать переменные len (текущая высота) и buff (список элементов ветви)
      • рекурсивно вызвать функцию MaxLenBranch для левого поддерева
      • рекурсивно вызвать функцию MaxLenBranch для правого поддерева
      • сравнить текущую высоту с максимальным значением
      • если текущая высота больше максимального значения
      • очистить ранее сохраненную ветвь и стек
      • клонировать новую ветвь и поместить ее в стек
      • вернуть максимальное значение
    • возвращает: максимальное значение
  12. Основная функция:
    • действия:
      • заполнить дерево случайными элементами
      • вывести поддерево на экран
      • найти самую высокую ветвь и вывести ее на экран
      • удалить все элементы стека и дерева
    • возвращает: 0

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

12   голосов , оценка 4.167 из 5
Похожие ответы