Однонаправленный линейный список. Формирование на его основе бинарного дерева - C (СИ)

Узнай цену своей работы

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

Нужно создать однонаправленный линейный список(элементы списка вводятся с клавиатуры и имеют свои ключи(целое без знака с произвольным значением) и сформировать на его основе бинарное дерево. Программа должна реализовывать следующие действия: включить новый элемент после i-го по номеру элемента, включить новый элемент вместо i-го по номеру элемента, поменять местами два элемента с заданными ключами, удалить все листья на заданном уровне дерева, определить количество листьев на каждом уровне дерева. Дерево выводить в виде таблицы с указанием вида обхода. P.S. Не обязательно, что бы все было как в условие P.P.S. Заранее огромная благодарность за помощь.

Решение задачи: «Однонаправленный линейный список. Формирование на его основе бинарного дерева»

textual
Листинг программы
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <malloc.h>
 
typedef struct node {
    struct node* next; //right
    struct node* prev; //left
    unsigned val;
} node_t;
 
int list_input(const char* str, node_t** lst);
 
node_t* bstree_make(node_t** lst);
void bstree_print(FILE* _out, const node_t* tr);
void bstree_clear(node_t* tr);
void bstree_sheets(FILE* _out, const node_t* tr);
void bstree_remove_sheets(node_t** tr, unsigned level);
static void _bst_remove_sheets(node_t** tr, unsigned i, unsigned level);
static unsigned _bst_height(const node_t* tr);
static void _bst_count(const node_t* tr, unsigned* arr, unsigned i);
 
 
int main(void){
    char    buf[256];
    node_t* lst = NULL;
 
    //для примера
    strcpy(buf, "5 4 2 0 1 3 7 6 9 8");
/*  printf("Enter: ");
    fgets(buf, sizeof(buf), stdin);*/
    list_input(buf, &lst);
 
    node_t* tr = bstree_make(&lst);
    bstree_print(stdout, tr);
    putchar('\n');
    bstree_sheets(stdout, tr);
    putchar('\n');
 
    //удалить листья на 4-ом уровне(уровень начинается с нуля)
    bstree_remove_sheets(&tr, 3);
    bstree_print(stdout, tr);
    putchar('\n');
    bstree_sheets(stdout, tr);
 
    bstree_clear(tr);
    getchar();
    return 0;
}
 
//ввод списка со строки
int list_input(const char* str, node_t** lst){
    char*    off;
    node_t*  tail, *p;
    unsigned val;
 
    tail = *lst = NULL;
    while(*str){
        val = strtoul(str, &off, 10);
        if(str == off)
            break;
        str = off;
 
        if((p = (node_t*)malloc(sizeof(node_t))) == NULL)
            break;
        
        p->next = p->prev = NULL;
        p->val  = val;
 
        if(tail == NULL)
            *lst = tail = p;
        else {
            p->prev = tail;
            tail    = tail->next = p;
        }
    }
    return 1;
}
 
//превращение двусвязного списка в двоичное дерево поиска, дубликаты удаляются
node_t* bstree_make(node_t** lst){
    node_t* i, *p;
    node_t* root = NULL, **ref = NULL;
 
    while(*lst != NULL){
        p    = *lst;
        *lst = (*lst)->next;
        if(*lst != NULL)
            (*lst)->prev = NULL;
 
        p->next = p->prev = NULL;
 
        if(root == NULL)
            root = p;
        else {
            ref = &root;
            i   = root;
            while(i != NULL){
                if(p->val < i->val){
                    ref = &i->prev;
                    i   = i->prev;
                } else if(p->val > i->val){
                    ref = &i->next;
                    i   = i->next;
                } else
                    break;
            }
 
            if(i != NULL)
                free(p);
            else
                *ref = p;
        }
    }
    *lst = NULL;
    return root;
}
 
//удаление всех листьев дерева на определённом уровне
void bstree_remove_sheets(node_t** tr, unsigned level){
    _bst_remove_sheets(tr, 0, level);
}
 
static void _bst_remove_sheets(node_t** tr, unsigned i, unsigned level){
    int m;
    if(*tr != NULL){
        m = 0;
        if((*tr)->prev != NULL){
            _bst_remove_sheets(&(*tr)->prev, i + 1, level);
            ++m;
        }
        if((*tr)->next != NULL){
            _bst_remove_sheets(&(*tr)->next, i + 1, level);
            ++m;
        }
 
        if((m == 0) && (i == level)){ //есть это лист, то удалим его
            free(*tr);
            *tr = NULL;
        }
    }
}
 
//печать: кол-во листьев на каждом уровне дерева
void bstree_sheets(FILE* _out, const node_t* tr){
    unsigned* arr;
    unsigned i, n = _bst_height(tr);
    if(n == 0)
        return;
 
    arr = (unsigned*)calloc(n, sizeof(unsigned));
    if(arr == NULL)
        return;
 
    _bst_count(tr, arr, 0);
    for(i = 0; i < n; ++i)
        fprintf(_out, "level: %u\tcount sheets: %u\n", i, arr[i]);
    free(arr);
}
 
//подсчёт листьев
static void _bst_count(const node_t* tr, unsigned* arr, unsigned i){
    if(tr != NULL){
        if((tr->prev == NULL) && (tr->next == NULL))
            ++arr[i];
 
        if(tr->prev != NULL)
            _bst_count(tr->prev, arr, i + 1);
        if(tr->next != NULL)
            _bst_count(tr->next, arr, i + 1);
    }
}
 
//высота дерева
static unsigned _bst_height(const node_t* tr){
    unsigned a, b;
    if(tr != NULL){
        a = (tr->prev != NULL) ? _bst_height(tr->prev) : 0;
        b = (tr->next != NULL) ? _bst_height(tr->next) : 0;
        return ((a > b) ? a : b) + 1;
    }
    return 0;
}
 
 
//обход в прямом порядке
void bstree_print(FILE* _out, const node_t* tr){
    if(tr != NULL){
        fprintf(_out, "%u ", tr->val);
        if(tr->prev != NULL)
            bstree_print(_out, tr->prev);
        if(tr->next != NULL)
            bstree_print(_out, tr->next);
    }
}
 
//удаление всего дерева
void bstree_clear(node_t* tr){
    if(tr != NULL){
        if(tr->prev != NULL)
            bstree_clear(tr->prev);
        if(tr->next != NULL)
            bstree_clear(tr->next);
        free(tr);
    }
}

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

В данном коде реализована задача формирования однонаправленного списка из строки, а затем создания бинарного дерева поиска из этого списка. Затем в коде реализованы функции для удаления листьев на определенном уровне, подсчета количества листьев на каждом уровне и обхода дерева в прямом порядке. Список представлен в виде динамического массива, где каждый элемент - это структура node_t, содержащая указатели на следующий и предыдущий элементы списка, а также значение. Для решения задачи использованы следующие функции:

  1. list_input - ввод списка из строки. Строка разделяется на отдельные числа, которые затем добавляются в список.
  2. bstree_make - создание бинарного дерева поиска из списка. В процессе создания дерева, элементы списка сравниваются между собой, и если текущий элемент меньше значения элемента, на который указывает ссылка, то ссылка обновляется, указывая на текущий элемент. Таким образом, в итоге получается бинарное дерево поиска.
  3. bstree_print - обход дерева в прямом порядке и вывод его элементов.
  4. bstree_clear - очистка дерева, включающая освобождение памяти, выделенной под элементы дерева.
  5. bstree_sheets - подсчет количества листьев на каждом уровне дерева.
  6. bstree_remove_sheets - удаление всех листьев на определенном уровне дерева. Также в коде используется статическая функция _bst_remove_sheets, которая рекурсивно удаляет листья на определенном уровне.

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

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