Однонаправленный линейный список. Формирование на его основе бинарного дерева - 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
, содержащая указатели на следующий и предыдущий элементы списка, а также значение.
Для решения задачи использованы следующие функции:
list_input
- ввод списка из строки. Строка разделяется на отдельные числа, которые затем добавляются в список.bstree_make
- создание бинарного дерева поиска из списка. В процессе создания дерева, элементы списка сравниваются между собой, и если текущий элемент меньше значения элемента, на который указывает ссылка, то ссылка обновляется, указывая на текущий элемент. Таким образом, в итоге получается бинарное дерево поиска.bstree_print
- обход дерева в прямом порядке и вывод его элементов.bstree_clear
- очистка дерева, включающая освобождение памяти, выделенной под элементы дерева.bstree_sheets
- подсчет количества листьев на каждом уровне дерева.bstree_remove_sheets
- удаление всех листьев на определенном уровне дерева. Также в коде используется статическая функция_bst_remove_sheets
, которая рекурсивно удаляет листья на определенном уровне.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д