Построить бинарное дерево поиска из букв строки, вводимой пользователем - 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;
}

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

  1. В коде используется структура данных NODE для представления элемента дерева поиска, которая содержит ключ, счетчик и указатели на левое и правое поддерево.
  2. Функция Insert отвечает за вставку элемента в дерево поиска. Если дерево пусто, создается новый узел, иначе элемент вставляется в соответствующее поддерево в зависимости от значения ключа.
  3. Функция Display выводит элементы дерева поиска в порядке возрастания и подсчитывает количество повторений каждого элемента.
  4. Функция Count возвращает количество вершин в дереве.
  5. Функция Search отвечает за поиск элемента в дереве. Если элемент не найден, возвращается NULL.
  6. В функции main создается пустое дерево поиска, затем в него вставляются все символы из строки s.
  7. Затем происходит поиск символа 'a' в дереве и выводится количество его вхождений в левое и правое поддерево.
  8. В конце программы выводится сообщение no, если символ не найден.

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

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

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