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

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


textual

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

#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



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

  1. Добрый день! Имеется код, переводящий двоичный код в символы, однако работает он только если на вход был дан двоичный код одного символа. Как изменить код так, чтобы прога выводила целые слова и предложения? При этом нельзя включать string.h в исходник.C1 2 3 4 5 6 7 8 9 10 11 12 13 #include #include #include   int main(void) {     char myChar;     char in[255];     fgets(in, sizeof(in), stdin);       myChar = strtol(in, 0, 2);     printf("%c\n",  myChar ); }

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

  1. Помогите пожалуйста, не получается. Преобразовать целое число, переставив цифры двоичного представления данного натурального числа в обратном порядке.

  1. Вот код.C1 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 #include #include #include     /*  Функция для вывода значений битов, представляющих     заданное целое число в памяти компьютера. */ void ShowInBin(int x) {     int     i, j, num_bits_in_int, num_bits;     char *  Arr;       /*  Количество битов, необходимое             для представления числа x.  */     num_bits = (int)(log((double)x) / log(2.0)) + 1;       /*  Количество битов, необходимое         для представления максимального                         целого числа.   */     j = num_bits_in_int = sizeof(int) * 8;       Arr = (char *) malloc(sizeof(char) * num_bits_in_int);       /*  Обнуляем необходимое количество битов слева.    */     for (i = 0; i < num_bits_in_int - num_bits; ++i)         Arr[i] = '0';       while (j > i)     {         Arr[--j] = x % 2 + '0';         x /= 2;     }       for (i = 0; i < num_bits_in_int; ++i)         printf("%c", Arr[i]);       free(Arr); }   int main() {     int x;     x = 8;     ShowInBin(x);     return 0; }почему-то в Codeblocks и Dev-C++ выводит все нули, а в Visual Studio выводит нормально.

  1. Помогите пожалуйста, преобразовать целое число, переставив цифры двоичного представления данного натурального числа в обратном порядке.

  1. Как можно реализовать запись двоичного числа в обратном порядке? т.е. к примеру такое число 0010011, обратный порядок - 1100100

  1. Вот, собственно, код:C1 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 #ifndef DICTIONARY_H_INCLUDED #define DICTIONARY_H_INCLUDED   #include   typedef struct dictionary_t {       struct dictionary_t* m_pLeft;     struct dictionary_t* m_pRight;       char m_key[10];     char m_value[10];   } dictionary_t;   dictionary_t* dictionary_ctor(dictionary_t* left, dictionary_t* right, char* key, char* value) {     dictionary_t* dic = (dictionary_t*)malloc(sizeof(dictionary_t));       dic->m_pRight = left;     dic->m_pLeft = right;     //dic->m_key = key;     //dic->m_value = value;     strncpy(dic->m_key, key, 10);     strncpy(dic->m_value, value, 10);       return dic; }   void dictionary_insert(dictionary_t* dic, char* key, char* value) {     if (dic == NULL) {         dic = dictionary_ctor(NULL, NULL, key, value);         printf("Added key:%s value:%s\n", key, value);         return;     }       if (strcmp(key, dic->m_key) > 0) {         dictionary_insert(dic->m_pRight, key, value);         return;     }       if (strcmp(key, dic->m_key) < 0) {         dictionary_insert(dic->m_pLeft, key, value);         return;     }       // if key == dic->m_key     //*dic->m_value = *value;     strncpy(dic->m_value, value, 10); }   char* dictionary_find(dictionary_t* dic, char* key) {     char* answer = NULL;       if (dic == NULL) {         return NULL;     }       if (*key == *dic->m_key) {         return dic->m_value;     }       if (strcmp(key, dic->m_key) > 0) {         answer = dictionary_find(dic->m_pRight, key);     }       if (strcmp(key, dic->m_key) < 0) {         answer = dictionary_find(dic->m_pLeft, key);     }       return answer; }   #endif // DICTIONATY_H_INCLUDEDПри использовании возникает ошибка сегментации. В чем может быть дело?

  1. Ввели число,скажем 0b00001001. Мне нужно обратиться к отдельному биту этого байта. Для примера сравнить первый байт (1) с нулем.