сортировка двоичным деревом си - сортировка с помощью двоичного дерева

Forums:

отличный разбор сортировки бинарным деревом находится здесь = http://algolist.manual.ru/sort/faq/q7.php

Собственно говоря код уже на приведён на языке Си =

#include < stdio.h >
#include < stdlib.h >

typedef struct tree
  {
    int a;              // данные
    struct tree *left;  // левый  сын
    struct tree *right; // правый сын
  } TREE;

TREE *add_to_tree(TREE *root, int new_value)
{
   if (root==NULL)  // если нет сыновей - создаем новый элемент
     {
        root = (TREE*)malloc(sizeof(TREE));
        root->a = new_value;
        root->left = root->right = 0;
        return root;
     }
   if (root->a < new_value)          // добавлем ветвь
     root->right = add_to_tree(root->right, new_value);
   else
     root->left  = add_to_tree(root->left,  new_value);
   return root;
}

void tree_to_array(TREE *root, int a[]) // процедура заполнения массива
  {
    static max2=0;                      // счетчик элементов нового массива
    if (root==NULL) return;             // условие окончания - нет сыновей
    tree_to_array(root->left, a);       // обход левого поддерева
    a[max2++] = root->a;
    tree_to_array(root->right, a);      // обход правого поддерева
    free(root);
  }

void sort_tree(int a[], int elem_total)        // собственно сортировка
{
   TREE *root;
   int i;

   root = NULL;
   for (i=0; i<elem_total; i++)        // проход массива и заполнение дерева
      root = add_to_tree(root, a[i]);
   tree_to_array(root, a);             // заполнение массива
}
  /* тестовая программа */
void main() {
   int i;
   /* Это будем сортировать */
   int a[19]={ 0,7,8,3,52,14,16,18,15,13,42,30,35,26 ,456, 5 ,78,99,12345};

   sort_tree(a, 19);
   
   printf("sorted array:\n");
   for (i=0;i<19;i++) printf("%d ",a[i]);   
}

,
мы же перепишем его с тем условием ,что в нашем случае сортируется последовательность структур, в каждой из которых имеется два поля -

  • некоторое текстовое значение (имя)
  • + второе поле - число вхождений этого значения в некоторое множество (я сформировал этот список ранее просмотрев множество имён пользователей).

Моя структура может быть описана следующим образом:

struct  akael // список данного формата мы и будем сортировать.
{
 char* name;// имя пользователя 
 int weight; // число повторов
  
};

Итак, в статье выше написано ,что дерево относительно массива входных данных по следующему принципу:
сортировка бинарным деревом, сортировка двоичным деревом

Внесём ещё одно изменение - на базе имеющихся функций составим функцию которая выводит спискок N aka (also known as) имён - то есть список N наиболее повторяющихся имён пользователей.

_____________________________________________
Источники(читать подробнее)=
http://ru.wikipedia.org/wiki/%D0%A1%D0%B...
http://algolist.manual.ru/sort/faq/q7.php
Ключевые слова и фразы(для поиска)=