Найти поддерево двоичного поиска с максимальным количеством элементов - C (СИ)

Формулировка задачи:

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

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

12   голосов, оценка 4.167 из 5


СОХРАНИТЬ ССЫЛКУ