Построить бинарное дерево поиска из букв строки, вводимой пользователем - C (СИ)
Формулировка задачи:
Не совсем понимаю как сделать данное задание, так и в плане реализации, помогите:
"Построить бинарное дерево поиска из букв строки, вводимой пользователем. Разработать функцию, которая для заданной буквы определяет число узлов в правом и левом поддеревьях."
Решение задачи: «Построить бинарное дерево поиска из букв строки, вводимой пользователем»
textual
Листинг программы
#include<stdio.h> #include<stdlib.h> // описание элемента дерева поиска typedef struct NODE { char key; long count; struct NODE *left, *right; } NODE; // вставка элемента со значением x в дерево поиска void Insert(NODE **q, char x) { if (*q == NULL) { *q = (NODE *)malloc(sizeof(NODE)); (*q)->key = x; (*q)->count = 1; (*q)->left = (*q)->right = NULL; } else { if ((*q)->key == x) ((*q)->count)++; else if ((*q)->key > x) Insert(&((*q)->left), x); else Insert(&((*q)->right), x); } } // вывод элементов дерева поиска на экран в порядке возрастания и количеством повторений void Display(NODE *q) { if (q != NULL) { Display(q->left); printf("%c : %d\n", q->key, q->count); Display(q->right); } } // количество вершин long Count(NODE *q) { return q == NULL ? 0 : 1 + Count(q->left) + Count(q->right); } // поиск вершины с определенным значением NODE *Search(NODE *q, char x) { if (q == NULL) return NULL; else if (q->key == x) return q; else if (q->key > x) return Search(q->left, x); else return Search(q->right, x); } int main() { NODE *root = NULL, *q; char s[] = "abcdeaba", *ps, c = 'a'; for(ps = s; *ps; ++ps) Insert(&root, *ps); Display(root); if (q = Search(root, c)) { printf("left: %d\n", Count(q->left)); printf("right: %d\n", Count(q->right)); } else puts("no"); return 0; }
Объяснение кода листинга программы
- В коде используется структура данных NODE для представления элемента дерева поиска, которая содержит ключ, счетчик и указатели на левое и правое поддерево.
- Функция Insert отвечает за вставку элемента в дерево поиска. Если дерево пусто, создается новый узел, иначе элемент вставляется в соответствующее поддерево в зависимости от значения ключа.
- Функция Display выводит элементы дерева поиска в порядке возрастания и подсчитывает количество повторений каждого элемента.
- Функция Count возвращает количество вершин в дереве.
- Функция Search отвечает за поиск элемента в дереве. Если элемент не найден, возвращается NULL.
- В функции main создается пустое дерево поиска, затем в него вставляются все символы из строки s.
- Затем происходит поиск символа 'a' в дереве и выводится количество его вхождений в левое и правое поддерево.
- В конце программы выводится сообщение
no
, если символ не найден.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д